Hasso-Plattner-Institut
  
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Endliche Automaten

Autor: Ralf Rothenberger

In dieser Unit wirst du endliche Automaten kennenlernen. Endliche Automaten stellen ein sehr einfaches Berechnungsmodell zur Lösung bestimmter Entscheidungsprobleme dar. Wie schon Turingmaschinen können endliche Automaten 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

Turingmaschinen und formale Sprachen solltest du schon aus der Vorlesung oder aus der Unit über Turingmaschinen kennen. Ein deterministischer endlicher Automat, kurz DFA (vom englischen deterministic finite automaton) ist nichts anderes als eine eingeschränkte Turinmaschine. Im Gegensatz zur Turingmaschine besitzt der DFA keinen Schreibkopf und kein Speicherband. Insbesondere ist es dadurch nicht möglich, Ausgaben zu kodieren. Der DFA kann eine Eingabe lediglich Zeichen für Zeichen lesen und sie dann entweder akzeptieren oder verwerfen.

Lesekopf und Steuereinheit eines DFAs

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 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\)

Beispiel eines Automatengraphen

Wir halten fest: Zustände sind als Knoten dargestellt. Nichtakzeptierende Zustände \(q_i\in Q\setminus F\) werden mit einfacher Umrandung dargestellt.

Darstellung von Zuständen als Knoten

Akzeptierende Zustände \(q_i\in F\) werden mit doppelter Umrandung dargestellt.

Darstellung akzeptierender Zustände

Der Startzustand wird mit einem eingehenden Pfeil, der aus dem Nichts kommt, markiert.

Darstellung des Startzustands

Zustandsübergänge \(\delta(q_i,a)=q_j\) mit \(q_i,q_j\in Q\) und \(a\in\Sigma\) werden als gerichtete Pfeilen von Knoten \(q_i\) zu Knoten \(q_j\) mit Beschriftung \(a\) dargestellt.

Darstellung von Zustandsübergängen

Beim DFA geht für jedes Zeichen \(a\in\Sigma\) genau ein mit \(a\) markierter 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.

Übung: Formalisiere diesen Automatengraphen

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:

  1. \(r_0 = q_0\)
  2. \(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

  1. \(\hat\delta(q,\varepsilon) = q\)
  2. \(\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\in \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?

Übung: Formalisiere diesen Automatengraphen

Nichtdeterministische Endliche Automaten

Du weißt nun, was deterministische endliche Automaten sind und wie sie funktionieren. Als Nächstes wirst du eine Verallgemeinerung dieser Automaten kennenlernen. Genauso wie sich deterministische Turingmaschinen zu nichtdeterministischen verallgemeinern lassen, lassen sich auch deterministische endliche Automaten zu nichtdeterministischen endlichen Automaten, kurz 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\}\)

Beispiel eines Automatengraphen

Wir halten fest: Die Überführung zwischen formaler Definition und graphischer Darstellung funktioniert dabei genauso wie beim DFA. Die einzigen Unterschiede sind die folgenden:

  1. Es kann nun mehrere mit einem eingehenden Pfeil markierte Startzustände geben.
  2. 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 oder aber gar kein mit dem gleichen Zeichen markierter Pfeile ausgeht.

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.

Übung: Formalisiere diesen Automatengraphen

Arbeitsweise

Für einen NFA \(N = (Q,\Sigma,\Delta,S,F)\) und ein Eingabewort \(w=w_1,\ldots,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:

  1. \(r_0 \in S\)
  2. \(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 Berechnungen geben, die alle parallel ausgeführt werden. 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

  1. \(\tilde\Delta(K,\varepsilon) = K\)
  2. \(\tilde\Delta(K,wa) = \bigcup_{q \in \tilde\Delta(K,w)}\Delta(q,a)\)
Intuitiv ausgedrück 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?

Übung: Formalisiere diesen Automatengraphen

Was haben wir gelernt?

  1. Die Darstellung als Automatengraph ist häufig kompakter und übersichtlicher als die formale Definition.
  2. Aus dem Automatengraphen können wir deren formale Definition herleiten und umgekehrt.
  3. Wir haben die Arbeitsweise von DFAs und NFAs kennengelernt.
  4. Die Klasse der regulären Sprachen enthält genau die Sprachen, für die wir einen DFA definieren können.