Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Syntaxdiagramme Aufwärts: Reguläre Sprachen Vorherige Seite: Pumping Lemma für reguläre   Inhalt

Unterabschnitte

Reguläre Ausdrücke

Syntax regulärer Ausdrücke

Induktive Definition:
  • $\emptyset$ und $\epsilon$ sind reguläre Ausdrücke
  • für jedes $a\in\Sigma$ ist $a$ 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 $M$, 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 $M$ 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}

next up previous contents
Nächste Seite: Syntaxdiagramme Aufwärts: Reguläre Sprachen Vorherige Seite: Pumping Lemma für reguläre   Inhalt