Reguläre Ausdrücke ::: Theoretische Informatik

Induktive Definition:

$\emptyset$ und $\epsilon$ sind reguläre Ausdrücke
für jedes $a\in\Sigma$ ist ein regulärer Ausdruck (alle Zeichen sind in sich selbst ein regulärer Ausdruck)
Mit $\alpha$ und $\beta$ sind auch $(\alpha\beta)$ , $(\alpha+\beta)$ und $(\alpha^{*})$ reguläre Ausdrücke.
Nichts sonst ist ein regulärer Ausdruck

CFG:

$\begin{displaymath}\alpha=\emptyset\,\vert\,\epsilon\,\vert\,a\,\vert\,\alpha\alpha\,\vert\,\alpha+\alpha\,\vert\,\alpha^{*}\end{displaymath}$

Syntaxdiagramm:
Beispiele für Syntaxdiagramme sehen wir gleich noch.

Regulärer Ausdruck $\rightarrow$ NFA

Zu jedem regulären Ausdruck $\alpha$ gibt es einen NFA

, so daß gilt $L(\alpha)=L(M)$

1.Verfahren:
Zu einem regulären Ausdruck $\alpha$ gehört eine Sprache $L(\alpha)$ die wie folgt definiert ist:

$L(\emptyset)=\emptyset$	$L(\epsilon)=\epsilon$
$L(a)=\{a\}$	$L(\alpha\beta)= L(\alpha)\circ L(\beta)$
$L(\alpha)+ L(\beta)=L(\alpha)\cup L(\beta)$	$L(\alpha^{})=L(\alpha)^{}$

Dies läßt uns erkennen, wie wir einen Automaten aus einem regulären Ausdruck bilden können. Wir können dies, indem wir triviale Automaten für Teilausdrücke zur Verfügung stellen und mit diesen Operationen für die Vereinigung, den Durchschnitt und den Kleenabschluß durchführen:

2.Verfahren:
Wir können aus einem initialen NFA einen äquivalenten NFA zum regulären Ausdruck konstruieren, indem wir die Kanten rekursiv ersetzen:

Initialer NFA:

Wenn $\alpha=\alpha_{1}+\alpha_{2}$ :

Wenn $\alpha=\alpha_{1}\cdot\alpha_{2}$ :

Wenn $\alpha=\alpha^{*}$ :

DFA $\rightarrow$ regulärer Ausdruck

Zu jedem DFA

gibt es einen regulären Ausdruck $\alpha$ , so daß gilt $L(M)=L(\alpha)$
Wir wenden das Verfahren des dynamischen Programmierens an. Dabei erstellen wir für Teilmengen an Zuständen des DFAs reguläre Ausdrücke und fügen diese zu immer größer werdenden Teilmengen zusammen. Wir starten dabei bei Teilmengen aus zwei oder einem Zustand, wobei bei zwei Zuständen diese Zustände direkt verbunden sein müssen.
Es gilt für $1\leq i$ und $j\leq n$ :

$\begin{displaymath}L^{0}_{i,j}=\{a\in\Sigma:\delta(q_{i},a)=q_{j}\}\end{displaymath}$

$\begin{displaymath}L^{0}_{i,i}=\{\epsilon\}\cup\{a\in\Sigma:\delta(q_{i},a)=q_{i}\}\end{displaymath}$

Wir können folgende reguläre Ausdrücke erzeugen:

$\begin{displaymath}\alpha_{i,j}^{0}=a_{1}+a_{2}+a_{3}\ldots+a_{n}\,\,\,\,\,f\uml {u}r\,\,L^{0}_{i,j}\end{displaymath}$

$\begin{displaymath}\alpha_{i,i}^{0}=\epsilon + a_{1}+a_{2}+a_{3}\ldots+a_{n}\,\,\,\,\,f\uml {u}r\,\,L^{0}_{i,i}\end{displaymath}$

Diese Ausdrücke können wir nach folgender Formel zusammenfügen

$\begin{displaymath}L^{k+1}_{i,j}=L^{k}_{i,j}\cup L^{k}_{i,k+1}\circ(L^{k}_{k+1,k+1})^{*}\circ L^{k}_{k+1,j}\end{displaymath}$

Wieder der reguläre Ausdruck

$\begin{displaymath}\alpha^{k+1}_{i,j}=\alpha^{k}_{i,j}+\alpha^{k}_{i,k+1}(\alpha^{k}_{k+1,k+1})^{*}\alpha^{k}_{k+1,j}\end{displaymath}$

Pumping Lemma für reguläre Sprachen Reguläre Sprachen Syntaxdiagramme

Ψ Die Informatikseite