Ein Kellerautomat ist ein endlicher Automat mit einem Keller, auf dessen oberstes Symbol er zugreifen kann. Er ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, Z, F)$. Neu gegenüber dem DFA sind das Kelleralphabet $\Gamma$ und das Kellerstartsymbol $Z$, das zu Beginn als einziges im Keller liegt. Ein Schritt hängt vom Zustand, vom gelesenen Zeichen (oder keinem, $\varepsilon$) und vom obersten Kellersymbol ab. Der Automat wechselt den Zustand und ersetzt das oberste Symbol durch eine Folge von Kellersymbolen. Eine leere Folge entfernt es. Der Keller ist unbegrenzt, aber nur das oberste Symbol ist lesbar. Der Automat akzeptiert ein Wort, wenn er es ganz gelesen hat und dann (gegebenenfalls nach Schritten ohne Lesen) in einem Endzustand steht.

Ein Kellerautomat ist deterministisch, wenn er in jeder Lage höchstens einen möglichen Schritt hat, und nichtdeterministisch, wenn mehrere möglich sind. Ein nichtdeterministischer Automat akzeptiert ein Wort, wenn mindestens ein Weg zum Akzeptieren führt. Er würfelt nicht: Man stellt sich vor, er probiert alle Wege.

Beispiel sind die Palindrome gerader Länge $w w^R$ (w gefolgt von w rückwärts, etwa abba). Der Automat legt die erste Hälfte auf den Keller und vergleicht die zweite beim Abbauen. Wo die Mitte liegt, sieht man dem Wort nicht an. Der nichtdeterministische Automat „rät“ sie. Ein deterministischer Kellerautomat erkennt diese Sprache nicht. Nichtdeterministische Kellerautomaten erkennen genau die kontextfreien Sprachen.

Ein nichtdeterministischer endlicher Automat (NFA) darf zu einem Zustand und Zeichen mehrere oder keinen Folgezustand haben. Er akzeptiert, wenn mindestens ein Weg in einem Endzustand endet. Beim endlichen Automaten bringt das keine neue Kraft: Jeder NFA lässt sich in einen DFA umbauen, der dieselbe Sprache erkennt. Die Potenzmengenkonstruktion geht so: Die Zustände des DFA sind Mengen von NFA-Zuständen, nämlich diejenigen, in denen der NFA nach dem gelesenen Wortanfang sein kann. Start ist $\{q_0\}$. Beim Zeichen x geht eine Menge in die Vereinigung der Folgezustände all ihrer Elemente über. Eine Menge ist Endzustand, wenn sie einen NFA-Endzustand enthält. Hat der NFA n Zustände, hat der DFA höchstens $2^n$.

In einer kontextsensitiven Grammatik darf ein Nichtterminal nur in einem bestimmten Umfeld ersetzt werden: $\alpha A \beta \to \alpha \gamma \beta$ mit nicht leerem $\gamma$. Man kann zeigen, dass dies dieselben Sprachen ergibt wie die Bedingung, dass keine Regel das Wort verkürzt: $|\alpha| \le |\beta|$. Die Chomsky-Hierarchie ordnet vier Klassen, jede liegt in der nächstgrößeren:

Es gilt Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0, und jede Klasse ist echt größer als die vorige. Je größer die Klasse, desto aufwendiger das Wortproblem: Bei Typ 3 und 2 gelingt es mit polynomiellem Aufwand, bei Typ 1 ist es lösbar, aber aufwendig, bei Typ 0 gibt es kein Verfahren, das es für jedes Wort entscheidet.