Kellerautomaten entwickeln: Übungen – Informatik Leistungskurs

A1

Welcher Automat genügt?

AFB I

Ordnen Sie jede Sprache über dem passenden Alphabet dem schwächsten Automaten zu, der sie erkennt.

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).

1DEA genügt

2Kellerautomat nötig

3auch Keller reicht nicht

Ohne Vergleich zweier unbeschränkter Anzahlen reicht ein DEA. Ein Vergleich (aⁿ gegen bⁿ⁺¹, w gegen wᴿ, m gegen n) gelingt mit einem Keller. Bei aⁿbⁿcⁿ muss dieselbe Anzahl zweimal verglichen werden — nach dem Vergleich mit den b ist der Keller leer und die Information verloren.

Ansatz: Muss der Automat überhaupt etwas Unbeschränktes vergleichen?

Weiter: Ein Keller kann eine Anzahl einmal abbauen. Wie oft muss hier verglichen werden?

A2

Entwurfsschritte

AFB I

Geben Sie zu jedem Entwurfsschritt die Leitfrage oder das Kennzeichen an, indem Sie beide verbinden.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.

Die Schritte bauen aufeinander auf: Erst der Kellerplan, dann Zustände für die Phasen, dann die Übergänge mit dem Abschluss. Getestet wird am Ende — gerade Randfälle wie ε decken vergessene Übergänge auf.

Ansatz: Beginnen Sie mit dem Abschluss — dort steht fast schon die Notation.

Weiter: Raten muss ein Automat nur, wenn er einen Wechsel nicht am gelesenen Zeichen erkennt.

A3

Rest im Keller

AFB I

Der Automat M lässt Reste im Keller zu.

Kellerautomat M für \(\{a^nb^m\mid n\ge m\ge 0\}\) (z0 und z1 Endzustände)

Bestimmen Sie, wie viele A nach dem vollständigen Lesen von aaaab im Keller liegen.

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.

