Reguläre Grammatik
aus Wikipedia, der freien Enzyklopädie
Die regulären Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ-3-Grammatiken der Chomsky-Hierarchie.
[Bearbeiten] Definition
Eine reguläre Grammatik G = (N,Σ,P,S) ist eine kontextfreie Grammatik, deren Produktionsregeln weiter eingeschränkt sind. Es gibt rechtsreguläre als auch linksreguläre Grammatiken, wobei normalerweise mit regulär die rechtsregulären Grammatiken gemeint sind.
Die rechte Seite einer Produktion w2 darf für rechtsreguläre Sprachen nur ein Terminalsymbol oder ein Terminal gefolgt von einem Nichtterminal sein. D.h. ein Wort einer solchen regulären Sprache entsteht durch Anfügen von Terminalsymbolen auf der rechten Seite. Entsprechend gilt für linksreguläre Sprachen, dass die rechte Seite w2 nur ein Terminal oder ein Nichtterminal gefolgt von einem Terminal sein darf..
Für die Produktionen P einer rechtsregulären Grammatik 
gilt
Gültige Produktionen einer regulären Grammatik wären beispielsweise:
[Bearbeiten] Von G erzeugte Sprache
Die regulären Grammatiken erzeugen die regulären Sprachen. Das heißt jeder regulären Grammatik lässt sich eine reguläre Sprache und umgekehrt zuordnen. Diese Sprachen sind abgeschlossen unter Komplementbildung, Konkatenation, Schnitt, Vereinigung und Kleenescher Abschluss. Die regulären Sprachen sind die Sprachen, die von einem endlichen Automaten (deterministisch oder nichtdeterministisch) erkannt werden können.
