Definition

Deterministische endliche Automaten DEA

$\mathcal{A}=\left\langle Q, \Sigma, \delta, q_{0}, F\right\rangle$

$Q$all possible states (finite)

$\sum$input alphabet (kein $\varepsilon$ erlaubt)

$\delta: Q \times \Sigma \mapsto Q$transition function

$q_{0} \in Q$initial state

$F \subseteq Q$final states

Erweiterte Übergangsfunktion (auch für Leerwort)

$\delta^{*}: Q \times \Sigma^{*} \mapsto Q$

$\forall q \in Q, s \in \Sigma, w \in \Sigma^{*}: \quad \delta^{*}(q, \varepsilon)=q, \quad \delta^{*}(q, s w)=\delta^{*}(\delta(q, s), w)$

Akzeptierte / Generierte Sprache

Nur Wörter die von initial state zu einem final state führen.

$\mathcal{L}(\mathcal{A})=\left\{w \in \Sigma^{*} \mid \delta^{*}\left(q_{0}, w\right) \in F\right\}$

Falle / Fehlerzustand

Wird meistens nicht eingezeichnet aber existiert in Tabelle.

Alle Fehlverhalten → Falle, dann kein Weg heraus.

Beispiel:

• 00-freie Binärstrings

  

  $c$ ist die Falle

  $Q=\{a, b, c\}$ Zustandsmenge

  $\Sigma=\{0,1\}$ Eingabealphabet

  $q_0 = a$ Anfagszustand

  $F=\{a, b\}$ Endzustand

  $\delta: Q \times \Sigma \mapsto Q$ definiert durch:

  $\begin{array}{l|ll}\delta & 0 & 1 \\\hline a & b & a \\b & c & a \\c & c & c\end{array}$

  Beispielsweise: $101 \in \mathcal{L}(\mathcal{A})$

Nichtdeterministische endliche Automaten NEA

$\mathcal{A}=\left\langle Q, \Sigma, \delta, q_{0}, F\right\rangle$

Alles gleich mit DEA nur $\varepsilon$ erlaubt:

Erweiterte Übergangsfunktion (auch für Leerwort)

$\delta^*$ ist die kleinste Menge mit den Eigenschaften

Akzeptierte / Generierte Sprache

Nur Wörter die von initial state zu einem final state führen.

$\mathcal{L}(\mathcal{A})=\left\{w \in \Sigma^{*} \mid\left(q_{0}, w, q_{f}\right) \in \delta^{*} \text { für ein } q_{f} \in F\right\}$ (Es kann mehrere Endzustände geben)

Beispiel:

• Reelle Numerale mit Exponential-Teil

  gültige Beispiele: 3.14 , 0.314E1 , 314.E-2 ,...

  Vorausgesetzt:

  1. Min 1 Ziffer vor Punkt

  2. Exponentialteil optional (mit E)
     • Vorzeichen optional
     • mindestens eine Ziffer nach E

  Endlicher (nicht deterministischer Automat) mit$\epsilon$als Leerwort.

  

  

  $\mathcal{A}=\langle\{1, \ldots, 7\},\{0, \ldots, 9, ., \mathrm{E},+,-\}, \delta, 1,\{3,6\}\rangle$

  $\mathcal{L}(\mathcal{A})=\left\{w \in \Sigma^{*} \mid(1, w, 3) \in \delta^{*} \text { oder }(1, w, 6) \in \delta^{*}\right\}$

  $\begin{array}{c|cccccccc} \delta & 0 & \cdots & 9 & . & \mathrm{E} & + & - & \varepsilon \\ \hline 1 & \{1,2\} & \cdots & \{1,2\} & \{\} & \{\} & \{\} & \{\} & \{\} \\ 2 & \{\} & \cdots & \{\} & \{3\} & \{\} & \{\} & \{\} & \{\} \\ 3 & \{3\} & \cdots & \{3\} & \{\} & \{4\} & \{\} & \{\} & \{\} \\ 4 & \{\} & \cdots & \{\} & \{\} & \{\} & \{5\} & \{5\} & \{5\} \\ 5 & \{5,6\} & \cdots & \{5,6\} & \{\} & \{\} & \{\} & \{\} & \{\} \\ 6 & \{\} & \cdots & \{\} & \{\} & \{\} & \{\} & \{\} & \{\} \end{array}$

