Äquivalenz Endlicher Automaten und regulärer Sprachen
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
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]*).
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]*.
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?