Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Algorithmen zur Feststellung von Aufwärts: Reguläre Sprachen Vorherige Seite: Endliche Automaten und reguläre   Inhalt

Unterabschnitte

Verknüpfungen regulärer Sprachen

NFAs mit $\epsilon$-Übergängen

Wir können in NFAs $\epsilon$-Übergänge51 definieren. Bei $\epsilon$-Übergängen verbraucht der NFA keine Eingabe. Er kann $\epsilon$-Übergänge spontan nichtdeterminitisch ausführen (dann wenn es so erforderlich ist, damit das Eingabewort möglichst akzeptiert).

Das jeder NFA in einen NFA mit $\epsilon$-Übergängen überführt werden kann, ist klar. Wir brauchen nichts zu machen.

Jeder NFA mit $\epsilon$-Übergängen kann auch in einen NFA ohne $\epsilon$-Übergänge umgeformt werden. Dazu ,,überbrücken'' wir sozusagen die $\epsilon$-Übergänge:

Sei

\begin{displaymath}A\rightarrow^{\!\!\!\!\!\!\epsilon}B\rightarrow^{\!\!\!\!\!\!a}C\end{displaymath}

der $\epsilon$-Übergang, noch gefolgt von einem anderen Übergang.
  • Wir entfernen die Regel $A\rightarrow^{\!\!\!\!\!\!\epsilon}B$
  • Wir fügen $A\rightarrow^{\!\!\!\!\!\!a}C$ hinzu.
  • Falls es eine Übergangsfunktion $B\rightarrow^{\!\!\!\!\!\!b}B$ gegeben hat, dann fügen wir $A\rightarrow^{\!\!\!\!\!\!b}B$ und lassen $B\rightarrow^{\!\!\!\!\!\!b}B$. Des weiteren lassen wir auch $B\rightarrow^{\!\!\!\!\!\!a}C$ stehen.

Vereinigung - $L(M_{1})\cup L(M_{2})$

Wir fassen beide NFAs als einen auf. Es wird nichtdeterministisch entschieden, welcher Startzustand verwendet wird. Entweder der von Automat $M_{1}$ oder $M_{2}$.52

Durchschnitt - $L(M_{1})\cap L(M_{2})$

  • Wir bilden einen Produktautomaten, indem wir einen jeden Knoten des Automatens $M_{1}$ mit allen Knoten des Automatens $M_{2}$ multiplizieren. In einem Zustand des Produktautomaten stehen dann also zwei Zustände.
  • Wir zeichnen eine Übergangsfunktion zwischen den beiden Zuständen mit der Inschrift $a$, wenn es zwischen den einzelnen Zuständen in den Produktzuständen auch zwei Übergangsfunktionen mit Inschrift $a$ gegeben hat. Also:

    \begin{displaymath}(P_{1}Q_{1})\rightarrow^{\!\!\!\!\!\!a}(P_{2}Q_{2})\Leftright... ...!\!\!\!\!\!a}P_{2} \wedge Q_{1}\rightarrow^{\!\!\!\!\!\!a}Q_{2}\end{displaymath}

Komplement - $\overline{L(M)}=\Sigma^{*}\backslash L(M)$

Wir gehen von einem Automaten hierbei aus, der eine totale Übergangsfunktion hat, d.h. das wir alle Übergänge, die nicht mehr ,,weitergehen'' in einen Fangzustand leiten.
Wir erhalten die Komplementsprache, indem wir alle Endzustände zu normalen Zuständen machen und alle normalen Zustände zu Endzuständen.

Konkatenation - $L(M_{1})\circ L(M_{2})$

Wir können zwei NFAs hintereinanderschalten, indem wir aus dem Endzustand von $M_{1}$ einen normalen Zustand machen und von diesem mit einem $\epsilon$-Übergang in $M_{2}$ überleiten.

Kleenabschluß - $L(M)^{*}=L(M^{*})$

  • Wir gehen vom Endzustand wieder in den Startzustand mit einem $\epsilon$-Übergang. Hiermit akzeptieren wir beliebig oft Wörter, die mit $M$ gebildet worden sind.
  • Desweiteren fügen wir zusätzlich noch einen Endzustand hinzu, der im NFA auch gleichzeitig Startzustand wird. Hiermit akzeptieren wir das leere Wort.

Fußnoten

...-Übergänge51
Diese heißen z.B. auch $\epsilon$-Moves
....52
Vereinigen wir zwei DFAs, so können wir auch die Morgansche Regel anwenden, um die Potenzmengenkonstruktion, die wir anwenden müssen, um aus dem entstehenden NFA wieder einen DFA zu machen, zu umgehen:

\begin{displaymath}L(M_{1})\cup L(M_{2})=\overline{\overline{L(M_{1})}\cap \overline{L(M_{2})}}\end{displaymath}

next up previous contents
Nächste Seite: Algorithmen zur Feststellung von Aufwärts: Reguläre Sprachen Vorherige Seite: Endliche Automaten und reguläre   Inhalt