9. Lösungen

Hier finden Sie Lösungen zu den Aufgaben des vorherigen Kapitels.

9.2 Übungen zu Turingmaschinen

Übungsaufgabe Sei $L := \{a^n \ | \ n = 5k\}$, also die Sprache aller Wörter über dem Alphabet $\Sigma = \{a\}$, deren Länge durch 5 teilbar ist.

Implementieren Sie auf turingmachinesimulator.com eine Einband-Turingmaschine, die diese Sprache entscheidet.

Zeichnen Sie einen endlichen Automaten für die gleiche Sprache. Schreiben Sie eine reguläre Grammatik (gerne ernstmal erweitert reguläre) und einen regulären Ausdruck.

Lösung. Wir beginnen von hinten und schreiben erst einmal einen regulären Ausdruck: \begin{align*} (aaaaa)^* \end{align*} Nun übersetzen wir dies in eine erweitert reguläre Grammatik: \begin{align*} S & \rightarrow aaaaa S \\ S & \rightarrow \epsilon \end{align*} Falls Sie $L$ interpretieren als Sprache aller nichtleeren Wörter, deren Länge durch 5 teilbar ist, müssen Sie $S \rightarrow \epsilon$ durch $S \rightarrow aaaaa$ ersetzen. Wir erlauben in dieser Lösung allerdings den Fall $n=0$. Das leere Wort ist also in $L$. Um obige Grammatik in eine echt reguläre zu übersetzen, müssen wir die rechte Seite $aaaaa S$ durch Einführung neuer Nichtterminale herunterbrechen: \begin{align*} S & \rightarrow \epsilon S & \rightarrow aS_1 \\ S_1 & \rightarrow aS_2 \\ S_2 & \rightarrow aS_3 \\ S_3 & \rightarrow aS_4 \\ S_4 & \rightarrow aS \\ \end{align*} In dieser Grammatik können wir also nun \begin{align*} S & \Step{}^* aaaaa S \end{align*} in mehereren Schritten erreichen und dadurch die Produktion $S \rightarrow aaaaaS$ simulieren.

Nun lässt sich die Grammatik einfach in einen endlichen Automaten übersetzen, der auch noch deterministisch ist:

Das ist auch gleich unsere Turingmaschine. Wir haben fünf Zustände und gehen in jedem Schritt nach rechts. Nur dass wir für eine Turingmaschine noch den akzeptierenden Zustand separieren müssen.

name: durch 5 teilbar?
init: 0
accept: accept 

0, a
1, a, > 

1, a 
2, a, > 

2, a 
3, a, > 

3, a 
4, a, > 

4, a
0, a, > 

0, _
accept, _, -

Übungsaufgabe Sei $L := \{a^k b^n \ | \ k, n \geq 1 \textnormal{ und $n$ ist durch $k$ teilbar }\}$. So ist beispielsweise $aaabbbbbb \in L$ aber $aaaabbbbbb \not \in L$.

Implementieren Sie auf turingmachinesimulator.com eine Zweiband-Turingmaschine, die diese Sprache entscheidet.

Lösung. Wir kopieren in einem ersten Schritt den Dividenden $a^k$ auf das zweite Band. Dann spulen wir zurück. Der erste Kopf steht nun auf dem ersten $b$, der zweite Kopf auf dem ersten $a$. In einem Zustand go gehen wir nach rechts, bis das $a$ zu Ende gelesen worden ist; dann spulen wir wieder zurück. Akzeptieren tun wir, wenn wir gleichzeitig oben und unten ein $\square$ lesen; lesen wir oben ein $\square$ aber unten nicht, so haben wir insgesamt oben kein Vielfaches von $k$ gelesen. In diesem Falle lehnen wir ab. Sonderfälle sind beispielsweise, wenn $n = 0$, also oben gar kein $b$ steht.

name: durch k teilbar?
init: copy
accept: accept 

copy, a, _ 
copy, a, a, >, > 

copy, b, _ 
rewind, b, _, -, < 

copy, _, _ 
accept, _, _, -, - 

rewind, b, a 
rewind, b, a, -, < 

rewind, b, _ 
go, b, _, -, > 

go, b, a 
go, b, a, >, > 

go, _, _
accept, _, _, -, - 

go, b, _ 
rewind, b, _, -, <

Probieren Sie es aus! Probieren Sie insbesondere $k=0$ aus! Da versucht die Turingmaschine also, durch 0 zu dividieren. Was hat das zur Folge?

Übungsaufgabe Hier ist eine Turingmaschine mit dem Eingabealphabet $\{a,b\}$. Ich habe keine Ahnung, welche Sprache sie akzeptiert, da ich sie teils zufällig erzeugt habe.

// macht seltsames Zeug über dem Alphabet a,b

name: read-only
init: q0 
accept: accept 

q0, a
q3, a, >

q0, b
q1, b, >

q1, a 
q0, a, > 

q1, b 
q3, b, < 

q2, a
q2, a, > 

q2, b 
q3, b, < 

q3, a
q1, a, < 

