Kleines Nachschlagewerk Informatik
Kellerautomaten
Worum geht es?
Ein Automat soll anzeigen (durch Betreten eines akzeptierten Endzustandes), ob ein Raum leer ist. Es gibt die Zeichen e (Person tritt ein) und a (Person verlässt den Raum).

Möchte man dies mit einem endlichen Automaten realisieren, kommt man schnell dazu, Zustände wie "Zwei Personen im Raum", "Drei Personen im Raum" etc. zu generieren. Ist die Zahl der möglichen Personen aber beliebig hoch, lässt sich dieses Problem nicht mehr mit einem endlichen Automaten realisieren. Man braucht etwas, das zählen kann.
Der Kellerspeicher
Der Kellerautomat braucht einen einfachen Speicher. Wenn man sich vorstellt, dass der Speicher aus Zellen, die sich Zeichen merken können, besteht, so ergeben sich zwei Aufgaben: Man muss die aktuelle Zelle auswählen und man muss diese beschreiben bzw. auslesen.

Der Speicher soll so einfach wie möglich sein. Um dies zu erreichen, lässt man die Adressierung beliebiger Zellen weg. Man kann nur etwas reinpacken bzw. herausnehmen. Man kann sich dies wie einen Bücherstapel vorstellen. Man kann Bücher hinlegen und wegnehmen.

Der Nachteil besteht darin, dass man immer nur das Zeichen lesen kann, welches man als letztes hingelegt hat. Das mag ungewöhnlich erscheinen, aber der Speicher bleibt einfach und er lässt sich in der Tat verwenden.

Einen leeren Keller erkennt man, wenn man das Endezeichen erreicht. Dies wird verschieden bezeichnet, der Simulator JFlap verwendet Z.
Der Kellerautomat
Basis für den Kellerautomaten ist der endliche Automat, der um einen Kellerspeicher und ein Kelleralphabet erweitert wird. Das Kelleralphabet beinhaltet alle Zeichen, die im Keller gespeichert werden können.

Die Überführungsfunktion sieht hier anders aus. Es wird ein Eingabezeichen UND ein Kellerzeichen gelesen. Davon abhängig ergibt sich ein Zustandswechsel. Dabei kann wieder ein Kellerzeichen gelesen werden. Achtung, Kellerautomaten verwenden das originale Stack-Prinzip: Wird ein Zeichen gelesen, so wird es auch gelöscht. Eine Funktion wie top gibt es nicht.
Beispiel - Einlasszähler
Das Eingabealphabet besteht aus e und a, das Kelleralphabet nur aus p. Für jede Person, die den Raum betritt, kommt ein Zeichen auf den Keller. Verlässt eine Person den Raum, verschwindet ein p. Das Ende des Kellers ist hier (in JFlap) Z.

alter ZustandEingabeKellerzeichenneuer ZustandKellerausgabe
leereZvollpZ
leera-Fehler-
vollepvollpp
vollapvoll-
vollaZleerZ