Unentscheidbare Grammatikprobleme

4. Unentscheidbare Grammatikprobleme

Satz: Seien G₁ und G₂ kontextfreie Grammatiken. Folgende Probleme sind unentscheidbar:

1. 
   L(G₁)  L(G₂) = ?
   
2. 
   |L(G₁)  L(G₂)| = ?
   
3. 
   L(G₁)  L(G₂) kontextfrei?
   
4. 
   L(G₁)  L(G₂) ?
   
5. 
   L(G₁) = L(G₂) ?
   

Beweisskizze:

(1) Wir reduzieren das PCP auf das Schnittproblem:

Sei K = ((x₁, y₁), ..., (x_k, y_k)) eine Instanz des Korrespondenzproblems über {0,1}.

A -> a₁Ax₁ | … | a_kAx_k

A -> a₁x₁ | … | a_kx_k

B -> y^~₁Ba₁ | …| y^~_kBa_k

B -> y^~₁a₁ | …| y^~_ka_k
w^~ ist die Umkehrung von w.

erzeugte Sprache: L₁= {a_in...a_i1x_i1...x_in$ y^~_jm... y^~_j1a_j1...a_jm | n, m  1}

T -> 0T0 | 1T1 | $

1. 
   das Wort x_i1...x_in wird durch die Indizes i₁, ...,i_n erzeugt (wegen G_K1),
   
2. 
   das Wort y_j1...y_jm wird durch die Indizes j₁, ...,j_m erzeugt (wegen G_K1),
   
3. 
   x_i1...x_in = y_j1...y_jm (wegen G_K2) und
   
4. 
   a_i1...a_in = a_j1...a_jm (wegen G_K2).
   

Damit besitzt K die Lösung i₁ ... i_n genau dann wenn a_in...a_i1x_i1...x_in$ y^~_in... y^~_i1a_i1...a_in im Schnitt der von G_K1 und G_K2 erzeugten Sprachen liegt.

A -> a₁A10 | a₂A11

A -> a₁10 | a₂11

B -> 1Ba₁ | 110Ba₂

B -> 1a₁ | 110a₂
aus G_K1 herleitbar: z. B. a₁10$1101a₁a₂ oder a₂a₁1011$110a₂, aber auch:
a₂a₁1011$1101a₁a₂
dieses Wort ist auch aus G_K2 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(G_K1)  L(G_K2)| = . Damit ist K auch auf Problem 2. reduziert.
(3) Falls K keine Lösung besitzt, ist L₁  L₂ leer und damit kontextfrei. Falls K Lösungen besitzt, ist L₁  L₂ 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: L₁ und L₂ 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:
L₁  L₂ leer  L₁  L(G'_K2)

 L₁  L(G'_K2) = L(G'_K2)

• 
  L(G₃) = L(G'_K2)
  

G₃ ist hier die Grammatik, die die Vereinigung L₁  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.

1. 
   L(G₁)  L(G₂) = ?
   
2. 
   |L(G₁)  L(G₂)| = ?
   
3. 
   L(G₁)  L(G₂) kontextfrei?
   
4. 
   L(G₁)  L(G₂) ?
   

Ä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.

1. 
   Ist G mehrdeutig?
   
2. 
   Ist das Komplement der von G erzeugten Sprache kontextfrei?
   
3. 
   Ist L(G) regulär?
   
4. 
   Ist L(G) deterministisch kontextfrei?
   

Satz: Das Leerheitsproblem und das Endlichkeitsproblem für Typ 1 Sprachen sind nicht entscheidbar.

5. 
   
   Download 233 Kb.