Verknüpfungen regulärer Sprachen ::: Theoretische Informatik

Wir können in NFAs $\epsilon$ -Übergänge⁵¹ 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}$ .⁵²

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 , wenn es zwischen den einzelnen Zuständen in den Produktzuständen auch zwei Übergangsfunktionen mit Inschrift 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 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änge ⁵¹

Diese heißen z.B. auch $\epsilon$ -Moves

....⁵²

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}$

Endliche Automaten und reguläre Grammatiken Reguläre Sprachen Algorithmen zur Feststellung von Eigenschaften

Ψ Die Informatikseite