Transcript
Inhalt
1
Einfuhrung ¨
2
Automatentheorie und Formale Sprachen Grammatiken ¨ Sprachen und endliche Automaten Regulare Kontextfreie Sprachen und Kellerautomaten Kontextsensitive und Typ 0-Sprachen
3
Berechenbarkeitstheorie
4
¨ Komplexitatstheorie
Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
115
Kontextsensitive Sprachen Zur Erinnerung Kontextsensitive Grammatiken/Sprachen: alle Produktionsregeln P einer kontextsensitiven Grammatik G = (V , Σ, P, S) haben die Form X →Y
mit |X | ≤ |Y |
oder
S→ε
wobei X und Y Satzformen in (V ∪ Σ)∗ sind und Y die Startvariable S nicht ¨ enthalt. n
Beispiel (L = {a2 | n ∈ N}). Kontextsensitive Grammatik G mit L(G) = L: S → YT | a | aa
Xa → aaX
XaaT → aaaa
Y → XY | aa
XaT → aaT
¨ Von der 2. Ubungsserie und Satz 61 wissen wir bereits, dass L nicht kontextfrei ist. Somit gibt es kontextsensitive, nicht kontextfreie Sprachen. Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
116
Kuroda–Normalform
Definition 72 (Kuroda–Normalform (KNF)). Sei G = (V , Σ, P, S) eine kontextsensitive Grammatik, in der jede Regel die Form A → CD
oder A → a oder A → B
oder AB → CD
oder S → ε
hat, wobei A, B ∈ V und C, D ∈ V \ {S}, sowie a ∈ Σ ist. Dann sagen wir, dass G in Kuroda–Normalform (KNF) vorliegt.
Satz 73 (Kuroda ). Fur ¨ jede kontextsensitive Grammatik G existiert eine kontextsensitive Grammatik G 0 in Kuroda–Normalform, so dass L(G) = L(G 0 ).
Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
117
Beweis von Satz 73 Beweis: Sei eine kontextsensitive Grammatik G = (V , Σ, P, S) gegeben. O.b.d.A. nehmen wir an, dass die Startvariable S nur auf der linken Seite von Produktionen vorkommt, ¨ S → ε ist die einzige mogliche Produktion die ε involviert und fur ¨ jede Regel B → X gilt |X | ≤ 2.
Ansonsten verfahren wir wie bei der Umformung in CNF bei kontextfreien Sprachen (siehe Schritt 0, 1 und 3). Daruber ¨ hinaus fuhren ¨ wir fur ¨ jedes Terminal a ∈ Σ eine neue Variable A ein und ersetzen a in jeder Produktion sowohl auf der rechten, wie auf der linken Seite, durch A und fugen ¨ A→a ¨ zusatzlich zu P hinzu.
Die einzigen Regeln die nun noch nicht in Kuroda Normalform vorliegen, haben die Form A1 . . . Am → B1 · · · Bn mit 2 ≤ m ≤ n und n ≥ 3. Fur ¨ eine solche Regel fuhren ¨ wir neue Variablen C1 , . . . , Cmax{m−1,n−2} ein und ersetzen A1 . . . Am → B1 . . . Bn durch A1 A2 → B 1 C 1 ,
C 1 A3 → B 2 C 2 , . ..
Cm−2 Am → Bm−1 Cm−1 , Theoretische Informatik 2 (WS 2006/07)
Cm−1 → Bm Cm ,
Cm → Bm+1 Cm+1 , . ..
Cmax{m−1,n−2} →
Bn−1 Bn Bn
falls n > m , falls n = m .
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
118
Beispiel: KNF n
a durch A ersetzen
L = {a2 | n ∈ N} S → YT | a | aa
Xa → aaX
XaaT → aaaa
XA → AC
XAAT → AAAA C → AX
X AAT → AAAA
XAT → AAT umformen
Y → XY | AA
S → YT | A | AA
XAT → AAT
XA → AC
XAAT → AAAA
A→a
XAAT → AAAA umformen S XA C F1 A
X A → AAX
XaT → aaT
XA → AAX umformen
S → YT | A | AA
S → YT | A | AA
Y → XY | aa
→ → → →
Theoretische Informatik 2 (WS 2006/07)
YT | A | AA AE1 AX AF2
C → AX
→ → → →
XY | AA AF1 AE2 AF3
XA A E2 F3 T
A→a
Y → XY | AA
XA → AE1 A→a
E1 T → AE2
E2 → T
Y XF1 E1 T F2 A
Y → XY | AA
X AT → AAT
→ → → →
AC a T A
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
119
Turingmaschinen
Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
120
TM – Turingmaschinen Definition 74 (TM). Eine (nichtdeterministische) Turingmaschine (TM) ist ein 7-Tupel M = (Z , Σ, Γ, δ, z 0 , , E ), wobei ¨ Z eine endliche Menge von Zustanden, Σ das Eingabealphabet, Γ ⊃ Σ das Arbeitsalphabet, Γ ∩ Z = ∅, ¨ δ : Z × Γ → P(Z × Γ × {L, R, N}) die Uberf uhrungsfunktion, ¨ z0 ∈ Z der Startzustand,
∈ Γ \ Σ das Blanksymbol und
¨ E ⊆ Z die Menge der Endzustande ist. Definition 75 (DTM). Eine Turingmachine M = (Z , Σ, Γ, δ, z0 , , E ) heißt deterministische Turingmaschine (DTM), falls |δ(z, γ)| ≤ 1 fur ¨ alle z ∈ Z und γ ∈ Γ gilt. Wie funktioniert δ? Was heißt (z 0 , b, λ) ∈ δ(z, a)? ¨ Eine Turingmaschine ist ahnlich wie ein Kellerautomat eine Maschine mit einem Speicher“. Den Speicher einer ” Turingmaschine kann man sich als endloses Band vorstellen, welches mit -Symbolen und der zu verarbeitenden Eingabe initialisiert ist. Die Turingmaschine hat einen Lesekopf auf dem Band. Wenn M in Zustand z ist und das Symbol a ∈ Γ liest, dann kann M in z 0 ubergehen, ¨ a mit b uberschreiben ¨ und den Lesekopf wie durch λ angegeben nach Links, Rechts, oder Nicht bewegen. Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
121
Konfigurationen Definition 76 (Konfiguration). Eine Konfiguration einer Turingmaschine M = (Z , Σ, Γ, δ, z0 , , E ) ist ein Tupel K = (γL , z, γR ) ∈ (Γ ∗ , Z , Γ ∗ ) wobei (γL , z, γR ) den aktuellen“ Zustand beschreibt. Genauer ist ” z der aktuelle Zustand von M, der Kopf steht auf dem ersten Zeichen von γR , falls γR 6= ε, links vom Kopf steht auf dem Band das Wort γL . Gestartet wird eine TM im Startzustand z0 auf der Eingabe w ∈ Σ∗ , d.h. in der Konfiguration (ε, z0 , w ). Definition 77 (Relationen: `M , `∗ M ). Sei M = (Z , Σ, Γ, δ, z0 , , E ) eine TM. Wir definieren die Relation `M (kurz `) auf der Menge der Konfigurationen von M wie folgt: Seien a ∈ Γ ∪ {ε}, b, c ∈ Γ , γL = γL0 a, γR = bγR0 ∈ Γ ∗ und z, z 0 ∈ Z , dann 0 0 falls (z 0 , c, N) ∈ δ(z, b), (γL , z , cγR ), 0 0 (γL , z, γR ) `M (γL c, z , γR ), falls (z 0 , c, R) ∈ δ(z, b) und γR 6= ε, (γ 0 , z 0 , acγ 0 ), falls (z 0 , c, L) ∈ δ(z, b) und a 6= ε . L R
Desweiteren gilt:
0
0
(γL , z, b) `M (γL c, z , ),
falls (z , c, R) ∈ δ(z, b)
(ε, z, γR ) `M (ε, z 0 , cγR0 ),
falls (z 0 , c, L) ∈ δ(z, b) .
∗ Mit `∗ ¨ von `M . M (kurz ` ) bezeichnen wir die reflexive und transitive Hulle Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
122
Turingmachinen und Sprachen
Definition 78 (akzeptierte Sprache (TM)). Sei M = (Z , Σ, Γ, δ, z0 , , E) eine TM. Die von M akzeptierte Sprache ist ¨ irgendein z ∈ E und γL , γR ∈ Γ ∗ } . T (M) := {w ∈ Σ∗ | (ε, z0 , w ) `∗M (γL , z, γR ) fur
Beispiel (MUN+1 = (Z , Σ, Γ, δ, z0 , , E)). Z = {z0 , za , ze } Σ = {a} z0
a → a, R
za
→ a, R
Γ = {a, }
ze
E = {z0 , ze } δ(z0 , a) = (za , a, R), δ(za , a) = (za , a, R) und δ(za , ) = (ze , a, R)
a → a, R
Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
123
Automatenmodell fur ¨ kontextsensitive Sprachen ¨ Das Modell des linear beschrankten Automaten (LBA) ist eine Turingmaschine, die nur den Teil ihres Bandes benutzen darf, auf dem die Eingabe steht. Um das Ende der Eingabe zu markieren, “verdoppeln” wir das Eingabealphabet Σ: es sei ^ | a ∈ Σ}. Σ 0 = Σ ∪ {a Definition 79 (LBA). ¨ Ein linear beschrankter Automat ist eine TM M mit folgender Eigenschaft: Ist n ≥ 1 und sind a1 , . . . , an ∈ Σ, so gilt fur ¨ alle Konfigurationen (γL , z, γR ) mit ^ n ) `∗M (γL , z, γR ), (ε, z0 , a1 . . . an−1 a dass |γL γR | = n. Die von M akzeptierte Sprache ist ^ n ) `∗ (γL , z, γR ) mit γL , γR ∈ Γ ∗ und z ∈ E}. T (M) = {w = a1 . . . an ∈ Σ+ | (ε, z0 , a1 . . . an−1 a Satz 80 (LBA’s und kontextsensitive Sprachen (Satz von Kuroda)). Sei L eine Sprache uber ¨ einem beliebigen Alphabet Σ. ∃ LBA M mit T (M) = L Theoretische Informatik 2 (WS 2006/07)
⇔
L ist kontextsensitiv.
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
124
Ruckrichtung ¨ von Satz 80 Beweis (⇐): Sei G = (V , Σ, P, S) eine kontextsensitive Grammatik. Wir beschreiben informal einen LBA M mit Arbeitsalphabet Γ ⊃ V ∪ Σ 0 der L(G) akzeptiert. Bei Eingabe w = a1 . . . an ∈ Σ∗ auf dem Band geht M wie folgt vor: 1
Zu jedem Zeitpunkt ist der Bandinhalt eine Satzform Z = z1 . . . zm mit m ≤ n, wobei das letzte Symbol zm evtl. durch z^m markiert ist.
2
¨ nun nichtdeterministisch eine Produktion X → Y ∈ P sowie ein Teilwort von M wahlt Z = z1 . . . zm , das mit Y ubereinstimmt ¨ aus, falls es dies fur ¨ Y gibt.
3 4
Dann ersetzt M das Teilwort Y in Z durch X und, falls X kurzer ¨ als Y ist, wird danach das Teilwort von Z = z1 . . . zm rechts von X entsprechend nach links verschoben. Wenn m = |Z | = 1 und z1 = S, dann geht M in den Endzustand und akzeptiert. Andernfalls wiederholt M Schritt 2 und 3.
Beachte: Da die Anzahl der Produktionen endlich ist, lassen sich Schritt 1 und 2 einfach mit einer Turingmaschine realisieren. ¨ Da G kontextsensitiv ist, ist die Maschine M linear bschrankt. Ferner gilt: w ∈ L(G) gdw. es gibt eine Ableitung S ⇒ · · · ⇒ w
gdw. es gibt eine Berechnung von M, die diese Ableitung simuliert gdw. w ∈ T (M).
Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
125
Hinrichtung von Satz 80 Beweis (⇒): Sei M = (Z , Σ, Γ, δ, z0 , , E) ein LBA. Wir konstruieren zuerst eine Hilfsgrammatik G 0 mit Variablenmenge ∆ und Produktionen P 0 , wobei ∆ := Γ ∪ (Z × Γ ) ¨ und die Menge P 0 von Produktionen die folgenden Regeln enthalt: c(z, a) → (z 0 , c)b
fur ¨ alle c ∈ Γ, falls (z 0 , b, L) ∈ δ(z, a),
(z, a)c → b(z 0 , c)
fur ¨ alle c ∈ Γ, falls (z 0 , b, R) ∈ δ(z, a),
(z, a) → (z 0 , b)
falls (z 0 , b, N) ∈ δ(z, a).
Wenn wir eine Konfiguration K = γL zaγR0
mit γL , γR0 ∈ Γ ∗ , a ∈ Γ, z ∈ Z
durch das Wort K 0 = γL (z, a)γR0 ∈ ∆∗ codieren, so gilt:
Theoretische Informatik 2 (WS 2006/07)
K `∗M L gdw. K 0 ⇒∗G 0 L 0 .
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
(6) 126
Hinrichtung von Satz 80
Teil 2
Nun definieren wir die kontextsensitive Grammatik G = (V , Σ, P, S): V = {S, A} ∪ ∆ × Γ ¨ die folgenden kontextsensitive Regeln und P enthalt 1 S → A(^ a, a) fur ¨ alle a ∈ Σ, 2 3 4 5 6
A → A(a, a) fur ¨ alle a ∈ Σ,
A → ((z0 , a), a) fur ¨ alle a ∈ Σ,
(X 1 , a)(X 2 , b) → (Y 1 , a)(Y 2 , b) fur ¨ alle a, b ∈ Σ, falls X 1 X 2 → Y 1 Y 2 ∈ P 0 ((z, a), b) → b fur ¨ alle z ∈ E , a ∈ Γ und b ∈ Σ, (a, b) → b fur ¨ alle a ∈ Γ und b ∈ Σ.
Ein Wort w = a1 . . . an ∈ T (M) kann mit G wie folgt erzeugt werden: mit den Regeln 1-3 leitet man
∗
S ⇒ ((z0 , a1 ), a1 ) . . . (an−1 , an−1 )(^ an , a n )
an ; die zweiten ab; die ersten Komponenten sind die Startkonfiguration von M auf der Eingabe a 1 · · · an−1 ^ Komponenten speichern stets das Wort a1 . . . an . Da a1 · · · an ∈ T (M), kann wegen (6) mittels der Regeln aus 4 weiter abgeleitet werden: ∗
∗
S ⇒ ((z0 , a1 ), a1 ) . . . (^ an , an ) ⇒ (γ1 , a1 ) . . . (γn , an ),
¨ wobei es ein 1 ≤ i ≤ n gibt, so dass γi ∈ E × Γ, wahrend γj ∈ Γ fur ¨ i 6= j.
¨ Schließlich werden Regeln 5 und 6 benutzt, um die ersten Komponenten zu l oschen: S ⇒∗ ((z0 , a1 ), a1 ) . . . (^ an , an ) ⇒∗ (γ1 , a1 ) . . . (γn , an ) ⇒ a1 · · · an ∈ L(G).
Also folgt L(G) ⊇ T (M).
Andererseits impliziert (6), dass auch L(G) ⊆ T (M) gilt. Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
127
Typ 0-Sprachen ¨ ¨ Lasst man im obigen Beweis jeweils die lineare Beschranktheit von M und die ¨ weg, so erhalt ¨ man sofort einen Beweis fur Kontextsensitivitat ¨ den folgenden Satz. Satz 81 (TM und Typ 0-Sprachen ). Sei L eine Sprache uber ¨ einem beliebigen Alphabet Σ. ∃ TM M mit T (M) = L Bemerkung.
⇔
L ist eine Sprache vom Typ 0.
¨ Es lasst sich zeigen, dass sich nichtdeterministische TM’s durch deterministische TM’s simulieren lassen, indem der Berechnungsbaum der gegebenen nichtdeterministischen TM systematisch nach einer Konfiguration mit Endzustand durchsucht wird. Allerdings ist nicht klar, ob die simulierende Maschine hernach ein LBA ist, falls die nichtdeterministische TM ein LBA war. Dies bedeutet: Fur ¨ Typ 0 Sprachen spielt die Unterscheidung von nichtdeterministischen und deterministischen TM’s keine Rolle. Fur ¨ kontextsensitive Sprachen ist die analoge Frage (das LBA-Problem) bis heute offen. D.h. es ist nicht bekannt, ob es fur ¨ jeden LBA M einen deterministischen LBA M 0 mit T (M) = T (M 0 ) gibt. Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
128
Wortproblem Satz 82 (Wortproblem fur ¨ kontextsensitive Sprachen). Das Wortproblem fur ¨ kontextsensitive Sprachen ist entscheidbar. D.h. es gibt einen Algorithmus, der bei Eingabe einer kontextsensitiven Grammatik G = (V , Σ, P, S) und eines Wortes w ∈ Σ ∗ in endlicher Zeit feststellt, ob w ∈ L(G) oder w 6∈ L(G). ¨ ¨ ¨ Idee: Da G kontextsensitiv ist, haben alle moglichen Satzformen bei einer Ableitung von w hochstens Lange ¨ |w | und somit gibt es nur endlich viele Moglichkeiten zu untersuchen. Beweis: Sei G = (V , Σ, P, S) kontextsensitiv gegeben. Fur ¨ n, m ∈ N setze n ∗ ¨ ¨ Tm = {X ∈ (V ∪ Σ) | |X | ≤ n und X lasst sich aus S in hochstens m Schritten ableiten} . Die Mengen Tmn lassen sich, fur ¨ gegebenes n ≥ 1, induktiv berechnen: n n n ∗ n T0 = {S}, Tm+1 = Tm ∪ X ∈ (V ∪ Σ) | ∃Y ∈ Tm : Y ⇒ X mit |X | ≤ n (7)
S ¨ Da es nur (|V ∪ Σ| + 1)n Satzformen X der Lange ≤ n gibt, ist m∈N Tmn fur ¨ jedes fixierte n endlich und somit existiert ein m0 ∈ N mit [ n Tmn = Tmn +1 = . . . und Tm = Tmn . (8) 0
0
0
m∈N
Falls nun w ∈ Σ∗ , |w | = n, dann gilt w ∈ L(G) genau dann, wenn w ∈ Tmn . 0
Bei Eingabe von w mit |w | = n berechnet der Algorithmus nacheinander T 0n , T1n , . . . , wie in (7) angegeben, bis n Tmn = Tm+1 und uberpr ¨ uft ¨ dann, ob w ∈ Tmn ist. Bemerkung. Die Definition in (8) funktioniert nicht fur ¨ Typ 0-Sprachen! ¨ Sprachen sind Der angegebene Algorithmus hat exponentielle Laufzeit. Fur ¨ kontextfreie und regul are bessere Algorithmen bekannt (siehe z.B. CYK-Algorithmus). Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
129
Abschlusseigenschaften Satz 83 (Einfache Abschlusseigenschaften kontextsensitiver Sprachen). Die Klasse der kontextsensitiven Sprachen ist unter Vereinigung, Produkt und Stern abgeschlossen. ´ Satz 84 (Immerman und Szelepcsenyi). Die Klasse der kontextsensitiven Sprachen ist unter Komplementbildung abgeschlossen.
Korollar 85 (Schnitt kontextsensitiver Sprachen). Die Klasse der kontextsensitiven Sprachen ist unter Schnitt abgeschlossen.
Satz 86 (Abschlusseigenschaften von Typ 0-Sprachen). Die Klasse der Typ 0-Sprachen ist unter Schnitt, Vereinigung, Produkt und Stern, aber nicht unter Komplementbildung abgeschlossen. Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Kontextsensitive und Typ 0-Sprachen
130
Zusammenfassung: Formale Sprachen und Automaten
Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Zusammenfassung
131
Beschreibungen Sprachtyp ¨ (Typ 3) regular
deterministisch kontextfrei
kontextfrei (Typ 2)
kontextsensitiv (Typ 1)
Typ 0
Theoretische Informatik 2 (WS 2006/07)
Beschreibungsarten ¨ Grammatik regulare deterministischer endlicher Automat (DFA) nichtdeterministischer endlicher Automat (NFA) ¨ regularer Ausdruck deterministischer Kellerautomat (DPDA) LR(k)-Grammatik (k > 0) kontextfreie Grammatik Kellerautomat (PDA) kontextsensitive Grammatik ¨ linear beschrankter Automat (LBA) Phrasenstrukturgrammatik deterministische Turingmaschine Turingmaschine Automatentheorie und Formale Sprachen / Zusammenfassung
132
Determinismus vs. Nichtdeterminismus Nichtdet. Automat
Determ. Automat
¨ aquivalent?
NFA
DFA
JA
PDA
DPDA
NEIN z.B. {ww R | w ∈ {a, b}∗ }
LBA
DLBA
???
TM
DTM
JA
Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Zusammenfassung
133
Abschlusseigenschaften
L1 ∩ L 2
L1 ∪ L 2
L
L 1 L2
L∗
¨ regular
JA Satz 45
JA Satz 45
JA Satz 45
JA Satz 45
JA Satz 45
det. kf.
NEIN L1 = {a` b ` c k | `, k ∈ N} L2 = {ak b ` c ` | `, k ∈ N}
NEIN wegen und ∩
JA E
NEIN
NEIN
kontextfrei
NEIN L1 = {a b c | `, k ∈ N} L2 = {ak b ` c ` | `, k ∈ N}
JA S → S 1 | S2
NEIN wegen ∪ und ∩
JA wie k.frei
JA Satz 84
JA S → S 1 S2
JA S → ε|S S → SS
JA wie k.frei
NEIN Satz 86
JA k.frei
JA wie k.frei
kontextsensitiv Typ 0
` ` k
JA Korollar 85 JA Satz 86
Theoretische Informatik 2 (WS 2006/07)
JA wie k.frei
Automatentheorie und Formale Sprachen / Zusammenfassung
0
JA wie k.frei
134
¨ des Wortproblems – w ∈ L? Komplexitat ¨ bekannte Komplexitat
Sprachtyp
Darstellung
¨ regular
DFA
linear in |w |
det. kf.
DPDA
linear in |w |
kontextfrei
Chomsky Normalform
kontextsensitiv
Grammatik/LBA
kubisch in |w|
exponentiell in |w| (NP-hart)
¨ im Allgemeinen unlosbar
Typ 0
Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Zusammenfassung
135
¨ Entscheidbarkeit/Losbarkeit algorithmischer Probleme Wort
Leerheit
¨ Aquivalenz
Schnitt
?
?
?
L ∩ L0 = ∅
?
w ∈L
L=∅
¨ regular
JA DFA
JA
JA Minimalautomat
JA Kreuzproduktautomat
det. kf.
JA DPDA
JA
JA schwerer Beweis
NEIN
JA CYK
JA
NEIN
NEIN
JA Satz 82
NEIN
NEIN
NEIN
NEIN
NEIN
NEIN
NEIN
kontextfrei
kontextsensitiv
Typ 0
L=
L0
Bemerkung. ¨ Unentscheibarkeitsprobleme sind Bestandteil der nachsten Vorlesungen. Theoretische Informatik 2 (WS 2006/07)
Automatentheorie und Formale Sprachen / Zusammenfassung
136
