Chomsky-Hierarchie
Chomsky-Hierarchie

==== Definition ====
Typ-3-Grammatiken werden auch ''reguläre Grammatiken'' genannt. Es handelt sich um Typ-2-Grammatiken, bei denen auf der rechten Seite von Produktionen genau ein Terminalsymbol auftreten darf und maximal ein weiteres Nichtterminalsymbol. Die erlaubte Stellung solcher Nichtterminalsymbole muss außerdem über alle Produktionen hinweg einheitlich ''immer vor'' oder ''immer hinter'' dem Terminalsymbol sein, je nachdem spricht man auch genauer von ''linksregulären'' und ''rechtsregulären Grammatiken''. Sie stimmen mit den links- beziehungsweise rechts-linearen Grammatiken überein, wohingegen lineare Grammatiken nicht den regulären Grammatiken entsprechen.
Für ''linksreguläre'' Typ-3-Grammatiken muss also die Bedingung erfüllt sein, dass
Sie dürfen also nur ''links''reguläre Produktionen (Nichtterminalsymbol auf der rechten Seite in ''Vorder''stellung) enthalten.
Üblicherweise gestattet man für reguläre Grammatiken, wie auch für kontextfreie Grammatiken Regeln mit leerer rechter Seite, also
''Rechtsreguläre Grammatiken'' erfüllen dagegen die analoge Bedingung
Diese enthalten also nur ''rechts''reguläre Produktionen (Nichtterminalsymbol auf der rechten Seite allenfalls in ''Hinter''stellung). Diese Bedingung drückt auch schon die Erlaubnis leerer rechter Seiten aus.
Linksreguläre und rechtsreguläre Grammatiken erzeugen genau dieselbe Sprachklasse, es gibt also zu jeder linksregulären Grammatik auch eine rechtsreguläre, die dieselbe Sprache erzeugt, und umgekehrt.
Man beachte, dass beim Auftreten von linksregulären ''und'' rechtsregulären Produktionen in ein und derselben Chomsky-Grammatik diese ''nicht'' regulär ist. Die Grammatiken mit sowohl linksregulären als auch rechtsregulären Produktionen erzeugen nämlich eine echt größere Sprachklasse.
Manche Autoren erlauben in den Definitionen für reguläre / linksreguläre / rechtsreguläre Grammatiken überall dort, wo hier in Produktionen nur ein einzelnes Nichtterminalzeichen stehen darf, auch eine beliebige nichtleere terminale Zeichenkette. An der Erzeugungsmächtigkeit der Klassen ändert sich dadurch nichts.
Man schreibt  für reguläre Grammatiken .