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.

Umsetzung der Grundelemente

regulärer AusdruckSyntaxdiagrammAkzeptor
[ a b c ]Dieses Bild hat ein leeres Alt-Attribut. Der Dateiname ist syntaxregulaer01.pngDieses Bild hat ein leeres Alt-Attribut. Der Dateiname ist akzeptorregular01.png
( ab | cd )Dieses Bild hat ein leeres Alt-Attribut. Der Dateiname ist akzeptorregular02.png
[ a ] ?Dieses Bild hat ein leeres Alt-Attribut. Der Dateiname ist syntaxregulaer03.pngDieses Bild hat ein leeres Alt-Attribut. Der Dateiname ist akzeptorregular03a.png
[ a ] +Dieses Bild hat ein leeres Alt-Attribut. Der Dateiname ist syntaxregulaer04.pngDieses Bild hat ein leeres Alt-Attribut. Der Dateiname ist akzeptorregular04.png

Beispiele

Je komplexer ein gegebener Akzeptor ist, desto schwieriger wird es, die akzeptierte Sprache bzw. einen regulären Ausdruck dafür zu bestimmen. Ein mögliches Vorgehen soll hier beschrieben werden …

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]*).

Wählen wir zusätzlich q1 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.

Wenn wir die Überführungsfunktion abändern und einen Weg im Graphen von q1 nach q0 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 zwischen denjenigen Worten unterscheiden, die den Automaten in den einen bzw. den anderen Endzustand überführen. Vom Anfangszustand q0 können wir folgendermaßen in den ersten Endzustand q1 gelangen: Mit allen durch b* beschriebenen Worten bleiben wir in q0. Mit genau einem durch a beschriebenen Wort kommen wir von q0 erstmalig nach q1. Mit allen durch bb*a beschriebenen Worten kommen wir von q1 erstmalig nach q1 zurück und durchlaufen dabei nur q0. Sämtliche von q1 nach q1 führenden Worte können wir dann durch (bb*a)* beschreiben. Wir erhalten daher für alle von q0 nach q1 führenden Worte den regulären Ausdruck b*a(bb*a)*.

Vom Anfangszustand q0 können wir folgendermaßen in den zweiten Endzustand q2 gelangen: Da kein Weg im Zustandsgrafen aus q2 wieder herausführt, genügt es, an die zum Zustand q1 führenden Worte diejenigen anzuhängen, die von q1 nach q2 führen und von q2 nach q2. Wir erhalten also für alle von q0 nach q2 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?