Prinzipiell gibt es sehr viele Varianten möglicher Automaten. Ein Anhaltspunkt bildet die Chomsky-Hierarchie für formale Sprachen (bzw. Grammatiken bzw. Automaten) (vgl. Hopcroft et. [38]:Kap.9). Nach dieser Hierarchie wäre die nächste größere Klasse an interessanten Automaten die sogenannten Kellerautomaten ('Push-Down Automata'). Gegenüber den endlichen Automaten besitzen sie einen zusätzlichen Kellerspeicher ('Push-Down Store'), der wie ein Stack funktioniert. Mittels einer 'Push'-Operation kann man Elemente 'oben' hinzufügen, und mittels einer 'Put'-Operation kann man das jeweils oberste Element wieder entfernen. Wie bei den endlichen Automaten gibt es auch bei den Kellerautomaten eine deterministische und eine nicht-deterministische Version. Während man aber zeigen kann, dass deterministische DFA und nicht-deterministische endliche Automaten NDFA äquivalent sind, ist dies bei den Kellerautomaten nicht der Fall. Die deterministische Version erkennt nur eine echte Teilmenge der kontextfreien Sprachen ('Context-Free Languages', CFLs), während die nichtdeterministische Version alle CFLs erkennt (siehe Hopcroft et. [38]:107). Das Erkennen bzw. Akteptieren einer Sprache kann man an unterschiedliche Kriterium knüpfen, z.B. an das Kriterium eines leeren Stacks oder an das Kriterium eines Endzustandes (vgl.Hopcroft, [38]:109f) oder an weitere (siehe Autebert et. [5]:140).
Wir werden zwei Versionen von Kellerautomaten unterscheiden: einen normalen Kellerautomaten [PDA] ohne Ausgabe und einen übersetzenden Kellerautomaten (Engl.: 'transducer') mit Ausgabe [PDT] (vgl. Autebert et. 1997 [5]:154ff).
(12.19) | |||
(12.20) | |||
(12.21) |
Mit den Bedeutungen:
Mit den besonderen Annahmen, dass als Input auch eine Zeichenkette auftreten darf. Im übrigen wird hier immer nur die aktuelle Eingabe notiert, nicht der gesamte Eingabestring , der als Teilstring umfasst, wie es sonst in der Literatur üblich ist. Desgleichen wird für den Stack angenommen, dass eine Stack-Zelle einen ganzen String enthalten kann. Dies entspricht dem generalisierten Kellerautomaten (vgl. Moll et. [67]:51).
Für den übersetzenden Kellerautomaten gelten alle Bestimmungen wie für den normalen Kellerautomaten, mit folgenden Besonderheiten:
(12.22) | |||
(12.23) | |||
(12.24) | |||
(12.25) |
Abhängig von den neu berechneten Nachfolgezuständen und Stacksymbolen wird die jeweilige Ausgabe berechnet.