Zweikellerautomat

Der Begriff Zweikellerautomat (TPDA – engl. Two-stack Push Down Automaton) steht in der Theoretischen Informatik für ein besonderes Automatenmodell. Er hat insbesondere für eine einheitliche Darstellung von Automaten-Charakterisierungen der Sprachenklassen der Chomsky-Hierarchie und anderen Klassen eine besondere Bedeutung erlangt.

So lassen sich die klassischen Begriffe Turingmaschine, Linear beschränkter Automat, Kellerautomat und Endlicher Automat mit speziellen Einschränkungen einheitlich darstellen.

Darüber hinaus gestattet er die Charakterisierung der von Elias Dahlhaus und Manfred Warmuth eingeführten Klasse der wachsend kontextsensitiven Sprachen.

In der Literatur werden zwei verschiedene Modelle betrachtet:

1. Der Zweikellerautomat liest von einem Extra-Eingabeband und kann dabei zwei Kellerspeicher zum Speichern und Lesen nutzen. Als Abkürzung wird hier meist 2-PDA verwendet.
2. Der Zweikellerautomat bekommt seine Eingabe direkt im Keller: Das erste Zeichen steht dabei oben. Dieses Modell ist das jüngere Modell. Als Abkürzung wird hier meist TPDA (engl. Two-PushDown-Automaton) verwendet.

In beiden Fällen ergibt sich, dass der Zweikellerautomat ohne weitere Einschränkung bereits Turing-mächtig ist. Im ersten Fall ist vor allem der Automat mit Realzeiteingabe untersucht worden. Diese Eingabe entspricht dem normalen Kellerautomaten, der nur einen Keller benutzt. Im zweiten Fall wurden verschiedene Einschränkungen definiert, mit denen sich einheitlich verschiedene Sprachklassen charakterisieren lassen.

So werden hier beschränkte und schrumpfende Zweikellerautomaten betrachtet. Weiterhin verbietet man das Schreiben im Eingabekeller, das führt zum normalen Kellerautomaten. Das Verbot des Schreibens in beiden Kellern führt schließlich zum endlichen Automaten.

Definition

Ein Zweikellerautomat ist ein nichtdeterministischer Automat, der während seiner Arbeit auf zwei Kellerspeicher zugreifen kann und seine Eingabe in einem der beiden Kellerspeicher erhält. Mathematisch wird ein solcher Automat ${\displaystyle M}$ beschrieben durch ein Siebentupel ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},\bot ,F,\delta )}$. Im Einzelnen bezeichnet dabei

• ${\displaystyle Q}$ eine endliche Menge: die Zustandsmenge
• ${\displaystyle \Sigma }$ ein (endliches) Alphabet, das Eingabealphabet
• ${\displaystyle \Gamma }$ ein weiteres endliches Alphabet, das Arbeitsalphabet: ${\displaystyle \Sigma \subset \Gamma }$ und ${\displaystyle \Gamma \cap Q=\emptyset }$
• ${\displaystyle q_{0}}$ den Startzustand mit ${\displaystyle q_{0}\in Q}$
• ${\displaystyle F}$ die Endzustände mit ${\displaystyle F\subseteq Q}$
• ${\displaystyle \delta }$ die totale Abbildung von ${\displaystyle Q\times \Gamma \times \Gamma }$ in die endlichen Teilmengen von ${\displaystyle Q\times \Gamma ^{*}\times \Gamma ^{*}}$. Wenn die Menge ${\displaystyle \delta (q,A,B)}$ stets höchstens einelementig ist, heißt der TPDA deterministisch; hier hat sich die Abkürzung DTPDA eingebürgert.

Jede Situation einer Berechnung eines TPDA wird durch seine Konfiguration vollständig beschrieben: Eine Konfiguration kann als Wort über dem Alphabet ${\displaystyle Q\cup \Gamma }$ beschrieben werden; in diesem Fall ist es üblich, die Konfigurationen mit dem folgenden regulären Ausdruck zu beschreiben:

• ${\displaystyle \Gamma ^{*}Q\Gamma ^{*}}$

Hierbei steht der erste Teil des Wortes vor dem Zustandssymbol für den linken Keller und der zweite für den rechten Keller. So liest der Automat im linken Keller von rechts nach links und im rechten von links nach rechts. (Das Zustandssymbol zwischen den beiden Kellerinhalten mag hier intuitiv als Lese-Schreibkopf interpretiert werden.) Daher wird in der Startkonfiguration im linken Keller die Eingabe rückwärts notiert:

• ${\displaystyle \bot w_{n}\dotso w_{1}q\bot }$ ist somit die Startkonfiguration.

Die Überführungsfunktion wird jetzt in folgender Weise angewandt:

