Musterlösungen zu Grundlagen der theoretischen Informatik (skizziert)

(3a) L_{2} = (a + ε)(ba)^{∗}(b + ϵ) oder L_{2} = ε + L2^{′} mit L2^{′} = a(ba)^{∗}(b + ε) + b(ab)^{∗}(a + ε) oder

L2^{′} = a + (a + ε)(ba)^{∗}b(a + ε)

L_{3} = ε + L3^{′} mit L3^{′} = L2^{′} + L_{2}(cL2^{′})^{∗}cL_{2}

L_{4} = ε + L3^{′} + L_{3}(dL3^{′})^{∗}dL_{3}

(3b) (aa^{+} + bb^{+} + cc^{+})^{∗}

(3c) l_{n} = l_{n−1} + (|Σ| − 1)l_{n−2}. (Wörter mit mindestens drei gleichen Buchstaben am Ende, plus Wörter, deren letzter Block genau die Länge 2 hat). l_{1} = 0, l_{2} = |Σ|. Für Σ_{2} ergeben sich die doppelten Fibonacci-Zahlen. Für Σ_{3} erhält man l_{n} = (2^{n+1} − 2(−1)^{n})/3. Allgemein ist

l_{n} = [(\frac{1}{2} + \sqrt{|Σ| − \frac{3}{4}})^{n} − (\frac{1}{2} − \sqrt{|Σ| − \frac{3}{4}})^{n}] / \sqrt{|Σ| − \frac{3}{4}}.

(8b) keine Kongruenzrelation für |Σ| ≥ 2: a = d = ε und b, c ∈ Σ, b ≠ c.

(8c) Es ist eine Kongruenzrelation. Die Eigenschaften einer Äquivalenzrelation weist man leicht nach. Wenn a = b = ε, ist ac = c und bd = d, und die Aussage ist trivial. Wenn a ≠ ε ≠ b ist, dann hat ac den selben Anfangsbuchstaben wie a und bd wie d.

(8d) keine Kongruenzrelation: a = d = 0, b = c = 1.

(10a) F = \{q_{6}\}, \begin{matrix}δ & q_{0} & q_{1} & q_{2} & q_{3} & q_{4} & q_{5} & q_{6} \\ 0 & q_{1} & q_{1} & q_{3} & q_{1} & q_{5} & q_{1} & q_{6} \\ 1 & q_{0} & q_{2} & q_{0} & q_{4} & q_{0} & q_{6} & q_{6} \end{matrix}

(10b) der gleiche Automat wie (10a), mit F′ = Q − F.

(10f) Die Wörter ε, 0, 01, 010, 0101, 01010, 010101 sind in verschiedenen Klassen L_{q}(M), weil die Relation in der letzten Zeile von Aufgabe 9 nicht erfüllt ist. Zum Beispiel für w_{1} = 010 und w_{2} = 01010 gilt: für x = 11: w_{1}x ∉ L, aber w_{2}x ∈ L. Im Allgemeinen kann man x so wählen, dass wx = 0101011 ist, wobei w das kürzere der Worte w_{1} und w_{2} ist. Daher hat M mindestens 7 Zustände. Dieses zeigt auch, dass der Automat aus Aufgabe 10a der Minimalautomat ist.

(14) Man beginnt mit

L_{ij}^{(0)} = {a ∈ Σ|(i, a, j) ∈ δ} (∪{ε}, falls i = j ist).

Am Ende muss man L(M) als Vereinigung der L_{q_{0},f}^{n} auch über alle Startzustände q_{0} ∈ Q_{0} bilden.

(15) NEA’s: Erzeuge einen neuen (einzigen) Endzustand f. Für alle Übergänge, die zu einem bisherigen akzeptierenden Zustand geführt haben, füge einen entsprechenden Übergang zu f hinzu. Formal:

δ′ := δ ∪ { (q, a, f) | (q, a, r) ∈ δ für ein r ∈ F }.

