Nichtdeterministischer endlicher Automat

Ein nichtdeterministischer endlicher Automat (NEA) darf bei einem Zeichen mehrere Wege offenhalten. Das macht viele Modelle kürzer und übersichtlicher.

Definition

Ein nichtdeterministischer endlicher Automat (kurz NEA) ist ein 5-Tupel [math]\displaystyle{ A = (Q; \Sigma; \delta; q_0; F) }[/math]:

  • [math]\displaystyle{ Q }[/math]: endliche, nicht leere Menge der Zustände
  • [math]\displaystyle{ \Sigma }[/math]: Eingabealphabet
  • [math]\displaystyle{ \delta: Q \times \Sigma \to \mathcal{P}(Q) }[/math]: Übergangsfunktion
  • [math]\displaystyle{ q_0 \in Q }[/math]: Startzustand
  • [math]\displaystyle{ F \subseteq Q }[/math]: Menge der Endzustände

Was ein Tupel ist und was [math]\displaystyle{ Q \times \Sigma }[/math] bedeutet, erklärt die Definition des DEA. Der NEA unterscheidet sich vom DEA nur in der Übergangsfunktion: Sie liefert keinen einzelnen Zustand, sondern eine Menge von Zuständen, die Menge der Folgezustände (kurz Folgemenge). [math]\displaystyle{ \mathcal{P}(Q) }[/math] ist die Potenzmenge von [math]\displaystyle{ Q }[/math], die Menge aller Teilmengen von [math]\displaystyle{ Q }[/math]. Zur Potenzmenge gehören auch die leere Menge [math]\displaystyle{ \emptyset }[/math] und [math]\displaystyle{ Q }[/math] selbst.

Zu einem Zustand und einem Zeichen gibt es deshalb keinen, einen oder mehrere Folgezustände. Diese Wahlmöglichkeit heißt Nichtdeterminismus. Der Wert [math]\displaystyle{ \delta(q; a) = \emptyset }[/math] bedeutet: kein Folgezustand.

Manche Aufgaben nennen statt der Übergangsfunktion eine Übergangsrelation. Das ist die Menge aller Tripel [math]\displaystyle{ (p; a; q) }[/math], bei denen der Automat im Zustand [math]\displaystyle{ p }[/math] mit dem Zeichen [math]\displaystyle{ a }[/math] nach [math]\displaystyle{ q }[/math] wechseln kann. Ein Tripel [math]\displaystyle{ (p; a; q) }[/math] gehört genau dann zur Übergangsrelation, wenn [math]\displaystyle{ q \in \delta(p; a) }[/math] gilt. Beide Schreibweisen beschreiben denselben Automaten.

Übergangsgraph und Übergangstabelle entsprechen den Darstellungsformen des DEA. Im Graphen gehen von einem Zustand für dasselbe Zeichen kein, ein oder mehrere Pfeile aus. In der Tabelle steht in jeder Zelle eine Menge von Folgezuständen, ein Strich steht für die leere Menge, also für „kein Folgezustand“. Der Pfeil [math]\displaystyle{ \rightarrow }[/math] markiert den Startzustand, der hochgestellte Stern [math]\displaystyle{ {}^* }[/math] die Endzustände.

Wortakzeptanz

Ein Pfad für ein Wort ist eine Zustandsfolge, die im Startzustand [math]\displaystyle{ q_0 }[/math] beginnt. Mit jedem Zeichen des Wortes kommt ein Zustand hinzu: einer der Folgezustände, die der zuletzt erreichte Zustand für dieses Zeichen hat. Weil es mehrere Folgezustände geben kann, hat ein Wort oft mehrere Pfade. Ein Pfad bricht ab, wenn der zuletzt erreichte Zustand für das nächste Zeichen keinen Folgezustand hat.

Ein Pfad wird mit beschrifteten Pfeilen geschrieben. Beim NEA bedeutet [math]\displaystyle{ p \xrightarrow{a} q }[/math]: Der Zustand [math]\displaystyle{ q }[/math] ist einer der Folgezustände von [math]\displaystyle{ p }[/math] für das Zeichen [math]\displaystyle{ a }[/math], also [math]\displaystyle{ q \in \delta(p; a) }[/math].

