TI2—Kapitel 5.5

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 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{align*} L_1 \circ L_2 := \{\alpha \beta \ | \alpha \in L_1, \beta \in L_2\} \end{align*}$
regulär;
wenn $L$ regulär ist, dann ist auch ihre Kleenesche Hülle
$\begin{align*} L^* := \{ \alpha_1 \dots \alpha_n \ | \ n \geq 0, \alpha_1,\dots,\alpha_n \in L\} \end{align*}$
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$, $\{\epsilon\}$ und $\{x\}$ für jedes $x \in \Sigma$ sind regulär.

Aus diesen $|\Sigma|+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 $\Sigma$ einendliches Alphabet. Die regulären Audrücke über $\Sigma$ sind induktiv definiert wie folgt und beschreiben folgende Sprachen:

Atome. $\emptyset$ ist ein regulärer Ausdruck und beschreibt die Sprache $\emptyset$. $\epsilon$ ist ein regulärer Ausdruck und beschreibt die Sprache $\{\epsilon\}$. Jedes einzelne Zeichen $x \in \Sigma$ ist ein regulärer Ausdruck und beschreibt die Sprache $\{x\}$.
Alternative. Wenn $R_1, R_2$ reguläre Ausdrücke über $\Sigma$ 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 gesehen haben).
Konkatenation. $(R_1R_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 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{align*} B : = a^+ \end{align*}

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{align*} T := B ({:}B)^* | B (\text{-}B)^* \end{align*}

Sehen Sie, dass wir in $T$ das erste $B$ "ausfaktorisieren" können und statt dem obigen folgenden Ausdruck schreiben können:

\begin{align*} T' := B ( ({:}B)^* | (\text{-}B)^* ) \end{align*}

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{align*} R := T ({.}T)^* \end{align*}

Somit können wir nun den regulären Ausdruck für $L$ in seiner ganzen Pracht zeigen:

\begin{align*} R := (a^+ ({:}a^+)^* | a^+ (\text{-}a^+)^*) ({.}(a^+ ({:}a^+)^* | a^+ (\text{-}a^+)^*))^* \end{align*}

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

user@home:~$ 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 $R$ 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

W3School

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 $L$, wo Sie aber neben $a$ alle alphanumerischen Zeichen zulassen.

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

Wir beweisen nun das Gegenstück zu Lemma 5.5.2:

Theorem 5.5.4 Sei $L$ eine reguläre Sprache. Dann gibt es einen regulären Ausdruck $R$, der $L$ beschreibt, also $L(R) = R$.

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

Beweis. Zunächst skizzieren wir die Beweisidee. Da $L$ regulär ist, gibt es einen nichtdeterministischen endlichen Automaten $M$, die $L$ akzeptiert. Wir werden nun $M$ Schritt für Schritt in einen regulären Ausdruck verwandeln. Kern der Idee ist, dass wir neben den üblichen Übergängen

\begin{align*} q_1 \step{x} q_2 \end{align*}

komplexere Übergänge wie zum Beispiel $q_1 \step{xy} q_2$ zulassen. Die Bedeutung wäre hier beispielsweise, dass der Automat von $q_1$ nach $q_2$ übergehen kann, wenn er die Eingabesymbole $xy$ liest. Wir lassen auch komplexere Übergänge wie

\begin{align*} q_1 \step{x|yz^*} q_2 \end{align*}

zu, also "von $q_1$ kann der Automat nach $q_2$ gehen, wenn er ein $x$ liest oder ein $y$, gefolgt von beliebig vielen $z$ "; ganz allgemein lassen wir Übergänge der Form

\begin{align*} q_1 \step{R} q_2 \ , \end{align*}

wobei $R$ ein regulärer Ausdruck ist. Insbesondere lassen wir Übergänge der Form $q_1 \step{\epsilon} q_2$ zu. Dies bedeutet, dass der Automat von $q_1$ nach $q_2$ "springen" kann, ohne ein Eingabesymbol zu lesen. Des weiteren verlangen wir, dass es genau einen akzeptierenden Endzustand $q_{\rm end}$ mit $\qstart \ne q_{\rm end}$, und dass es keine Kanten gibt, die in $\qstart$ hineingehen, und keine, die aus $q_{\rm end}$ 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 $\Sigma$, einer Zustandsmenge $Q$, einen Startzustand $\qstart \in Q$, einem akzeptierenden Zustand $q_{\rm end} \in Q \setminus \{\qstart\}$, einer Menge von gerichteten Kanten

\begin{align*} E \subseteq (Q \setminus \{\qstart\}) \times (Q \setminus \{q_{\rm end}\}) \ . \end{align*}

Jede Kante $(q_i, q_j) \in E$ ist mit einem regulären Ausdruck $\delta(q_i, q_j)$ beschriftet. Wenn $R = \delta(q_i, q_j)$ gilt, dann schreiben wir $q_i \step{R} q_j$. Wenn $\beta \in L(R)$ gilt, $\beta$ also ein Wort in der von $R$ beschriebenen Sprache ist, dann schreiben wir auch $q_i \step{\beta \in R} q_j$. Für $q, q' \in Q$ und $\alpha \in \Sigma^*$ schreiben wir

\begin{align*} q \Step{\alpha} q' \end{align*}

wenn man $\alpha$ zerlegen kann als $\alpha = \beta_1 \beta_2 \dots \beta_k$ gibt (wobei $\beta_i = \epsilon$ zulässig ist) und es eine Zustandsfolge $q = q_0, q_1, \dots, q_k = q'$ gibt, wobei $(q_{i-1}, q_i)\in E$ ist und mit einem regulären Ausdruck $R_i$ beschriftet ist und jedes $\beta_i$ in der von $R_i$ beschriebenen Sprache ist. Wenn also

\begin{align*} q_0 \step{\beta_1 \in R_1} q_1 \step{\beta_2 \in R_2} q_2 \dots q_{k-1} \step{\beta_k \in R_k} p_k \end{align*}

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 $(q_i, x, q_j), (q_i, y, q_j)$ zu einer Kante zusammenfassen, der dann mit dem regulären Ausdruck $x | y$ 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

\begin{align*} q_0 \step{R_1} q_1 \step{R_2} q_2 \end{align*}

haben, dann können wir ja ein Wort in $R_1 R_2$ lesen und direkt von $q_0$ nach $q_2$ übergehen; wir brauchen also $q_1$ gar nicht. Wir müssen nur aufpassen, das neue $R_1 R_2$ mit einem eventuell bereits bestehenden Übergang von $q_0$ nach $q_2$ zu kombinieren. Im allgemeinen:

Falls die mit $R_2$ beschriftete Selbstschleife an Zustand $B$ nicht existieren sollte, dann schreiben wir einfach $R_1R_3$ anstatt $R_1 R_2^* R_3$; falls der Übergang $A \step{R_4} B$ nicht existieren sollte , lassen wir das $R_4 |$ 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 $\emptyset$ beschriften.) Wir suchen uns also einen Zustand $B \in Q \setminus \{\qstart, \qend\}$, den wir eliminieren wollen, und führen die oben beschriebene $B$-Umfahrung parallel für alle Paare $A,C$ aus, für die es $A \step{} B \step{} C$ 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 $L$ wie der ursprüngliche NEA, mit dem wir begonnen haben. Welche Sprache ist das? Es ist die Sprache aller $\alpha \in \Sigma$ mit

\begin{align*} \qstart \Step{\alpha} \qend \end{align*}

Da der Pfad von $\qstart$ nach $\qend$ nur eine Kante hat, muss $\alpha$ in der von $R$ beschriebenen Sprache liegen. $R$ ist der gesuchte reguläre Ausdruck: er beschreibt die Sprache $L$.A$\square$

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.