Vier a legen vier A ab, das b entfernt eines: Es bleiben 3 A (Keller AAA#). M steht in z1, einem Endzustand — das Wort wird trotz Rest akzeptiert. Hier ist das gewollt: Es dürfen mehr a als b vorkommen. Typischer Fehler: 4 — das gelesene b nicht abziehen.

Ansatz: Zählen Sie die abgelegten A und die entfernten A.

Weiter: Jedes a legt ein A ab, jedes b entfernt eines.

A4

Kellerplan für aⁿbⁿ⁺¹

AFB II

Ein Kellerautomat soll \(L=\{a^nb^{n+1}\mid n\ge 0\}\) erkennen: Jedes a legt ein A ab, jedes b entfernt eines — und das letzte b wird gelesen, wenn # oben liegt. Wenden Sie diesen Kellerplan an (Kellerinhalt mit oberstem Zeichen links).

Arbeiten Sie die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.

Was legt (#,a) ab?
Was legt (A,a) ab?
Kellerinhalt nach dem Lesen von aabb
Oberstes Kellerzeichen, wenn das letzte b von aabbb gelesen wird
Wie viele b werden nach aaa noch gelesen?

Nach aⁿ liegen n A im Keller. Die ersten n b bauen sie ab, das (n + 1)-te b wird mit # oben gelesen — etwa durch (#,b):# in einen Endzustand. Typischer Fehler im letzten Schritt: 3 statt 4, also die zusätzliche Eins in n + 1 vergessen.

Ansatz: Jedes a erhöht den Keller um eins, jedes b senkt ihn um eins.

Weiter: Nach n b ist der Keller wieder bei #. Wie viele b fehlen dann noch?

A5

Welche Wörter akzeptiert M?

AFB II

Ermitteln Sie für jedes Wort, ob der Automat M aus A3 es akzeptiert (ja/nein).

Tragen Sie „ja“ oder „nein“ ein und prüfen Sie dann. Enter prüft ebenfalls.

Wort	aaab	abab	aabb	bb	ε
akzeptiert?

M akzeptiert genau \(\{a^nb^m\mid n\ge m\ge 0\}\). abab scheitert, weil in z1 kein a mehr gelesen werden kann, bb schon am Anfang (# oben, b gelesen). ε wird akzeptiert, weil z0 Endzustand ist. Typischer Fehler: aabb ablehnen, weil „n ≥ m“ als „n > m“ gelesen wird.

Ansatz: Spielen Sie jedes Wort mit dem Keller durch.

Weiter: Endzustände sind z0 und z1 — ein Rest im Keller schadet nicht.

A6

Entwurf für w c wᴿ

AFB II

Lena entwirft einen Kellerautomaten für \(\{w\,c\,w^R\mid w\in\{a,b\}^*\}\). Ordnen Sie ihre Arbeitsschritte in eine sinnvolle Reihenfolge ein.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.

1Vor dem c muss das Wort gespeichert, danach rückwärts verglichen werden.

2Kellerplan: a legt A ab, b legt B ab; nach dem c entfernt a ein A und b ein B.

3Phasen festlegen: z0 „ablegen“, z1 „vergleichen“, z2 „fertig“.

4Übergänge notieren, z. B. (A,b):BA in z0 und (B,b):ε in z1.

5Abschluss: (#,ε):# von z1 in den Endzustand z2.

6Testen mit abcba, c und abcab.

Erst die Idee, dann der Keller, dann die Zustände, dann die Übergänge — und zum Schluss der Test, der auch Wörter knapp neben L enthält (abcab). Typischer Fehler: Übergänge zu notieren, bevor feststeht, welche Zeichen im Keller liegen.

Ansatz: Was muss feststehen, bevor Sie einen einzigen Übergang notieren können?

Weiter: Die Übergänge nennen Kellerzeichen und Zustände — beides muss vorher festgelegt sein.

A7

DEA oder Keller?

AFB II Mix

Vergleichen Sie Kellerautomaten mit DEA (9.1) und markieren Sie alle zutreffenden Aussagen. M ist der Automat aus A3.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.

Ein Kellerautomat kann den Keller auch einfach ignorieren (immer # ablegen) — damit kann er jeden DEA nachbilden. Ohne ε-Übergänge hat er trotzdem den Keller, ist also kein DEA. Fehlende Übergänge bedeuten beim Kellerautomaten „stecken bleiben“; ein zF ist nicht nötig. ε akzeptiert M, weil z0 Endzustand ist.

Ansatz: Was kann ein Kellerautomat, was ein DEA nicht kann — und umgekehrt?

Weiter: Denken Sie daran: Ein Kellerautomat darf den Keller auch unverändert lassen.

A8

Fehlersuche: Lenas Automat

AFB III

Lena hat ihren Entwurf für \(\{w\,c\,w^R\mid w\in\{a,b\}^*\}\) aus A6 notiert (Start z0). Überprüfen Sie ihn — drei Zeilen sind fehlerhaft.

In dieser Lösung stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.

Beim c ändert sich der Keller nicht, darum legen (A,c):A usw. das gelesene Zeichen wieder ab — das ist korrekt. Die drei Fehler: falsche Ablagereihenfolge, ein Vergleich, der nicht vergleicht, und ein Endzustand vor dem Abschluss.

Ansatz: Testen Sie die Zeilen mit abcba und mit Wörtern knapp daneben wie acb oder abc.

Weiter: Welches Zeichen liegt nach (A,b):AB oben? Und was darf in z1 schon akzeptiert werden?

A9

Zwei a für jedes b

AFB III

Ein Kellerautomat soll \(L=\{a^{2n}b^n\mid n\ge 0\}\) erkennen. Jedes a legt ein A ab; für jedes b sollen zwei A entfernt werden. Entwickeln Sie den Automaten, indem Sie die Menüs ausfüllen (Zustände z0 bis z4).

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.

Erstes a in z0:

Ein b in z1 oder z3 entfernt ein A und führt nach z2:

Das zweite A entfernt in z2:

Endzustände:

Das Wort aaab wird

Der Trick ist der ε-Übergang (A,ε):ε: Er entfernt das zweite A, ohne ein Zeichen zu lesen. Danach wartet z3 auf das nächste b oder prüft mit (#,ε):# den leeren Keller. z0 muss Endzustand sein, damit ε (n = 0) akzeptiert wird. Bei aaab bleibt nach dem b und dem ε-Abbau ein A übrig — z3 ist kein Endzustand.

Ansatz: Ein Übergang kann nur ein Kellerzeichen entfernen. Wie entfernen Sie ein zweites, ohne ein weiteres Zeichen zu lesen?

Weiter: Ein ε-Übergang darf den Keller verändern. Ob ε zu L gehört, entscheidet, ob z0 Endzustand ist.

A10

Behauptungen über Kellerautomaten

AFB III Trick

Beurteilen Sie jede Behauptung.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.

Aussage 1 von 5

Die Falle steckt in den ersten beiden Aussagen: Nicht jede Sprache mit Vergleich braucht einen leeren Keller am Ende, und nicht jede Sprache, die nach aⁿbⁿ aussieht, braucht überhaupt einen Keller.

Ansatz: Prüfen Sie bei jeder Aussage ein kleines Beispiel.

Weiter: Endliche Sprachen erkennt immer schon ein DEA.

Übungen: Keller entwickeln

Übungsaufgaben