Reguläre Grammatik

Formale Grammatiken vom Typ 3 der Chomsky-Hierarchie werden reguläre Grammatiken genannt. Die durch sie spezifizierten formalen Sprachen werden als reguläre Sprachen bezeichnet.

Kommentare

Es gibt rechtsreguläre und linksreguläre Grammatiken. Auf der rechten Seite einer Produktion <math>w_2</math> darf für rechtsreguläre Sprachen nur ein Terminalsymbol oder ein Terminalsymbol gefolgt von einem Nichtterminalsymbol sein. Für linksreguläre Sprachen ist es genau umgekehrt, die rechte Seite <math>w_2</math> darf nur ein Terminalsymbol oder ein Nichtterminal- gefolgt von einem Terminalsymbol sein darf.

Reguläre Grammatiken gelten - was die Beschreibung natürlicher Sprachen betrifft – als nicht beschreibungsadäquat, da es in natürlichen Sprachen syntaktische Phänomene gibt, die sich mit Regeln dieser Form nicht erfassen lassen (z.B. nicht-lokale Abhängigkeiten, Einbettungen beliebiger Tiefe).

REF	This article has no reference(s) or source(s). Please remove this block only when the problem is solved.