Unentscheidbare Grammatikprobleme

4. Unentscheidbare Grammatikprobleme
Satz: Seien G1 und G2 kontextfreie Grammatiken. Folgende Probleme sind unentscheidbar:
L(G1) L(G2) = ?
|L(G1) L(G2)| = ?
L(G1) L(G2) kontextfrei?
L(G1) L(G2) ?
L(G1) = L(G2) ?
Beweisskizze:
(1) Wir reduzieren das PCP auf das Schnittproblem:
Sei K = ((x1, y1), ..., (xk, yk)) eine Instanz des Korrespondenzproblems über {0,1}.
Wir definieren zu K die beiden Grammatiken GK1 und GK2 (Terminalalphabet {0,1,$, a1, ..., ak}), so dass K eine Lösung hat gdw. der Schnitt der von GK1 und Gk2 erzeugten Sprachen nicht leer ist:
GK1: S -> A$B
A -> a1Ax1 | … | akAxk
A -> a1x1 | … | akxk
B -> y~1Ba1 | …| y~kBak
B -> y~1a1 | …| y~kak
w~ ist die Umkehrung von w.
erzeugte Sprache: L1= {ain...ai1xi1...xin$ y~jm... y~j1aj1...ajm | n, m 1}
also: beliebige umgedrehte Folge von Indizes, Folge von entsprechenden xis, $, beliebige umgedrehte Folge von gespiegelten yjs, entsprechende Folge von Indizes.
GK2: S -> a1Sa1 | … | akSak | T
T -> 0T0 | 1T1 | $
erzeugte Sprache: L2 = {uv$v~u~ | u {a1, ..., ak}*, v {0,1}*}
Ein Wort ain...ai1xi1...xin$ y~jm... y~j1aj1...ajm wird aus beiden Grammatiken erzeugt (liegt also im Schnitt der erzeugten Sprachen), genau dann wenn gilt:
das Wort xi1...xin wird durch die Indizes i1, ...,in erzeugt (wegen GK1),
das Wort yj1...yjm wird durch die Indizes j1, ...,jm erzeugt (wegen GK1),
xi1...xin = yj1...yjm (wegen GK2) und
ai1...ain = aj1...ajm (wegen GK2).
Damit besitzt K die Lösung i1 ... in genau dann wenn ain...ai1xi1...xin$ y~in... y~i1ai1...ain im Schnitt der von GK1 und GK2 erzeugten Sprachen liegt.
Da die Funktion, die einer Instanz K des PCP die beiden Grammatiken GK1 und GK2 zuordnet, total und berechenbar ist, ist das PCP auf das Schnittproblem reduziert, das somit unentscheidbar ist.
Beispiel: K = ((10,1), (11, 011)) Lösung: 1,2
GK1: S -> A$B
A -> a1A10 | a2A11
A -> a110 | a211
B -> 1Ba1 | 110Ba2
B -> 1a1 | 110a2
aus GK1 herleitbar: z. B. a110$1101a1a2 oder a2a11011$110a2, aber auch:
a2a11011$1101a1a2
dieses Wort ist auch aus GK2 herleitbar. Das bedeutet, dass 1,2 eine Lösung von K ist.
(2) Wenn K eine Lösung hat, dann auch unendlich viele (Indexfolge kann beliebig oft wiederholt werden, im obigen Beispiel: auch 1,2,1,2 und 1,2,1,2,1,2 etc. Lösungen). Also hat K Lösung gdw. mit obigen Grammatiken |L(GK1) L(GK2)| = . Damit ist K auch auf Problem 2. reduziert.
(3) Falls K keine Lösung besitzt, ist L1 L2 leer und damit kontextfrei. Falls K Lösungen besitzt, ist L1 L2 unendlich, und man kann mit dem Pumping Lemma zeigen, dass der Schnitt nicht kontextfrei ist. Wäre also Kontextfreiheit des Schnitts entscheidbar, so auch das PCP.
(4) (5) Man kann zeigen: L1 und L2 sind sogar deterministisch kontextfrei. Damit ist das Komplement kontextfrei und es gibt effektiv konstruierbare Grammatiken G'K1 und G'K2 für die jeweils komplementären Sprachen. Es gilt:
L1 L2 leer L1 L(G'K2)
L1 L(G'K2) = L(G'K2)
G3 ist hier die Grammatik, die die Vereinigung L1 L(G'K2) erzeugt. Wären Inklusion oder Gleichheit kontextfreier Sprachen entscheidbar, so könnte man demnach Leerheit des Schnitts entscheiden, im Widerspruch zu 1.
Anmerkung: hieraus folgt sofort die Unentscheidbarkeit des Äquivalenzproblems für alle Formalismen, in die kontextfreie Grammatiken übersetzbar sind: Kellerautomaten, LBAs, kontextsensitive Grammatiken, Turingmaschinen, While-, Goto-Programme.
Wir nennen die kontextfreie Grammatik G deterministisch kontextfrei, wenn L(G) deterministisch kontextfrei ist (L(G) wird von det. Kellerautomat akzeptiert). Mit obigem Beweis ist implizit auch bewiesen:
Satz: Seien G1 und G2 deterministisch kontextfreie Grammatiken. Folgende Probleme sind unentscheidbar:
L(G1) L(G2) = ?
|L(G1) L(G2)| = ?
L(G1) L(G2) kontextfrei?
L(G1) L(G2) ?
Äquivalenz deterministisch kontextfreier Sprachen dagegen ist entscheidbar (Senizergues 1997)! Der obige Unentscheidbarkeits-Beweis schlägt fehl, da die Vereinigung deterministisch kontextfreier Sprachen nicht notwendigerweise det. kontextfrei ist.
Weitere unentscheidbare Probleme kontextfreier Grammatiken (ohne Beweis):
Satz: Sei G kontextfreie Grammatik. Folgende Probleme sind unentscheidbar:
Ist G mehrdeutig?
Ist das Komplement der von G erzeugten Sprache kontextfrei?
Ist L(G) regulär?
Ist L(G) deterministisch kontextfrei?
Satz: Das Leerheitsproblem und das Endlichkeitsproblem für Typ 1 Sprachen sind nicht entscheidbar.
|