Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Entscheidbarkeit zweier kontextfreien Sprachen
Hallo,
Ich habe gelesen, dass der Schnitt zweier kontextfreien Sprachen unentscheidbar ist. Stimmt das? Leider kenne/finde ich den Beweis dazu nicht. Kann mir jemand weiterhelfen?
Außerdem verwirrt mich die Aussage auf http://de.wikipedia.org/wiki/Entscheidbar#Beispiele.
“Zu zwei entscheidbaren Mengen sind deren Schnittmenge und deren Vereinigungsmenge entscheidbar.”
Kann man diese Aussage auch auf auf Sprachen übertragen?
Gruß,
Trigger
Das Schnittproblem zweier kontextfreien Sprachen ist nicht entscheidbar, siehe z. B. hier im Satz 9.9.
Hallo,
Der Schnitt zweier kontextfreier Sprachen ist nattuerlich entscheidbar:
jede einzelne ist entscheidbar => gibt einband-DTM1,2 die die sprachen L1, L2 entscheiden (inbesondere sich nie aufhaengen).
=> pruefe die eine und dann die andere.
==> baue -Band DTM:
kopiere eingabe auf zweites band. (backup)
lasse DTM1 auf band 1 laufen
endzustaende von DTM1 gehen in anfangszustand von DTM2 ueber, dtm2 laeuft auf band 2
endzustand von DTM2 ist endzustand der schnitttmaschine.
Der Schnitt zweier Kontextfreier Sprachen nur ist nicht Kontextfrei.
Dieses Schnittproblem ist aber etwas anderes:
gegeben gramatiken fuer L1, L2, ist L1 n L2 leer oder gibt es woerter, die in beiden Sprachen sind.
Danke für den Beweis.
Beweise für Entscheidbarkeit stehen also immer im Zusammenhang mit dem Wortproblem, sofern nicht anders gefordert?
Was ist mit der Aussage auf Wiki: “Zu zwei entscheidbaren Mengen sind deren Schnittmenge und deren Vereinigungsmenge entscheidbar.” Gilt das auch für Kontextfreie Sprachen?
Eine kontextfreie Sprache ist ja gerade eine entscheidbare Menge. Der Satz sagt, dass du auch die Schnittmenge (wie oben) und die Vereinigung (fast wie oben, denk mal drüber nach) dieser Sprachen entscheiden kannst.
Edit: Spoilerfree =) Berechnung der Vereinigung:
[size=4]immer true zurückgeben, sobald auch nur eine der beiden TMs erfolgreich war[/size]