q3, b 
q2, b, < 

q0, _
accept, _, - 
q1, _
accept, _, - 
q2, _
accept, _, - 
q3, _
accept, _, -

Allerdings verrate ich Ihnen was: die Turingmaschine ist read only; sie schreibt immer nur das gelesene Zeichen wieder hin. Das sollte es doch irgendwie sehr beschränken, was sie machen kann. Experimentieren Sie auf turingmachinesimulator.com mit dieser Maschine und versuchen Sie, rauszufinden, welche Sprache sie akzeptiert.

Übungsaufgabe Denken Sie sich ein PCP-Puzzle aus, das in irgendeiner Form "interessant" ist.

9.3 Kontextfreie Sprachen

Übungsaufgabe Betrachten Sie die Grammatik \begin{align*} S & \rightarrow x A y S \ | \ y B x S \ | \ \epsilon \\ A & \rightarrow x A y A \ | \ \epsilon \\ B & \rightarrow y B x B \ | \ \epsilon \end{align*} Schreiben Sie dazu eine äquivalente Grammatik in Chomsky-Normalform. Gehen Sie wie folgt vor:

Führen Sie neue Nichtterminale ein, um zu erzwingen, dass alle rechte Seiten höchstens Länge 2 haben.
Welche Nichtterminale können $\epsilon$ erzeugen, also $X \Step{}^* \epsilon$?
Eliminieren Sie die Regeln der Form $X \rightarrow \epsilon$, indem Sie auf den rechten Seiten $X$ optional weglassen.
Eliminieren Sie Kettenregeln der Form $A \rightarrow C$, indem Sie diese "trivialen Produktionen" überspringen, also beispielsweise bei $X \rightarrow Y$ und $Y \rightarrow uv$ die Regel $X \rightarrow uv$ hinzufügen.
Erlauben Sie Regeln der Form $U \rightarrow xy$. In der Chomsky-Normalform müssten Sie strenggenommen Hilfs-Nichtterminale $X$ und $Y$ einführen. Ersparen Sie sich diesen Schritt.

Lösung. Brechen wir zuerst die rechten Seiten auf Größe 2 herunter. Beachten Sie, dass das die Muster $xAy$ und $yBx$ je zweimal rechts vorkommen. Es lohnt sich also, jeweils ein Nichtterminal einzuführen. \begin{align*} S & \rightarrow C S \ | \ D S \ | \ \epsilon \\ A & \rightarrow C A \ | \ \epsilon \\ B & \rightarrow D B \ | \ \epsilon\\ C & \rightarrow x E \\ E & \rightarrow Ay \\ D & \rightarrow y F \\ F & \rightarrow Bx \end{align*} Wie Sie sehen, gilt $C \Step{}^* xAy$ und $D \Step{}^* yBx$. Als nächstes nehmen wir uns die $\epsilon$-Regeln vor. Folgende Nichtterminale können $\cdot \Step{}^* \epsilon$: $S,A,B$. Alle anderen sind "geschützt". Das $C$ beispielsweise erzeugt rechts immer ein $x$, und so weiter. Wir tragen der Tatsache, dass $A \Step{}^* \epsilon$ gilt, nun Rechnung, indem wir jedes $A$ auf einer rechten Seite optional durch $\epsilon$ ersetzen (das Gleiche für $S$ und $B$) und dafür die Regeln $\cdot \rightarrow \epsilon$ weglassen: \begin{align*} S & \rightarrow C S \ | \ D S \ | \ C \ | \ D \\ A & \rightarrow C A \ | \ C \\ B & \rightarrow D B \ | \ D \\ C & \rightarrow x E \\ E & \rightarrow Ay \ | \ y \\ D & \rightarrow y F \\ F & \rightarrow Bx \ | \ x \end{align*} Wir sind fast fertig. Unsere Behandlung von $\epsilon$ hat nun leider Kettenregeln wie $A \rightarrow C$ erzeugt. Hier ist ein Diagramm aller Kettenregeln:

Um diese nun "abzukürzen", zeichnen wir die "sinnvollen" Regeln ein, die von $C$ und $D$ ausgehen:

und nun können wir die Abkürzung nehmen:

Jetzt noch ein Super-Startsymbol $S'$, um die Regel $S' \rightarrow \epsilon$ einzubauen, die ja dennoch notwenig ist (weil $\epsilon \in L$): \begin{align*} S' & \rightarrow C S \ | \ D S \ | \ xE \ | \ yF \ | \ \epsilon \\ S & \rightarrow C S \ | \ D S \ | \ xE \ | \ yF \\ A & \rightarrow C A \ | \ xE \\ B & \rightarrow D B \ | \ yF \\ C & \rightarrow x E \\ E & \rightarrow Ay \ | \ y \\ D & \rightarrow y F \\ F & \rightarrow Bx \ | \ x \end{align*} Als allerletzten Schritt müssen wir jetzt für $x$ und $y$ die Wächter-Nichtterminale $X, Y$ einführen und dann beispielsweise $D \rightarrow yF$ durch $D \rightarrow YF$ ersetzen. Das führe ich jetzt nicht im Detail aus.

