Fachkonzept - Reguläre Grammatik/Sprache
Grammatik zu einem endlichen Automaten
Die Untersuchung mit FLACI auf der vorherigen Seite zeigt: Aus einem endlichen Automaten A, der eine Sprache L erkennt, lässt sich automatisiert eine Grammatik GA erzeugen, die genau diese Sprache beschreibt.
Als Beispiel betrachten wir wieder die Sprache LBin = {0, 1, 10, 11, 100, 101, 110, 111, 1000, ...} der Binärzahlen ohne führende Nullen. Die Zahl 0 ist ebenfalls erlaubt.
Der folgende DEA mit dem Startzustand S und den Endzuständen A und B erkennt diese Sprache:
Jedem Zustand des Automaten entspricht ein Nichtterminal der Grammatik. Der Startzustand S wird zum Startsymbol. Jeder Übergang liefert eine Produktion: Beispielsweise wird aus dem Übergang von S nach A mit dem Zeichen 0 die Regel S -> 0A.
Für jeden Endzustand kommt eine Produktion hinzu, die das zugehörige Nichtterminal durch das leere Wort ε ersetzt. So kann eine Ableitung genau dann enden, wenn der Automat das gelesene Wort akzeptiert.
Damit ergibt sich die folgende Grammatik GA:
S -> 0A | 1B A -> 0C | 1C | ε B -> 0B | 1B | ε C -> 0C | 1C
Vom Zustand C aus kann der Automat keinen Endzustand mehr erreichen. Entsprechend lässt sich das Nichtterminal C nicht vollständig durch Terminale ersetzen: Jede Anwendung einer seiner Regeln lässt wieder ein C stehen. Eine Ableitung, die C enthält, liefert daher kein Wort der Sprache.
Bei allen Produktionen steht links ein einzelnes Nichtterminal. Rechts steht entweder ein Terminal gefolgt von einem Nichtterminal oder das leere Wort. Diese gemeinsame Struktur führt zum Begriff der regulären Grammatik.
Reguläre Sprachen
Eine Produktion u -> v heißt regulär genau dann, wenn gilt:
- Die linke Seite
uder Produktion ist ein Nichtterminalsymbol. - Die rechte Seite
vder Produktion besteht aus- einem Terminalsymbol gefolgt von einem Nichtterminalsymbol oder
- einem einzelnen Terminalsymbol oder
- 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.
Aufgabe 1
Betrachte den folgenden deterministischen endlichen Automaten:
- Nenne drei Wörter, die zur erkannten Sprache gehören, und drei Wörter, die nicht dazugehören.
Wörter der Sprache (für das leere Wort kannst du
εeingeben):1.
2.
3.Wörter über dem Alphabet {
0,1}, die nicht zur Sprache gehören:1.
2.
3. - Wandle den DEA von Hand in eine reguläre Grammatik um.
- Erstelle den DEA in FLACI oder öffne dort die Datei DEA_Vertiefung.json. Lasse den Automaten in eine Grammatik umwandeln. Vergleiche das Ergebnis mit deiner Grammatik aus b.
- Beschreibe die so definierte Sprache möglichst genau in Worten, und gib dann einen regulären Ausdruck an, der diese Sprache beschreibt.