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

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

// 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, _, - 
                            
                        

1. Führen Sie neue Nichtterminale ein, um zu erzwingen, dass alle rechte Seiten höchstens Länge 2 haben.
2. Welche Nichtterminale können \(\epsilon\) erzeugen, also \(X \Step{}^* \epsilon\)?
3. Eliminieren Sie die Regeln der Form \(X \rightarrow \epsilon\), indem Sie auf den rechten Seiten \(X\) optional weglassen.
4. 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.
5. 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.

1. Zeichnen Sie einen Ableitungsbaum des Wortes \(sababb\).
2. Berechnen Sie die Mengen \(\First_1\) und \(\First_2\) für jedes Nichtterminal. Die Definition können Sie in Kapitel 5.4 nachlesen.
3. Ist die Grammatik \(LL(2)\)? Können Sie beim Links-Parsen also immer anhand der nächsten zwei Zeichen erkennen, welche Regel anzuwenden ist?
4. 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.

1. Zeichnen Sie einen Ableitungsbaum des Wortes \(babsbs\).
2. 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.
3. Ist es eine \(LR\)-Grammatik? Das können Sie dem DK-Automaten direkt ablesen.
4. 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.