In dieser Unit wirst du endliche Automaten kennenlernen.
Endliche Automaten stellen ein sehr einfaches Berechnungsmodell zur Lösung bestimmter Entscheidungsprobleme dar.
Sie können uns helfen zu verstehen, wo die Grenzen der Berechenbarkeit verschieden mächtiger Rechenmodelle liegen.
Darüber hinaus finden endliche Automaten auch praktische Anwendung, z. B. im Compilerbau und in der Prozesssteuerung.
Deterministische Endliche Automaten
Ein deterministischer endlicher Automat, kurz DEA oder DFA (vom englischen deterministic finite automaton) ist eine sehr einfache Maschine, die eine Eingabe Zeichen für Zeichen liest und sie dann entweder akzeptiert oder verwirft.
Zu jedem Zeitpunkt befindet sich die Maschine in einem bestimmten Zustand, den sie abhängig vom gelesenen Zeichen wechseln kann.
Formale Definition
Ein deterministischer endlicher Automat \(M\) ist ein 5-Tupel \(M = (Q,\Sigma,\delta,q_0,F)\), sodass gilt
\(Q\) ist eine nichtleere, endliche Menge von Zuständen,
\(\Sigma\) ist das nichtleere, endliche Eingabealphabet,
\(\delta\colon Q \times \Sigma \to Q\) ist die totale Überführungsfunktion,
\(q_0 \in Q\) ist der Startzustand,
\(F \subseteq Q\) ist die Menge der akzeptierenden Zustände.
Alternativ können wir DFAs auch als Automatengraphen darstellen.
Die Darstellung als Automatengraph ist in vielen Fällen kompakter und übersichtlicher als die formale Definition.
Ein Beispiel:
\(M = (Q,\Sigma,\delta,q_0,F)\) mit
\(Q=\left\{q_0,q_1,q_2,q_3\right\}\),
\(\Sigma=\left\{0,1\right\}\),
\(F=\left\{q_1, q_3\right\}\)
und \(\delta\) wie folgt:
\(\delta\)
\(0\)
\(1\)
\(q_0\)
\(q_3\)
\(q_2\)
\(q_1\)
\(q_3\)
\(q_2\)
\(q_2\)
\(q_3\)
\(q_1\)
\(q_3\)
\(q_2\)
\(q_3\)
Wir halten fest:
Zustände sind als Knoten dargestellt. Nichtakzeptierende Zustände \(q_i\in Q\setminus F\) werden mit einfacher Umrandung dargestellt.
Akzeptierende Zustände \(q_i\in F\) werden mit doppelter Umrandung dargestellt.
Der Startzustand wird mit einem eingehenden Pfeil, der aus dem Nichts kommt, markiert.
Zustandsübergänge \(\delta(q_i,a)=q_j\) mit \(q_i,q_j\in Q\) und \(a\in\Sigma\) werden als gerichtete Pfeile von Knoten \(q_i\) zu Knoten \(q_j\) mit Beschriftung \(a\) dargestellt.
Beim DFA geht für jedes Zeichen \(a\in\Sigma\) genau einen mit \(a\) markierten Pfeil von jedem Zustandsknoten aus.
Natürlich lässt sich aus der grafischen Darstellung eines DFAs auch wieder dessen formale Definition herleiten.
Probiere es doch einmal an dem folgenden Beispiel aus.
Übung:
Formalisiere den folgenden DFA \(M\), der als Automatengraph gegeben ist.
\(M = (Q,\Sigma,\delta,q_0,F)\) mit
\(Q=\left\{q_0,q_1,q_2\right\}\),
\(\Sigma=\left\{0,1\right\}\),
\(F=\left\{q_1\right\}\)
und
\(\delta\)
\(0\)
\(1\)
\(q_0\)
\(q_2\)
\(q_1\)
\(q_1\)
\(q_1\)
\(q_1\)
\(q_2\)
\(q_2\)
\(q_2\)
Arbeitsweise
Du weißt nun, wie ein deterministischer endlicher Automat definiert ist und wie man ihn darstellen kann.
Als Nächstes erfährst du, was DFAs überhaupt tun.
Nehmen wir einmal an, unser DFA \(M = (Q,\Sigma,\delta,q_0,F)\) bekommt ein Eingabewort \(w = w_1\dots w_n \in \Sigma^*\).
Achtung: Wir erlauben auch das Wort ohne Zeichen als Eingabe. Dieses bezeichnen wir als das leere Wort und versehen es mit dem Symbol \(\varepsilon\).
\(M\) startet im Zustand \(q_0\) und liest nun in jedem Schritt genau ein Zeichen der Eingabe, beginnend bei \(w_1\).
Dabei ändert sich der Zustand des Automaten.
Die Änderung des Zustandes ist durch die Zustandsübergangsfunktion \(\delta\) definiert, die, abhängig vom aktuellen Zustand des Automaten und vom gerade gelesenen Eingabezeichen, den neuen Zustand des Automaten angibt.
Der DFA stoppt, sobald die Eingabe vollständig gelesen und der Zustandsübergang für das letzte Zeichen ausgeführt wurde.
Dadurch ergibt sich eine Zustandsfolge \(r_0,r_1,\ldots,r_n\).
Diese wird auch als Berechnung von \(M\) auf Eingabe \(w\) bezeichnet, kurz \(M(w)\).
Formal ist \(M(w)=(r_0, r_1, \ldots, r_n)\) wie folgt rekursiv definiert:
\(r_0 = q_0\)
\(r_{i}=\delta(r_{i-1},w_i)\) für \(i=1,\ldots,n\)
Da DFAs deterministisch arbeiten, gibt es in jedem Schritt genau einen Folgezustand.
Insbesondere bedeutet das, dass jede Berechnung auf einem Eingabewort in einem eindeutig bestimmten Zustand endet.
Ist dieser Zustand akzeptierend, sagen wir \(M\) akzeptiert \(w\).
Andernfalls sagen wir \(M\) verwirft \(w\).
An dem folgenden Beispiel kannst du die Berechnung eines DFA einmal selbst nachvollziehen.
Wähle, ob das nächste gelesene Zeichen der Eingabe eine 0 oder eine 1 ist oder ob der Automat in den Startzustand zurückgesetzt werden soll.
Eingabe:
wird akzeptiert.
Zu jedem DFA \(M\) gehört genau eine von \(M\) akzeptierte Sprache \(L(M)\).
Diese besteht aus allen Eingabeworten, die von \(M\) akzeptiert werden, d. h.
\[L(M) = \{w \in \Sigma^* \mid \text{ $M$ akzeptiert $w$}\}.\]
Für die Analyse von DFAs führen wir noch eine weitere nützliche Notation ein. Für einen DFA \(M = (Q,\Sigma,\delta,q_0,F)\) sei die erweiterte Zustandsübergangsfunktion \(\hat\delta\colon Q\times \Sigma^* \to Q\) induktiv wie folgt definiert:
Für \(q \in Q\), \(w \in \Sigma^*\) und \(a \in \Sigma\) sei
\(\hat\delta(q,\varepsilon) = q\)
\(\hat\delta(q,wa) = \delta(\hat\delta(q,w),a)\).
Das heißt, \(\hat\delta(q,wa)\) gibt den Zustand aus, in dem sich der DFA \(M\) nach Abarbeitung des Wortes \(wa\) ausgehend vom Zustand \(q\) befindet. Damit gilt
\[L(M) = \{w \in \Sigma^* \mid \hat\delta(q_0,w) \in F\}\]
bzw. für alle \(w\in \Sigma^*\) gilt
\[w \in L(M) \iff \hat\delta(q_0,w) \in F.\]
Die neue Notation ist nützlich, um zu beweisen, dass ein DFA \(M\) eine bestimmte Sprache \(L\) akzeptiert.
Wir nennen eine Sprache \(L\subseteq \Sigma^*\) regulär, wenn es einen DFA \(M\) gibt, für den \(L(M)=L\) gilt.
Die Menge aller regulärer Sprachen ist die Sprachklasse \(REG\). D. h.
\[\textbf{REG} = \{L \subseteq \Sigma^* \mid \text{es gibt einen DFA $M$ mit $L(M) = L$}\}.\]
Übung:
Welche Sprache akzeptiert der folgende DFA?
Der Automat akzeptiert alle Wörter, deren vorletztes Zeichen eine 1 ist.
Nichtdeterministische Endliche Automaten
Du weißt nun, was deterministische endliche Automaten sind und wie sie funktionieren.
Deterministische endliche Automaten lassen sich nun zu nichtdeterministischen endlichen Automaten, kurz NEA oder NFAs (vom englischen non-deterministic finite automaton) verallgemeinern.
Obwohl deterministische und nichtdeterministische endliche Automaten gleich mächtig sind, sind NFAs leichter zu handhaben und erleichtern oft die Konstruktion von Automaten für bestimmte Sprachen.
Formale Definition
Ein nichtdeterministischer endlicher Automat \(N\) ist ein 5-Tupel \(N = (Q,\Sigma,\Delta,S,F)\), sodass gilt
\(Q\) ist eine nichtleere, endliche Menge von Zuständen,
\(\Sigma\) ist das Eingabealphabet,
\(\Delta\colon Q \times \Sigma \to \mathcal{P}(Q)\) ist die Überführungsfunktion,
\(S \subseteq Q\) ist die Menge der Startzustände,
\(F \subseteq Q\) ist die Menge der akzeptierenden Zustände.
Der Hauptunterschied zum DFA ist, dass NFAs mehrere Startzustände haben können und dass die Überführungsfunktion in die Potenzmenge aller Zustände abbildet.
Zur Erinnerung: Die Potenzmenge von \(Q\), kurz \(\mathcal{P}(Q)\), ist die Menge aller Teilmengen der Menge \(Q\).
Damit kann es für eine Kombination aus aktuellem Zustand und aktuellem Eingabezeichen mehrere Folgezustände oder auch gar keinen Folgezustand (falls auf \(\emptyset\) abgebildet wird) geben.
Auch NFAs können als Automatengraphen dargestellt werden. Ein Beispiel:
\(N = (Q,\Sigma,\Delta,S,F)\) mit
\(Q=\left\{q_0,q_1,q_2,q_3\right\}\),
\(\Sigma=\left\{0,1\right\}\),
\(S=\left\{q_0,q_1\right\}\),
\(F=\left\{q_1, q_3\right\}\)
und \(\Delta\) wie folgt:
\(\Delta\)
\(0\)
\(1\)
\(q_0\)
\(\left\{q_2,q_3\right\}\)
\(\emptyset\)
\(q_1\)
\(\left\{q_3\right\}\)
\(\left\{q_2\right\}\)
\(q_2\)
\(\emptyset\)
\(\emptyset\)
\(q_3\)
\(\left\{q_3\right\}\)
\(\left\{q_2,q_3\right\}\)
Wir halten fest: Die Überführung zwischen formaler Definition und graphischer Darstellung funktioniert dabei genauso wie beim DFA.
Die einzigen Unterschiede sind die folgenden:
Es kann nun mehrere mit einem eingehenden Pfeil markierte Startzustände geben.
Für einen Zustand \(q_i\in Q\) und ein Eingabezeichen \(a\in\Sigma\) muss nun für jeden Zustand \(q_j \in \Delta(q_i,a)\) ein mit \(a\) markierter Pfeil von \(q_i\) nach \(q_j\) gezeichnet werden.
Es kann also vorkommen, dass von einem Zustand mehrere mit dem gleichen Zeichen markierte Pfeile ausgehen - oder auch gar keiner.
Auch beim NFA können wir aus der grafischen Darstellung wieder die formale Definition herleiten.
Probiere es doch einmal an dem folgenden Beispiel aus.
Übung:
Formalisiere den folgenden NFA \(N\), der als Automatengraph gegeben ist.
\(N = (Q,\Sigma,\Delta,S,F)\) mit
\(Q=\left\{q_0,q_1,q_2\right\}\),
\(\Sigma=\left\{0,1\right\}\),
\(S=\left\{q_0,q_2\right\}\)
\(F=\left\{q_2\right\}\)
und
\(\Delta\)
\(0\)
\(1\)
\(q_0\)
\(\left\{q_0\right\}\)
\(\left\{q_0, q_1\right\}\)
\(q_1\)
\(\left\{q_2\right\}\)
\(\left\{q_2\right\}\)
\(q_2\)
\(\emptyset\)
\(\emptyset\)
Arbeitsweise
Für einen NFA \(N = (Q,\Sigma,\Delta,S,F)\) und ein Eingabewort \(w=w_1\dots w_n\) ist eine Berechnung von \(N\) auf \(w\), kurz \(N(w)\), eine Folge \(r_0,r_1,\ldots,r_n\) von Zuständen mit den folgenden Eigenschaften:
\(r_0 \in S\)
\(r_{i}\in\Delta(r_{i-1},w_i)\) für \(i=1,\ldots,n\)
In einem NFA kann es somit für eine Eingabe \(w\) mehrere mögliche Berechnungen geben.
Außerdem kann es auch passieren, dass ein NFA während der Berechnung stecken bleibt, d. h., es kann passieren, dass es für den aktuellen Zustand und das aktuelle Eingabezeichen keinen Folgezustand gibt und die Berechnung somit an dieser Stelle hält, ohne zu akzeptieren.
Wir sagen \(N\) akzeptiert \(w\), falls es mindestens eine Berechnung \(N(w)\) gibt, die in einem akzeptierenden Zustand endet, ohne irgendwann einmal stecken zu bleiben.
Andernfalls sagen wir \(N\) verwirft \(w\).
An dem folgenden Beispiel kannst du die Berechnung eines NFAs selbst nachvollziehen. Markiert sind jeweils alle im aktuellen Schritt erreichbaren Zustände.
Wähle, ob das nächste gelesene Zeichen der Eingabe eine 0 oder eine 1 ist oder ob der Automat in den Startzustand zurückgesetzt werden soll.
Eingabe:
wird akzeptiert.
Für einen NFA \(N\) definieren wir die von \(N\) akzeptierte Sprache \(L(M)\) wie beim DFA auch als die Menge aller von \(N\) akzeptierten Eingabewörter, d. h.
\[L(N) = \{w \in \Sigma^* \mid \text{ $N$ akzeptiert $w$}\}.\]
Für die Analyse von NFAs führen wir, ähnlich wie bei den DFAs, eine neue Funktion ein. Sei \(N = (Q,\Sigma,\Delta,S,F)\). Wir definieren die Funktion \(\tilde\Delta\colon \mathcal{P}(Q)\times \Sigma^* \to \mathcal{P}(Q)\) wie folgt induktiv:
Für \(K \in \mathcal{P}(Q)\), \(w \in \Sigma^*\) und \(a \in \Sigma\) sei
Intuitiv ausgedrückt ist \(\tilde\Delta(K,w)\) die Menge von Zuständen, die der NFA \(N\) nach Abarbeitung des Wortes \(w\) ausgehend von Zustandsmenge \(K\) erreichen kann.
Somit gilt
\[ L(N) = \left\{w \in \Sigma^* \mid \tilde\Delta(S,w) \cap F \neq \emptyset\right\}\]
und, äquivalent dazu,
\[\textrm{für alle $w\in \Sigma^*$ gilt: }w \in L(N) \iff \tilde\Delta(S,w) \cap F \neq \emptyset.\]
Übung:
Welche Sprache akzeptiert der folgende NFA?
Der Automat akzeptiert alle Wörter, die 00 enthalten und auf 01 enden.
\(\varepsilon\)-Übergänge
Als nützliche Erweiterung können wir in der Übergangsfunktion auch sogenannte \(\varepsilon\)-Übergänge erlauben.
Diese ermöglichen einen spontanen Zustandswechsel ohne ein Eingabezeichen zu lesen.
Formal gesehen erweitert dies die Berechnung eines NFA auf eine Folge von Zuständen, sodass der erste Zustand ein Startzustand ist, und der jeweils nächste Zustand entweder über einen Übergang mit einem Zeichen des Eingabeworts oder einen \(\varepsilon\)-Übergang erreicht wird.
Diese zusätzlichen \(\varepsilon\)-Übergänge ermöglichen eine komfortablere Beschreibung von NFAs für viele Einsatzzwecke, ohne dabei das Berechnungsmodell mächtiger zu machen.
Was haben wir gelernt?
Die Darstellung als Automatengraph ist häufig kompakter und übersichtlicher als die formale Definition.
Aus dem Automatengraphen können wir dessen formale Definition herleiten und umgekehrt.
Wir haben die Arbeitsweise von DFAs und NFAs kennengelernt.
Die Klasse der regulären Sprachen enthält genau die Sprachen, für die wir einen DFA definieren können.
Algorithm Engineering
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.
