Äquivalenz Endlicher Automaten und regulärer Sprachen

Aus Informatik

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(a+b)* beschrieben, sie heißt L(b*ab*a(a+b)*).

Wählen wir zusätzlich z₁ 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 Summe b*ab*a(a+b)*+b*ab* oder b*ab*(a(a+b)*+ε) angegeben.

Wenn wir die Überführungsfunktion abändern und einen Weg im Grafen von z₁ nach z₀ zurückführen, so erhalten wir einen Automaten, der die Sprache L(b*a(bb*a)*(ε+a(a+b)*)) 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 z₀ können wir folgendermaßen in den ersten Endzustand z₁ gelangen: Mit allen durch b* beschriebenen Worten bleiben wir in z₀. Mit genau einem durch a beschriebenen Wort kommen wir von z₀ erstmalig nach z₁. Mit allen durch bb*a+ε beschriebenen Worten kommen wir von z₁ erstmalig nach z₁ zurück und durchlaufen dabei nur z₀. Sämtliche von z₁ nach z₁ führenden Worte können wir dann durch (bb*a+)ε= (bb*a)* beschreiben. Wir erhalten daher für alle von z₀ nach z₁ führenden Worte den regulären Ausdruck b*a(bb*a)*.

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

Die Sprache des Automaten ist die Vereinigungsmenge dieser Wortmengen. Wir können sie durch die Summe der beiden regulären Ausdrücke b*a(bb*a)*+b*a(bb*a)*a(a+b)*= b*a(bb*a)*(ε+a(a+b)*) beschreiben.

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.

Auf die Angabe eines allgemeinen Verfahrens soll hier jedoch verzichtet werden.

Uns kommt es nur darauf an, ein Beschreibungsmittel für die von Endlichen Automaten erkannten Sprachen zur Verfügung zu haben. Deshalb geben wir hier auch keine Beispiele dafür an, wie man umgekehrt zu einem gegebenen regulären Ausdruck einen zugehörigen Automaten findet.