Rechtslineare Grammatik

Eine rechtslineare Grammatik ist eine spezielle formale Grammatik. Mittels rechtslinearer Grammatiken lassen sich beliebige reguläre Sprachen erzeugen. Ihre Besonderheit besteht in der Einschränkung ihrer Regelmenge: Die Regeln einer rechtslinearen Grammatik G = {Π, Σ, R, S} dürfen nur die Form

A -> aB oder
A -> w

aufweisen, wobei A und B Nichtterminalsymbole aus Π und w ein Wort aus Σ* ist. Dies bedeutet anschaulich, dass ein Wort durch die Anwendung einer Regel nur auf der rechten Seite wachsen kann, indem dort ein Nichtterminalsymbol aus Π angefügt wird.