• Wenn ${\displaystyle \gamma _{0}AqB\gamma _{1}}$ die aktuelle Konfiguration des TPDA ist und ${\displaystyle \delta (q,A,B)=\{(q_{1},\alpha _{1},\beta _{1}),(q_{2},\alpha _{2},\beta _{2}),\dotsc ,(q_{m},\alpha _{m},\beta _{m})\}}$ gilt, dann stellt für jedes ${\displaystyle i\in \{1,2,\dotsc ,m\}}$ die Konfiguration ${\displaystyle \gamma _{0}\alpha _{i}q_{i}\beta _{i}\gamma _{1}}$ eine mögliche Nachfolgekonfiguration von ${\displaystyle \gamma _{0}AqB\gamma _{1}}$ dar.

Eine Eingabewort ${\displaystyle w\in \Sigma ^{*}}$ wird von einem TPDA akzeptiert, wenn es eine Folge von Konfigurationen gibt, die durch wiederholtes Anwenden der Überführungsfunktion gebildet wird, mit der Eigenschaft: die letzte Konfiguration besteht nur noch aus einem Zeichen, dieses Zeichen ist ein Endzustand aus ${\displaystyle F}$.

Es wird gelegentlich auch gestattet, dass die Keller nicht leer sein müssen. Das TPDA-Modell ist hier ausreichend robust.

Für die Einschränkungen, die üblicherweise betrachtet werden, wird der Begriff der Bewertungsfunktion benötigt: Eine Bewertungsfunktion ist ein Monoid-Homomorphismus vom freien Monoid über ${\displaystyle \Gamma \cup Q}$ in die natürlichen Zahlen (mit 0):

${\displaystyle h\colon ((\Gamma \cup Q)^{*},\circ )\rightarrow (\mathbb {N} ,+)}$,

${\displaystyle h(\varepsilon )=0}$

für alle Wörter ${\displaystyle v,w\in (\Gamma \cup Q)^{*}}$ gilt: ${\displaystyle h(v)+h(w)=h(v\circ w)}$.

Hier bezeichnet ${\displaystyle \varepsilon }$ das leere Wort und ${\displaystyle \circ }$ die Konkatenation.

• Ein TPDA ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},\bot ,F,\delta )}$ heißt schrumpfend, wenn es eine Bewertung ${\displaystyle h}$ gibt, so dass für die Überführungsfunktion ${\displaystyle \delta }$ gilt: Wenn ${\displaystyle (q',\alpha ,\beta )\in \delta (q,A,B)}$ dann ist ${\displaystyle h(q'\circ \alpha \circ \beta )<h(q\circ A\circ B)}$.
• Ein TPDA ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},\bot ,F,\delta )}$ heißt beschränkt, wenn es eine Bewertung ${\displaystyle h}$ gibt, so dass für die Überführungsfunktion ${\displaystyle \delta }$ gilt: Wenn ${\displaystyle (q',\alpha ,\beta )\in \delta (q,A,B)}$ dann ist ${\displaystyle h(q'\circ \alpha \circ \beta )\leq h(q\circ A\circ B)}$.

Charakterisierungen

1. Die rekursiv aufzählbaren Sprachen werden vom Modell TPDA charakterisiert.
2. Die rekursiv aufzählbaren Sprachen werden vom Modell DTPDA charakterisiert.
3. Die kontextsensitiven Sprachen werden von beschränkten TPDA charakterisiert.
4. Die deterministisch kontextsensitiven Sprachen werden von beschränkten DTPDA charakterisiert.
5. Die wachsend kontextsensitiven Sprachen werden von schrumpfenden TPDA charakterisiert.
6. Die Church-Rosser-Sprachen werden von schrumpfenden DTPDA charakterisiert.
7. Die kontextfreien Sprachen werden von TPDA charakterisiert, die nur im rechten Keller schreiben dürfen.
8. Die deterministisch kontextfreien Sprachen werden von DTPDA charakterisiert, die nur im rechten Keller schreiben dürfen.
9. Die regulären Sprachen werden von TPDA charakterisiert, die in ihren Kellern nicht schreiben dürfen.
10. Die regulären Sprachen werden von DTPDA charakterisiert, die in ihren Kellern nicht schreiben dürfen.

Ausblicke

Wenn wir in dem Modell weitere Keller hinzunehmen, so ergibt sich für den schrumpfenden Fall, dass er die nichtdeterministischen Quasi-Realzeit-Sprachen (${\displaystyle \mathbf {Q} }$) akzeptiert.

Literatur

• Gerhard Buntrock, Friedrich Otto: Growing context-sensitive languages and Church-Rosser languages. In Information and Computation, Volume 141, Issue 1,(February 1998), Pages: 1-36
• Elias Dahlhaus, Manfred K Warmuth: Membership for growing context-sensitive grammars is polynomial. In Journal of Computer and System Sciences, Volume 33, Issue 3 (December 1986), Pages: 456-472
• Gundula Niemann, Friedrich Otto: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. In Information and Computation, Volume 197, Issue 1/2 (February 25, 2005/March 15, 2005), Pages: 1-21