Kellerautomat

Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton) ist ein Automat im Sinne der Theoretischen Informatik. Es handelt sich also um ein rein theoretisches Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen – ob es tatsächlich möglich oder sinnvoll wäre, eine solche Maschine zu bauen, ist dabei zunächst unerheblich.

Bei einem Kellerautomaten handelt es sich um einen endlichen Automaten, der um einen Kellerspeicher erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine.

Funktionsweise

Kellerautomat.png Die zugrundeliegende Idee ist die folgende: Die Eingabe wird zeichenweise von links nach rechts verarbeitet. Wenn es möglich ist, wird das Eingabezeichen sofort verarbeitet, wenn nicht, wird es in den Kellerspeicher gelegt und die Bearbeitung sobald wie möglich nachgeholt. Die möglichen Aktionen des Automaten hängen dabei, wie beim endlichen Automaten, vom momentan verarbeiteten Eingabezeichen, vom momentanen Zustand des Automaten und (das ist die Erweiterung gegenüber dem endlichen Automaten) zusätzlich vom Kellerinhalt ab, wobei immer nur das oberste Zeichen des Kellers relevant ist. In jedem Verarbeitungsschritt (das Lesen eines Zeichens und die damit zusammenhängenden Operationen) kann sich der Zustand des Automaten und der Kellerinhalt ändern.

Beispiel

Um das Prinzip eines Kellerautomaten zu verdeutlichen, wird häufig die syntaktische Untersuchung geklammerter Ausdrücke herangezogen. Beispielsweise muss in einem Ausdruck einer bestimmten Sprache zu jeder öffnenden Klammer auch eine schließende Klammer existieren:

Beispiel: { .... { ...... } .... }

