Grundlagen der theoretischen Informatik, SS 2001

1. Teilklausur, Montag, 11. Juni 2001 — Lösungen

Anleitung: Bearbeiten Sie jede Aufgabe auf dem dafür vorgesehenen Blatt. Verwenden Sie gegebenfalls Ergänzungsblätter. Schreiben Sie auf alle Blätter Ihren Namen und Ihre Matrikelnummer.

Sie können alle Aussagen, die in der Vorlesung oder auf den Übungsblättern vorgekommen sind, verwenden, ohne die Beweise abzuschreiben.

Kriterium für positive Bewertung: mindestens 50 %, das sind 15 Punkte.

1. (10 Punkte) Zeichnen Sie das Zustandsdiagramm des nichtdeterministischen endlichen Automaten ({a, b, c, d}, {0, 1}, δ, {a}, {d}) mit

δ = {(a, 0, b), (a, 1, a), (a, 1, c), (b, 0, a), (b, 1, b), (b, 1, c), (c, 0, d), (d, 0, d)},

und bestimmen Sie den Minimalautomaten.

Lösung: Nebenstehend ist der deterministische Automat angegeben, der aus der Potenzmengenkonstruktion entsteht, wobei mit den Einzelzuständen begonnen wurde, aber nur diejenigen zusätzlichen Zustände berücksichtigt wurden, die auf der rechten Seite auftreten.

Die Zustände c, d, ∅ sind nicht erreichbar und können gestrichen werden. Es bleibt die Zustandsmenge Q = {a, b, ac, bc, ad, bd} mit den akzeptierenden Zuständen F = {ad, bd}.

Anfangszerlegung der Zustandsmenge: K_{1} = Q − F = {a, b, ac, bc}, K_{2} = F = {ad, bd}. K_{1} wird zerlegt gemäß δ(a, 0), δ(b, 0) ∈ K_{1}, δ(ac, 0), δ(bc, 0) ∈ K_{2}.

\begin{matrix}δ′ & 0 & 1 \\ a & b & ac \\ b & a & bc \\ c & d & ∅ \\ d & d & ∅ \\ ac & bd & ac \\ bc & ad & bc \\ ad & bd & ac \\ bd & ad & bc \\ ∅ & ∅ & ∅ \end{matrix}

Neue Zerlegung K_{1} = {a, b}, K_{2} = {ac, bc}, K_{3} = {ad, bd}. Keine weitere Zerlegung möglich. Der Minimalautomat ist ({q_{1}, q_{2}, q_{3}}, {0, 1}, δ̄, q_{1}, {q_{3}}) mit δ̄ = {(q_{1}, 0, q_{1}), (q_{1}, 1, q_{2}), (q_{2}, 0, q_{3}), (q_{2}, 1, q_{2}), (q_{3}, 0, q_{3}), (q_{3}, 1, q_{2})}.

2. (10 Punkte)

(a) (7 Punkte) Konstruieren Sie einen endlichen Automaten für die Sprache L_{1} der Wörter über {0, 1}, bei denen auf jedes Vorkommen der Teilfolge 0011 unmittelbar die Teilfolge 1100 anschließt. Zum Beispiel ist w_{1} = 0001111100 ∉ L_{1}, w_{2} = 01011001111001111000 ∈ L_{1}, w_{3} = 0010 ∈ L_{1}, und w_{4} = 00111100011 ∉ L_{1}. Erklären Sie Ihren Automaten in wenigen Sätzen. (Ein formaler Korrektheitsbeweis ist nicht erforderlich.) Geben Sie eine akzeptierende Zustandsfolge für w_{2} und w_{3} an.

(b) (3 Punkte) Konstruieren Sie einen endlichen Automaten, der alle Präfixe der Wörter aus L_{1} akzeptiert.

L_{2} = { x | es gibt ein y mit xy ∈ L_{1} }

(Zum Beispiel ist w_{5} = 010110011110011110 ∈ L_{2} − L_{1}, wegen w_{5}00 = w_{2} ∈

L_{1}.)

