Fachkonzept - Reguläre Sprache
Grammatik zu einem endlichen Automaten
Die Experimente mit JFlap zeigen, dass man aus einem endlichen Automaten A zur Erkennung
der Sprache L eine Grammatik GA für diese Sprache automatisiert erzeugen kann.
Als Beispiel betrachten wir die Sprache LBin = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}
der Binärzahlen.
Diese Sprache wird vom endlichen Automaten A akzeptiert:
Zum endlichen Automaten A lässt sich die folgende Grammatik GA erzeugen:
S -> 0B B -> λ S -> 1A A -> 0A A -> 1A A -> λ
Es fällt auf, dass alle Produktionen dieser Grammatik eine bestimmte Struktur haben. Diese Struktur soll mit einem neuen Begriff beschrieben werden.
Reguläre Sprachen
Eine Produktion u -> v heißt regulär genau dann, wenn gilt:
Die linke Seite u der Produktion ist ein Nichtterminalsymbol.
Die rechte Seite v der Produktion besteht aus
- einem Terminalsymbol gefolgt von einem Nichtterminalsymbol oder
- aus dem leeren Wort.
Eine Grammatik heißt regulär genau dann, wenn alle Produktionen der Grammatik regulär sind.
Eine Sprache heißt regulär genau dann, wenn es eine reguläre Grammatik gibt, die diese Sprache erzeugt.
Beispiel für eine reguläre Grammatik zur Sprache LBin = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}:
S -> 0B B -> λ S -> 1A A -> 0A A -> 1A A -> λ
Beispiel für eine nicht-reguläre Grammatik zur Sprache LBin = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...}:
S -> 0 S -> 1R R -> ZR R -> λ Z -> 0 Z -> 1
Das Beispiel zeigt, dass es zu einer regulären Sprache durchaus nicht-reguläre Grammatiken geben kann.
Um nachzuweisen, dass eine Sprache regulär ist, reicht es aus, eine reguläre Grammatik zur Sprache zu konstruieren. Zu einer Sprache kann man stets eine Vielzahl von Grammatiken angeben. Auch wenn man noch keine reguläre Grammatik zu einer Sprache gefunden hat, so heißt das noch nicht, dass die Sprache nicht-regulär ist.