Der Automat beginnt in einem Startzustand z0; im Keller befindet sich ein Zeichen, welches das Ende kennzeichnet (#). Bei der Abarbeitung des Ausdrucks bewegt sich der Lesekopf Zeichen für Zeichen weiter. Stößt er dabei auf eine öffnende Klammer, so wird diese in den Keller geschrieben. Tritt in der weiteren Abarbeitung eine schließende Klammer auf, so wird das oberste Klammer-Auf-Zeichen im Keller wieder gelöscht. Der Ausdruck ist dann erfolgreich abgearbeitet, wenn der Lesekopf das Ende des Eingabebandes erreicht hat und sich im Keller ausschließlich das Zeichen # befindet. Befände sich hingegen noch eine geöffnete Klammer nach der Ausdrucksabarbeitung im Keller, so würde dies bedeuten, dass eine schließende Klammer fehlt und ein syntaktischer Fehler vorliegt.

Formale Definition

Ein nichtdeterministischer Kellerautomat wird definiert als ein 7-Tupel $M=(Z,\Sigma,\Gamma,\delta,z_0,\#,F)$ , wobei

$Z\,$ eine endliche Menge von Zuständen,
$\Sigma\,$ ein Eingabealphabet,
$\Gamma\,$ das Kelleralphabet,
$\delta\,$ die Zustandsübergangsrelation, $\delta \subseteq (Z \times (\Sigma \cup \{ \epsilon \} ) \times \Gamma) \rightarrow (Z \times \Gamma^{*})$ ,
$z_0\in Z$ der Startzustand,
$\# \in \Gamma$ das Anfangssymbol im Keller und
$F \subseteq Z$ eine Menge von finalen Zuständen

ist.

Wenn die Übergangsrelation die Eigenschaft $\forall z \in Z, \forall a \in \Sigma, \forall A \in \Gamma, \left|\delta(z,a,A)\right| + \left|\delta(z,\epsilon,A)\right|\leq 1$ erfüllt, spricht man von einem deterministischen Kellerautomaten. Zu einer festen Eingabe gibt es dann höchstens eine Zustandsübergangsabfolge, Mehrdeutigkeiten können also nicht auftreten.

Anmerkungen

Für einen nichtdeterministischen Kellerautomaten ist es möglich, in der Definition auf die Menge der finalen Zustände zu verzichten. Stattdessen definiert man, dass der nichtdeterministische Kellerautomat seine Eingabe akzeptiert, wenn es einen Berechnungspfad gibt, bei dem nach dem Einlesen der Eingabe der Keller das leere Wort enthält. Die beiden Definitionen sind hinsichtlich der akzeptierten Sprachen äquivalent. Für einen deterministischen Kellerautomaten ist diese Aussage im Allgemeinen jedoch falsch.
Das heißt, dass ein deterministischer Kellerautomat terminieren kann, sobald ein finaler Zustand erreicht wurde, aber nicht sofort terminieren muss. Dabei spielt der Keller keine Rolle. Er akzeptiert ein Wort, wenn er terminiert und das Eingabewort leer ist. Ist es nicht leer, und es sind keine Regeln mehr anwendbar, wurde es nicht akzeptiert.
Für einen solchen bei leerem Keller akzeptierenden nichtdeterministischen Kellerautomaten ist es möglich, einen äquivalenten Kellerautomaten mit einem einzigen Zustand zu konstruieren, indem die Zustände des alten Kellerautomaten vollständig im Keller des neuen Kellerautomaten simuliert werden. In der Definition eines nichtdeterministischen Kellerautomaten kann also neben der Menge der finalen Zustände auch zusätzlich auf den Startzustand und die Zustandsmenge verzichtet werden.
Es kann in der Definition eines nichtdeterministischen Kellerautomaten auf $\epsilon$ -Übergänge verzichtet werden. Die Zustandsübergangsrelation ist dann eine endliche Teilmenge von $(Z \times \Sigma \times \Gamma) \rightarrow (Z \times \Gamma^{*})$ . Mit Hilfe der Greibach-Normalform zeigt man, dass zu jedem nichtdeterministischen Kellerautomaten ein äquivalenter nichtdeterministischer Kellerautomat ohne $\epsilon$ -Übergänge existiert.

Beispiel 1

Der folgende Kellerautomat M erkennt die kontextfreie Sprache $L = \{a^n\,b^n\,|\,n > 0\}$ :

M = (Z, Σ, Γ, δ, z0, #, F)
* Z = {z0, z1, z2} * Σ = {a, b} * Γ = {#, a} * F = {z2}
δ: Zustand Eingabe Keller -> Zustand Keller z0 a # z0 a# (1) z0 a a z0 aa (2) z0 b a z1 ε (3) z1 b a z1 ε (4) z1 ε # z2 ε (5)

Bemerkung: Bei einer Eingabe wird immer das oberste Kellerelement gelöscht.

(1), (2) Im Zustand z0 werden die führenden a-Zeichen der Eingabe gelesen und im Keller gespeichert.
(3) Bei Eingabe b und einem a als oberstes Kellerelement erfolgt ein Zustandswechsel von z0 zu z1. Abgleich im Keller erfolgt.
(4) Alle weiteren b-Zeichen werden gelesen, sofern noch genügend a-Zeichen im Keller gespeichert sind. Der Keller wird abgeglichen.
(5) Wenn sich nur noch das Anfangssymbol $\#\,$ im Keller befindet und keine Eingabe erfolgt, geht der Kellerautomat in den Endzustand z2 über und akzeptiert damit die Eingabe.

Erhält der Kellerautomat beispielsweise die Eingabe aabb, so durchläuft er folgende Zustände, wobei ein Tripel $(z,\,a ,\,b)$ die Konfiguration eines Kellerautomaten im

Zustand $z \in Z$ ,
bei dem noch zu lesenden Wort $a \in \Sigma^*$ und
aktuellem Kellerinhalt $b \in \Gamma^*$ beschreibt:

(die hochgestellte Nummer am Pfeil kennzeichnet die benutzte Zustandsübergangsrelation)

(z0, aabb, #) →⁽¹⁾ (z0, abb,a#) →⁽²⁾ (z0, bb, aa#) →⁽³⁾ (z1, b, a#) →⁽⁴⁾ (z1, ε, #) →⁽⁵⁾ (z2, ε, ε)

Dieser Kellerautomat M kann grundsätzlich, wenn er begonnen hat den Keller zu lesen, nicht wieder schreiben. Daher ist die erkannte Sprache insbesondere auch eine lineare Sprache.

Beispiel 2

Der folgende nichtdeterministische Kellerautomat M erkennt die kontextfreie Sprache: $L = \{w\,sp(w)\,|\,w \in (a\,b)^*\}$
( $sp(w)\,$ sei hier das gespiegelte Wort zu $w\,$ )

M = (Z, Σ, Γ, δ, z0, #, F)
* Z = {z0, z1, z2} * Σ = {a, b} * Γ = {#, a, b} * F = {z2} δ: Zustand Eingabe Keller → Zustand Keller z0 ε # z2 ε (1) leeres Wort z0 a # z0 a# (2) z0 b # z0 b# (3) z0 a a z0 aa (4) z0 a a z1 ε (5) Mitte des Wortes erreicht z0 b b z0 bb (6) z0 b b z1 ε (7) Mitte des Wortes erreicht z0 a b z0 ab (8) z0 b a z0 ba (9) z1 a a z1 ε (10) z1 b b z1 ε (11) z1 ε # z2 ε (12) geht in Endzustand
Wenn K beispielsweise die Eingabe aabbbbaa erhält, durchläuft er folgende Zustände:
(die hochgestellte Nummer am Pfeil kennzeichnet die benutzte Zustandsübergangsrelation)

(z0, aabbbbaa, #) →⁽²⁾ (z0, abbbbaa, a#) →⁽⁴⁾ (z0, bbbbaa, aa#) →⁽⁹⁾ (z0, bbbaa, baa#) →⁽⁶⁾ (z0, bbaa, bbaa#) →⁽⁷⁾ (z1, baa, baa#) →⁽¹¹⁾ (z1, aa, aa#) →⁽¹⁰⁾ (z1, a, a#) →⁽¹⁰⁾ (z1, ε, #) →⁽¹²⁾ (z2, ε, ε)

L kann nicht durch einen deterministischen Kellerautomaten erkannt werden, da der Kellerautomat nicht erkennen kann, wann die Mitte des Wortes erreicht ist. Durch die Zustandsübergangsrelation (5)/(6) und (7)/(8) treten Mehrdeutigkeiten auf.

Kellerautomaten und formale Sprachen

Ein (Keller-)Automat liest eine aus einzelnen Zeichen bestehende Eingabe und akzeptiert (oder erkennt) diese – oder auch nicht. Die Menge der akzeptierten Eingaben bildet die durch den Automaten definierte Sprache.

Der nichtdeterministische Kellerautomat erkennt genau die kontextfreien Sprachen (Typ 2, vgl. Chomsky-Hierarchie). Sie sind damit mächtiger als endliche Automaten, welche genau die regulären Sprachen (Typ 3) erkennen, aber weniger mächtig als Turingmaschinen, welche genau die rekursiv aufzählbaren Sprachen (Typ 0) erkennen. Ein deterministischer Kellerautomat (DPDA) erkennt die deterministisch-kontextfreien Sprachen, also nur eine echte Teilmenge der kontextfreien Sprachen.

Die Bedeutung des Kellerautomaten ergibt sich also daraus, dass sich Erkenntnisse über diesen (beispielsweise Äquivalenz mit anderen Automaten) auf die kontextfreien Sprachen übertragen lassen (und umgekehrt).

Anwendungen in Technik und Wissenschaft

Die Gleitkommaeinheit (engl. Floating Point Unit, FPU) des in heutigen PCs verwendeten Prozessors (Intel 32-Bit x86-Architektur) ist ursprünglich als Kellerautomat (engl. Stack Machine) realisiert. Ihr Kellerspeicher besitzt eine Tiefe von 8 Speicherplätzen (für jeweils einen 80-Bit-Fließkommawert). Aufgrund der Einschränkungen durch das Kellermodell ist tendenziell jedoch erkennbar, dass künftig auch im PC wie in anderen Rechnerarchitekturen üblich vorwiegend Verarbeitungseinheiten mit direkt adressierbaren Registern verwendet werden (SIMD-Erweiterung).

Siehe auch

Chomsky-Hierarchie
Umgekehrte Polnische Notation (Postfix-Notation)

Automatentheorie | Formale Sprachen

Gourt Home::Gourt :: Kellerautomat