Reguläre Grammatik

Eine reguläre Grammatik erzeugt eine reguläre Sprache. Die Menge der Wörter, die durch eine reguläre Grammatik erzeugt werden können, stellt eine Teilmenge der Wörter dar, die durch eine kontextfreie Grammatik erzeugt werden können. Eine reguläre Grammatik unterliegt also stärkeren Einschränkungen als einer kontextfreien Grammatik, und laut der Chomsky-Hierachie deshalb insbesondere auch stärkeren Einschränkungen als einer kontextsensitiven Grammatik oder generell einer formalen Grammatik.

Die Produktionsregeln einer regulären Grammatik lassen auf der linken Seite jeder Produktionsregel nur ein einzelnes Nichtterminalssymbol zu – genauer besteht die linke Seite jeder Produktionsregel einer regulären Grammatik aus genau einem Nonterminalsymbol. Daraus folgt, dass eine reguläre Grammatik insbesondere auch kontextfrei ist. Die Einschränkung, die für eine reguläre Grammatik hinzukommt, ist, dass die rechte Seite jeder Produktionsregel höchstens aus einem Terminalsymbol und einem Nichtterminalssymbol bestehen darf. Gibt es Produktionsregeln deren rechte Seite dieses Maximum an zwei Symbolen besitzen, so müssen die Terminalsymbole und Nichtterminalsymbole der rechten Seiten dieser Produktionsregeln alle in der selben Reihenfolge stehen. Dies führt zu der Unterscheidung in

  • linksreguläre Grammatiken
  • rechtsreguläre Grammatiken

Linksreguläre Grammatik

Für eine linksreguläre Grammatik gilt, dass eine Produktionsregel, deren rechte Seite das Maximum von zwei Symbolen erfüllt, genauer das Maximum an genau einem Terminal- und genau einem Nichtterminalsymbol erfüllt, jeweils aus einem Nonterminalsymbol gefolgt von einem Terminalsymbol besteht.

Rechtsreguläre Grammatik

Für eine rechtsreguläre Grammatik gilt, dass eine Produktionsregel, deren rechte Seite das Maximum von zwei Symbolen erfüllt, genauer das Maximum an genau einem Terminal- und genau einem Nichtterminalsymbol erfüllt, jeweils aus einem Terminalsymbol gefolgt von einem Nichtterminalsymbol besteht.