Übungsaufgabe Betrachten Sie die Grammatik \begin{align*} S & \rightarrow s AB \ | \ \epsilon \\ A & \rightarrow a BS \ | \ \epsilon \\ B & \rightarrow b SA \ | \ b \end{align*}

Zeichnen Sie einen Ableitungsbaum des Wortes $sababb$.
Berechnen Sie die Mengen $\First_1$ und $\First_2$ für jedes Nichtterminal. Die Definition können Sie in Kapitel 5.4 nachlesen.
Ist die Grammatik $LL(2)$? Können Sie beim Links-Parsen also immer anhand der nächsten zwei Zeichen erkennen, welche Regel anzuwenden ist?
Zeigen Sie, wie ein $LL(2)$-Parser das Wort $sababb$ abzuleiten versucht (oder an welcher Stelle er scheitert, falls die Grammatik nicht $LL(2)$ sein sollte). Ich gebe Ihnen Starthilfe. Der erste Schritt ist recht klar: \begin{align*} S & \Step{} sAB \Step{}^* \dots \Step{}^* sababb \end{align*} Ihr Linksparser hat nun also $sAB$ auf dem Stack liegen, matcht das oberste Stacksymbol (das Terminal $s$) mit dem nächsten (also ersten) Inputsymbol. Es bleibt $AB$ auf dem Stack. Die Restaufgabe ist also, eine die Ableitung \begin{align*} AB \Step{}^* ababb \end{align*} zu finden. Der Parser überlegt nun, welche der zwei Produktionen für $A$ er anwenden soll: \begin{align*} \begin{array}{rcl} AB \Step{} & aBSB & \Step{}^* \dots \Step{}^* ababb \quad \textnormal{ oder aber }\\ AB \Step{} & B & \Step{}^* \dots \Step{}^* ababb \end{array} \end{align*} Sie müssen nun mit Hilfe Ihrer bereits berechneten Mengen $\First_2$ die Mengen \begin{align*} & \First_2(aBSB) \quad \textnormal{ und}\\ & \First_2(B) \end{align*} berechnen und schauen, welche davon $\First_2(ababb)$ enthält. Wenn beide es enthalten, dann schlecht. Weil sich der Parser nicht entscheiden kann. Allerdings haben Sie in diesem Fall einen Beweis in der Hand, dass die Grammatik nicht $LL(2)$ ist und können mir die Schuld zuschieben.
Fahren Sie dann nach diesem Parser-Schritt entsprechend fort.

Lösung.

$\First_1(S) = \{\epsilon,s\}$, $\First_1(A) = \{\epsilon,a\}$ und $\First_1(B) = \{b\}$.

Übungsaufgabe Betrachten Sie die Grammatik \begin{align*} S & \rightarrow ABs \ | \ \epsilon \\ A & \rightarrow BSa \ | \ \epsilon \\ B & \rightarrow SAb \ | \ b \end{align*} (Vorsicht: die ist ähnlich aber nicht identisch mit der aus der letzten Übungsaufgabe).

Zeichnen Sie einen Ableitungsbaum des Wortes $babsbs$.
Zeichnen Sie den nichtdeterministischen DK-Automaten und machen Sie den dann deterministisch. Oder zeichnen Sie gleich den deterministischen. Sie können die Details in Kapitel 5.5 und Kapitel 5.6 nachlesen.
Ist es eine $LR$-Grammatik? Das können Sie dem DK-Automaten direkt ablesen.
Zeigen Sie, wie ein Rechtsparser vorgeht, wenn er das Wort $babsbs$ abeiten will. Oder zeigen Sie, dass es zu einem Zeitpunkt mehrere gültige Schritte gibt. Dann wüssten Sie, dass es keine $LR$-Grammatik ist.

9.4 Übungen zu regulären Sprachen

Übungsaufgabe Betrachten Sie die Sprache $L$ aller Wörter über dem Alphabet $\Sigma = \{a,b\}$, die das Unterwort $abaab$ enthalten.

Schreiben Sie einen regulären Ausdruck für $L$.
Schreiben Sie eine reguläre Grammatik für $L$.
Formen Sie die reguläre Grammatik in einen deterministischen endlichen Automaten um.
Schreiben Sie nun eine reguläre Grammatik für $\bar{L}$, die Sprache aller Wörter, die $abaab$ nicht enthalten.
Schreiben Sie für $\bar{L}$ einen regulären Ausdruck.

Übungsaufgabe Erinnern Sie sich an $L := \{a^k b^n \ | \ k, n \geq 1 \textnormal{ und $n$ ist durch $k$ teilbar }\}$ aus der obigen Übungsaufgabe 8.1.2. Zeigen Sie, dass diese Sprache nicht regulär ist. Die Techniken hierfür finden Sie in Kapitel 4.6.

Zeigen Sie, dass die Sprache auch nicht kontextfrei ist. Benutzen Sie hierfür das Pumping-Lemma aus Kapitel 5.10.