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  cbeschreiben. 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