Kontextfreie Grammatik
Eine kontextfreie Grammatik ist eine Grammatik, bei der alle Produktionen die Form N ⟹ S* haben. Dabei ist N ein Nichtterminal und S* eine Kette aus Terminalen und Nichtterminalen.
Beispiel:
EXPR ⟹ EXPR + EXPR
EXPR ⟹ EXPR * EXPR
EXPR ⟹ ( EXPR)
EXPR ⟹ num
Diese einfache Grammatik (bzw. die Produktionsregeln; vom Rest der Grammatik sieht man hier nichts) erzeugt arithmetische Ausdrücke mit beliebig vielen Klammerebenen, beispielsweise
(num * ((num + num) + num)) + num
Einen determinierten endlichen Automaten, der die gleiche Sprache hat wie diese Grammatik, kann man nicht konstruieren, weil DEAs nicht zählen können. Für die Überprüfung der Zahl der Klammerebenen müsste der Automat aber zählen können. Die kontextfreie Grammatik hat damit kein Problem.