Aufgabenblock — AFB II
Zehn Aufgaben zum Anwenden in neuen Situationen: Sprachen erkennen, Keller und Ableitungen verfolgen, Modelle vergleichen. Erst selbst rechnen, dann prüfen.
Gegeben ist der DEA:
Analysieren Sie den Automaten: Beschreiben Sie die Bedeutung der Zustände und geben Sie an, wie viele Wörter der Länge 3 er akzeptiert.
Lösung anzeigen
Der DEA akzeptiert alle Wörter, die das Teilwort aa enthalten. Länge 3: aaa, aab, baa → 3 Wörter
aba wird abgelehnt: Das b dazwischen führt zurück nach z0.
Ein Mealy-Automat mit \(\Sigma=\{a,b\}\) und \(\Omega=\{X\}\) hat die Zustände q0 (Start), q1, q2. Mit a geht er von q0 nach q1 und von q1 nach q2 (Ausgabe ε), von q2 zurück nach q0 mit Ausgabe X; b ist überall eine Schleife mit Ausgabe ε. Untersuchen Sie, wie viele X er zur Eingabe aabaaaab ausgibt.
Lösung anzeigen
q0 –a→ q1 –a→ q2 –b→ q2 –a/X→ q0 –a→ q1 –a→ q2 –a/X→ q0 –b→ q0 → XX, also 2
Das Wort enthält sechs a; nach dem dritten und dem sechsten kommt ein X. Die b ändern nichts.
Der Kellerautomat erkennt \(\{a^{2n}b^n\mid n\ge 1\}\); z3 ist Endzustand.
| von | Übergang | nach |
|---|---|---|
| z0 | (#,a):# | z1 |
| z0 | (A,a):A | z1 |
| z1 | (#,a):A# | z0 |
| z1 | (A,a):AA | z0 |
| z0 | (A,b):ε | z2 |
| z2 | (A,b):ε | z2 |
| z2 | (#,ε):# | z3 |
Ermitteln Sie Zustand und Kellerinhalt (oberstes Zeichen links) nach dem Lesen von aaaab.
Lösung anzeigen
(z0, #) –a→ (z1, #) –a→ (z0, A#) –a→ (z1, A#) –a→ (z0, AA#) –b→ (z2, A#)
Mit einem weiteren b wird der Keller zu #, der ε-Übergang führt nach z3: aaaabb wird akzeptiert.