Übungsaufgaben
Zehn Übungen zum Klicken, Zuordnen, Nachverfolgen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
Ordnen Sie jeden Bestandteil zu: Gehört er zu beiden Automatenarten oder nur zum Kellerautomaten?
Nennen Sie zu jeder Aussage über Kellerautomaten, ob sie stimmt.
Betrachten Sie den Übergang (K,[):KK. Geben Sie zu jedem Teil der Notation die passende Bedeutung an, indem Sie beide verbinden.
(K,[):KK bedeutet: K liegt oben und wird entfernt, [ wird gelesen, dann werden zwei K abgelegt — netto liegt ein K mehr im Keller. Typischer Fehler: Die Reihenfolge in der Klammer vertauschen. Zuerst steht das Kellerzeichen, dann das Eingabezeichen.Der Kellerautomat KL soll korrekt geklammerte Folgen aus eckigen Klammern erkennen.
Wenden Sie den Automaten auf das Wort [[]] an. Notieren Sie den Kellerinhalt mit dem obersten Zeichen links, z. B. K#.
- Keller nach dem 1. Zeichen
- Keller nach dem 2. Zeichen
- Keller nach dem 3. Zeichen
- Keller nach dem 4. Zeichen
- Zustand nach dem ε-Übergang
- angenommen oder abgelehnt?
(#,ε):# nach z1: angenommen. Typischer Fehler: beim ersten Zeichen #K schreiben — das rechte Zeichen von K# wird zuerst abgelegt, oben liegt also K.Im Keller liegt AB# (A oben). Bestimmen Sie für jeden Übergang einzeln, welcher Kellerinhalt danach entsteht (oberstes Zeichen links, leerer Keller als ε).
| Übergang | Kellerinhalt danach |
|---|---|
| (A,a):BA | |
| (A,b):ε | |
| (A,c):A | |
| (A,ε):CCA | |
| (A,d):B |
B#), dann W links davorschreiben. So wird aus (A,ε):CCA der Inhalt CCAB#. (A,c):A ändert den Keller gar nicht, (A,d):B tauscht das oberste Zeichen aus. Typischer Fehler: W rechts anhängen statt links davor.KL (siehe A4) liest das Wort [][]. Ordnen Sie die Konfigurationen (Zustand, Resteingabe, Keller) in die Reihenfolge des akzeptierenden Laufs ein.
# und K#. Erst ganz am Ende führt der ε-Übergang nach z1. Typischer Fehler: die Konfiguration (z0, [], #) direkt nach dem Start einordnen — dazwischen liegt noch der Schritt mit K#.Ermitteln Sie mithilfe von KL (siehe A4) und Ihrem Wissen aus 9.2.2, welche Aussagen zutreffen.
(#,ε):# nach z1 führt und nichts mehr zu lesen ist. Bei []] steht beim dritten Zeichen # oben — (#,]) gibt es nicht; der Umweg über z1 hilft nicht, weil das Wort nicht vollständig gelesen ist. Beliebig tiefe Klammerung kann nach 9.2.2 kein DEA prüfen.Mia erklärt, was KL (siehe A4) mit dem Wort []] macht. Überprüfen Sie ihre Erklärung — drei Zeilen sind fehlerhaft.
KL (siehe A4) soll so verändert werden, dass er auch Spitzklammern < > prüft: Σ = {[, ], <, >}, Γ = {K, W, #}. K steht für eine offene [, W für eine offene <. Jede schließende Klammer muss zur zuletzt geöffneten passen.
Liegt # oben und wird < gelesen: . Liegt K oben und wird < gelesen: . Liegt W oben und wird [ gelesen: . Eine > schließt die zuletzt geöffnete Spitzklammer: . Der Übergang in den Endzustand bleibt: .
(K,<):WK, nicht KW — sonst läge K oben. (K,>):ε fehlt absichtlich: Eine > darf keine offene [ schließen, der Automat bleibt dann stecken. Genau das verhindert Überkreuzungen wie [<]>.Tom hat einen Kellerautomaten T für \(L=\{a^nb^n\mid n\ge 0\}\) gebaut: nur ein Zustand z0, zugleich Start- und Endzustand, mit den Schleifen (#,a):A#, (A,a):AA und (A,b):ε. Beurteilen Sie seinen Automaten, indem Sie die Menüs ausfüllen.
aab wird von T akzeptiert:
abab wird von T akzeptiert:
ba wird von T akzeptiert:
T akzeptiert genau die Wörter,
Urteil:
aab (Rest A im Keller) und abab (a und b im Wechsel). Stecken bleibt T nur, wenn ein b kommt, während # oben liegt. Es fehlen die Phasentrennung (nach dem ersten b kein a mehr) und die Prüfung (#,ε):# vor dem Endzustand.