(nondeterministic pushdown automaton, NPDA), Kellerautomat mit nichtdeterministischer Überführungsrelation.

Zu einem Zustand und einem Eingabezeichen können mehrere Folgekonfigurationen, bestehend aus neuem Zustand und verändertem Kellerinhalt zur Verfügung stehen. Eine Eingabe wird durch einen nichtdeterministischen Kellerautomaten akzeptiert, falls es in jedem Zustand möglich ist, eine der zur Verfügung stehenden Folgekonfigurationen so auszuwählen, daß der Automat sich nach beendeter Eingabe in einer Akzeptierungskonfiguration befindet (üblicherweise also in einem Akzeptierungszustand, evtl. mit einem leeren Kellerspeicher).

Zu einer Sprache gibt es genau dann einen akzeptierenden nichtdeterministischen Kellerautomat, wenn sie eine kontextfreie Grammatik besitzt.