5.5 Reguläre Ausdrücke

Wir werden nun eine weitere Weise finden, reguläre Sprachen zu beschreiben: neben regulären Grammatik (ob normal, erweitert, eingeschränkt), endlichen Automaten und nichtdeterministischen endlichen Automaten gibt es noch die regulären Ausdrücke. Dies wird wahrscheinlich von allen Beschreibungsweise die sein, mit der Sie in der Praxis am ehesten in Berührung kommen. Wir haben bereits in Kapitel 4.1 das Baukastenprinzip kennengelernt:

Wenn $L_{1}$ und $L_{2}$ reguläre Sprachen sind, dann ist $L_{1} \cup L_{2}$ auch regulär;
dann ist auch die Konkatenation $\begin{array}{r} L_{1} \circ L_{2} := {α β | α \in L_{1}, β \in L_{2}} \end{array}$ regulär;
wenn $L$ regulär ist, dann ist auch ihre Kleenesche Hülle $\begin{array}{r} L^{*} := {α_{1} \dots α_{n} | n \geq 0, α_{1}, \dots, α_{n} \in L} \end{array}$ regulär.

Darüberhinaus haben wir Techniken kennengelernt, um aus den gegebenen regulären Grammatiken eine neue Grammatik für $L_{1} \cup L_{2}$ , $L_{1} \circ L_{2}$ und $L$ konstruieren zu können. Sie sollten sich jetzt folgende Frage stellen:

Frage: Können alle regulären Sprachen nach diesem Baukastenprinzip erstellt werden?

Damit diese Frage überhaupt die Chance hat, mit ja beantwortet zu werden, müssen wir "Atome" zur Verfügung stellen, mit denen wir beginnen können. Daher:

Die Sprachen $\emptyset$ , ${ϵ}$ und ${x}$ für jedes $x \in Σ$ sind regulär.

Aus diesen

| Σ | + 2

"Grundbausteinen" und den drei Kombinatoren

\cup

\circ

und

^{*}

können Sie jede reguläre Sprache zusammenbauen. Dieses Baukastenprinzip hat auch einen Namen: reguläre Ausdrücke. Definieren wir diese nun formal.

Definition 5.5.1 Sei

Σ

einendliches Alphabet. Die regulären Audrücke über

Σ

sind induktiv definiert wie folgt und beschreiben folgende Sprachen:

Atome. $\emptyset$ ist ein regulärer Ausdruck und beschreibt die Sprache $\emptyset$ . $ϵ$ ist ein regulärer Ausdruck und beschreibt die Sprache ${ϵ}$ . Jedes einzelne Zeichen $x \in Σ$ ist ein regulärer Ausdruck und beschreibt die Sprache ${x}$ .
Alternative. Wenn $R_{1}, R_{2}$ reguläre Ausdrücke über $Σ$ sind und die Sprachen $L_{1}$ und $L_{2}$ beschreiben, so ist $(R_{1} | R_{2})$ ein regulärer Ausdruck und beschreibt die Sprache $L_{1} \cup L_{2}$ (die regulär ist, wie wir in Kapitel 4.1 gesehen haben).
Konkatenation. $(R_{1} R_{2})$ ist ein regulärer Ausdruck, der die Sprache $L_{1} \circ L_{2}$ beschreibt (die auch wiederum regulär ist). Der Deutlichkeit halber schreiben wir auch manchmal $R_{1} \circ R_{2}$ .
Kleenesche Hülle. Wenn $R$ ein regulärer Ausdruck ist und die Sprache $L$ beschreibt, dann ist $(R^{*})$ ein regulärer Ausdruck und beschreibt die Sprache $L^{*}$ .

Weil in der Praxis neben $L^{*}$ , also beliebig langen, möglicherweise leeren Folgen von $L$ -Wörtern wir oft nichtleere Folgen wollen, führen wir die Abkürzung $R^{+}$ für $R (R^{*})$ ein und bezeichnen die beschriebene Sprache $L \circ L^{*}$ kurzerhand als $L^{+}$ .

In konkreten fällen lassen gerne die Klammerung weg, wenn keine Verwechslungsgefahr besteht. Auch gehen wir davon aus, dass die Operatoren die Präzedenz $^{*}$ vor $\circ$ vor $|$ haben (wie hoch vor Punkt vor Strich in der Arithmetik), sodass beispielsweise der Ausdruck $a^{*} b | c^{*}$ die Bedeutung von $(((a^{*}) b) (c^{*}))$ hat, genauso wie wir in der Arithmetik $a^{2} b + c^{3}$ statt $(((a^{2}) b) + c^{3})$ schreiben.

