Theory: FSA |
Reguläre Sprachen |
Die reguläre Sprache vom Sprachtyp 3 in der Chomsky-Hierarchie sind jene Sprachen, die keine Abhängigkeiten zwischen den einzelnen Satzelementen besitzen. Formal lässt sich eine reguläre Sprache durch den Ausdruck an bo cp beschreiben. Die einzelnen Komponenten lassen sich beliebig und unabhängig von einander wiederholen. Die reguläre Sprache ist entsprechend primitiv und lässt keine komplexeren Beschreibungen zu.
Definition der regulären
Grammatik (nach [Hes97], S.120):
In einer
Grammatik für regulären Sprachen darf ein Nonterminal nur ersetzt
werden durch
a) ein einziges Terminal oder
b) ein Paar aus Terminal und Nonterminal
Beispiel einer regulären Grammatik, anhand des Automaten mit Fangzustand.
A -> aB
A -> a
B -> bC
C -> bB
C -> aC
C -> b
Um den Endzustand zu erreichen,
müssen entweder das Nichtterminal A oder C mit a bzw. b ersetzt werden.
A entspricht dabei dem Anfangszustand q0, C dem Zustand q2 im Zustandsdiagramm.
Da der Endzustand q1 dazwischen liegt gibt es zwei Grammatikregeln, welche
die Uebergangsfunktion zum Endzustand beschreiben.
Es werden zwei Subtypen
von regulären Sprachen unterschieden:
rechtslineare und linkslineare
reguläre Sprachen. Der Unterschied betrifft die Abarbeitungsfolge
auf der rechten Seite der Grammatikregel, ändert aber nichts am Abarbeitungsprinzip.
rechtslinear:
Nonterminal steht nach dem Terminal-Symbol
linkslinear:
Nonterminal steht vor dem Terminal-Symbol