Determinisierung (NEA $\rarr$ DEA)

Gegeben: NEA

$\mathcal{A}=\left\langle Q, \Sigma, \delta, q_{0}, F\right\rangle$(A steht für Automat)

$\delta \subseteq Q \times(\Sigma \cup\{\varepsilon\}) \times Q$

Gesucht: DEA

$\widehat{\mathcal{A}}=\left\langle\widehat{Q}, \Sigma, \widehat{\delta}, \widehat{q_{0}}, \widehat{F}\right\rangle$

$\widehat{\delta}: \widehat{Q} \times \Sigma \mapsto \widehat{Q}$

Unter der Bedingung dass $\mathcal{\hat{A}}$ und $\mathcal{A}$ äquivalent sind (dieselbe Sprache akzeptieren = sich gleich verhalten) gilt: $\mathcal{L}(\mathcal{A})=\mathcal{L}(\widehat{\mathcal{A}})$

Definition von DEA$\mathcal{\widehat{A}}$

$\widehat{Q}=2^{Q}$(Potenzmenge von$Q$- Alle Teilmengen / Zustands-Wörter)

$\widehat{q_{0}}=\left\{q_{0}\right\}$(Klammern stehen nicht für Menge)

$\widehat{F}=\left\{\begin{array}{ll}\{\widehat{q} \in \widehat{Q} \mid \widehat{q} \cap F \neq \emptyset\} \cup\left\{\widehat{q_{0}}\right\} & \text { falls } \varepsilon \in \mathcal{L}(\mathcal{A}) \\\{\widehat{q} \in \widehat{Q} \mid \widehat{q} \cap F \neq \emptyset\} & \text { sonst }\end{array}\right.$

$\forall \widehat{q} \in Q, s\in \sum :$

Beispiel:

• Suche nach "max" und "ana"

  

  Dadurch, dass es keine$\epsilon$gibt ist Tabelle von$\delta$gleich mit$\delta^*$

  Anfangszustand ist $1$ , Endzustand ist $6$ .

  $\begin{array}{c|ccccc}\delta^{*} & \mathrm{a} & \mathrm{m} & \mathrm{n} & \mathrm{x} & \mathrm{z} \\\hline 1 & \{1,3\} & \{1,2\} & \{1\} & \{1\} & \{1\} \\2 & \{4\} & \{\} & \{\} & \{\} & \{\} \\3 & \{\} & \{\} & \{5\} & \{\} & \{\} \\4 & \{\} & \{\} & \{\} & \{6\} & \{\} \\5 & \{6\} & \{\} & \{\} & \{\} & \{\} \\6 & \{6\} & \{6\} & \{6\} & \{6\} & \{6\}\end{array}$

  Wir definieren eine $\widehat{\delta}$

  Anfangszustand ist $1$ , Endzustand ist jeder Block der mit $1$ anfängt und mit $6$ endet.

  Wichtig: die Tabelleneinträge sind keine Mengen sondern Wörter obwohl wir {} benutzen.

  $\begin{array}{c|ccccc}\widehat{\delta} & \mathrm{a} & \mathrm{m} & \mathrm{n} & \mathrm{x} & \mathrm{z} \\\hline\{1\} & \{1,3\} & \{1,2\} & \{1\} & \{1\} & \{1\} \\\{1,2\} & \{1,3,4\} & \{1,2\} & \{1\} & \{1\} & \{1\} \\\{1,3\} & \{1,3\} & \{1,2\} & \{1,5\} & \{1\} & \{1\} \\\{1,3,4\} & \{1,3\} & \{1,2\} & \{1,5\} & \{1,6\} & \{1\} \\\{1,5\} & \{1,3,6\} & \{1,2\} & \{1\} & \{1\} & \{1\} \\\{1,6\} & \{1,3,6\} & \{1,2,6\} & \{1,6\} & \{1,6\} & \{1,6\} \\\{1,3,6\} & \{1,3,6\} & \{1,2,6\} & \{1,5,6\} & \{1,6\} & \{1,6\} \\\{1,2,6\} & \{1,3,4,6\} & \{1,2,6\} & \{1,6\} & \{1,6\} & \{1,6\} \\\{1,5,6\} & \{1,3,6\} & \{1,2,6\} & \{1,6\} & \{1,6\} & \{1,6\} \\\{1,3,4,6\} & \{1,3,6\} & \{1,2,6\} & \{1,5,6\} & \{1,6\} & \{1,6\}\end{array}$

  

  Da von den Endzuständen keine Kanten zurückführen und man somit den Endzustand nicht verlässt: kürzen möglich.

  

Endlicher Transducer

Automat beschrieben durch $\mathcal{A}=\langle Q, \Sigma, \Gamma, \delta, I, F\rangle$

$\Gamma$output alphabet

$\delta \subseteq Q \times(\Sigma \cup\{\varepsilon\}) \times(\Gamma \cup\{\varepsilon\}) \times Q$ Übergangsrelation

$I \subseteq Q$initial states

Erweiterte Übergangsrelation (auch für Leerwort)

$\delta^{*} \subseteq Q \times \Sigma^{*} \times \Gamma^{*} \times Q$

$\delta^*$ ist die kleinste Menge bei der

Übersetzungsrelation

Automat generiert nicht mehr Sprache sondern gibt uns eine Übersetzungsrelation (zu jedem Eingabewort, ein Ausgabewort)

$[\mathcal{A}]=\left\{\left(w, w^{\prime}\right) \in \Sigma^{*} \times \Gamma^{*} \mid \forall i \in I, f \in F: \left (i, w, w^{\prime}, f\right) \in \delta^{*} \right\}$

$[\mathcal{A}] \subseteq \Sigma^{*} \times \Gamma^{*}$

Beispiele:

• Binäraddition von R nach L (deterministisch)

  

• Binäraddition von L nach R (nicht deterministisch)

  

Mealy-Automat

Art von Transducer, deterministisch

Automat beschrieben durch $\mathcal{A}=\left\langle Q, \Sigma, \Gamma, \delta, \gamma, q_{0}\right\rangle$

$\Gamma$output alphabet

$\gamma: Q \times \Sigma \mapsto \Gamma$output function / Ausgabefunktion

Erweiterte Ausgabefunktion (auch für Leerwort)

$\gamma^{*}: Q \times \Sigma^{*} \mapsto \Gamma^{*}$

$\forall q \in Q, s \in \Sigma, w \in \Sigma^{*}:$

Übersetzungsfunktion

$[\mathcal{A}](w)=\gamma^{*}\left(q_{0}, w\right)$

$[\mathcal{A}]: \Sigma^{*} \mapsto \Gamma^{*}$

Beispiel:

• (1:2)-(0,1)-RLL Encoder

  $\mathcal{A}=\langle\{a, b\},\{0,1\},\{01,10,11\}, \delta, \gamma, a\rangle$

  

  $\begin{array}{c|cc}\delta & 0 & 1 \\\hline a & a & b \\b & b & a\end{array}$ Zustand $\begin{array}{l|cc}\gamma & 0 & 1 \\\hline a & 01 & 10 \\b & 10 & 11\end{array}$ Ausgabe

  $\begin{array}{rllllllllllll}w: & \varepsilon & 0 & 1 & 00 & 10 & 01 & 11 & 000 & 100 & \cdots \\\hline[\mathcal{A}](w): & \varepsilon & 01 & 10 & 0101 & 1010 & 0110 & 1011 & 010101 & 101010 & \cdots\end{array}$

Moore-Automat

Art von Transducer (technisch gesehen aber nicht), deterministisch

Automat beschrieben durch $\mathcal{A}=\left\langle Q, \Sigma, \Gamma, \delta, \gamma, q_{0}\right\rangle$

$\text { Г }$output alphabet

$\gamma: Q \mapsto \Gamma$output function(bei Mealy:$\gamma: Q \times \Sigma \mapsto \Gamma$)

Erweiterte Ausgabefunktion (auch für Leerwort)

$\gamma^{*}: Q \times \Sigma^{*} \mapsto \Gamma^{*}$

$\forall q \in Q, s \in \Sigma, w \in \Sigma^{*}:$

Übersetzungsfunktion (gleich wie Mealy)

$[\mathcal{A}](w)=\gamma^{*}\left(q_{0}, w\right)$

$[\mathcal{A}]: \Sigma^{*} \mapsto \Gamma^{*}$

Beispiel:

• (1:2)-(0,1)-RLL Encoder

  $\mathcal{A}=\langle\{a, b\},\{0,1\},\{01,10,11\}, \delta, \gamma, a\rangle$bei Mealy

  $\mathcal{A}=\left\langle\left\{a_{1}, a_{2}, b\right\},\{0,1\},\{01,10,11\}, \delta, \gamma, a\right\rangle$

  

  $\begin{array}{c|cc}\delta & 0 & 1 \\\hline a_{1} & a_{1} & b \\a_{2} & a_{1} & b \\b & b & a_{2}\end{array}$$\begin{array}{c|c}\gamma & \\\hline a_{1} & 01 \\a_{2} & 11 \\b & 10\end{array}$

Büchi-Automaten

Deterministisch

Automat beschrieben durch $\mathcal{A}=\left\langle Q, \Sigma, \delta, q_{0}, F\right\rangle$(alles gleich wie in DEAs definiert)

Akzeptanz von Wörtern

Wort $s_{1} s_{2} s_{3} \cdots \in \sum^\omega$ wird akzeptiert wenn es Zustände $q_{0}, q_{1}, q_{2}, q_{3}, \cdots \in Q$ gibt, sodass

• $q_{0} \in Q$ ist Startzustand

• $\forall i \in \N: \delta\left(q_{i-1}, s_{i}\right)=q_{i}$

• $\lim_{i\to\infty}$ sodass irgendwann $q_{i} \in F$(Endzustand ist ein "guter Zustand", kein Deadlock)

Akzeptierte/Generierte Sprache

$\mathcal{L}(\mathcal{A})=\left\{w \in \Sigma^{\omega} \mid w \text { wird von } \mathcal{A} \text { akzeptiert }\right\}$

Beispiel:

Anwendung: in Programmen die liveliness property feststellen - Programm darf nicht absterben

• Faire Verkehrsampel

  Es werden die wörter aus $\{\texttt{a}, \ldots, \texttt{h}\}^{\omega}$ akzeptiert bei denen es immer wieder grün wird.

  

Nicht-Deterministisch

Automat beschrieben durch $\mathcal{A}=\langle Q, \Sigma, \delta, I, F\rangle$

$I \subseteq Q$ Anfangszustände

$\delta \subseteq Q \times \Sigma \times Q$ Übergangsrelation

Akzeptanz von Wörtern

Wort $s_{1} s_{2} s_{3} \cdots \in \Sigma^\omega$ wird akzeptiert wenn es Zustände $q_{0}, q_{1}, q_{2}, q_{3}, \cdots \in Q$ gibt, sodass

Akzeptierte/Generierte Sprache

$\mathcal{L}(\mathcal{A})=\left\{w \in \Sigma^{\omega} \mid w \text { wird von } \mathcal{A} \text { akzeptiert }\right\}$

Beispiel:

• Nur endlich viele 1er

  Ein Büchi-Automat, der genau jene ω-Wörter über {0, 1} akzeptiert, die nur eine endliche Anzahl an 1ern enthalten.

  (wird nur von deterministischen akzeptiert)

  

Modellierung