Einstieg

Ein Kellerautomat für die Sprache aⁿbⁿ

Im vorigen Kapitel hast du gesehen, dass ein Akzeptor nicht in der Lage ist, die Sprache aⁿbⁿ zu prüfen. Der Grund dafür war, dass sich der Automat während der Prüfung des Eingabeworts nicht "merken" konnte, wie viele 'a' bereits eingelesen wurden.

Der Kellerautomat als Erweiterung des Akzeptors bekommt nun die Möglichkeit, sich etwas zu speichern. Dies geschieht in seinem Keller, in dem einzelne Zeichen abgelegt werden können. Dieser Kellerspeicher ist wie ein Stapel organisiert: Der Automat kann Symbole oben (nur oben!) hinzufügen und entsprechend auch nur das oberste Zeichen im Keller lesen und entnehmen. In der Abbildung ist also das oberste 'a' zuletzt dazugekommen und kann entsprechend im Moment als einziges Zeichen gelesen und entfernt werden. Achtung: Durch den Lesevorgang wird das Zeichen automatisch aus dem Speicher entfernt!

Durch den Kellerspeicher ergeben sich weitere Unterschiede zum Akzeptor.

• Neben einem Eingabealphabet muss nun auch ein Kelleralphabet definiert werden.
• Jeder Zustandsübergang hängt jetzt nicht nur vom eingelesenen Zeichen des Eingabeworts ab, sondern auch vom obersten Kellersymbol: Das heißt: Wenn im Zustand Z₀ im Eingabewort ein 'a' eingelesen wird und im Keller ein 'S' gelesen wird (der Keller ist leer), dann werden das eingelesene 'S' und ein 'a' im Keller ablegt und der Automat geht in den Zustand Z₁ über.
• Der Keller braucht ein Kellervorbelegungszeichen mit dem der leere Keller markiert ist. In der Abbildung ist das das 'S'.

Nun lässt sich ein Automat konstruieren, der für jedes eingelesene 'a' ein weiteres 'a' im Keller ablegt und danach für jedes eingelesene 'b' ein 'a' aus dem Keller wieder entfernt. Ist am Ende des Eingabeworts der Keller leer (nur noch das 'S' ist im Keller), dann gehört das Eingabewort zur Sprache aⁿbⁿ.

Aufgabe

• Teste den Automaten mit verschiedenen Eingabewörtern und beobachte dabei die Zustandsübergänge und die Kellerbelegung.
• Untersuche dabei die Rolle des letzten Zustandsübergangs mit dem Eingabezeichen ε.
• Beschreibe, in welchen Situationen ein Kellerautomat seine Arbeit beendet.