Wir haben bereits gesehen, dass sehr einfache Sprachen wie \(L=\{a^nb^n \mid n\ge 0\}\) nicht regulär sind. Das mag nicht überraschend sein, da wir mit begrenztem Speicher nicht das Wortproblem für diese Sprache entscheiden können. Dennoch steht wohl außer Frage, dass es sich bei L um keine komplizierte Sprache handelt. Wir werden im Folgenden ein Berechnungsmodell (Kellerautomat) vorstellen, in welchem wir das Wortproblem für L lösen können. Die Sprachen, die ein Kellerautomat erkennt, nennen wir kontextfrei. Diese Sprachklasse ist eine sehr wichtige Sprachklasse mit vielen Anwendungen in der Informatik (zum Beispiel beim Entwurf von Programmiersprachen). Wir gehen auf alternative Methoden zur Beschreibung kontextfreier Sprachen ein und diskutieren die Grenzen dieses Modells.