Falls ε ∈ L(M) ist, wird f überdies zu einem Anfangszustand erklärt.

(Man kann auch erreichen, dass es nur einen einzigen Anfangszustand und nur einen einzigen Endzustand gibt.)

DEA’s: Solche Automaten erkennen nicht alle Sprachen. Beispiel: 0^{∗} + 1^{∗}. Mit Aufgabe 9 kann man zeigen, dass δ(q_{0}, 0) ≠ δ(q_{0}, 1) sein muss. Beides sind jedoch akzeptierende Zustände.

(16) Zu jedem NEA gibt es einen äquivalenten DEA. Dieser ist ein NEA mit einem einzigen Anfangszustand. Die Zusatzfrage geht ähnlich wie Aufgabe 15.

(17a) DEA und NEA benötigen beide mindestens 5 Zustände. Nichtdeterminismus bringt keine Ersparnis.

(17b) Der NEA kommt mit 5 = n + 1 Zuständen aus (Umkehrung von 17a). Ein DEA braucht mindestens 16 = 2^{n} Zustände. Im allgemeinen ist der Unterschied zwischen NEA und DEA in diesem Beispiel exponentiell.

(19) Q = Q_{1} × Q_{2}, q = (q_{1}_{0}, q_{2}_{0}), F = F_{1} × F_{2}, δ((q_{1}, q_{2}), a) = (δ_{1}(q_{1}, a), δ_{2}(q_{2}, a))

(26a) Wende das Pumping-Lemma auf w = 0^{n}10^{n} an. L_{1} ist nicht regulär.

(26b) Wende das Pumping-Lemma auf w = 0^{n^{2}} an. n^{2} + k ist für kein k mit 1 ≤ k ≤ n eine Quadratzahl, und somit ist 0^{n^{2}+k} ∉ L_{2}. L_{2} ist nicht regulär.

(26c–e) L_{5} ∩ {00, 01, 10, 11}^{∗} ∩ 0^{∗}1^{n} ist die Sprache { 0^{n}1^{n} }, die bekanntlich nicht regulär ist. Da die regulären Sprachen abgeschlossen unter ∩ sind, ist auch L_{5} nicht regulär. Dasselbe Argument zeigt, dass L_{4} nicht regulär ist. L_{3} ist ebenfalls nicht regulär.

(26f) L_{6} = {01, 10}^{∗} · {ε, 0, 1} ist regulär.

(28) h_{3}(L_{4}) = (01)^{∗} und h_{2}(L_{1}) = 1^{∗} sind regulär. h_{1}(L) ist genau dann regulär, wenn L regulär ist.

(30) Beginnend von rechts, wird jeweils das erste nicht markierte Bit von y und von x markiert. Wenn dieses Bit von y gleich 1 ist, wird es zur entsprechenden Stelle von x addiert, und gegebenenfalls ein Übertrag nach links weitergereicht. Ein B-Symbol am Anfang von x wird dabei wie eine 0 behandelt. Wenn alle Stellen von y markiert sind, werden alle Markierungen gelöscht, und der Automat hält.

