Nichtdeterministische (endliche) Automaten

Definition 30

Bei einem nichtdeterministischen (endlichen) Automaten (NFA nondeterministic finite automation) ist es zugelassen, dass vom selben Zustand $z\in Z$ aus mehrere (oder auch garkeine) Pfeile ausgehen, die mit $a\in\Sigma$ beschriftet sind.

Ein NFA $M$ ist ein $5$-Tupel $M=\left(Z,\Sigma,\delta,S,E\right)$:

• $Z$ Zustandsmenge (endlich)
• $\Sigma$ Eingabealphabet (endlich)
• $Z\cap\Sigma=\emptyset$
• $\delta:Z\times\Sigma\rightarrow\mathcal{P}\left(Z\right)$
  (Zustands-)Überführungsfunktion
• $S\subseteq Z$ Startzustandsmenge
• $E\subseteq Z$ Endzustandsmenge

Zustandsgraph

Vom Prinzip her wie beim DFA (siehe sub:Zustandsgraph DFA). Einzige Unterschiede sind:

• Es gibt mehrere Startsustände
• Es kann von einem Zustand zwei Pfeile mit der gleichen Beschriftung zu unterschiedlichen Zuständen geben

Sprache des NFA 31

Zu einem gegebenen NFA $M=\left(Z,\Sigma,\delta,S,E\right)$ definieren wie eine Funktion $\hat{\delta}:\mathcal{P}\left(Z\right)\times\Sigma^{*}\rightarrow\mathcal{P}\left(Z\right)$ durch eine induktive Definition wie folgt (erweitert die Definition von $\sigma$ von Einzelzeichen zu ganzen Wörtern):

$$\hat{\delta}\left(Z',\varepsilon\right) = Z'\qquad\forall Z'\subseteq Z$$

$$\hat{\delta}\left(Z',ax\right) = \cup_{z\in Z'}\hat{\delta}\left(\delta\left(z,a\right),x\right)$$

Die Menge der akzeptierten Wörter bildet die durch den NFA akzeptierte Sprache:

$$T\left(M\right)=\left\{ x\in\Sigma^{*}\vert\hat{\delta}\left(S,x\right)\cap E\neq\emptyset\right\}$$

• eine Sprache $L$ wird durch einen endlichen Automaten erkannt $\Leftrightarrow$ die Sprache ist regulär ( $L\in\mathcal{L}_{3}$)
• Jede von einem NFA akzepierbare Sprache ist auch durch einen DFA akzeptierbar

Vom NFA zum DFA - Potenzmengenkonstruktion 32

Sei $M=\left(Z,\Sigma,\delta,S,E\right)$ ein gegebener NFA. Wir konstruieren einen DFA $M'=\left(Z',\Sigma,\delta',z_{0}',E'\right)$, der ebenfalls die gleiche Sprache erkennt $T\left(M\right)=T\left(M'\right)$ wie folgt (der neue DFA hat Mengen als Zustände):

• Terminalalphabet $\Sigma$ bleibt unverändert.
• $Z'=\mathcal{P}\left(Z\right)$
  die neuen Zustände sind alle möglichen Teilmengen der alten Zustandsmenge
• $z_{0}=S$
  die Startzustandsmenge ist der neue Startzustand
• $E'=\left\{ Z'\subseteq Z\vert Z'\cap E\neq\emptyset\right\}$
  Alle Zustandsmengen, die Endzustände enthalten sind auch neue Endzustände
• $\delta'\left(Z_{k},a\right)=\cup_{z\in Z_{k}}\delta\left(z,a\right)=\hat{\delta}\left(Z_{k},a\right)\quad\left(Z_{k}\in Z'\right)$
  Das Bild eines Urbildes, ist die Menge von allen möglichen Ableitungen von Elementen aus dem Urbild.

Hierbei entstehen in der Regel sehr viele unnötige Zustände und Überführungsfunktionen. Besser ist den Algorithmus aus sub:Vom-NFA-zumDFA-efficient zu nutzen.

Der Laufzeitkomplexität ist dieses Algorithmus ist $O\left(c^{n}\right)$.

Vom NFA zum DFA - effizientere Methode

