Pushdownautomat, ein Automat, der neben der Zustandsmenge mit einem unbeschränkten Speicherbereich, dem Keller, ausgestattet ist, der harten, einem Stapel nachempfundenen Zugriffsbeschränkungen ausgesetzt ist.

So können beliebig neue Daten gespeichert werden, aber nur die jeweils zuletzt gespeicherten Daten gelesen, überschrieben bzw. gelöscht werden. Zum Zugriff auf früher gespeicherte (im Stapel unten liegende) Daten müssen zunächst alle später gespeicherten (darüberliegenden) Daten gelöscht werden.

Formal wird ein Kellerautomat durch die gleichen Bestimmungsstücke wie ein Automat beschrieben. Dabei hängen Zustandsüberführungsfunktion und Ausgabefunktion nun zusätzlich vom obersten Kellersymbol (einem Zeichen aus einem anzugebenden Kelleralphabet K, bzw. einem Sonderzeichen, das einen leeren Keller signalisiert) ab. Außerdem liefert die Zustandsüberführungsfunktion zusätzlich eine neu im Keller zu speichernde Zeichenreihe (ein Wort über K). Eine Konfiguration eines Kellerautomaten besteht aus einem (dem aktuellen) Zustand und einem Wort über K, der aktuellen Kellerbelegung. Die Anfangskonfiguration wird vom Anfangszustand und dem leeren Wort gebildet. Eine Folgekonfiguration einer Konfiguration [𝓏,wa] (bzw. [𝓏, ε]) bei Eingabe des Zeichens x besteht aus einem Folgezustand 𝓏^′ von 𝓏 und dem Wort 𝓌𝓌^′ (bzw. 𝓌^′), wobei 𝓏^′ und 𝓌^′ durch die Überführungsfunktion an der Stelle 𝓏, x und a (bzw. dem Sonderzeichen) gegeben sind. Sind 𝓏^′ und 𝓌^′ durch 𝓏, x und a eindeutig bestimmt, handelt es sich um einen deterministischen, anderenfalls um einen nichtdeterministischen Kellerautomaten. Als Akzeptierungskriterien für die Definition formaler Sprachen auf der Basis von Kellerautomaten werden das Erreichen ausgewiesener Endzustände oder das Erreichen eines leeren Kellerspeichers verwendet. Die Wahl des Akzeptierungskriteriums hat aber keine Konsequenzen für die Leistungsfähigkeit.

Kellerautomaten bilden die formale Grundlage für die Analyse kontextfreier Sprachen (Grammatik).