Push-down Automata - Kellerautomaten

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).


$\displaystyle PDA(x)$ $\textstyle iff$ $\displaystyle x=\langle Q, I, F, \Sigma, Z, \Delta \rangle$ (12.19)
$\displaystyle I,F$ $\textstyle \subseteq$ $\displaystyle Q$ (12.20)
$\displaystyle \Delta$ $\textstyle :$ $\displaystyle Q \times \Sigma^{*} \cup\{\epsilon\} \times Z^{*} \longmapsto Z^{*} \times 2^{Q}$ (12.21)

Mit den Bedeutungen:

Mit den besonderen Annahmen, dass als Input auch eine Zeichenkette $\sigma \in \Sigma^{*}$ auftreten darf. Im übrigen wird hier immer nur die aktuelle Eingabe$\sigma$ notiert, nicht der gesamte Eingabestring $w$, der $\sigma$ 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 $z \in Z^{*}$ 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:


$\displaystyle PDT(x)$ $\textstyle iff$ $\displaystyle x=\langle Q, I, F, \Sigma, Z, \Xi, \Delta, \Lambda \rangle$ (12.22)
$\displaystyle I,F$ $\textstyle \subseteq$ $\displaystyle Q$ (12.23)
$\displaystyle \Delta$ $\textstyle :$ $\displaystyle Q \times \Sigma^{*} \cup\{\epsilon\} \times Z^{*} \longmapsto Z^{*} \times 2^{Q}$ (12.24)
$\displaystyle \Lambda$ $\textstyle :$ $\displaystyle Q \times Z^{*} \longmapsto \Xi$ (12.25)

Abhängig von den neu berechneten Nachfolgezuständen und Stacksymbolen wird die jeweilige Ausgabe berechnet.



Subsections
Gerd Doeben-Henisch 2013-01-16