L kontextfrei => L^c ktf ? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:23 Fr 21.11.2008 | | Autor: | Rheinsi |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo!
Habe eine Frage zu einem Beweis von mir!
Aufgabe war:
Wenn L [mm] \subseteq \Sigma [/mm] * kontextfrei ist, ist dann auch [mm] \Sigma [/mm] * \ L kontextfrei?
Meine Lösung:
L [mm] \subseteq \Sigma [/mm] * kontextfrei. Es gilt [mm] \Sigma [/mm] * \ L = [mm] L^c
[/mm]
w [mm] \in \L^c \gdw [/mm] w [mm] \notin [/mm] L [mm] \forall [/mm] w [mm] \in \Sigma [/mm] *
Eine Sprache S ist genau dann kontextfrei, wenn es einen Kellerautomaten B gibt, der genau S akzeptiert (Skript s. 24) "Zitat Skript: (....) wollen wir nun eine Klasse von verallgemeinerten Automaten definieren, die genau die kontextfreien Sprachen realisieren. Die Automaten sind die "Kellerautomaten", die es in deterministischer und nichtdeterministischer Variante gibt. (...) "
Sei A nun der Kellerautomat, der genau L akzeptiert mit
A = (Q, [mm] \Sigma, \Gamma [/mm] , [mm] \delta, q_{0} [/mm] , [mm] F_{A} [/mm] )
Beh: B = (Q, [mm] \Sigma, \Gamma [/mm] , [mm] \delta, q_{0} [/mm] , Q \ [mm] F_{A} [/mm] ) akzeptiert genau [mm] L^c \gdw [/mm] B akzeptiert alle w [mm] \notin [/mm] L
Bew:
zz. w [mm] \notin [/mm] L [mm] \gdw [/mm] B akzeptiert w
" => "
es existiert keine Zustandsfolge [mm] q_{n_{0}},.....,q_{n_{m}} [/mm] mit m= lh(w)
und 1.) [mm] q_{n_{m}} \in F_{A} [/mm] 2.) [mm] q_{n_{0}} [/mm] = [mm] q_{0} [/mm] und 3.) [mm] \delta (q_{n_{i}}, w_{i}, x_{i}) [/mm] = [mm] q_{n_{i+1}} [/mm] für 0 [mm] \le [/mm] i < m
=> für alle Folgen [mm] q_{n_{0}},.....,q_{n_{m}} [/mm] mit m= lh(w) und [mm] q_{n_{0}} [/mm] = [mm] q_{0} [/mm] und [mm] \delta (q_{n_{i}}, w_{i}, x_{i}) [/mm] = [mm] q_{n_{i+1}} [/mm] für 0 [mm] \le [/mm] i < m
gilt [mm] q_{n_{m}} \in F_{A}^c [/mm] = Q \ [mm] F_{A}
[/mm]
Mit der Existenz einer solchen Folge folgt
=> B akzeptiert w
" <= "
es existiert eine Zustandsfolge [mm] q_{n_{0}},.....,q_{n_{m}} [/mm] mit
1.) [mm] q_{n_{m}} \in F_{A}^c [/mm] = Q \ [mm] F_{A} [/mm] 2.) [mm] q_{n_{0}} [/mm] = [mm] q_{0} [/mm] und 3.) [mm] \delta (q_{n_{i}}, w_{i}, x_{i}) [/mm] = [mm] q_{n_{i+1}} [/mm] für 0 [mm] \le [/mm] i < m
=> w [mm] \in L^c [/mm] <=> w [mm] \notin [/mm] L
=> Behauptung
Es existiert also ein Kellerautomat, der genau [mm] L^c [/mm] = [mm] \Sigma [/mm] \ L akzeptiert
=> [mm] \Sigma [/mm] \ L ist kontextfrei.
Soweit zu meinem Beweis. Der muss irgendwo kaputt gehen, kann mir wer sagen, wo?
Der Gegenbeweis sieht so aus:
Sei L = [mm] L_{1} \cap L_{2} [/mm] , [mm] L_{1} [/mm] und [mm] L_{2} [/mm] kontextfrei.
Annahme: [mm] L_{1}^c [/mm] ist kontextfrei, so auch [mm] L_{2}^c [/mm] und auch [mm] L_{1}^c \cup L_{2}^c [/mm] (Haben wir bewiesen). [mm] L_{1}^c \cup L_{2}^c [/mm] ist aber [mm] L^c. [/mm] Nach Annahme ist also [mm] (L^c)^c [/mm] auch kontextfrei. => L = [mm] (L^c)^c [/mm] kontextfrei, das hatten wir aber gezeigt, dass das nicht so sein muss!
=> Widerspruch => L muss nicht kontextfrei sein!
Meine Vermutung ist ja, dass der Satz aus dem Skript falsch sein muss, kann mir aber nicht erklären warum. Habe ich ihn falsch gedeutet?!
Über Antworten würde ich mich freuen!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:43 So 23.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
