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