Äquivalenz Endlicher Automaten und regulärer Sprachen

Aus Informatik
Wechseln zu: Navigation, Suche

Reguläre Ausdrücke stehen in engem Zusammenhang mit Endlichen Automaten. Wir geben hier ohne Begründung folgenden Satz an:

Zu jedem endlichen Akzeptor A gibt es einen regulären Ausdruck r, der die von A erkannte Sprache beschreibt, für den also L(r)= L(A) gilt.

Auch die Umkehrung dieses Satzes ist richtig:

Zu jedem regulären Ausdruck r gibt es einen endlichen Akzeptor A, der die von r bezeichnete Sprache erkennt, für den also L(A) = L(r) gilt.

Man kann also sagen, dass die von endlichen Akzeptoren erkannten Sprachen und die durch reguläre Ausdrücke beschreibbaren äquivalent sind, man spricht daher meist von regulären Sprachen.

Beispiele

Automat01.png
Wir setzen das Eingabealphabet X= {a,b} voraus. Um die Sprache des abgebildeten Automaten zu bestimmen, beachten wir, dass das kürzeste erkannte Wort aa ist und dass vor dem ersten und dem zweiten a beliebig viele b stehen können und nach dem zweiten a beliebige Folgen aus a und b. Genau diese Worte werden erkannt. Die erkannte Sprache wird also durch den regulären Ausdruck b*ab*a[ab]* beschrieben, sie heißt L(b*ab*a[ab]*).


Automat02.png
Wählen wir zusätzlich z1 als Endzustand, so kommen weitere erkannte Worte hinzu, nämlich die durch den regulären Ausdruck b*ab* beschriebenen. Die Sprache des Automaten wird also durch die Verknüpfung (b*ab*a[ab]*)|(b*ab*) oder zusammengefasst b*ab*(a[ab]*)? angegeben.


Automat03.png
Wenn wir die Überführungsfunktion abändern und einen Weg im Grafen von z1 nach z0 zurückführen, so erhalten wir einen Automaten, der die Sprache L(b*a(bb*a)*(a[ab]*)) erkennt. Das wollen wir im Folgenden begründen. Wir müssen wie oben unterscheiden zwischen denjenigen Worten, die den Automaten in den einen bzw. den anderen Endzustand überführen. Vom Anfangszustand z0 können wir folgendermaßen in den ersten Endzustand z1 gelangen: Mit allen durch b* beschriebenen Worten bleiben wir in z0. Mit genau einem durch a beschriebenen Wort kommen wir von z0 erstmalig nach z1. Mit allen durch bb*a beschriebenen Worten kommen wir von z1 erstmalig nach z1 zurück und durchlaufen dabei nur z0. Sämtliche von z1 nach z1 führenden Worte können wir dann durch (bb*a)* beschreiben. Wir erhalten daher für alle von z0 nach z1 führenden Worte den regulären Ausdruck b*a(bb*a)*.

Vom Anfangszustand z0 können wir folgendermaßen in den zweiten Endzustand z2 gelangen: Da kein Weg im Zustandsgrafen aus z2 wieder herausführt, genügt es, an die zum Zustand z1 führenden Worte diejenigen anzuhängen, die von z1 nach z2 führen und von z2 nach z2. Wir erhalten also für alle von z0 nach z2 führenden Worte den regulären Ausdruck b*a(bb*a)*a[ab]*.

Automat04.png
Wenn wir für ein viertes Beispiel den Automaten nochmals abändern, wird ein systematisches Vorgehen, wie es beim dritten Beispiel schon angeklungen ist, zum Ermitteln der Sprache des Automaten unerlässlich.

Finden Sie einen geeigneten regulären Ausdruck für die akzeptierte Sprache?