Ψ Die Informatikseite

Menü
Unterabschnitte

Endliche Automaten und reguläre Grammatiken

Übersicht

DFA $\rightarrow$ reguläre Grammatik

Wir können aus einem DFA eine reguläre Grammatik machen.

Dazu verwenden wir folgende Regeln:
Wenn $q_{0}\in F$: $q_{0}\rightarrow\epsilon$
Wenn $\delta(q,a)=p$: $q\rightarrow ap$
Wenn $\delta(q,a)=p$ und $p\in F$: $q\rightarrow a$

NFA $\rightarrow$ DFA (Potenzmengenkonstruktion)

Beim Überführen von einem NFA in einen DFA generieren wir die Potenzmenge der Zustände des NFAs. D.h. das wir aus allen Untermengen der Menge $Q$ einen neuen Zustand machen.
Wir generieren den neuen DFA $M'=(q',\Sigma,\delta',q_{0},f')$ wie folgt:

\begin{displaymath}F'=\{p\subseteq q: p\cap f\not= \emptyset\}\end{displaymath}


\begin{displaymath}\delta'(p,a)=\bigcup_{p\in p}\delta(p,a)\end{displaymath}

Da dies niemand verstehen kann, hier noch einmal eine Konstruktionsvorschrift für den DFA. Zur Konstruktion müssen wir folgendes tun:
  • Potenzmenge der Zustände des NFAs bilden und alle Zustände aufmalen. Dabei darauf achten, daß die Potenzzustände, in denen ein Endzustand vorkommt auch Endzustände werden. (erste Regel)
  • Nun die Übergangsfunktionen in Form von Pfeilen mit Inschriften einzeichnen. Dabei betrachten wir für jeden Potenzzustand alle Symbole des Eingabealphabetes. Sei nun das aktuelle Symbol gerade $a$.
    • Wir legen uns eine Menge $Z$ an.
    • Nun gehen wir jeden Zustand, der in unserem Potenzzustand vorhanden ist, durch. Können wir von diesem Zustand in dem NFA einen anderen Zustand oder vielleicht sogar mehrere mit Hilfe von $a$ erreichen? Dann kommen diese Zustände in die Menge $Z$.
    • Wenn wir alle Zustände im vorhergehenden Schritt abgearbeitet haben, dann haben wir einen Potenzzustand in der Menge $Z$ stehen, zu dem wir nun einen Pfeil mit der Inschrift $a$ malen.

Die grauen Knoten und Kanten kann man auch weglassen, da sie nie erreicht werden. Formal werden sie aber auch bei der Konstruktion erzeugt.

Effizienz von NFAs

Der DFA zu einem NFA hat im schlechtesten Falle exponentiell viele Zustände wie der NFA. Es gibt Sprachen, die sich durch NFAs viel besser darstellen lassen, wie zum Beispiel

\begin{displaymath}L_{n}=\{w\in\{0,1\}^{*}:das\,n-letzte\,Zeichen\,von\,w\,ist\,eine\,1\}\end{displaymath}

Reguläre Grammatik $\rightarrow$ NFA

Wir können aus einer regulären Grammatik einen NFA machen:
  • Jedes Non-Terminal wird zu einem Zustand konvertiert.
  • Dazu kommt der Zustand $q_{F}$, welcher Endzustand ist.
  • Existiert in der Grammatik eine Regel $S\rightarrow\epsilon$, wobei $S$ Startzustand ist, so ist im NFA $S$ ein Endzustand. Dadurch wird erreicht, daß auch das leere Wort akzeptiert wird.
    • Wenn es eine Regel $A\rightarrow a$ gibt, dann kreiren wir eine Übergangsfunktion $\delta$ (zeichnen einen Pfeil) von dem Zustand $A$ nach $q_{F}$ mit der Inschrift $a$.
    • Wenn es eine Regel $A\rightarrow aB$ gibt, dann kreiren wir eine Übergangsfunktion (zeichnen einen Pfeil) von dem Zustand $A$ in den Zustand $B$ mit der Inschrift $a$.