Die von den atomaren Ausdrücken beschriebenen Sprachen sind alle regulär, da sie alle endliche Sprachen sind. Dank unserer Vorarbeit aus Kapitel 4.1 wissen wir, dass Alterantive, Konkatenation und Kleenesche Hülle wiederum reguläre Sprachen erzeugen. Wir erhalten das folgende Ergebnis:

Lemma 5.5.2 Die von einem regulären Ausdruck

R

beschriebene Sprache

L (R)

ist regulär.

Es ist Zeit für ein paar Beispiele.

Beispiel 5.5.3 Nehmen wir die Sprache der Wörter der Form bla:bla:blu.xyz-12-ab.b:x aus dem letzten Kapitel. Sie erinnern sich: eine endliche Folge von Labels, wo ein Label eine nichtleere Folge von Blöcken ist, die entweder : oder durch - separiert sind, wobei innerhalb eines Labels immer nur ein Separatortyp vorkommen darf, und wobei ein Block eine nichtleere Folge von alphanumerischen Zeichen ist (wir haben uns dann auf den Buchstaben

a

beschränkt). Sehen Sie, dass bereits unsere natürlichsprachliche Beschreibung von

L

von dem Baukastenprinzip gebraucht macht. Wenn wir nun einen regulären Ausdruck für

L

erstellen wollen, so können wir bequem Stück für Stück vorgehen.

