Problem mit regulären Grammatiken
Mit regulären Wörtern lassen sich folgende Wörter konstruieren: mit
Also: , ,
Mit dieser Grammatik kann leider nicht sichergestellt werden, dass ist (gleich viele und ). Nachdem man die generiert hat, weiß man (aus Sicht der Grammatik) nicht mehr wie viele generiert werden müssen. Somit kann man die Regel, dass gleichviele und existieren müssen, nicht festlegen, da diese nicht umsetzbar ist.
Zur besseren Verständnis sind hier die Produktionsregeln der rechtsregulären Grammatik:
Kontextfreie Grammatik als Lösung
Mit kontextfreien Grammatiken kann man diese Regel von gleichvielen und ermöglichen. So sehen die Produktionsregeln der kontextfreien Grammatik aus:
Diese Grammatik ist nicht mehr regulär, da die Syntax der Terminale und Nicht-Terminale der regulären Grammatiken nicht entspricht.