Grundlagen der Theoretischen Informatik Unentscheidbarkeit

1
2
Unentscheidbarkeit
Grundlagen der
Theoretischen Informatik
Till Mossakowski
Fakultät für Informatik
Otto-von-Guericke Universität
Magdeburg
Wintersemester 2014/15
#include <stdio.h>
char *s="include <stdio.h>%cchar *s=%c%s%c;%cint main(){printf(s,10,34,s,34,10,10);}%c";
int main(){printf(s,10,34,s,34,10,10);}
3
4
Sei ATM = {hM, wi | M ist eine Turing-Maschine, die w akzeptiert}.
Satz: Die Sprache ATM ist nicht entscheidbar.
hMi
Beweis:
Nehmen wir an, es gäbe eine Turing-Maschine M ∗ , die die Sprache
ATM entscheidet.
hM, hMii
M∗
D
Basierend auf M ∗ könnten wir dann eine Turing-Maschine D
konstruieren, die bei Eingabe hMi Turing-Maschine M ∗ für Eingabe
hM, hMi i simuliert, aber im verwerfenden Haltezustand hält, falls
M ∗ diese Eingabe akzeptiert und im akzeptierenden Haltezustand
sonst.
D verwirft hMi genau dann wenn M die Eingabe hMi akzeptiert.
Was tut D bei Eingabe hDi? Die Turing-Maschine D verwirft hDi
genau dann wenn D die Eingabe hDi akzeptiert!
Damit ist die Annahme, dass M ∗ existiert, ad absurdum geführt. 5
Halteproblem
6
Bei Eingabe hM, wi führt M ∗ zunächst die Berechnung von H für
diese Eingabe aus.
Falls H die Eingabe akzeptiert, so wissen wir, dass M bei Eingabe
w hält. M ∗ simuliert dann die Berechung von M bei Eingabe w und
hält im akzeptierenden Haltezustand, falls M Eingabe w akzeptiert,
und im verwerfenden Haltezustand sonst.
H = {hM, wi | Turingmaschine M hält bei Eingabe w}
Satz: Die Sprache H ist nicht entscheidbar.
Beweis:
Nehmen wir an, es gäbe eine Turing-Maschine H, die H
entscheidet. Dann könnten wir uns das zu Nutze machen, um eine
Turing-Maschine M ∗ zu konstruieren, die ATM entscheidet:
Falls H die Eingabe verwirft, so wissen wir, dass M bei Eingabe w
nicht hält. M ∗ hält im verwerfenden Haltezustand.
M ∗ würde die nicht entscheidbare Sprache ATM entscheiden.
Also kann H nicht existieren. Also ist das Halteproblem H
unentscheidbar.
7
8
Unentscheidbare Probleme bei
Turing-Maschinen
Satz: Die Sprache ETM = {hMi | L(M) = 0}
/ ist nicht entscheidbar.
Satz: Die Sprache ATM,ε = {hMi | ε ∈ L(M)} ist nicht
entscheidbar.
Beweis:
Wäre ETM entscheidbar, so wäre auch ATM entscheidbar: Zu
gegebenem M und w können wir leicht eine Turingmaschine Mw0
konstruieren, die jede von w verschiedene Eingabe verwirft und bei
Eingabe w die Berechnung von M bei Eingabe w simuliert.
Beweis:
Wäre ATM,ε entscheidbar, so wäre auch ATM entscheidbar: Zu
gegebenem M und w können wir leicht eine Turingmaschine Mw
konstruieren, die, wenn sie mit leerem Band gestartet wird,
zunächst w auf das Band schreibt und dann M simuliert.
Dann ist hM, wi ∈ ATM genau dann wenn hMw i ∈ ATM,ε .
Dann ist hM, wi ∈ ATM genau dann wenn hMw0 i 6∈ ETM .
9
Satz: Die Sprache ATM,all = {hMi | L(M) = Σ∗ } ist nicht
entscheidbar.
10
Satz: Die Sprache QTM = {hM1 , M2 i | L(M1 ) = L(M2 )} ist nicht
entscheidbar.
Beweis:
Wäre ATM,all entscheidbar, so wäre auch ATM entscheidbar: Zu
gegebenem M und w können wir leicht eine Turingmaschine Mw00
konstruieren, die zunächst jede Eingabe löscht, dann w aufs Band
schreibt und die Berechnung von M bei Eingabe w simuliert.
Beweis:
Wäre QTM entscheidbar, so wäre auch ATM,all entscheidbar: Wir
können leicht eine Turingmaschine Y konstruieren, die jede
Eingabe akzeptiert.
Dann ist hMi ∈ ATM,all genau dann wenn hM, Yi ∈ QTM .
Dann ist hM, wi ∈ ATM genau dann wenn hMw00 i ∈ ATM,all .
11
12
Reduzierbarkeit
Definition:
Eine Sprache A heißt abbildungsreduzierbar auf eine Sprache B,
falls es eine Turing-berechenbare Funktion f : Σ∗ → Σ∗ gibt, so dass
für alle w ∈ Σ∗ gilt
Wir haben die Unentscheidbarkeit der betrachteten Sprachen bei
Turing-Maschinen gezeigt, indem wir sie auf die bereits bekannte
Unentscheidbarkeit anderer Sprachen zurückgeführt haben,
insbesondere auf die Unentscheidbarkeit von ATM .
w ∈ A ⇐⇒ f (w) ∈ B
Die Funktion f heißt Reduktion von A auf B.
Um zu zeigen, dass L nicht entscheidbar ist, haben wir gezeigt,
dass eine unentscheidbare Sprache U entscheidbar wäre, wenn L
entscheidbar wäre.
Wir schreiben A B, falls A auf B abbildungsreduzierbar ist.
Satz:
Falls A B und A ist nicht entscheidbar, dann ist auch B nicht
entscheidbar.
13
14
Dies folgt unmittelbar aus folgendem
Satz:
Falls A B und B ist entscheidbar, dann ist auch A entscheidbar.
Analog zeigt man
Satz:
Falls A B und B ist rekursiv aufzählbar, dann ist auch A rekursiv
aufzählbar.
Beweis:
f (w)
w
TM f
TM B
f (w) ∈ B
w∈A
f (w) 6∈ B
w 6∈ A
Ferner gilt
Lemma: Die Relation ist transitiv.
TM A
15
Aus dem Beweis der Unentscheidbarkeit von ATM,ε lässt sich
ATM ATM,ε
ableiten: Wir definieren eine Reduktion f : Σ∗ → Σ∗ , die hM, wi auf
hMw i abbildet und Wörter, die nicht von der Form hM, wi sind, auf
Wörter, die nicht von der Form hMi sind.
Diese Reduktionsfunktion f ist Turing-berechenbar und es gilt für
alle x ∈ Σ∗
x ∈ ATM ⇐⇒ f (x) ∈ ATM,ε
16
Ferner lassen sich aus den Beweisen zur Unentscheidbarkeit von
ETM , ATM,all und QTM Turing-berechenbare Reduktionsfunktionen
ableiten, so dass gilt:
ATM ETM
ATM ATM,all
ATM,all QTM
17
18
Lemma: ATM H .
Halten und Akzeptieren
Beweis:
Wir müssen eine Reduktion f ? : Σ∗ → Σ∗ angeben, so dass für alle
x ∈ Σ∗ gilt
x ∈ ATM ⇐⇒ f ? (x) ∈ H
Wenn eine Turing-Maschine ein Wort w nicht akzeptiert, so kann
sie w verwerfen oder nie halten. Sei M eine Turing-Maschine, die L
akzeptiert. Wir zeigen nun im Wesentlichen, dass wir annehmen
dürfen, dass M genau dann hält, wenn das Eingabewort zu L
gehört, denn wenn M diese Eigenschaft nicht besitzt, so lässt sich
doch aus M leicht eine Turing-Maschine M ? mit dieser Eigenschaft
ableiten, so dass L = L(M ? ) = L(M).
Falls x nicht von der Form hM, wi ist, so ist f ? (x) = ε 6∈ H .
Ansonsten ist f ? (hM, wi) = hM ? , wi, wobei M ? genau dann hält,
wenn M das Wort w akzeptiert:
M ? enthält alle Zustände von M und einen weiteren Zustand qloop .
M ? besitzt die gleichen Übergänge wie M, außer dass jeder
Übergang, der in M zu qreject führt, nun zu qloop führt. Ferner ist
δ (qloop , σ ) = (qloop , σ , S) für alle σ aus dem Bandalphabet. Nun
gilt L(M) = L(M ? ). Schließlich ist f ? Turing-berechenbar.
Wir brauchen also in diesem Sinne nicht zwischen Halten und
Akzeptieren zu unterscheiden.
19
Lemma: H ATM,all .
H = {x | x ist von der Form hM, wi und die Turing-Maschine M
hält nicht bei Eingabe w oder x ist nicht von dieser Form}
Beweis:
Wir müssen eine Reduktion f : Σ∗ → Σ∗ angeben, so dass für alle
x ∈ Σ∗ gilt
x ∈ H ⇐⇒ f (x) ∈ ATM,all
Lemma: H ist nicht rekursiv aufzählbar.
Beweis:
H ist rekursiv aufzählbar. Wäre auch H rekursiv aufzählbar, so
wäre H entscheidbar, ist es aber nicht.
20
Falls x nicht von der Form hM, wi ist, so ist f (x) = hMall i, wobei
Mall eine Turing-Maschine ist, die bei allen Eingaben hält. Folglich
gilt hMall i ∈ ATM,all .
Ansonsten ist f (hM, wi) = hMw# i, wobei Mw# eine Turing-Maschine
ist, die ihre Eingabe y nach folgendem Verfahren bearbeitet:
21
22
Sei
1
2
3
4
5
Kopiere Eingabe y auf ein zweites Band
Lösche das Eingabeband und schreibe w auf das Band
Simuliere M bei Eingabe w für |y| Schritte oder bis M hält
Falls M angehalten hat, gehe in eine Endlosschleife über
Ansonsten halte akzeptierend an
Hε
= {hMi | M hält bei Eingabe ε}
Hall = {hMi | M hält bei allen Eingaben}
Dann gilt
H
H
M hält bei Eingabe w nicht, genau dann wenn Mw# alle Eingaben
akzeptiert. Ferner ist die Reduktion f , die hM, wi auf hMw# i
abbildet, Turing-berechenbar.
Hε
Hall
ATM,ε Hε
ATM,all Hall
und somit
Lemma: Hε ist nicht entscheidbar.
Lemma: ATM,all ist nicht rekursiv aufzählbar.
Lemma: Hall ist nicht rekursiv aufzählbar.
23
24
Satz von Rice
Satz: [Rice]
Sei T eine echte, nicht-leere Teilmenge der Klasse aller rekursiv
aufzählbaren Sprachen. Dann ist
LT = {hMi | L(M) ∈ T }
nicht entscheidbar.
Beweis:
Wäre LT entscheidbar, so wäre auch ATM entscheidbar:
O.B.d.A. sei 0/ 6∈ T . Sei L eine Sprache in T und sei ML eine
Turing-Maschine, die L akzeptiert.
Zu gegebenem M und w können wir eine Turingmaschine AM,w
konstruieren, die zunächst ihre Eingabe x auf einem zweiten Band
sichert, dann die Berechnung von M bei Eingabe w simuliert, und,
falls diese Berechnung in einem akzeptierenden Haltezustand
endet, anschließend die Berechnung von ML bei Eingabe x ausführt.
L(AM,w ) ist entweder leer, also nicht in T , oder L, also in T , je
nachdem ob M bei Eingabe w akzeptierend hält oder nicht.
Also ist hM, wi ∈ ATM genau dann wenn hAM,w i ∈ LT .
25
26
Unentscheidbare Probleme
bei allgemeinen Grammatiken
Typischerweise ist T durch eine Eigenschaft definiert. Um den Satz
von Rice anwenden zu können, muss nachgewiesen werden, dass
mindestens eine, aber nicht alle von Turing-Maschinen akzeptierten
Sprachen diese Eigenschaft besitzen.
Da wir zu einer Turing-Maschine M eine allgemeine Grammatik G
konstruieren können, so dass L(G) = L(M), lassen sich die
Unentscheidbarkeitsresultate von Turing-Maschinen auf allgemeine
Grammatiken übertragen:
Beispiel:
Satz: Die Sprache {hMi | L(M) ist regulär} ist nicht entscheidbar.
Beweis:
Die Behauptung folgt aus dem Satz von Rice mit T = REG: Die
Sprachklasse REG ist weder leer, denn L(a∗ ) liegt in REG, noch
umfasst REG alle rekursiv aufzählbaren Sprachen, denn die
Sprache {an bn | n ≥ 0} ist rekursiv aufzählbar, liegt aber nicht in
REG. Also ist der Satz von Rice anwendbar.
ATM {hG, wi | G ist eine Grammatik und w ∈ L(G)}
Satz:
Die Sprache AUG = {hG, wi | G ist eine Grammatik und w ∈ L(G)}
ist nicht entscheidbar.
27
28
Postsches Korrespondenzproblem
Ebenso gilt
Satz: Die Sprache {hG1 , G2 i | G1 und G2 sind Grammatiken und
L(G1 ) = L(G2 )} ist nicht entscheidbar.
Definition:
Sei Σ ein Alphabet. Eine nicht-leere Folge von geordneten
Wortpaaren ((x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )) mit xi , yi ∈ Σ+ heißt
Postsches Korrespondenzsystem.
Aus dem Satz von Rice folgt ferner beispielsweise
Satz: Die Sprachen
{hGi | G ist eine Grammatik und
{hGi | G ist eine Grammatik und
{hGi | G ist eine Grammatik und
{hGi | G ist eine Grammatik und
{hGi | G ist eine Grammatik und
{hGi | G ist eine Grammatik und
sind jeweils nicht entscheidbar.
ε ∈ L(G)},
L(G) = 0},
/
L(G) ist endlich},
L(G) ist regulär},
L(G) ist kontextfrei} und
L(G) ist entscheidbar}
Eine nicht-leere Folge (i1 , i2 , . . . , ik ) von Indizes aus {1, 2, . . . , n}
heißt Lösung des Korrespondenzsystems, falls
xi1 xi2 . . . xik = yi1 yi2 . . . yik
Eine Lösung (i1 , i2 , . . . , ik ) des Korrespondenzsystems heißt
speziell, falls i1 = 1.
29
30
Beispiele:
Das Korrespondenzsystem ((11, 111), (100, 001), (111, 11)) besitzt
eine spezielle Lösung, nämlich (1, 2, 3):
Beim Postschen Korrespondenzproblem ist zu entscheiden, ob ein
gegebenes Postsches Korrespondenzsystem eine Lösung besitzt.
11100111
11100111
Beim modifizierten Postschen Korrespondenzproblem wird für ein
gegebenes Postsches Korrespondenzsystem nach der Existenz einer
speziellen Lösung gefragt, also nach einer Folge (1, i2 , . . . , ik ) von
Indizes gesucht, so dass x1 xi2 . . . xik = y1 yi2 . . . yik .
Das Korrespondenzsystem ((00, 0), (001, 11), (1000, 011)) besitzt
keine Lösung!
Das Korrespondenzsystem ((011, 1), (0, 00), (0, 11), (11, 0)) besitzt
eine Lösung, nämlich (2, 1, 1, 4, 3, 3, 2, 2), aber keine spezielle.
0011011110000
0011011110000
31
Im Folgenden sei hPi eine Kodierung des Postschen
Korrespondenzsystem P, z.B. über dem Alphabet {0, 1}.
pcp = {hPi | P besitzt eine Lösung}
mpcp = {hPi | P besitzt eine spezielle Lösung}
Satz: mpcp ist unentscheidbar.
32
Ansonsten sei G = (V, Γ, R, S) die in x kodierte Grammatik und w
das in x kodierte Wort. Dann ist f (x) die Kodierung des folgenden
Postschen Korrespondenzsystem P:
O.B.d.A. nehmen wir an, dass ` und a nicht in Γ enthalten sind.
Das erste Wortpaar in P ist
(`, ` S ⇒)
Beweis:
Wir zeigen AUG = {hG, wi | w ∈ L(G)} mpcp.
Ferner enthält P das Wortpaar (a, a) für alle a ∈ Γ, das Wortpaar
(A, A) für alle A ∈ V, sowie das Wortpaar (⇒, ⇒).
Wir müssen eine geeignete Reduktionsfunktion f : Σ∗ → Σ∗
angeben. Falls x ∈ Σ∗ keine Grammatik kodiert, ist f (x) keine
Kodierung eines Postschen Korrespondenzsystem.
Für alle u →G v in R enthält P das Wortpaar
(u, v)
33
34
Beispiel:
Schließlich enthält G das Wortpaar
G = ({S, B, C}, {a, b, c}, R, S)
(⇒ w a, a)
P besitzt eine spezielle Lösung genau dann wenn w ∈ L(G). Die
Funktion f ist Turing-berechenbar und es gilt für alle x ∈ Σ∗
S
S
CB
aB
bB
bC
cC
x ∈ AUG ⇐⇒ f (x) ∈ mpcp
Mit einem Algorithmus, der das modifizierte Postsche
Korrespondenzproblem löst, könnte man also entscheiden, ob ein
Wort w zu der von einer Grammatik G erzeugten Sprache L(G)
gehört.
→
→
→
→
→
→
→
ε
aSBC
BC
ab
bb
bc
cc
w = aabbcc
(`, ` S ⇒)
(a, a)
(b, b)
(c, c)
(S, S)
(B, B)
(C, C)
(S, ε)
(S, aSBC)
(CB, BC)
(aB, ab)
(bB, bb)
(bC, bc)
(cC, cc)
(⇒, ⇒)
(⇒ aabbcc a, a)
35
36
Lemma: mpcp pcp.
Beweis:
O.B.d.A. nehmen wir an, dass # und $ nicht in den Wortpaaren des
Postschen Korrepondenzsystems P vorkommen.
` S ⇒ aSBC ⇒ aaSBCBC ⇒ aaBCBC ⇒ aaBBCC ⇒
` S ⇒ aSBC ⇒ aaSBCBC ⇒ aaBCBC ⇒ aaBBCC ⇒ aabBCC ⇒
Zu P = ((u1 , v1 ), . . . , (un , vn )) konstruieren wir ein Postsches
Korrepondenzsystems P0 , so dass P genau dann eine spezielle
Lösung besitzt, wenn P0 eine Lösung besitzt.
aabBCC ⇒ aabbCC ⇒ aabbcC ⇒ aabbcc a
aabbCC ⇒ aabbcC ⇒ aabbcc a
Für w = σ1 σ2 · · · σm ∈ Γ+ mit σi ∈ Γ für i = 1, . . . , m sei
g#L (w) = #σ1 #σ2 . . . #σm
und
g#R (w) = σ1 #σ2 # . . . σm #
37
P0 = ((#g#R (u1 ), g#L (v1 )), (g#R (u1 ), g#L (v1 )), (g#R (u2 ), g#L (v2 )),. . .
. . . , (g#R (un ), g#L (vn )), ($, #$)).
Beispiel:
P=
((1, 101), (10, 00), (011, 11)).
Falls (1, i2 , . . . , ik ) eine spezielle Lösung für P ist, so ist
(1, i2 + 1, . . . , ik + 1, n + 2) eine Lösung für P0 .
P0 =
((#1#, #1#0#1), (1#, #1#0#1), (1#0#, #0#0), (0#1#1#, #1#1), ($, #$)).
P0
Falls (j1 , j2 , . . . , jk ) eine Lösung für
ist, so muss j1 = 1 und
jk = n + 2 gelten. Dann ist (1, j2 − 1, . . . , jk−1 − 1) eine spezielle
Lösung für P.
Die Reduktionsfunktion f bildet hPi auf
hP0 i
ab.
38
#1#0#1#1#1#0#0#1#1#$
#1#0#1#1#1#0#0#1#1#$
39
40
Unentscheidbare Probleme
bei kontextfreien Grammatiken
Aus dem Gezeigten ergibt sich
Satz: pcp ist nicht entscheidbar.
Ferner gilt
Satz: pcp ist rekursiv aufzählbar.
Satz:
Die Sprache {hG1 , G2 i | G1 und G2 sind kontextfreie Grammatiken
und L(G1 ) ∩ L(G2 ) = 0}
/ ist nicht entscheidbar.
Beweis:
Wir zeigen
pcp {hG1 , G2 i | L(G1 ) ∩ L(G2 ) 6= 0}
/
41
42
R1 umfasst die Regeln
Sei P = ((x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )) ein Postsches
Korrespondenzproblem über dem Alphabet Σ.
S1 → A$B
Zu P konstruieren wir Grammatiken
B → yR1 Ba1 | · · · | yRn Ban | yR1 a1 | · · · | yRn an
A → a1 Ax1 | · · · | an Axn | a1 x1 | · · · | an xn
G1 = ({S1 , A, B}, Σ ∪ {a1 , . . . , an , $}, R1 , S1 )
und
R2 umfasst die Regeln
S2 → a1 S2 a1 | · · · | an S2 an | T
G2 = ({S2 , T}, Σ ∪ {a1 , . . . , an , $}, R2 , S2 )
T → σ Tσ für alle σ ∈ Σ
T → $
43
L(G1 ) = {aik . . . ai1 xi1 . . . xik $yRjm . . . yRj1 aj1 . . . ajm | k, m ≥ 1, iµ , jν ∈ {1, . . . , n} }
44
Da alle Wörter in L(G1 ) ∩ L(G2 ) von obiger Form sind, ist
L(G1 ) ∩ L(G2 ) 6= 0/ genau dann wenn P eine Lösung besitzt.
L(G2 ) = {uv$vR uR | u ∈ {a1 , . . . , an }∗ , v ∈ Σ∗ }
Die zu dieser Transformation gehörige Reduktionsfunktion ist
Turing-berechenbar. Also ist {hG1 , G2 i | L(G1 ) ∩ L(G2 ) 6= 0}
/ nicht
/ nicht
entscheidbar, also ist auch {hG1 , G2 i | L(G1 ) ∩ L(G2 ) = 0}
entscheidbar.
P besitzt die Lösung (i1 , i2 , . . . , ik ) genau dann wenn L(G1 ) ∩ L(G2 )
das Wort aik . . . ai1 xi1 . . . xik $yRik . . . yRi1 ai1 . . . aik enthält.
45
Satz:
Die Sprache ACFG,all = {hGi | G ist eine kontextfreie Grammatik
über dem Alphabet Σ mit L(G) = Σ∗ } ist nicht entscheidbar.
46
Wir kodieren die Konfigurationen von M in naheliegender Weise als
Kodierung des relevanten Bandinhalts, in den der aktuelle Zustand
als Markierung der Position des Schreib-Lesekopfs integriert ist.
hCi bezeichne die Kodierung der Konfiguration C.
Beweisskizze:
Wir zeigen, dass ETM = {hMi | L(M) = 0}
/ entscheidbar wäre, wenn
ACFG,all entscheidbar wäre.
Eine Berechnung C0 `M C1 `M · · · `M Cn gerader Länge kodieren wir
als Wort
Ein Wort w wird von einer Turingmaschine M akzeptiert, genau
dann wenn es eine akzeptierende Berechnung für w gibt, also eine
Folge C0 , C1 , . . . , Cn von Konfigurationen mit
hC0 i#hC1 iR #hC2 i#hC3 iR #hC4 i# · · · #hCn i
und eine Berechnung C0 `M C1 `M · · · `M Cn ungerader Länge als
C0 `M C1 `M C2 `M · · · `M Cn
hC0 i#hC1 iR #hC2 i#hC3 iR #hC4 i# · · · #hCn iR
so dass C0 die Startkonfiguration für w und Cn eine akzeptierende
Haltekonfiguration ist.
47
Die Sprache LM , die alle Wörter über dem Kodierungsalphabet
umfasst, die keiner gültigen Berechnung von M entsprechen, ist
kontextfrei, denn es gibt einen Kellerautomaten, der genau diese
Wörter akzeptiert.
Ein Wort w gehört zu LM , falls
• w nicht von der gesuchten Form ist, oder
• C0 keine Startkonfiguration ist, oder
• Cn keine akzeptierende Haltekonfiguration ist, oder
• es ein i ∈ [0 . . n − 1] gibt, so dass Ci `M Ci+1 nicht gilt.
Jede dieser Bedingungen lässt sich mit einem Kellerautomaten
überprüfen.
48
Also gibt es einen Kellerautomaten, der LM akzeptiert.
Zu diesem Kellerautomaten können wir eine kontextfreie
Grammatik G mit L(G) = LM konstruieren.
LM enthält alle Wörter über dem Kodierungsalphabet genau dann
wenn L(M) = 0.
/ Zu gegebenem hMi können wir wie beschrieben
eine kontextfreie Grammatik G konstruieren, so dass
hGi ∈ ACFG,all
g.d.w.
hMi ∈ ETM
Wäre ACFG,all entscheidbar, so wäre also auch ETM entscheidbar. 49
Ferner kann man zeigen:
Satz: Die Sprachen
{hG1 , G2 i | G1 und G2 sind kontextfreie Grammatiken und
|L(G1 ) ∩ L(G2 )| = ∞},
{hG1 , G2 i | G1 und G2 sind kontextfreie Grammatiken und
L(G1 ) ∩ L(G2 ) ist kontextfrei},
{hG1 , G2 i | G1 und G2 sind kontextfreie Grammatiken und
L(G1 ) ⊆ L(G2 )},
{hG1 , G2 i | G1 und G2 sind kontextfreie Grammatiken und
L(G1 ) = L(G2 )},
{hGi | G ist eine kontextfreie Grammatik und G ist mehrdeutig},
{hGi | G ist eine kontextfreie Grammatik und L(G) ist regulär} und
{hGi | G ist eine kontextfreie Grammatik und L(G) ist kontextfrei}
sind jeweils nicht entscheidbar.

Download Report