Die Auswahl der durch diese Systeme darstellbaren Sprachen lässt bereits eine ähnliche Mächtigkeit vermuten.
Typische Sprachvertreter sind Klammersprachen, also Sprachen mit geschachtelten Abhängigkeiten zwischen jeweils zwei Konstituenten.
Während beim Automaten der Keller die Möglichkeit bietet, Zwischenergebnisse zu speichern und zu einem späteren Zeitpunkt wieder abzurufen,
gelingt dieser Schritt bei den kontextfreien Grammatiken durch die Wahl der Nichtterminale auf der rechten Seite einer Regel.
Für die 4 Komponenten der Grammatik Entsprechungen unter den 7 Komponenten eines Automaten zu finden, sollte nicht allzu schwer sein.
Die Alphabete können direkt abgeleitet werden, die Übergangsfunktion muss sich aus den Regeln ergeben.
Von der Umsetzung der Regeln hängt auch die Menge der Zustände und damit der Start- und die Endzustände ab.
Etwas schwieriger gestaltet sich der Übergang vom Automaten mit 7 Komponenten zur Grammatik mit 4 Komponenten.
Die Informationen mehrerer Komponenten des Automaten müssen zu komplexen Einheiten der Grammatik zusammen gefasst werden.
Dies betrifft v.a. die Information zu den Zuständen, da diese keine Entsprechung in der Grammatik haben.
So müssen bei der Umwandlung der Übergänge in Regeln die Zustände des Automaten vor und nach der Anwendung dieser Regel mitkodiert werden.
Das genaue Verfahren zur Überführung eines Kellerautomaten in eine Grammatik und der umgekehrte Fall
wird in Abschnitt 4.3.2 beschrieben.
| 
Übersicht: Sprachklassen