Bei folgenden Algorithmus bietet es sich an, zunächst einen Graphen von $M$ zu zeichnen, und anhand diesem den Graphen von $M'$ anhand des Algorithmusses zu erstellen. Diesen Graphen sollte man dann erst zum Schluss als Funktion nierderschreiben.

Sei $M=\left(Z,\Sigma,\delta,S,E\right)$ ein gegebener NFA. Wir konstruieren einen DFA $M'=\left(Z',\Sigma,\delta',z_{0}',E'\right)$, der ebenfalls die gleiche Sprache erkennt $T\left(M\right)=T\left(M'\right)$ wie folgt (der neue DFA hat Mengen als Zustände):

• Terminalalphabet $\Sigma$ bleibt unverändert.
• $z_{0}'=S$
  die Startzustandsmenge ist der neue Startzustand
• Folgendes solange ausführen, bis sich an $\delta$ und $Z'$ nichts mehr ändert.
  • Für jedes Element $z_{x}\in Z'$:
    • Für jedes Terminal $t\in\Sigma$:
      • Bestimme für jedes Element $a$ der Menge die den akt. Zustand $z_{x}$ bildet, die Menge der neuen Zustände bezüglich dem Terminal $t$. $\cup_{a\in z_{x}}\left\{ b\in Z\vert\delta\left(a,t\right)=b\right\}$
      • Fasse diese zu einer neuen Menge $z_{neu}$ zusammen. $z_{neu}=\cup_{a\in z_{x}}\left\{ b\in Z\vert\delta\left(a,t\right)=b\right\}$
      • Wenn $z_{neu}$ noch nicht in $Z'$ enthalten $\left(z_{neu}\notin Z'\right)$, füge es in die Zustandsmenge $Z'$ hinzu. $Z'\cup\left\{ z_{neu}\right\}$
      • Wenn die Menge $z_{neu}$ ein Endzustand aus $E$ enthält und $z_{neu}$ noch nicht in $E'$ enthalten ist ( $\left(\exists_{z_{neu}}^{a}:a\in E\right)\wedge z_{neu}\notin E'$), dann füge $z_{neu}$ der Menge $E'$ hinzu.
      • Wenn es in $\delta$ noch keine Regel der Gestalt $\delta\left(z_{x},t\right)=z_{neu}$ gibt, ergänze diese.

Der Laufzeitkomplexität ist dieses Algorithmus ist $O\left(c^{n}\right)$.

Von einer Grammatik zum NFA 35

Für jede reguläre Grammatik $G=\left(V,\Sigma,P,S\right)$ (Typ 3) gibt es einen NFA $M=\left(Z,\Sigma,\delta,S',E\right)$ mit $L\left(G\right)=M\left(G\right)$. Diese lässt sich wie folgt konstruieren:

• $Z=V\cup\left\{ X\right\} ,\quad X\notin V$
  Die Zustandsmenge besteht aus der Menge der Variablen, zuzüglich einer neuen Variable (hier $X$)
• $S'=\left\{ S\right\}$
  Der Startzustand ist die Menge, die nur die Startvariable enthält
• $E=\left\{ \begin{array}{cc} \left\{ S,X\right\} , & \left(S\rightarrow\varepsi... ...\{ X\right\} , & \left(S\rightarrow\varepsilon\right)\notin P\end{array}\right.$
  Die Menge der Endzustände enthält $X$ und wenn es eine Produktion der Form $\left(S\rightarrow\varepsilon\right)\in P$ gibt zusätzlich auch noch $S$
• $B\in\delta\left(A,a\right),\quad\left(A\rightarrow aB\right)\in P$
  Erstelle für alle Produktionen der Form $\left(A\rightarrow aB\right)\in P$ eine Regel für $\delta$ mit $B\in\delta\left(A,a\right)$
• $X\in\delta\left(A,a\right),\quad\left(A\rightarrow a\right)\in P$
  Erstelle für alle Produktionen der Form $\left(A\rightarrow a\right)\in P$ eine Regel für $\delta$ mit $X\in\delta\left(A,a\right)$

Der Laufzeitkomplexität ist dieses Algorithmus ist $O\left(n\right)$.