Lösung zu a: Wir konstruieren einen DEA. (Einen NEA zu finden, der den Nichtdeterminismus ausnützt, ist schwierig.) Der Automat merkt sich den längsten Präfix der Wortes 0011, mit dem die bisher gelesene Eingabe aufhört. Wenn die letzen i gelesenen Symbole mit den ersten i Symbolen von 0011 übereinstimmen, befindet sich der Automat im Zustand q_{i}.

Im Zustand q_{4} hat der Automat erkannt, dass die Folge 0011 vorgekommen ist, und er prüft nun, ob die Symbole 1100 in dieser Reihenfolge kommen, und geht dabei in die Zustände q_{5}, q_{6}, q_{7}. Wenn das Ende der Folge 00111100 erreicht ist, geht der Automat wieder in den Zustand q_{2}. Wenn die Folge 1100 nicht ohne Fehler gefunden wird, geht der Automat in einen Abbruchzustand q_{∞}, in dem er immer bleibt.

Der Ausgangszustand ist q_{0}, die akzeptierenden Zustände sind F = {q_{0}, q_{1}, q_{2}, q_{3}}.

Der Weg von q_{0} bis q_{7} (oder gegebenfalls q_{8}) ist klar, bei der ”Rückwärtskanten“, wenn nicht das erwartete Zeichen kommt, muss man etwas aufpassen, wohin sie führen. (Zum Beispiel ist δ(q_{2}, 0) = q_{2} weil im Zustand q_{2} nach dem Lesen einer 0 bekannt ist, dass das Wort mit 000 aufhört; Die letzten beiden Nullen sind der längste Präfix von 0011 am Ende des bisher gelesenen Wortes.)

\begin{matrix}δ & 0 & 1 \\ q_{0} & q_{1} & q_{0} \\ q_{1} & q_{2} & q_{0} \\ q_{2} & q_{2} & q_{3} \\ q_{3} & q_{1} & q_{4} \\ q_{4} & q_{∞} & q_{5} \\ q_{5} & q_{∞} & q_{6} \\ q_{6} & q_{7} & q_{∞} \\ q_{7} & q_{2} & q_{∞} \\ q_{∞} & q_{∞} & q_{∞} \end{matrix}

Zur Kontrolle: Bei Eingabe von w_{2} durchläuft der endliche Automat die akzeptierende Zustandsfolge q_{0}q_{1}q_{0}q_{1}q_{0}q_{0}q_{1}q_{2}q_{3}q_{4}q_{5}q_{6}q_{7}q_{2}q_{3}q_{4}q_{5}q_{6}q_{7}q_{2}q_{2}, bei w_{3} die Zustandsfolge q_{0}q_{1}q_{2}q_{3}q_{1}.

Lösung zu b: Man muss die Endzustände des vorigen endlichen Automaten auf F′ = {q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}, q_{6}, q_{7}} erweitern. Wenn der Automat in einem der neuen Endzustände q_{4}, q_{5}, q_{6}, q_{7} ist, kann er durch Verlängerung des Eingabewortes (um einen passenden Suffix von 1100) in den für den ursprünglichen Automaten akzeptierenden Zustand q_{2} gebracht werden. Daher ist das gelesene Wort ein Präfix eines Wortes aus L_{1}.

Wenn der Automat im Zustand q_{∞} ist, dann hilft auch eine Verlängerung des gelesenen Wortes nichts mehr, um in einen akzeptierenden Zustand zu kommen. Das gelesene Wort ist kein Präfix eines Wortes aus L_{1}.

3. (10 Punkte) Beweisen Sie:

(a) (5 Punkte) Wenn L_{1} regulär ist, dann ist auch die Sprache L_{3} aller Suffixe von

L_{1} regulär.

L_{3} = { x | es gibt ein y mit yx ∈ L_{1} }

(b) (5 Punkte) Wenn L_{1} regulär ist, dann ist auch die Sprache L_{4} aller Teilwörter

von L_{1} regulär.

L_{4} = { x | es gibt y, z mit yxz ∈ L_{1} }

