Reguläre Grammatik
Eine reguläre Grammatik ist eine besonders einfache kontextfreie Grammatik.
Eine reguläre Grammatik erzeugt eine Sprache, die von einem endlichen Automaten akzeptiert wird. Umgekehrt kann man jeden endlichen Automaten in eine äquivalente reguläre Grammatik umwandeln. Man unterscheidet linksreguläre und rechtsreguläre Grammatiken.
Formal bestehen die Produktionen einer rechtsregulären Grammatik aus
- genau einem Nichtterminal auf der linken Seite
sowie
- einem Nichtterminal und einem Terminal tN (das Nichtterminal N steht also rechts vom Terminal t)
- einem Terminal t oder
- dem leeren Wort
auf der rechten Seite.
Eine linksreguläre Grammatik ist genau so aufgebaut, allerdings steht das Nichtterminal immer links vom Terminal: N ⟹ Nt.
Laut Wikipedia ist die rechtsreguläre Form eine Art Standardform der regulären Grammatik, wenn also keine weiteren Informationen vorliegen, kann man davon ausgehen, dass eine rechtsreguläre Grammatik gemeint ist.
Abituraufgaben
In den Abituraufgaben des Landes NRW spielen reguläre Grammatiken eine weit wichtigere Rolle als kontextfreie Grammatiken. Häufig beginnt die Abituraufgabe mit einem determinierten endlichen Automaten, der zunächst analysiert, getestet und erweitert werden soll. Im zweiten Teil kommt dann aber regelmäßig eine reguläre Grammatik, welche die gleiche Sprache hat wie der DEA oder die Sprache des DEA um weitere Möglichkeiten erweitert. Es kommt auch gelegentlich vor, dass Sie eine eigene reguläre Grammatik nach Vorgaben entwickeln sollen oder eine vorgegebene reguläre Grammatik analysieren müssen.
In den folgenden Abituraufgaben spielen reguläre Grammatiken eine entscheidende Rolle:
Weiterführende Links
"Reguläre Grammatik" in der Wikipedia
"Reguläre Grammatik" auf Studyflix.de
"Reguläre Grammatik" auf YouTube.com (Suchanfrage)