· 

NFA konstruieren (skizzieren)

1. Einführung

Wie ist ein nicht deterministischer endlicher Automat (kurz NFA bzw. NEA) definiert? Mathematisch betrachtet ist ein NFA ein Quintupel \((Q,\Sigma,\Delta,S,F)\).
  • \(Q\) ist eine endliche Zustandsmenge, d. h. \(|Q|\lt\infty\). Dort sind die Zustände des NFAs enthalten.
  • \(\Sigma\) ist das Alphabet, also die Zeichen, die im Automaten gelesen werden können. Auch das Alphabet ist endlich.
  • \(\Delta\) ist eine Zustandsübergangsfunktion, die einen Zustand, sowie ein Zeichen erhält und als Ergebnis eine Zustandmenge ergibt, die in der Potenzmenge der Zustandsmenge liegt.
  • \(S\) ist der Startzustand, der aus der Menge aller Zustände im Automaten stammt.
  • \(F\) ist ebenfalls eine Teilmenge der Zustandsmenge. Diese ist die Menge der Endzustände bzw. der akzeptierenden Zustände.

2. Beispiel

Wir betrachten die folgende formale Definition eines NFAs:

$$𝑁𝐹𝐴=( 𝑄=\{𝑄_1,𝑄_2,𝑄_3,𝑄_4 \}, \Sigma=\{0,1\}, \Delta(𝑄_1,0)=\{𝑄_2,𝑄_4 \} \Delta(𝑄_1,1)=\{𝑄_2 \} \Delta(𝑄_2,0)=\{𝑄_2 \} \Delta(𝑄_2,1)=\{𝑄_2,𝑄_3 \} \Delta(𝑄_3,0)=\{𝑄_1,𝑄_3 \} \Delta(𝑄_3,1)=\{𝑄_4 \} \Delta(𝑄_4,0)=\{ \} \Delta(𝑄_4,1)=\{ \}, 𝑆=𝑄_1, 𝐹=\{𝑄_1,𝑄_3 \} ) $$

Aus dieser formalen Definition werden wir nun schrittweise den NFA skizzieren.

Zuerst betrachten wir die endliche Zustandsmenge. Diese besitzt vier Elemente, d. h. der Automat hat insgesamt vier Zustände, nämlich \(Q_1,Q_2,Q_3\) und \(Q_4\).
Das Alphabet \(\Sigma\) enthält zwei Zeichen, nämlich \(0\) und \(1\). Diese (und nur diese) werden an die Übergangspfeile zwischen den Zuständen des Automaten geschrieben.
Als nächstes ist die Zustandsübergangsfunktion an der Reihe. Diese gibt an, welche Pfeile zwischen den einzelnen Zuständen existieren und welche Zeichen aus \(\Sigma\) an den Pfeilen stehen:
  • Wenn du dich in \(Q_1\) befindest und eine \(0\) liest, dann kommst du entweder in den Zustand \(Q_2\) oder in den Zustand \(Q_4\). Insgesamt kommst du also in die Zustandsmenge \(\{Q_2,Q_4\}\)
  • Wenn du dich in \(Q_1\) befindest und eine \(1\) liest, dann kommst du in den Zustand \(\{Q_2\}\). Auch dann, wenn du nur einen Zustand mit einem bestimmten Zeichen erreichen kannst, verwendest du die Mengenschreibweise, da die Zustandsübergangsfunktion (wie anfangs erwähnt) in die Potenzmenge der Zustandsmenge abbildet.
  • Wenn du dich in \(Q_2\) befindest und eine \(0\) liest, dann kommst in den Zustand \(\{Q_2\}\).
  • Wenn du dich in \(Q_2\) befindest und eine \(1\) liest, dann kommst du entweder in den Zustand \(Q_2\) oder in den Zustand \(Q_3\). Insgesamt kommst du also in die Zustandsmenge \(\{Q_2,Q_3\}\)
  • Wenn du dich in \(Q_3\) befindest und eine \(0\) liest, dann kommst du entweder in den Zustand \(Q_1\) oder in den Zustand \(Q_3\). Insgesamt kommst du also in die Zustandsmenge \(\{Q_1,Q_3\}\)
  • Wenn du dich in \(Q_3\) befindest und eine \(1\) liest, dann kommst in den Zustand \(\{Q_4\}\).
  • Wenn du dich in \(Q_4\) befindest und eine \(0\) liest, dann kommst du in die leere Zustandsmenge. Was heißt das? Das bedeutet, dieser Pfeil führt nirgendwo hin und wird deshalb nicht gezeichnet.
  • Wenn du dich in \(Q_4\) befindest und eine \(1\) liest, dann kommst du ebenfalls in die leere Zustandsmenge. D. h. vom Zustand \(Q_4\) führt kein Pfeil in einen anderen Zustand
Der Startzustand \(S\) ist \(Q_1\). D. h. in den Zustand \(Q_1\) führt von außen ein Pfeil.
\(F\) ist die Menge der akzeptierenden Zustände. Diese kennzeichnest du, indem du in den jeweiligen Zustand einen weiteren Kreis zeichnest. Die Menge der akzeptierenden Zustände besteht aus \(Q_1\) und \(Q_3\).