Chomsky Hierarchie

Typ 3 - rechtslineare Grammatik

Eigenschaften:
- linke Seite: ein Nichtterminalsymbol
- rechte Seite: genau ein Terminalsymbol oder genau ein Terminalsymbol gefolgt von einem Nichtterminalsymbol
- Erkennung durch endliche Automaten
- Festlegung von regulären Sprachen
Mächtigkeit:
- Alternativen, Gruppierungen und Optionen fehlen in der Grammatik, weshalb die rechtslineare Grammatik umständlich und weniger mächtig ist.
- Produktionsregeln der Form "Nichtterminal = Nichtterminal;" sind nicht erlaubt.
- Reguläre Ausdrücke können sehr gut Muster in Texten erkennen.

Beispiel zur Erfassung aller einstelliger ganzen Zahlen:

RegEx: ^-?[0-9]$

Grammatik:

G = {V, Σ, P, S}
V = {Zahl, ZahlPos}
Σ = {'', '-', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}
P = {Zahl = '-' ZahlPos;	Zahl = '' ZahlPos;
    ZahlPos = '0';		ZahlPos = '1';
    ZahlPos = '2';		ZahlPos = '3';
    ZahlPos = '4';		ZahlPos = '5';
    ZahlPos = '6';		ZahlPos = '7';
    ZahlPos = '8';		ZahlPos = '9'}
S = {Zahl}

Automat:

Der Automat geht je nach Vorzeichen der einstelligen Zahl in den entsprechenden Zustand über und landet nach Erkennen der Ziffern 0 - 9 im Endzustand.

Weiter