Ein NEA akzeptiert ein Wort, wenn mindestens ein Pfad das ganze Wort liest und in einem Endzustand endet. Pfade, die abbrechen oder nicht in einem Endzustand enden, sprechen nicht dagegen. Abgelehnt wird ein Wort erst, wenn kein einziger Pfad das ganze Wort liest und in einem Endzustand endet.

Anschaulich verfolgt der NEA alle Pfade gleichzeitig. Die akzeptierte Sprache [math]\displaystyle{ L(A) }[/math] besteht aus allen Wörtern, die der NEA akzeptiert.

Unterschied zum DEA

Merkmal DEA NEA
Folgezustände höchstens einer je Zustand und Zeichen, im vollständigen DEA genau einer keiner, einer oder mehrere
Fehlender Übergang im vollständigen DEA nicht möglich, dort führt jedes Zeichen in einen Folgezustand, notfalls in den Fehlerzustand [math]\displaystyle{ q_F }[/math]. Im unvollständigen DEA bricht der Lauf ab, und das Wort ist abgelehnt. erlaubt: Der Pfad bricht dort ab, andere Pfade laufen weiter.
Akzeptanz der eine Lauf liest das ganze Wort und endet in einem Endzustand mindestens ein Pfad liest das ganze Wort und endet in einem Endzustand
Prüfaufwand ein Lauf je Wort mehrere Pfade je Wort, im ungünstigen Fall müssen alle verfolgt werden

Jeder DEA ist auch ein NEA, bei dem jede Menge von Folgezuständen höchstens ein Element hat. Beide Automatenarten erkennen dieselben Sprachen, siehe Gleichwertigkeit von NEA und DEA.

ε-NEA

Ein [math]\displaystyle{ \varepsilon }[/math]-NEA hat zusätzlich Übergänge, die kein Zeichen lesen. Sie heißen [math]\displaystyle{ \varepsilon }[/math]-Übergänge, denn [math]\displaystyle{ \varepsilon }[/math] steht für das leere Wort. Ein [math]\displaystyle{ \varepsilon }[/math]-Übergang lässt den Automaten den Zustand wechseln, ohne dass das Wort weitergelesen wird. Die Übergangsfunktion lautet:

[math]\displaystyle{ \delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q) }[/math]

[math]\displaystyle{ \Sigma \cup \{\varepsilon\} }[/math] enthält die Zeichen des Alphabets und zusätzlich [math]\displaystyle{ \varepsilon }[/math]: Ein Übergang ist entweder mit einem Zeichen oder mit [math]\displaystyle{ \varepsilon }[/math] beschriftet. In der Tabelle steht für die [math]\displaystyle{ \varepsilon }[/math]-Übergänge eine eigene Spalte [math]\displaystyle{ \varepsilon }[/math].

Mit [math]\displaystyle{ \varepsilon }[/math]-Übergängen lassen sich Teilautomaten verbinden, die je einen Teil einer Regel prüfen. Der Automat wechselt von einem Teil in den nächsten oder wählt am Anfang zwischen mehreren Teilen, ohne dass dafür ein Zeichen im Wort stehen muss. Jeder Teil kann einzeln entworfen werden, das macht den Entwurf übersichtlich.

Ein [math]\displaystyle{ \varepsilon }[/math]-NEA akzeptiert ein Wort, wenn mindestens ein Pfad vom Startzustand in einen Endzustand führt, auf dem die gelesenen Zeichen in ihrer Reihenfolge genau das Wort ergeben. [math]\displaystyle{ \varepsilon }[/math]-Übergänge dürfen dabei vor dem ersten Zeichen, zwischen zwei Zeichen und nach dem letzten Zeichen vorkommen, auch mehrere hintereinander.

Jeder [math]\displaystyle{ \varepsilon }[/math]-NEA lässt sich in einen NEA ohne [math]\displaystyle{ \varepsilon }[/math]-Übergänge und in einen DEA umwandeln, die dieselbe Sprache erkennen, siehe Umwandlung ε-NEA zu NEA und Umwandlung eines ε-NEA.

