Zweikellerautomat

Grundidee und Bedeutung

Ein Zweikellerautomat (TPDA, englisch Two-stack Push Down Automaton) ist ein Automatenmodell der Theoretischen Informatik. Er besitzt zwei Kellerspeicher und ist ohne zusätzliche Einschränkungen bereits Turing-mächtig: Er kann also dieselben Sprachen erkennen wie eine Turingmaschine. Seine besondere Bedeutung liegt darin, dass sich mit ihm verschiedene Automatenmodelle und Sprachklassen der Chomsky-Hierarchie einheitlich darstellen lassen. Dazu gehören Turingmaschinen, linear beschränkte Automaten, Kellerautomaten und endliche Automaten.

In der Literatur gibt es zwei Modelle: Beim 2-PDA wird die Eingabe von einem zusätzlichen Eingabeband gelesen; beide Keller dienen zum Speichern und Lesen. Beim jüngeren TPDA-Modell liegt die Eingabe direkt in einem Keller, wobei das erste Zeichen oben steht. Beim 2-PDA wurde besonders die Realzeiteingabe untersucht; sie entspricht der Eingabeweise eines gewöhnlichen Kellerautomaten mit einem Keller.

Durch Einschränkungen entstehen weniger mächtige Automaten: Schrumpfende und beschränkte Zweikellerautomaten werden über eine Bewertungsfunktion festgelegt. Darf nicht in den Eingabekeller geschrieben werden, erhält man den normalen Kellerautomaten. Ist Schreiben in beiden Kellern verboten, entsteht ein endlicher Automat.

Aufbau und Arbeitsweise

Ein TPDA ist ein nichtdeterministischer Automat mit dem Siebentupel M=(Q,Σ,Γ,q₀,⊥,F,δ). Dabei ist Q eine endliche Zustandsmenge, Σ ein endliches Eingabealphabet und Γ ein endliches Arbeitsalphabet. Es gilt Σ⊂Γ und Γ∩Q=∅. Der Startzustand q₀ liegt in Q, und F⊆Q ist die Menge der Endzustände.

Die Überführungsfunktion δ ordnet jedem Element aus Q×Γ×Γ eine endliche Teilmenge von Q×Γ*×Γ* zu. Sie ist total. Hat jede Menge δ(q,A,B) höchstens ein Element, heißt der Automat deterministisch; dafür wird DTPDA verwendet.

Eine Konfiguration hat die Form ΓQΓ. Der Teil links vom Zustandssymbol ist der linke Keller, der Teil rechts davon der rechte Keller. Im linken Keller wird von rechts nach links gelesen, im rechten von links nach rechts. Für ein Eingabewort w steht die Eingabe deshalb rückwärts im linken Keller; die Startkonfiguration lautet ⊥wₙ…w₁q⊥.

Ist γ₀AqBγ₁ eine Konfiguration und enthält δ(q,A,B) etwa (qᵢ,αᵢ,βᵢ), dann ist γ₀αᵢqᵢβᵢγ₁ eine mögliche Nachfolgekonfiguration. Wegen der Nichtdeterminismus können mehrere solcher Folgen möglich sein. Ein Wort w∈Σ* wird akzeptiert, wenn eine durch wiederholte Übergänge erreichbare letzte Konfiguration nur aus einem Zeichen besteht und dieses ein Endzustand aus F ist. Gelegentlich werden auch nichtleere Keller bei der Akzeptanz zugelassen; das Modell gilt dennoch als ausreichend robust.

Beschränkungen und zugehörige Sprachklassen

Für beschränkte und schrumpfende TPDA wird eine Bewertungsfunktion h verwendet. Sie ist ein Monoid-Homomorphismus h:((Γ∪Q),∘)→(ℕ,+), mit h(ε)=0 und h(v)+h(w)=h(v∘w) für alle Wörter v,w∈(Γ∪Q). Dabei ist ε das leere Wort und ∘ die Konkatenation.

Ein TPDA heißt schrumpfend, wenn für jeden Übergang (q',α,β)∈δ(q,A,B) gilt: h(q'∘α∘β)<h(q∘A∘B). Er heißt beschränkt, wenn entsprechend h(q'∘α∘β)≤h(q∘A∘B) gilt.

Die Sprachklassen werden folgendermaßen charakterisiert:

• TPDA erkennen die rekursiv aufzählbaren Sprachen; DTPDA erkennen die rekursiven Sprachen.
• Beschränkte TPDA charakterisieren kontextsensitive Sprachen, beschränkte DTPDA deterministisch kontextsensitive Sprachen.
• Schrumpfende TPDA charakterisieren wachsend kontextsensitive Sprachen; schrumpfende DTPDA charakterisieren Church-Rosser-Sprachen.
• Schreiben TPDA nur im rechten Keller, charakterisieren sie kontextfreie Sprachen; für DTPDA gilt dies für deterministisch kontextfreie Sprachen.
• Dürfen TPDA beziehungsweise DTPDA in keinen Keller schreiben, charakterisieren beide reguläre Sprachen.

Erweiterung auf weitere Keller

Werden dem Modell weitere Keller hinzugefügt, so akzeptiert der schrumpfende Fall die nichtdeterministischen Quasi-Realzeit-Sprachen (Q).