δ  0  1  ¯0  ¯1  #  $  B  Kommentar
q_{0} (q_{0}, 0, R) (q_{0}, 1, R) (q_{0}, ¯0, R) (q_{0}, ¯1, R) (q_{0}, #, R) (q_{1}, $, L) −  fahre nach rechts
q_{1} (q_{2}, ¯0, L) (q_{4}, ¯1, L) (q_{1}, ¯0, L) (q_{1}, ¯1, L) (q_{7}, #, R) − − finde erstes nicht markiertes

Bit y_{0} von y und markiere es

q_{2} (q_{2}, 0, L) (q_{2}, 1, L) −  − (q_{3}, #, L) −  −  falls y_{0} = 0, finde erstes unmar-
q_{3} (q_{0}, ¯0, R) (q_{0}, ¯1, R) (q_{3}, ¯0, L) (q_{3}, ¯1, L)  −  − (q_{0}, ¯0, R) kiertes Bit von x, markiere es.
q_{4} (q_{4}, 0, L) (q_{4}, 1, L) −  − (q_{5}, #, L) −  −  falls y_{0} = 1, finde erstes Bit
q_{5} (q_{0}, ¯1, R) (q_{6}, ¯0, L) (q_{5}, ¯0, L) (q_{5}, ¯1, L)  −  − (q_{0}, ¯1, R) von x, markiere es, addiere 1,
q_{6} (q_{0}, 1, R) (q_{6}, 0, L) −  −  −  − (q_{0}, 1, R) gegebenenfalls Übertrag
q_{7}  −  − (q_{7}, ¯0, R) (q_{7}, ¯1, R)  −  (q_{8}, $, L) −  Ende, fahre ganz nach rechts
q_{8} (q_{8}, 0, L) (q_{8}, 1, L) (q_{8}, 0, L) (q_{8}, 1, L) (q_{8}, #, L) − (q_{F} , B, R) nach links, lösche Markierungen

q_{0}101#11$ ⊢ 1q_{0}01#11$ ⊢ 10q_{0}1#11$ ⊢ 101q_{0}#11$ ⊢ 101#q_{0}11$ ⊢ 101#1q_{0}1$ ⊢
101#11q_{0}$ ⊢ 101#1q_{1}1$ ⊢ 101#q_{4}1¯1$ ⊢ 101q_{4}#1¯1$ ⊢ 10q_{5}1#1¯1$ ⊢ 1q_{6}0¯0#1¯1$
⊢ 11q_{0}¯0#1¯1$ ⊢ 11¯0q_{0}#1¯1$ ⊢ 11¯0#q_{0}1¯1$ ⊢ 11¯0#1q_{0}¯1$ ⊢ · · · ⊢ 10¯0¯0#¯1¯1q_{0}$
⊢ 10¯0¯0#¯1q_{1}¯1$ ⊢ 10¯0¯0#q_{1}¯1¯1$ ⊢ 10¯0¯0q_{1}#¯1¯1$ ⊢ 10¯0¯0#q_{7}¯1¯1$ ⊢ 10¯0¯0#¯1q_{7}¯1$
⊢ 10¯0¯0#¯1¯1q_{7}$ ⊢ 10¯0¯0#¯1q_{8}¯1$ ⊢ 10¯0¯0#q_{8}¯11$ ⊢ 10¯0¯0q_{8}#11$ ⊢ 10¯0q_{8}¯0#11$ ⊢
10q_{8}¯00#11$ ⊢ 1q_{8}000#11$ ⊢ q_{8}1000#11$ ⊢ q_{8}B1000#11$ ⊢ q_{F}1000#11$.

(33) Fall 1. y = ε:
Fall 1L. δ(q, B) = (q′, a, L).
Fall 1Lε. x = ε: Dann ist x′ = ε und y′ = Ba.
Fall 1L+. x = ux_{0} mit x_{0} ∈ Γ, u ∈ Γ^{∗}: Dann ist x′ = u und y′ = x_{0}a.
Fall 1N. δ(q, B) = (q′, a, N): Dann ist x′ = x und y′ = a.
Fall 1R. δ(q, B) = (q′, a, R): Dann ist x′ = xa und y′ = ε.

Fall 2. y = y_{1}z mit y_{1} ∈ Γ, z ∈ Γ^{∗}:

Fall 2L. δ(q, y_{1}) = (q′, a, L):

Fall 2Lε. x = ε: Dann ist x′ = ε und y′ = Baz.
Fall 2L+. x = ux_{0} mit x_{0} ∈ Γ, u ∈ Γ^{∗}: Dann ist x′ = u und y′ = x_{0}az.
Fall 2N. δ(q, y_{1}) = (q′, a, N): Dann ist x′ = x und y′ = az.
Fall 2R. δ(q, y_{1}) = (q′, a, R): Dann ist x′ = xa und y′ = z.

In allen Fällen kann man noch, wenn man will, x′ = B oder y′ = B durch x′ = ε beziehungsweise y′ = ε ersetzen.

(35a) Wahr. Man muss nur beim Entscheidungsalgorithmus die Antworten JA und NEIN vertauschen.

Bei einem Beweis auf der Ebene von Turingmaschinen muss man zunächst sicherstellen, dass die Maschine nur dann in einen akzeptierenden Zustand geht, wenn sie anhält. Man kann eine Turingmaschine, die immer hält, so modifizieren, dass es nur zwei Haltezustände gibt, einen akzeptierenden und einen nicht akzeptierenden. Durch Vertauschen dieser beiden Zustände erhält man eine Turingmaschine für die komplementäre Sprache.

(35b) Wahr. Überprüfe zuerst, ob w ∈ L_{1} ist. Wenn ja, akzeptiere das Wort w. Wenn nein, überprüfe, ob w ∈ L_{2} ist, und akzeptiere w genau dann wenn w ∈ L_{2} ist.

(35c) Wahr. Die Aussage ist logisch äquivalent zu (35a).

(35d) Falsch. Wenn D eine beliebige unentscheidbare Sprache ist, dann ist auch ihr Komplement D̄ unentscheidbar. D ∪ D̄ = Σ^{∗} ist jedoch trivialerweise entscheidbar.

(36a) Entscheidungsalgorithmus für das Eingabewort w = w_{1} … w_{n}: Für alle i = 0, …, n, teste ob w_{1} … w_{i−1} ∈ L_{1} und w_{i} … w_{n} ∈ L_{2} ist. Wenn ja, akzeptiere w. Wenn die Schleife beendet wird, verwirf w.

(36b) M_{1} und M_{2} seien zwei Maschinen mit L(M_{1}) = L_{1} und L(M_{2}) = L_{2}, Für das Eingabewort w = w_{1} … w_{n} gehen wir der Reihe nach alle Tripel (k_{1}, k_{2}, i) mit k_{1}, k_{2} ≥ 0, 0 ≤ i ≤ n durch (in irgendeiner passenden Reihenfolge), und testen durch Simulation ob M_{1} das Wort w_{1} … w_{i−1} in k_{1} Schritten akzeptiert und ob M_{2} das Wort w_{i} … w_{n} ∈ L_{2} in k_{2} Schritten akzeptiert. Wenn ja, akzeptieren wir w.

(37) Die Vorwärtsrichtung ergibt sich aus (35a). Wenn sowohl L als auch L̄ rekursiv aufzählbar ist, gibt es Maschinen M und M′ mit L(M) = L und L(M′) = M̄. Lass die Maschinen M und M′ ”parallel“ laufen; das heißt, simuliere abwechselnd einen Schritt von M und einen Schritt von M′. Mindestens eine der beiden Maschinen muss halten, und dann hat man entschieden, ob das Wort zur Sprache L gehört.

(39) Wenn M_{0} eine beliebige Turingmaschine ist, dann gilt nach Definition, mit M = M_{0} und w = ⟨M_{0}⟩:

⟨M_{0}⟩⟨M_{0}⟩ ∈ U′ ⟺ M_{0} akzeptiert das Wort ⟨M_{0}⟩⟨M_{0}⟩ nicht

Daher ist L(M_{0}) ≠ U′, weil sich die beiden Sprachen zumindest im Wort ⟨M_{0}⟩⟨M_{0}⟩ unterscheiden. Es gibt also keine Turingmaschine, die U′ akzeptiert, und U′ ist nicht einmal rekursiv aufzählbar.

(40a) L_{1} is rekursiv. Es genügt, die ersten k Schritte der Maschine M zu simulieren, um die Zugehörigkeit zur Sprache L_{1} zu entscheiden.

(40b–c) L_{2} ist rekursiv, mit dem gleichen Algorithmus wie für Aufgabe 40a. Die rekursiven Sprachen sind abgeschlossen gegenüber Vereinigung und Komplement, daher ist auch L_{3} is rekursiv.

(40d) L_{4} is rekursiv aufzählbar, aber nicht rekursiv. Eine Turingmaschine für L_{4} braucht nur die Maschine M zu simulieren, und die Eingabe zu akzeptieren, wenn M mindestens k Schritte läuft und irgendwann danach in einem akzeptierenden Zustand hält.

Wenn L_{4} rekursiv wäre, dann wäre auch die Sprache (L_{4} ∪ L_{1}) ∩ 1{0, 1}^{∗} (das sind die Eingaben mit k = 0) rekursiv; dies ist aber die universelle Sprache U.

(41) Wenn L endlich ist, ist es trivialerweise entscheidbar. Wenn L unendlich ist, muss L = 0^{∗} sein, denn mit 0^{i} gehören auch alle 0^{j} mit j < i zu L. Auch diese Sprache ist klarerweise entscheidbar.

(44b) Wenn die Sprache L rekursiv ist, dann kann eine Maschine M alle Wörter von Σ^{∗} in der passenden Reihenfolge untersuchen, und diejenigen, die zu L gehören, auf das Ausgabeband schreiben.

Nehmen wir umgekehrt an, dass es eine solche Maschine M gibt. Falls die Sprache L endlich ist, ist sie sowieso rekursiv. Falls die Sprache L unendlich ist, dann brauchen wir zur Entscheidung, ob ein Wort w ∈ L ist, nur zu warten, bis die Maschine M ein Wort schreibt, das länger als w ist. Wenn das Wort w bis dahin noch nicht auf das Band geschrieben wurde, dann gehört es nicht zu L.

(46) Zwischen den Randmarkierungen A und B fährt das ”Schiffchen“ C/D beliebig oft hin und her. Beim Weg nach rechts verdoppelt das C alle a’s, die es trifft. Am rechten Rand wird das C in D umgewandelt, und es fährt an den linken Rand, wobei es die a’s unverändert überspringt. Am linken Rand wird D wieder in C umgewandelt, und er ganze Prozess kann von vorne beginnen. In jedem Durchlauf wird die Gesamtanzahl der a’s verdoppelt. Am rechten Rand kann das C auch mit dem B zu E verschmelzen.

Das E wandert dann nach links und löst sich zusammen mit dem A auf. Damit ist der Ableitungsprozess beendet.

Die erzeugte Sprache ist { a^{2^{i}} | i ≥ 1 }.

(48) \begin{matrix}S → S + B | S − B | B & F → V ↑ F | V \\ B → B ∗ F | B ÷ F | F & V → (S) | Z \end{matrix}

(54a) L_{1} ist nicht kontextfrei. Beweis durch Widerspruch: N sei die Konstante aus dem Pumping-Lemma. Dann ist 0^{N}1^{N^{2}} = uvxyz und alle Wörter uv^{i}xy^{i}z gehören zu L_{1}. Die Möglichkeiten vxy ∈ 0^{+} und vxy ∈ 1^{+} führen direkt zu einem Widerspruch, ebenso v ∈ 0^{+}1^{+}, y ∈ 0^{+}1^{+}, oder y = ε. Es ist also v ∈ 0^{∗} und y = 1^{k} für 1 ≤ k ≤ N Somit ist uv^{2}xy^{2}z ∈ 0^{∗}1^{N^{2}+k}. Jedoch ist N^{2}+k keine Quadratzahl. Die nächstgrößere Quadratzahl nach N^{2} ist (N + 1)^{2} = N^{2} + 2N + 1 > N + k

(54b) S → 0S | 0S1 | ε erzeugt L_{2}.

(54c) L_{3} ist nicht kontextfrei. Beweis durch Widerspruch mit dem Pumping-Lemma. N sei die Konstante aus dem Pumping-Lemma. Dann ist w = 10^{N}10^{N}10^{N}10^{N} = uvxyz und alle Wörter uv^{i}xy^{i}z gehören zu L_{3}. Wegen |vxy| ≤ N kann vxy höchstens eine 1 enthalten. Wenn vy eine Eins enthält, dann enthält uxz ∈ L_{3} genau drei Einsen, ein Widerspruch. Es folgt, dass vy ∈ 0^{+} ist. Somit ist jedes Wort uv^{i}xy^{i}z von der Form 0^{j}10^{k}10^{l}10^{m}. Ein solches Wort ist nur dann ein Doppelwort, wenn j = l und k = m ist. vxy kann nur Nullen aus einem oder aus zwei aufeinanderfolgenden Nullerblöcken enthalten. Das heißt, die Wörter uv^{i}xy^{i}z = 0^{j}10^{k}10^{l}10^{m} haben zwei oder drei Nullblöcke konstanter Länge und ein oder zwei benachbarte Nullblöcke variabler Länge. Unter diesen Einschränkungen kann aber die Bedingung j = l und k = m nicht aufrechterhalten werden.

(54d) L_{4}: \begin{aligned}S → 0S1 | T_{1} | U_{1}, & T_{1} → 0T_{1}0 | T_{2}, & T_{2} → 1T_{2}0 | ε, \\ & U_{1} → 1U_{1}1 | U_{2}, & U_{2} → 0U_{2}1 | ε. \end{aligned}

L_{5}: S → 0S1 | S_{10}S_{01} | S_{01}S_{10}, S_{01} → 0S_{01}1 | ε, S_{10} → 1S_{10}0 | ε. (Mit Aufgabe 69 könnte man auch aus L_{5} = { gleich viele Nullen und Einsen }∩0^{∗}1^{∗}0^{∗}1^{∗} folgern, dass L_{5} kontextfrei ist.)

(54e) S: #(0) = 2 · #(1). S_{+}: #(0) = 2 · #(1) + 1. S_{−}: #(0) = 2 · #(1) − 1.

S → 1S_{+}S_{+} | 0S_{−} | ε , S_{+} → 1S_{+}S_{+}S_{+} | 0S , S_{−} → 1S_{+} | 0S_{−}S_{−}.

(55) Dass jedes Wort der erzeugten Sprache diese Eigenschaft hat, beweist man leicht mit vollständiger Induktion nach der Länge der Ableitung.

Wir beweisen nun mit Induktion nach der Länge n, dass jedes Wort w der Länge n mit der angegebenen Eigenschaft von der Grammatik erzeugt wird. Der Induktionsanfang n = 0 ist offensichtlich erfüllt. Falls in w jeder nichtleere Präfix x mehr a’s als b’s enthält, dann ist w = aw′, und w′ hat die angegebene Eigenschaft. Also wird w nach Induktion durch die Ableitung S → aS →^{∗} aw′ erzeugt.

Im anderen Fall sei w_{1} der kürzeste nichtleere Präfix von w, in dem die a’s und b’s ausgeglichen sind. Dann ist w = w_{1}w_{2} und w_{1} = aw′_{1}b. Man überlegt sich leicht, dass w′_{1} und w_{2} zur Sprache gehören, und somit kann w abgeleitet werden, indem man mit der zweiten Regel anfängt: S → aSbS →^{∗} aw′_{1}bS →^{∗} aw′_{1}bw_{2}.

(56) Die Grammatik

S → T | U

T → if (B) T else T | print(0); | print(1); | print(2); U → if (B) S | if (B) T else U B → true | false

ist eine äquivalente eindeutige Grammatik. Aus T sind alle Ausdrücke ableitbar, bei denen kein else mehr “fehlt”.^{1} Durch geeignete Klammerung kann man übrigens erreichen, dass das angegebene Programm auch 0 oder 1 druckt.^{2}

(58) In einer Grammatik in CNF mit n Variablen, die eine endliche Sprache erzeugt, ist das längste Wort höchstens 2^{n−1} Zeichen lang. Der Beweis geht durch vollständige Induktion. Der Fall n = 1 ist einfach. Wir können annehmen, dass die Grammatik keine überflüssigen Variablen enthält. Der erste Ableitungsschritt sei von der Form S → AB. Da die Sprache endlich ist, kann man aus A oder B keine Satzform ableiten, die die Variable S enthält. Daher ist nach Induktionannahme das längste Wort, das aus A erzeugt wird höchstens 2^{n−2} Zeichen lang, und ebenso für B. (Man kann A als das Startsymbol einer neuen Grammatik auffassen, bei der alle Regeln entfernt wurden, in denen S vorkommt.)

(59) Die Ableitung eines Wortes w mit |w| = n hat genau 2n − 1 Ableitungsschritte, für n ≥ 1. Jede Regel der Form A → BC verlängert die Satzform um 1, daher werden diese Regeln genau (n−1)-mal angewendet. Außerdem muss man noch n Regeln der Form A → a anwenden.

(62) Aus welchen Variablen kann man Terminalworte erzeugen? Aus A und C, sodann aus D, S, und schließlich aus S. Die Variable B ist überflüssig. Somit kann man die Regeln S → AB und C → aB streichen. Damit kann man aus S nur noch Satzformen mit den Variablen C und A erzeugen. Die Variablen D und E sind nicht erreichbar. Die äquivalente Grammatik ohne überflüssige Variablen ist

S → CA, A → a, C → c.
(63) \begin{aligned}c & d & c & c & d \\ C & B, D & C & C & D \\ S, D & A & ∅ & S, D \\ C, A & ∅ & S, D \\ ∅ & A, S \\ & C, A, S, D \end{aligned}

(66a) Der Automat ist ein binärer Zähler: Wenn man die Folge der Kellerinhalte an den Übergängen von q_{0} nach q_{1} betrachtet, dann wird von 0^{n} bis 1^{n} hochgezählt, wobei die niedrigwertigste Stelle ganz oben auf dem Stapel liegt. Der Eingabekopf wird immer synchron mit dem Wachsen und Schrumpfen des Kellers bewegt. Bei Eingabe von a^{n} benötigt der Automat 2^{n+2} − 2 Schritte.

1siehe auch http://www.inf.fu-berlin.de/~rote/Lere/Grundlagen%20der%20theoretischen%20 Informatik/bison/Bedingungen.y

2siehe auch http://www.inf.fu-berlin.de/~rote/Lere/Grundlagen%20der%20theoretischen%20 Informatik/bison/test-Aufgabe56

(q_{0}, ♢\underline{$}, Z_{0}) ; (q_{1}, ♢\underline{$}, Z_{0}) ; (q_{1}, ♢\underline{$}, ε) ; (q_{0}, ♢\underline{a}$, Z_{0}) ; (q_{0}, ♢a\underline{$}, 0Z_{0}) ; (q_{1}, ♢a\underline{$}, 0Z_{0}) ; (q_{0}, ♢a\underline{$}, 1Z_{0}) ; (q_{1}, ♢a\underline{$}, 1Z_{0}) ; (q_{1}, ♢\underline{a}$, Z_{0}) ; (q_{1}, ♢\underline{a}$, ε) ; (q_{0}, ♢\underline{a}a$, Z_{0}) ; (q_{0}, ♢a\underline{a}$, 0Z_{0}) ; (q_{0}, ♢aa\underline{$}, 00Z_{0}) ; (q_{1}, ♢aa\underline{$}, 00Z_{0}) ; (q_{0}, ♢aa\underline{$}, 10Z_{0}) ; (q_{1}, ♢aa\underline{$}, 10Z_{0}) ; (q_{1}, ♢a\underline{a}$, 0Z_{0}) ; (q_{0}, ♢a\underline{a}$, 1Z_{0}) ; (q_{0}, ♢aa\underline{$}, 01Z_{0}) ; (q_{1}, ♢aa\underline{$}, 01Z_{0}) ; (q_{0}, ♢aa\underline{$}, 11Z_{0}) ; (q_{1}, ♢aa\underline{$}, 11Z_{0}) ; (q_{1}, ♢a\underline{a}$, 1Z_{0}) ; (q_{1}, ♢\underline{a}a$, Z_{0}) ; (q_{1}, ♢\underline{a}a$, ε)  (q_{0}, ♢\underline{a}aa$, Z_{0}) ; (q_{0}, ♢a\underline{a}a$, 0Z_{0}) ; (q_{0}, ♢aa\underline{a}$, 00Z_{0}) ; (q_{0}, ♢aaa\underline{$}, 000Z_{0}) ; (q_{1}, ♢aaa\underline{$}, 000Z_{0}) ; (q_{0}, ♢aaa\underline{$}, 100Z_{0}) ; (q_{1}, ♢aaa\underline{$}, 100Z_{0}) ; (q_{1}, ♢aa\underline{a}$, 00Z_{0}) ; (q_{0}, ♢aa\underline{a}$, 10Z_{0}) ; (q_{0}, ♢aaa\underline{$}, 010Z_{0}) ; (q_{1}, ♢aaa\underline{$}, 010Z_{0}) ; (q_{0}, ♢aaa\underline{$}, 110Z_{0}) ; (q_{1}, ♢aaa\underline{$}, 110Z_{0}) ; (q_{1}, ♢aa\underline{a}$, 10Z_{0}) ; (q_{1}, ♢a\underline{a}a$, 0Z_{0}) ; (q_{0}, ♢a\underline{a}a$, 1Z_{0}) ; (q_{0}, ♢aa\underline{a}$, 01Z_{0}) ; (q_{0}, ♢aaa\underline{$}, 001Z_{0}) ; (q_{1}, ♢aaa\underline{$}, 001Z_{0}) ; (q_{0}, ♢aaa\underline{$}, 101Z_{0}) ; (q_{1}, ♢aaa\underline{$}, 101Z_{0}) ; (q_{1}, ♢aa\underline{a}$, 01Z_{0}) ; (q_{0}, ♢aa\underline{a}$, 11Z_{0}) ; (q_{0}, ♢aaa\underline{$}, 011Z_{0}) ; (q_{1}, ♢aaa\underline{$}, 011Z_{0}) ; (q_{0}, ♢aaa\underline{$}, 111Z_{0}) ; (q_{1}, ♢aaa\underline{$}, 111Z_{0}) ; (q_{1}, ♢aa\underline{a}$, 11Z_{0}) ; (q_{1}, ♢a\underline{a}a$, 1Z_{0}) ; (q_{1}, ♢\underline{a}aa$, Z_{0}) ; (q_{1}, ♢\underline{a}aa$, ε)

(66b) Für q ∈ Q, i ≥ 1, haben wir

E(q, i, 0) = E(q, i, 1) = (q_{1}, i − 1)
E(q, i, Z_{0}) = (q_{1}, i)

Für i = 0 hängt die Entladefunktion davon ab, wie man δ(·, ·, ♢) definiert. Wir können zum Beispiel δ(q, γ, ♢) = δ(q, γ, a) oder δ(q, γ, ♢) = (q, ε, N) setzen.

(76) Ja.

(77) Nein. Zum Beispiel ist die Sprache

{ 00^{i}1^{2i} | i ≥ 1 } ∪ { 10^{2i}1^{i} | i ≥ 1 }

deterministisch kontextfrei, nicht aber ihre Umkehrung.