ε-Abschluss

Der [math]\displaystyle{ \varepsilon }[/math]-Abschluss [math]\displaystyle{ E(q) }[/math] (auch [math]\displaystyle{ \varepsilon }[/math]-Hülle) enthält den Zustand [math]\displaystyle{ q }[/math] selbst und alle Zustände, die von [math]\displaystyle{ q }[/math] nur über [math]\displaystyle{ \varepsilon }[/math]-Übergänge erreichbar sind. Mehrere [math]\displaystyle{ \varepsilon }[/math]-Übergänge hintereinander sind erlaubt. Für eine Menge [math]\displaystyle{ Z }[/math] von Zuständen ist [math]\displaystyle{ E(Z) }[/math] die Vereinigung aller [math]\displaystyle{ E(q) }[/math] mit [math]\displaystyle{ q \in Z }[/math]. Für die leere Menge gilt [math]\displaystyle{ E(\emptyset) = \emptyset }[/math].

Beispiele

Potenzmenge einer Zustandsmenge angeben

Gegeben ist die Zustandsmenge [math]\displaystyle{ Q = \{q_0; q_1\} }[/math]. Ihre Potenzmenge enthält alle Teilmengen von [math]\displaystyle{ Q }[/math]:

[math]\displaystyle{ \mathcal{P}(Q) = \{\emptyset; \{q_0\}; \{q_1\}; \{q_0; q_1\}\} }[/math]

Das sind [math]\displaystyle{ 2^2 = 4 }[/math] Mengen: die leere Menge, zwei Mengen mit einem Zustand und die Menge [math]\displaystyle{ Q }[/math] selbst. Jeder Wert der Übergangsfunktion eines NEA mit diesen Zuständen ist eine dieser vier Mengen. Bei drei Zuständen hat die Potenzmenge schon [math]\displaystyle{ 2^3 = 8 }[/math] Elemente, bei [math]\displaystyle{ n }[/math] Zuständen sind es [math]\displaystyle{ 2^n }[/math].

Spam-Filter als NEA modellieren

 
Spam-Filter als NEA

Ein Spam-Filter erkennt E-Mails, die die Zeichenfolge UML enthalten. Das Alphabet ist [math]\displaystyle{ \Sigma = \{U; M; L; x\} }[/math], dabei steht [math]\displaystyle{ x }[/math] für jedes andere Zeichen.

Die Idee des Automaten:

  • In [math]\displaystyle{ q_0 }[/math] bleibt der Automat bei jedem Zeichen. Bei jedem [math]\displaystyle{ U }[/math] vermutet er zusätzlich einen Anfang von UML und öffnet einen zweiten Weg nach [math]\displaystyle{ q_1 }[/math].
  • In [math]\displaystyle{ q_1 }[/math] wartet der Automat auf [math]\displaystyle{ M }[/math], in [math]\displaystyle{ q_2 }[/math] auf [math]\displaystyle{ L }[/math]. Jedes andere Zeichen lässt den Pfad dort abbrechen.
  • [math]\displaystyle{ q_3 }[/math] ist der Endzustand. Dort bleibt der Automat bei jedem weiteren Zeichen.

Als 5-Tupel [math]\displaystyle{ A = (Q; \Sigma; \delta; q_0; F) }[/math] hat der Automat die Zustandsmenge [math]\displaystyle{ Q = \{q_0; q_1; q_2; q_3\} }[/math], das Alphabet [math]\displaystyle{ \Sigma = \{U; M; L; x\} }[/math], den Startzustand [math]\displaystyle{ q_0 }[/math] und die Endzustandsmenge [math]\displaystyle{ F = \{q_3\} }[/math]. Die Übergangsfunktion [math]\displaystyle{ \delta }[/math] steht in der Übergangstabelle. Bei [math]\displaystyle{ U }[/math] in [math]\displaystyle{ q_0 }[/math] gibt es zwei Folgezustände: [math]\displaystyle{ \delta(q_0; U) = \{q_0; q_1\} }[/math]. Das ist der Nichtdeterminismus.

[math]\displaystyle{ \delta }[/math] [math]\displaystyle{ U }[/math] [math]\displaystyle{ M }[/math] [math]\displaystyle{ L }[/math] [math]\displaystyle{ x }[/math]
[math]\displaystyle{ \rightarrow q_0 }[/math] [math]\displaystyle{ \{q_0; q_1\} }[/math] [math]\displaystyle{ \{q_0\} }[/math] [math]\displaystyle{ \{q_0\} }[/math] [math]\displaystyle{ \{q_0\} }[/math]
[math]\displaystyle{ q_1 }[/math] – [math]\displaystyle{ \{q_2\} }[/math] – –
[math]\displaystyle{ q_2 }[/math] – – [math]\displaystyle{ \{q_3\} }[/math] –
[math]\displaystyle{ {}^*q_3 }[/math] [math]\displaystyle{ \{q_3\} }[/math] [math]\displaystyle{ \{q_3\} }[/math] [math]\displaystyle{ \{q_3\} }[/math] [math]\displaystyle{ \{q_3\} }[/math]

Die Nachricht [math]\displaystyle{ xUML }[/math] hat zwei Pfade:

  • [math]\displaystyle{ q_0 \xrightarrow{x} q_0 \xrightarrow{U} q_0 \xrightarrow{M} q_0 \xrightarrow{L} q_0 }[/math] (kein Endzustand)
  • [math]\displaystyle{ q_0 \xrightarrow{x} q_0 \xrightarrow{U} q_1 \xrightarrow{M} q_2 \xrightarrow{L} q_3 }[/math] (akzeptiert)

Der zweite Pfad liest das ganze Wort und endet im Endzustand [math]\displaystyle{ q_3 }[/math]. Mindestens ein Pfad ist erfolgreich, daher wird [math]\displaystyle{ xUML }[/math] akzeptiert. Der erste Pfad endet in [math]\displaystyle{ q_0 }[/math] und spricht nicht dagegen.

Abgelehntes Wort mit einem NEA prüfen

Der Spam-Filter aus dem vorigen Beispiel prüft die Nachricht [math]\displaystyle{ xUMx }[/math]. Sie hat ebenfalls zwei Pfade:

  • [math]\displaystyle{ q_0 \xrightarrow{x} q_0 \xrightarrow{U} q_0 \xrightarrow{M} q_0 \xrightarrow{x} q_0 }[/math] (kein Endzustand)
  • [math]\displaystyle{ q_0 \xrightarrow{x} q_0 \xrightarrow{U} q_1 \xrightarrow{M} q_2 }[/math] (bricht ab)

Der erste Pfad liest das ganze Wort, endet aber in [math]\displaystyle{ q_0 }[/math], und [math]\displaystyle{ q_0 }[/math] ist kein Endzustand. Der zweite Pfad erreicht [math]\displaystyle{ q_2 }[/math] und bricht dort ab, weil es in [math]\displaystyle{ q_2 }[/math] für [math]\displaystyle{ x }[/math] keinen Folgezustand gibt. Kein Pfad liest das ganze Wort und endet in einem Endzustand. Die Nachricht [math]\displaystyle{ xUMx }[/math] wird abgelehnt.

NEA entwerfen

 
NEA für das Wartungsmenü

Ein Kaffeeautomat hat die Tasten [math]\displaystyle{ K }[/math] (Kaffee) und [math]\displaystyle{ E }[/math] (Espresso). Sein Wartungsmenü öffnet sich, wenn eine Tastenfolge mit [math]\displaystyle{ KK }[/math] oder mit [math]\displaystyle{ KEK }[/math] beginnt. Alles danach wird im Menü verarbeitet und ist beliebig. Gesucht ist ein NEA über [math]\displaystyle{ \Sigma = \{K; E\} }[/math], der genau diese Tastenfolgen akzeptiert.

Schritt 1: Für jede Möglichkeit einen eigenen Weg anlegen. Beide Anfänge beginnen mit [math]\displaystyle{ K }[/math]. Der NEA muss sich nach dem ersten [math]\displaystyle{ K }[/math] nicht festlegen, er hält beide Wege offen:

  • Oberer Weg für [math]\displaystyle{ KK }[/math]: von [math]\displaystyle{ q_0 }[/math] mit [math]\displaystyle{ K }[/math] nach [math]\displaystyle{ q_1 }[/math], von dort mit [math]\displaystyle{ K }[/math] in den Endzustand [math]\displaystyle{ q_4 }[/math].
  • Unterer Weg für [math]\displaystyle{ KEK }[/math]: von [math]\displaystyle{ q_0 }[/math] mit [math]\displaystyle{ K }[/math] nach [math]\displaystyle{ q_2 }[/math], von [math]\displaystyle{ q_2 }[/math] mit [math]\displaystyle{ E }[/math] nach [math]\displaystyle{ q_3 }[/math] und von [math]\displaystyle{ q_3 }[/math] mit [math]\displaystyle{ K }[/math] in den Endzustand [math]\displaystyle{ q_4 }[/math].

Schritt 2: Endzustand festlegen. In [math]\displaystyle{ q_4 }[/math] ist das Menü geöffnet. Alle weiteren Zeichen sind erlaubt, deshalb hat [math]\displaystyle{ q_4 }[/math] eine Schleife für [math]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math].

Schritt 3: Übergangstabelle aufstellen. Bei [math]\displaystyle{ K }[/math] in [math]\displaystyle{ q_0 }[/math] gibt es zwei Folgezustände. Viele Zellen enthalten einen Strich: Dort bricht der Pfad ab.

[math]\displaystyle{ \delta }[/math] [math]\displaystyle{ K }[/math] [math]\displaystyle{ E }[/math]
[math]\displaystyle{ \rightarrow q_0 }[/math] [math]\displaystyle{ \{q_1; q_2\} }[/math] –
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \{q_4\} }[/math] –
[math]\displaystyle{ q_2 }[/math] – [math]\displaystyle{ \{q_3\} }[/math]
[math]\displaystyle{ q_3 }[/math] [math]\displaystyle{ \{q_4\} }[/math] –
[math]\displaystyle{ {}^*q_4 }[/math] [math]\displaystyle{ \{q_4\} }[/math] [math]\displaystyle{ \{q_4\} }[/math]

Schritt 4: Mit Wörtern prüfen. Die Tastenfolge [math]\displaystyle{ KEKE }[/math] hat zwei Pfade:

  • [math]\displaystyle{ q_0 \xrightarrow{K} q_2 \xrightarrow{E} q_3 \xrightarrow{K} q_4 \xrightarrow{E} q_4 }[/math] (akzeptiert)
  • [math]\displaystyle{ q_0 \xrightarrow{K} q_1 }[/math] (bricht ab)

Ein Pfad liest das ganze Wort und endet in [math]\displaystyle{ q_4 }[/math], die Tastenfolge wird akzeptiert. Für [math]\displaystyle{ KEE }[/math] ergibt sich:

  • [math]\displaystyle{ q_0 \xrightarrow{K} q_1 }[/math] (bricht ab)
  • [math]\displaystyle{ q_0 \xrightarrow{K} q_2 \xrightarrow{E} q_3 }[/math] (bricht ab)

Beide Pfade brechen ab, die Tastenfolge wird abgelehnt. Für die Tastenfolge [math]\displaystyle{ EKK }[/math] gibt es nur einen Pfad, und er bricht schon in [math]\displaystyle{ q_0 }[/math] ab, denn für [math]\displaystyle{ E }[/math] gibt es dort keinen Folgezustand. Auch sie wird abgelehnt.

Wie aus diesem NEA ein DEA wird, zeigt das Beispiel NEA mit Fehlerzustand in einen DEA überführen.

Übergangsfunktion als Übergangsrelation schreiben

Der NEA für das Wartungsmenü aus dem vorigen Beispiel wird als Übergangsrelation angegeben. Jede Zelle der Übergangstabelle liefert für jeden Zustand, der in ihr steht, ein Tripel aus Zustand, Zeichen und Folgezustand. Die Zelle für [math]\displaystyle{ q_0 }[/math] und [math]\displaystyle{ K }[/math] enthält zwei Zustände und liefert deshalb zwei Tripel. Eine Zelle mit Strich liefert keines.

Die Übergangsrelation besteht aus sieben Tripeln: [math]\displaystyle{ (q_0; K; q_1) }[/math], [math]\displaystyle{ (q_0; K; q_2) }[/math], [math]\displaystyle{ (q_1; K; q_4) }[/math], [math]\displaystyle{ (q_2; E; q_3) }[/math], [math]\displaystyle{ (q_3; K; q_4) }[/math], [math]\displaystyle{ (q_4; K; q_4) }[/math] und [math]\displaystyle{ (q_4; E; q_4) }[/math].

Im Übergangsgraphen entspricht jedem Tripel ein Zeichen an einem Pfeil. Die Schleife an [math]\displaystyle{ q_4 }[/math] trägt die Zeichen [math]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math] und steht deshalb für zwei Tripel.

ε-Abschluss bestimmen

 
ε-NEA für Wörter nur aus a oder nur aus b

Der [math]\displaystyle{ \varepsilon }[/math]-NEA hat die Zustände [math]\displaystyle{ q_0 }[/math], [math]\displaystyle{ q_1 }[/math] und [math]\displaystyle{ q_2 }[/math] über dem Alphabet [math]\displaystyle{ \Sigma = \{a; b\} }[/math]. Von [math]\displaystyle{ q_0 }[/math] führen zwei [math]\displaystyle{ \varepsilon }[/math]-Übergänge nach [math]\displaystyle{ q_1 }[/math] und nach [math]\displaystyle{ q_2 }[/math]. Die Zustände [math]\displaystyle{ q_1 }[/math] und [math]\displaystyle{ q_2 }[/math] sind Endzustände. [math]\displaystyle{ q_1 }[/math] liest beliebig viele [math]\displaystyle{ a }[/math], [math]\displaystyle{ q_2 }[/math] liest beliebig viele [math]\displaystyle{ b }[/math].

[math]\displaystyle{ \delta }[/math] [math]\displaystyle{ a }[/math] [math]\displaystyle{ b }[/math] [math]\displaystyle{ \varepsilon }[/math]
[math]\displaystyle{ \rightarrow q_0 }[/math] – – [math]\displaystyle{ \{q_1; q_2\} }[/math]
[math]\displaystyle{ {}^*q_1 }[/math] [math]\displaystyle{ \{q_1\} }[/math] – –
[math]\displaystyle{ {}^*q_2 }[/math] – [math]\displaystyle{ \{q_2\} }[/math] –

Die [math]\displaystyle{ \varepsilon }[/math]-Abschlüsse:

  • [math]\displaystyle{ E(q_0) = \{q_0; q_1; q_2\} }[/math]: [math]\displaystyle{ q_0 }[/math] selbst, dazu [math]\displaystyle{ q_1 }[/math] und [math]\displaystyle{ q_2 }[/math] über je einen [math]\displaystyle{ \varepsilon }[/math]-Übergang.
  • [math]\displaystyle{ E(q_1) = \{q_1\} }[/math]: Von [math]\displaystyle{ q_1 }[/math] geht kein [math]\displaystyle{ \varepsilon }[/math]-Übergang aus.
  • [math]\displaystyle{ E(q_2) = \{q_2\} }[/math]: Von [math]\displaystyle{ q_2 }[/math] geht kein [math]\displaystyle{ \varepsilon }[/math]-Übergang aus.

Der Automat akzeptiert Wörter, die nur aus [math]\displaystyle{ a }[/math] oder nur aus [math]\displaystyle{ b }[/math] bestehen. Auch das leere Wort wird akzeptiert: Ohne ein Zeichen zu lesen, erreicht der Automat über einen [math]\displaystyle{ \varepsilon }[/math]-Übergang den Endzustand [math]\displaystyle{ q_1 }[/math] oder [math]\displaystyle{ q_2 }[/math].

Wörter mit einem ε-NEA prüfen

 
ε-NEA für Wörter aus erst a, dann b, dann c

Der [math]\displaystyle{ \varepsilon }[/math]-NEA über [math]\displaystyle{ \Sigma = \{a; b; c\} }[/math] akzeptiert alle Wörter, in denen zuerst beliebig viele [math]\displaystyle{ a }[/math], dann beliebig viele [math]\displaystyle{ b }[/math] und zuletzt beliebig viele [math]\displaystyle{ c }[/math] stehen. Jede der drei Gruppen darf fehlen. [math]\displaystyle{ q_0 }[/math] liest die [math]\displaystyle{ a }[/math], [math]\displaystyle{ q_1 }[/math] die [math]\displaystyle{ b }[/math] und [math]\displaystyle{ q_2 }[/math] die [math]\displaystyle{ c }[/math]. Zwei [math]\displaystyle{ \varepsilon }[/math]-Übergänge führen von [math]\displaystyle{ q_0 }[/math] nach [math]\displaystyle{ q_1 }[/math] und von [math]\displaystyle{ q_1 }[/math] nach [math]\displaystyle{ q_2 }[/math]. Der Endzustand ist [math]\displaystyle{ q_2 }[/math].

[math]\displaystyle{ \delta }[/math] [math]\displaystyle{ a }[/math] [math]\displaystyle{ b }[/math] [math]\displaystyle{ c }[/math] [math]\displaystyle{ \varepsilon }[/math]
[math]\displaystyle{ \rightarrow q_0 }[/math] [math]\displaystyle{ \{q_0\} }[/math] – – [math]\displaystyle{ \{q_1\} }[/math]
[math]\displaystyle{ q_1 }[/math] – [math]\displaystyle{ \{q_1\} }[/math] – [math]\displaystyle{ \{q_2\} }[/math]
[math]\displaystyle{ {}^*q_2 }[/math] – – [math]\displaystyle{ \{q_2\} }[/math] –

Die [math]\displaystyle{ \varepsilon }[/math]-Abschlüsse:

  • [math]\displaystyle{ E(q_0) = \{q_0; q_1; q_2\} }[/math]: Von [math]\displaystyle{ q_0 }[/math] führt ein [math]\displaystyle{ \varepsilon }[/math]-Übergang nach [math]\displaystyle{ q_1 }[/math] und von dort ein weiterer nach [math]\displaystyle{ q_2 }[/math]. Auch der Zustand hinter zwei [math]\displaystyle{ \varepsilon }[/math]-Übergängen gehört zum Abschluss.
  • [math]\displaystyle{ E(q_1) = \{q_1; q_2\} }[/math]
  • [math]\displaystyle{ E(q_2) = \{q_2\} }[/math]

Drei Wörter werden geprüft. Über jedem Pfeil steht das gelesene Zeichen oder [math]\displaystyle{ \varepsilon }[/math]:

  • [math]\displaystyle{ abc }[/math]: [math]\displaystyle{ q_0 \xrightarrow{a} q_0 \xrightarrow{\varepsilon} q_1 \xrightarrow{b} q_1 \xrightarrow{\varepsilon} q_2 \xrightarrow{c} q_2 }[/math]. Die [math]\displaystyle{ \varepsilon }[/math]-Übergänge liegen zwischen den Zeichen. Der Pfad liest das ganze Wort und endet im Endzustand, das Wort wird akzeptiert.
  • [math]\displaystyle{ ac }[/math]: [math]\displaystyle{ q_0 \xrightarrow{a} q_0 \xrightarrow{\varepsilon} q_1 \xrightarrow{\varepsilon} q_2 \xrightarrow{c} q_2 }[/math]. Zwischen [math]\displaystyle{ a }[/math] und [math]\displaystyle{ c }[/math] liegen zwei [math]\displaystyle{ \varepsilon }[/math]-Übergänge hintereinander, weil kein [math]\displaystyle{ b }[/math] vorkommt. Das Wort wird akzeptiert.
  • [math]\displaystyle{ ba }[/math]: Um das [math]\displaystyle{ b }[/math] zu lesen, muss der Automat zuerst über [math]\displaystyle{ \varepsilon }[/math] nach [math]\displaystyle{ q_1 }[/math] wechseln. Von [math]\displaystyle{ q_1 }[/math] und von [math]\displaystyle{ q_2 }[/math] aus gibt es keinen Übergang mit [math]\displaystyle{ a }[/math], und kein Übergang führt zurück nach [math]\displaystyle{ q_0 }[/math]. Kein Pfad liest das ganze Wort, es wird abgelehnt.

Auch das leere Wort wird akzeptiert: Über die beiden [math]\displaystyle{ \varepsilon }[/math]-Übergänge erreicht der Automat den Endzustand [math]\displaystyle{ q_2 }[/math], ohne ein Zeichen zu lesen. Wie aus diesem Automaten ein DEA wird, zeigt das Beispiel ε-Abschluss nach jedem Schritt bilden.

ε-Übergänge entfernen

Aus dem [math]\displaystyle{ \varepsilon }[/math]-NEA des vorigen Beispiels entsteht ein NEA ohne [math]\displaystyle{ \varepsilon }[/math]-Übergänge, der dieselbe Sprache akzeptiert. Die Regel steht im Abschnitt Umwandlung ε-NEA zu NEA.

Schritt 1: Übergänge bestimmen. Für jeden Zustand und jedes Zeichen wird gefragt: Welche Zustände erreicht der Automat, wenn er zuerst beliebig viele [math]\displaystyle{ \varepsilon }[/math]-Übergänge nimmt, dann das Zeichen liest und danach wieder beliebig viele [math]\displaystyle{ \varepsilon }[/math]-Übergänge nimmt? Für [math]\displaystyle{ q_0 }[/math] und [math]\displaystyle{ b }[/math] heißt das: Über [math]\displaystyle{ \varepsilon }[/math] gelangt der Automat nach [math]\displaystyle{ q_1 }[/math], liest dort das [math]\displaystyle{ b }[/math] und bleibt in [math]\displaystyle{ q_1 }[/math]. Von [math]\displaystyle{ q_1 }[/math] führt ein [math]\displaystyle{ \varepsilon }[/math]-Übergang weiter nach [math]\displaystyle{ q_2 }[/math]. Die Folgemenge ist [math]\displaystyle{ \{q_1; q_2\} }[/math].

Schritt 2: Endzustände bestimmen. Der [math]\displaystyle{ \varepsilon }[/math]-Abschluss jedes der drei Zustände enthält den Endzustand [math]\displaystyle{ q_2 }[/math]. Deshalb sind im neuen Automaten alle drei Zustände Endzustände.

[math]\displaystyle{ \delta }[/math] [math]\displaystyle{ a }[/math] [math]\displaystyle{ b }[/math] [math]\displaystyle{ c }[/math]
[math]\displaystyle{ \rightarrow {}^*q_0 }[/math] [math]\displaystyle{ \{q_0; q_1; q_2\} }[/math] [math]\displaystyle{ \{q_1; q_2\} }[/math] [math]\displaystyle{ \{q_2\} }[/math]
[math]\displaystyle{ {}^*q_1 }[/math] – [math]\displaystyle{ \{q_1; q_2\} }[/math] [math]\displaystyle{ \{q_2\} }[/math]
[math]\displaystyle{ {}^*q_2 }[/math] – – [math]\displaystyle{ \{q_2\} }[/math]

Schritt 3: Prüfen. Das Wort [math]\displaystyle{ ac }[/math] hat im neuen Automaten den Pfad [math]\displaystyle{ q_0 \xrightarrow{a} q_2 \xrightarrow{c} q_2 }[/math] und wird akzeptiert. Das Wort [math]\displaystyle{ ba }[/math] wird abgelehnt: Nach dem [math]\displaystyle{ b }[/math] sind nur [math]\displaystyle{ q_1 }[/math] und [math]\displaystyle{ q_2 }[/math] erreichbar, und beide haben für [math]\displaystyle{ a }[/math] keinen Folgezustand. Das leere Wort wird akzeptiert, weil der Startzustand [math]\displaystyle{ q_0 }[/math] jetzt ein Endzustand ist.