Ein Block ist eine nichtleere Folge von $a$ 's. Der entsprechende reguläre Ausdruck $B$ für Blöcke ist also $\begin{array}{r} B := a^{+} \end{array}$ Für ein Label müssen wir uns entscheiden, ob wir die Blöcke mit : oder - separieren; wir erhalten den regulären Ausdruck $T$ für Labels ist also $\begin{array}{r} T := B (: B)^{*} | B (- B)^{*} \end{array}$ Sehen Sie, dass wir in $T$ das erste $B$ "ausfaktorisieren" können und statt dem obigen folgenden Ausdruck schreiben können: $\begin{array}{r} T^{'} := B ((: B)^{*} | (- B)^{*}) \end{array}$ Beide Varianten sind äquivalent, d.h., sie beschreiben die gleiche Sprache; die erste Variante, also $T$ , ähnelt mehr dem, was wir in unserer Grammatik bzw. dem nichtdeterministischen Automaten für $L$ getan haben, während $T^{'}$ eher die Arbeitsweise des determinisitschen Automaten reflektiert (wir lesen erst einmal einen Block und erst, wenn wir zum ersten mal auf : oder - stoßen, entscheiden wir uns für den "Typ" des Labels). Schlussendlich ist ein Wort in der Sprache eine mit . separierte Folge von Labels, also: $\begin{array}{r} R := T (. T)^{*} \end{array}$ Somit können wir nun den regulären Ausdruck für $L$ in seiner ganzen Pracht zeigen: $\begin{array}{r} R := (a^{+} (: a^{+})^{*} | a^{+} (- a^{+})^{*}) (. (a^{+} (: a^{+})^{*} | a^{+} (- a^{+})^{*}))^{*} \end{array}$

Übungsaufgabe 5.5.1 Laden Sie sich TestRegex.java herunter, kompilieren und starten Sie es.

java TestRegex                            
Please enter a regular expression: (a+)(:a+)*
Enter words to be matched, one per line 
aaaaa:aa:aaaa:a
true
aaa:aa:
false

Schreiben Sie nun einen regulären Ausdruck für die obige Sprache und testen Sie ihn mit dem Java-Programm.

Übungsaufgabe 5.5.2 In der Praxis gibt es bei reguläre Ausdrücken viele Abkürzung, so beschreibt [a-z] beispielsweise die Menge aller Kleinbuchstaben, [aoeiuy] beschreibt die Menge \{a,o,e,i,u,y\} etc. Der reguläre Ausdruck [a-z]*[aeiuoy][a-z]* beschreibt also die Menge aller Wörter, die mindesten einen Vokal enthalten. Lesen Sie hierfür unter Anderem

W3Schools

und

Patternl.html auf der Java-API,

lassen sich aber bitte nicht von der Menge an Details erschlagen.

Schreiben Sie nun in der Java-Regex-Syntax einen regulären Ausdruck für unsere obige Sprache , wo Sie aber neben alle alphanumerischen Zeichen zulassen.

Einen regulären Ausdruck für jede reguläre Sprache

Wir beweisen nun das Gegenstück zu Lemma 4.5.2:

Theorem 5.5.4 Sei

eine reguläre Sprache. Dann gibt es einen regulären Ausdruck

, der

beschreibt, also

Wir paraphrasieren hier den Beweis aus Michael Sipsers Introduction to the Theory of Computation.

Beweis. Zunächst skizzieren wir die Beweisidee. Da

regulär ist, gibt es einen nichtdeterministischen endlichen Automaten

, die

akzeptiert. Wir werden nun

Schritt für Schritt in einen regulären Ausdruck verwandeln. Kern der Idee ist, dass wir neben den üblichen Übergängen

komplexere Übergänge wie zum Beispiel

zulassen. Die Bedeutung wäre hier beispielsweise, dass der Automat von

nach

übergehen kann, wenn er die Eingabesymbole

liest. Wir lassen auch komplexere Übergänge wie

zu, also "von

kann der Automat nach

gehen, wenn er ein

liest oder ein

, gefolgt von beliebig vielen

"; ganz allgemein lassen wir Übergänge der Form

wobei

ein regulärer Ausdruck ist. Insbesondere lassen wir Übergänge der Form

zu. Dies bedeutet, dass der Automat von

nach

"springen" kann, ohne ein Eingabesymbol zu lesen. Des weiteren verlangen wir, dass es genau einen akzeptierenden Endzustand

mit

, und dass es keine Kanten gibt, die in

hineingehen, und keine, die aus

hinausgehen. All dies lässt sich leicht verwirklichen, wenn wir reguläre Ausdrücke als Kantenbeschriftung zulassen. Wir nennen so einen Automaten einen verallgemeinerten nichtdeterministischen endlichen Automaten (VNEA).

Definieren wir nun formal, was VNEAs sind und welche Sprache sie akzeptieren:

Definition 5.5.5 (Verallgemeinerter nichtdeterministischer endlicher Automat, VNEA). Ein VNEA besteht aus einem Alphabet

, einer Zustandsmenge

, einen Startzustand

, einem akzeptierenden Zustand

, einer Menge von gerichteten Kanten

Jede Kante

ist mit einem regulären Ausdruck

beschriftet. Wenn

gilt, dann schreiben wir

. Wenn

gilt,

also ein Wort in der von

beschriebenen Sprache ist, dann schreiben wir auch

Für und schreiben wir wenn man zerlegen kann als gibt (wobei zulässig ist) und es eine Zustandsfolge gibt, wobei ist und mit einem regulären Ausdruck beschriftet ist und jedes in der von beschriebenen Sprache ist. Wenn also gilt.

Einen gegebenen NEA können wir leicht in einen VNEA transformieren, indem wir, soweit nötig, (1) einen neuen Startzustand kreieren (damit dieser keine eingehenden Kanten hat), (2) einen neuen Endzustand kreieren, (3) "parallele" Übergänge wie zu einer Kante zusammenfassen, der dann mit dem regulären Ausdruck beschriftet ist.

Wir haben den ganzen Aufwand betrieben, weil wir für einen VNEA sehr leicht Zustände eliminieren können. Wenn wir zum Beispiel haben, dann können wir ja ein Wort in lesen und direkt von nach übergehen; wir brauchen also gar nicht. Wir müssen nur aufpassen, das neue mit einem eventuell bereits bestehenden Übergang von nach zu kombinieren. Im allgemeinen:

Falls die mit beschriftete Selbstschleife an Zustand nicht existieren sollte, dann schreiben wir einfach anstatt ; falls der Übergang nicht existieren sollte , lassen wir das im rechten Bild einfach weg. (Sipser führt hier den eleganten Formalismus ein, zu verlangen, dass jedes Paar durch eine Kante verbunden ist und würde fehlende Kanten einfach mit dem regulären Ausdruck beschriften.)

Wir suchen uns also einen Zustand , den wir eliminieren wollen, und führen die oben beschriebene -Umfahrung parallel für alle Paare aus, für die es gibt. Wir erhalten einen VNEA mit einem Zustand weniger, der zu dem vorherigen VNEA äquivalent ist, also die gleiche Sprache akzeptiert. Wiederholen wir diesen Schritt, so erhalten wir am Ende einen Automat mit nur zwei Zuständen, nämlich

Dieser VNEA akzeptiert immer noch die gleiche Sprache wie der ursprüngliche NEA, mit dem wir begonnen haben. Welche Sprache ist das? Es ist die Sprache aller mit Da der Pfad von nach nur eine Kante hat, muss in der von beschriebenen Sprache liegen. ist der gesuchte reguläre Ausdruck: er beschreibt die Sprache .

Hier sehen Sie den ganzen Ablauf an unserer aaaa:a:aaa.aa-aa-Sprache:

Übungsaufgabe 5.5.3 Wandeln Sie nach dem eben beschriebenen Schema den Automaten

in einen regulären Ausdruck um.