Lösung 1 zu a: Die Lösung von Aufgabe 2b lässt sich verallgemeinern. Wenn L(M) = L_{1} ist, erhält man einen Automaten M′ für die Sprache L_{2} der Präfixe von L_{1} indem man in M alle Zustände, von denen ein akzeptierender Zustand von M erreichbar ist, zusätzlich zu akzeptierenden Zuständen macht.

Beweis für den Fall eines deterministischen Automaten M: (Das Verfahren funktioniert aber genauso gut bei nichtdeterministischen endlichen Automaten.) Wenn δ(q_{0}, x) = q ist und von q aus ein akzeptierender Zustand q_{F} ∈ F erreichbar ist (δ(q, y) = q_{F} für ein y ∈ Σ^{∗}), dann ist δ(q_{0}, xy) = q_{F} ∈ F und somit xy ∈ L_{1}, und x ∈ L_{2}. Umgekehrt, wenn es ein y ∈ Σ^{∗} mit xy ∈ L_{1} gibt, dann ist δ(q_{0}, xy) = δ(δ(q_{0}, x), y) ∈ F und somit ist von δ(q_{0}, x) aus ein akzeptierender Zustand erreichbar. Somit ist δ(q_{0}, x) ∈ F′ und x wird von M′ akzeptiert.

Reguläre Sprachen sind abgeschlossen unter Umkehrung (oder Spiegelbild, siehe Übungsaufgabe 25). Die Suffixe eines Wortes oder einer Sprache sind die Umkehrungen der Präfixe der Umkehrung:

L_{3} = Suffixe(L_{1}) = (Präfixe(L_{1}^{R}))^{R}

Somit ergibt sich die Abgeschlossenheit gegenüber Suffixen aus der Abgeschlossenheit gegenüber Präfixen.

Lösung 2: Man kann auch direkt einen nichtdeterministischen endlichen Automaten für die Suffixe konstruieren. Man macht alle Zustände, die von einem Ausgangszustand aus erreichbar sind, zusätzlich zu Ausgangszuständen. Der Beweis ist analog wie bei Lösung 1.

Lösung 3: Eine andere Möglichkeit ist ein nichtdeterministischer endlicher Automat mit ε-Übergängen: M sei ein deterministischer oder nichtdeterministischer Automat mit L(M) = L_{1}. Man erstellt eine Kopie M′ von M und ersetzt alle Übergänge (q′_{1}, a, q′_{2}) ∈ δ′ durch ε-Übergänge (q′_{1}, ε, q′_{2}). Zusätzlich verbindet man jeden Zustand q′ ∈ Q′ des Automaten M′ mit dem entsprechenden Zustand q ∈ Q durch einen ε-Übergang (q′, ε, q). Der neue Automat M_{3}, der L_{3} akzeptiert, hat die Zustände Q ∪ Q′, die Anfangszustände Q′_{0} ⊆ Q′ und die akzeptierenden Zustände F des ursprünglichen Automaten. Dieser Automat kann nun mit den ε-Übergängen in Q′ beginnen und so tun, als ob er ein Wort y liest, ohne es wirklich zu lesen. Irgendwann entscheidet er sich, in die Zustandsmenge Q zu springen und den Rest (Suffix) x des Wortes yx ∈ L_{1} wirklich zu lesen.

Lösung zu b: Die Teilwörter sind die Präfixe der Suffixe (oder die Suffixe der Präfixe). Somit ergibt sich der Beweis aus Lösung 1 zu Teil (a).

4. (Zusatzfrage, 5 Punkte) Wie kann man für zwei gegebene reguläre Sprachen L_{1} und L_{2} entscheiden, ob L_{1} ⊆ L_{2} ist?

Lösung: L_{1} ⊆ L_{2} gilt genau dann, wenn L_{1} ∩ L̄_{2} = ∅ ist. Reguläre Sprachen sind gegenüber Durchschnitt und Komplement abgeschlossen. Daher braucht man nur zu überprüfen, ob die reguläre Sprache L_{1} ∩ L̄_{2} leer ist.