3. Kontextfreie Sprachen

Wir haben im letzten Kapitel gesehen, dass bereits sehr einfache Sprachen wie L = {aⁿbⁿ∣n ≥ 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 können problemlos einen Algorithmus angeben, der das Wortproblem für L löst. Dafür müssen wir nur alle as am Anfang zusammenzählen und dann kontrollieren, ob nur bs folgen, und zwar genauso viele, wie wir as gezählt hatten. Diesen Algorithmus kann man nicht durch einen endlichen Automaten ausführen lassen, da in diesem Modell nicht unbeschränkt „gezählt“ werden kann. Wir werden in diesem Kapitel mit dem Kellerautomaten ein Berechnungsmodell vorstellen, in welchem wir den beschriebenen Algorithmus ausführen können. Unser Ziel ist es zudem, ein Modell zu finden, das möglichst nahe am endlichen Automaten bleibt. 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). Das Modell des Kellerautomaten ist ein nichtdeterministisches Modell. Daraus lässt sich aber auch eine deterministische Version ableiten. Wie wir sehen werden, sind diese Modell (anders als bei den endlichen Automaten) nicht gleich mächtig.