Aufgabe zu Abschlusseigenschaften

24.05.2012, 19:11	Auf diesen Beitrag antworten »
bandchef	Aufgabe zu Abschlusseigenschaften Aufgabe: Die Operation $[latex]min: \mathbb P\left(\Sigma^{\star}\right) \to \mathbb P\left(\Sigma^{\star}\right)[/latex]$ sei definiert durch $[latex]min(L)=\{ w \in L \| \forall u,v \in \Sigma^{\star} \text{ mit } w=uv, 1 \leq \|u\|, \|v\| \geq 1: u \notin L \}[/latex]$ min beinhaltet also alle diejenigen Wörter aus L, deren echten Präfixe nicht in L liegen. Sei nun L eine reguläre Sprache, ist dann auch min(L) regulär? Begründen Sie Ihre Antwort. Ich komm mit der Aufgabe nicht zurecht. Könnt ihr mir etwas weiterhelfen? Ich hab übrigens den Hopcroft als Lehrbuch. In diesem steht, dass gilt: Wenn L eine reguläre Sprache über dem Alphabt $[latex]\Sigma[/latex]$ ist, dann ist $[latex]\overline{L} = \Sigma^{\star} - L[/latex]$ auch eine reguläre Sprache. Kann mir das da weiterhelfen? Gegeben ist ja nur die Sprache min(L). Wie ist dann eigentlich die Sprachdefinition für L alleine? Lautet die so: $[latex]L=\{ w \in L \| \forall u,v \in \Sigma^{\star} \text{ mit } w=uv, 1 \leq \|u\|, \|v\| \geq 1\}[/latex]$ ? Also eigentlich genauso wie min(L), nur, dass $[latex]u \notin L[/latex]$ fehlt; also, dass das echte Präfix mit enthalten ist. Stimmt das alles soweit?

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »