Deterministische (endliche) Automaten

Definition 27

Ein deterministischer (endlicher) Automat, kurz DFA (deterministic finite automation), wird auf ein Eingabewort angesetzt und erkennt, bzw. akzeptiert dieses Wort, oder auch nicht. Ein DFA M wird spezifiziert durch ein $5$-Tupel

$$M=\left(Z,\Sigma,\delta,z_{0},E\right)$$

• $Z$ Menge der Zustände
• $\Sigma$ Eingabealphabet
• $Z\cap\Sigma=\emptyset$
• $z_{0}\in Z$ Startzustand
• $E\subseteq Z$ Menge der Endzustände
• $\delta:Z\times\Sigma\rightarrow Z$
  (Zustands-)Überführungsfunktion

Zustandsgraph 27

Darstellen lässt sich ein Automat durch einen Zustandsgraphen, (gerichtet und beschrifteter Graph) der sich wie folgt konstruieren lässt:

• Zeichne für jeden Zustand $z_{n}$ aus der Menge $z_{n}\in Z$ einen Kreis, und beschrifte ihn mit $z_{n}$
• Umkreise alle Kreise (doppelt Umkreisen) die einen $z_{n}\in E$ Endzustand enthalten
• Markiere den Startzustand $z_{0}$ mit einem nicht beschrifteten Pfeil der auf ihn Zeigt (entspringt aus dem Nichts)
• Für jede Überführungsvorschrift: $\delta\left(z_{n},a\right)=z_{m}$
  • Zeichen einen Pfeil von $z_{n}$ nach $z_{m}$ (wenn noch nicht vorhanden)
  • beschrifte ihn (zusätzlich) mit $a$

Sprache eines DFA 29

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

Mit $z\in Z,\; x\in\Sigma^{*},\; a\in\Sigma$

$$\hat{\delta}\left(z,\varepsilon\right) = z$$

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

Die Menge der akzeptierten Wörter bildet die durch den Automaten dargestellte oder definierte Sprache:

$$T\left(M\right)=\left\{ x\in\Sigma^{*}\vert\hat{\delta}\left(z_{0},x\right)\in E\right\}$$

• eine Sprache $L$ wird durch einen endlichen Automaten erkannt $\Leftrightarrow$ die Sprache ist regulär ( $L\in\mathcal{L}_{3}$)
• das lösen des Wortproblems ist mit Hilfe eines DFA in $O\left(n\right)$ möglich.

Grammatik zu einem gegebenen DFA 30

Aus einem DFA $M=\left(Z,\Sigma,\delta,z_{0},E\right)$ lässt sich wie folgt eine (reguläre / Typ 3) Grammatik $G=\left(V,\Sigma,P,S\right)$ konstruieren:

• $\Sigma$ die Mengen der Terminale sind gleich
• $Z=V$ die Menge der Variablen entspricht der Menge der Zustände
• $S=z_{0}$ die Startvariable ist der Startzustand des Automaten
• Für jede Überführungsvorschrift: $\delta\left(z_{n},a\right)=z_{m}$
  • falls $z_{m}\in E$:
    • füge eine Produktion $\left(z_{n}\rightarrow a\right)$ zu $P$ (der Menge der Produktionen) hinzu
    • wenn es eine Regel in $\sigma$ gibt, die von $z_{m}$ fortführt ( $\exists_{Z}^{z_{k}}:\exists_{\Sigma}^{b}:\delta\left(z_{m},b\right)=z_{k}$)
      • füge eine Produktion $\left(z_{n}\rightarrow az_{m}\right)$ zu $P$ (der Menge der Produktionen) hinzu
  • falls $z_{m}\notin E$:
    • füge eine Produktion $\left(z_{n}\rightarrow az_{m}\right)$ zu $P$ (der Menge der Produktionen) hinzu

$M$ und $G$ beschreiben die gleiche Sprache:

$$T\left(M\right)=L\left(G\right)$$