Zum Inhalt springen

Endlicher Automat: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
Zeile 1: Zeile 1:
== Einführung ==
Technische Systeme und Programme wie Getränkeautomaten, Ampelsteuerungen, Aufzüge oder Textfilter reagieren auf Eingaben nach festen Regeln. Ein endlicher Automat modelliert solche Systeme mathematisch mithilfe endlich vieler Zustände und eindeutig festgelegter Zustandsübergänge.
Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein mathematisches Modell eines Systems mit diskreten Ein- und Ausgaben. Diskret bedeutet, dass zu jedem Zeitpunkt nur eine Eingabe und eine Ausgabe verarbeitet wird. Es gibt eine endliche Anzahl an Ein- und Ausgaben. Das durch den Automaten beschriebene System befindet sich in einem von endlich vielen Zuständen. Das Verhalten des Systems wird durch Zustände, Zustandsübergänge und Aktionen beschrieben.


Automaten lassen sich unter anderem durch ein [[Zustandsdiagramm|UML Zustandsdiagramm]] darstellen.
==Definition==
Ein '''endlicher Automat''' (kurz '''EA''', auch '''Zustandsmaschine''' oder '''Zustandsautomat'''; englisch ''finite state machine'', ''FSM'') ist ein abstraktes Verhaltensmodell eines Systems mit diskreten Ein- und Ausgaben. '''Diskret''' bedeutet, dass der Automat ein Eingabewort schrittweise (Zeichen für Zeichen) in einzelnen Taktschritten verarbeitet.


== Motivation ==
Jeder endliche Automat besitzt folgende Grundbestandteile:
Computer, andere Maschinen oder Programme erscheinen im Alltag oft als eine Black Box, egal ob sie triviale oder schwierige Probleme lösen. Sie reagieren auf Eingaben, verarbeiten Informationen, ohne dass wir sehen, wie, und präsentieren eine Antwort bzw. eine Lösung. Manchmal scheinen sie sogar ‚intelligenter‘ als Menschen zu sein, wenn sie gegen Schachweltmeister gewinnen, die 2,7 Billionen Nachkommastellen von π berechnen, einem sagen, was man als Nächstes kaufen möchte, oder wenn man mit einem Computer spricht, ohne es zu bemerken.
* '''Endliche Zustandsmenge <math>Q</math>:''' Eine nicht leere, endliche [[Menge]] von Zuständen (<math>Q \neq \emptyset</math>). Das System befindet sich zu jedem Zeitpunkt in genau einem Zustand <math>q \in Q</math> (bzw. beim nichtdeterministischen Automaten in einer Menge möglicher Zustände).
* '''Endliches Eingabealphabet <math>\Sigma</math>:''' Ein nicht leeres [[Alphabet]] (<math>\Sigma \neq \emptyset</math>), aus dessen [[Zeichen]] die Eingabewörter <math>w \in \Sigma^*</math> gebildet werden.
* '''Startzustand <math>q_0 \in Q</math>:''' Der eindeutig festgelegte Ausgangszustand, in dem sich der Automat vor dem Lesen des ersten Zeichens befindet.
* '''Übergangsfunktion <math>\delta</math>:''' Eine Zuordnungsvorschrift, die festlegt, in welchen Folgezustand der Automat wechselt, wenn er im aktuellen Zustand ein bestimmtes Eingabezeichen liest.


Doch das Verarbeiten der Eingaben ist weder Zauberei noch (zumindest bis heute) intelligentes Vorgehen. Es sind Programme, die das Verhalten der Maschine bestimmen, und diese Maschinen lassen sich sogar durch einfach strukturierte Modelle wie den endlichen Automaten beschreiben. Die Einfachheit des Modells sollte aber nicht über seine Mächtigkeit hinwegtäuschen.
Nach ihrem Verwendungszweck unterscheidet man zwei Grundtypen endlicher Automaten:
Das Automatenmodell dient zum Beispiel der Zellforschung als probates Mittel, um das Verhalten von Zellen zu beschreiben, und auch die Hirnforschung greift bei der Beschreibung des Gehirns durch neuronale Netze darauf zurück. Automaten findet man außerdem in zahlreichen Alltagssituationen vor: Fahrstühle, Ampeln, Waschmaschinen, Getränke-, Fahrkarten- und Geldautomaten sind nur einige der vielen Maschinen, die von einem endlichen Automaten gesteuert werden.  
* '''Akzeptoren (Spracherkenner, z. B. [[Deterministischer endlicher Automat|DEA]] und [[Nichtdeterministischer endlicher Automat|NEA]]):''' Sie besitzen keine eigene Ausgabe, sondern eine Menge akzeptierender '''Endzustände''' <math>F \subseteq Q</math>. Nach dem vollständigen Lesen eines [[Wort|Wortes]] <math>w \in \Sigma^*</math> entscheidet der erreichte Zustand darüber, ob das Wort akzeptiert wird und damit zur [[Formale Sprache|formalen Sprache]] <math>L(A)</math> des Automaten gehört (<math>w \in L(A)</math>) oder ob es abgelehnt wird (<math>w \notin L(A)</math>).
* '''Transduktoren (Automaten mit Ausgabe, z. B. [[Mealy-Automat]]):''' Sie besitzen zusätzlich ein endliches '''Ausgabealphabet''' <math>\Omega</math> und eine '''Ausgabefunktion''' <math>\lambda</math>, die bei jedem Zustandsübergang ein Ausgabezeichen erzeugt.


Diese Automaten werden als endlich bezeichnet, weil die Menge der Eingaben, der Ausgaben und der Zustände, die sie durchlaufen, endlich sind.
==Übergangsfunktion==
Die Übergangsfunktion <math>\delta</math> beschreibt das Verhalten eines endlichen Automaten vollständig. Sie lässt sich auf zwei gleichwertige Arten darstellen:


== Mealy-Automat ==  
* '''Übergangsgraph ([[Zustandsdiagramm|UML-Zustandsdiagramm]]):'''
** Die Zustände <math>q \in Q</math> werden als Kreise gezeichnet.
** Der Startzustand <math>q_0</math> wird durch einen eingehenden Pfeil ohne Ursprungsknoten markiert.
** Akzeptierende Endzustände <math>q \in F</math> werden durch einen Doppelkreis gekennzeichnet.
** Zustandsübergänge werden als gerichtete Pfeile (Kanten) zwischen den Zuständen dargestellt und mit dem auslösenden Eingabezeichen <math>a \in \Sigma</math> beschriftet (beim Mealy-Automaten ergänzt um die Ausgabe in der Form <code>Eingabe / Ausgabe</code>).
* '''Übergangstabelle:'''
** Die Zeilen der Tabelle entsprechen den aktuellen Zuständen <math>q \in Q</math>, die Spalten den Eingabezeichen <math>a \in \Sigma</math>.
** Im Schnittpunkt einer Zeile <math>q</math> und einer Spalte <math>a</math> steht der Folgezustand <math>\delta(q, a)</math> (bzw. beim NEA die Menge der Folgezustände).
** In der ersten Spalte wird der Startzustand häufig mit einem Pfeil (<math>\rightarrow q_0</math>) und jeder Endzustand mit einem Stern (<math>{}^*q</math>) markiert.
 
==Mealy-Automat==
''Hauptartikel: [[Mealy-Automat]]''
''Hauptartikel: [[Mealy-Automat]]''
=== Definition ===
Ein Mealy-Automat ist ein endlicher Automat mit Ausgabe: Zu jedem gelesenen Zeichen des Eingabealphabets gibt er ein Zeichen des Ausgabealphabets aus. Die Übergangsfunktion legt den Folgezustand fest, die Ausgabefunktion die Ausgabe; beide werden tabellarisch oder als Übergangsgraph dargestellt.


Formal definiert man einen Mealy-Automaten als 7-Tupel <math>A = (Q, \Sigma, \Omega, \delta, \lambda, q0, F)</math>:
===Definition===
Ein '''Mealy-Automat''' ist ein deterministischer endlicher Automat mit Ausgabe. Zu jedem gelesenen Zeichen des Eingabealphabets wechselt er abhängig vom aktuellen Zustand in einen eindeutig bestimmten Folgezustand und gibt gleichzeitig ein Zeichen des Ausgabealphabets aus.


<math>Q</math> ist eine nicht leere, endliche Menge von Zuständen
Formal ist ein Mealy-Automat definiert als 7-Tupel <math>A = (Q, \Sigma, \Omega, \delta, \lambda, q_0, F)</math>:
* <math>Q</math> ist eine endliche, nicht leere Menge von Zuständen (<math>Q \neq \emptyset</math>).
* <math>\Sigma</math> ist ein endliches, nicht leeres Eingabealphabet (<math>\Sigma \neq \emptyset</math>).
* <math>\Omega</math> ist ein endliches, nicht leeres Ausgabealphabet (<math>\Omega \neq \emptyset</math>).
* <math>\delta: Q \times \Sigma \to Q</math> ist die '''Übergangsfunktion''', die jedem Paar aus aktuellem Zustand <math>q \in Q</math> und Eingabezeichen <math>a \in \Sigma</math> genau einen Folgezustand <math>\delta(q, a) \in Q</math> zuordnet.
* <math>\lambda: Q \times \Sigma \to \Omega</math> ist die '''Ausgabefunktion''', die jedem Paar aus aktuellem Zustand <math>q \in Q</math> und Eingabezeichen <math>a \in \Sigma</math> genau ein Ausgabezeichen <math>\lambda(q, a) \in \Omega</math> zuordnet.
* <math>q_0 \in Q</math> ist der Startzustand.
* <math>F \subseteq Q</math> ist die Menge der Endzustände. Da ein Mealy-Automat primär zur fortlaufenden Ausgabe dient, ist oft jeder Zustand ein Endzustand (<math>F = Q</math>). In der Fachliteratur wird der Mealy-Automat daher häufig auch als 6-Tupel <math>A = (Q, \Sigma, \Omega, \delta, \lambda, q_0)</math> ohne <math>F</math> definiert.


<math>\Sigma</math> ist ein nicht leeres, endliches Eingabealphabet
==DEA - Deterministischer endlicher Automat==
''Hauptartikel: [[Deterministischer endlicher Automat]]''


<math>\Omega</math> ist ein nicht leeres, endliches Ausgabealphabet
===Definition===
Ein endlicher Automat heißt '''deterministisch''' (kurz '''DEA'''; englisch ''deterministic finite automaton'', ''DFA''), wenn für jeden Zustand <math>q \in Q</math> und jedes Eingabezeichen <math>a \in \Sigma</math> höchstens ein (bei einem vollständigen DEA '''genau ein''') Folgezustand existiert. Das Verhalten des Automaten ist für jede Eingabe eindeutig vorbestimmt; es gibt keine Wahlmöglichkeiten beim Zustandswechsel. Im Unterschied zum Mealy-Automaten besitzt ein DEA keine Ausgabefunktion, sondern entscheidet über die Zugehörigkeit eines Wortes zu einer [[Formale Sprache|formalen Sprache]].


<math>\delta: Q \times \Sigma \to Q</math> ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.
Formal ist ein deterministischer endlicher Automat definiert als 5-Tupel <math>A = (Q, \Sigma, \delta, q_0, F)</math>:
* <math>Q</math> ist eine endliche, nicht leere Menge von Zuständen (<math>Q \neq \emptyset</math>).
* <math>\Sigma</math> ist ein endliches, nicht leeres Eingabealphabet (<math>\Sigma \neq \emptyset</math>).
* <math>\delta: Q \times \Sigma \to Q</math> ist die '''Übergangsfunktion''', die jedem Paar aus Zustand <math>q \in Q</math> und Eingabezeichen <math>a \in \Sigma</math> eindeutig einen Folgezustand zuordnet.
* <math>q_0 \in Q</math> ist der Startzustand.
* <math>F \subseteq Q</math> ist die Menge der akzeptierenden Endzustände.


<math>\lambda: Q \times \Sigma \to \Omega</math> ist die Ausgabefunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen eine Ausgabe zuordnet.
Ein [[Wort]] <math>w \in \Sigma^*</math> wird vom DEA '''akzeptiert''' (es gilt <math>w \in L(A)</math>), wenn sich der Automat nach dem vollständigen Lesen aller Zeichen von <math>w</math> (beginnend bei <math>q_0</math>) in einem Endzustand <math>q \in F</math> befindet. Die Menge aller akzeptierten Wörter bildet die vom Automaten erkannte Sprache <math>L(A)</math>.


<math>q0 \in Q</math> ist der Startzustand
==Nichtdeterministischer endlicher Automat==
''Hauptartikel: [[Nichtdeterministischer endlicher Automat]]''


<math>F \subseteq Q</math> ist die Menge der Endzustände. Oft ist jeder Zustand ein Endzustand, also <math>F = Q</math>. In der Literatur ist auch das 6-Tupel ohne <math>F</math> üblich.
===Definition===
Ein '''nichtdeterministischer endlicher Automat''' (kurz '''NEA'''; englisch ''nondeterministic finite automaton'', ''NFA'') ist ein endlicher Automat, bei dem für denselben Zustand und dasselbe Eingabezeichen mehrere gleichwertige Folgezustände oder auch gar kein Folgezustand existieren können. Der Automat ist beim Lesen eines Zeichens also nicht auf einen einzigen Pfad festgelegt, sondern kann mehrere Berechnungswege parallel verfolgen.


=== Beispiel ===
Formal ist ein nichtdeterministischer endlicher Automat definiert als 5-Tupel <math>A = (Q, \Sigma, \delta, q_0, F)</math>:
Die Funktionsweise eines endlichen Automaten lässt sich leicht an einer einfachen Maschine wie einem Bonbonautomaten erläutern. Die Eingabe besteht aus der richtigen Münze (M) und dem Drehen des Hebels (H). Die Verarbeitung erfolgt im Inneren des Automaten und führt zur Ausgabe, dem Bonbon (B) im Ausgabefach oder keiner Ausgabe (N). Es kommt auf die korrekte Reihenfolge an: Dreht man zuerst den Hebel und wirft dann die korrekte Münze ein, so erhält man nicht die gewünschte Ausgabe.
* <math>Q</math> ist eine endliche, nicht leere Menge von Zuständen (<math>Q \neq \emptyset</math>).
* <math>\Sigma</math> ist ein endliches, nicht leeres Eingabealphabet (<math>\Sigma \neq \emptyset</math>).
* <math>\delta: Q \times \Sigma \to \mathcal{P}(Q)</math> ist die '''Übergangsfunktion''', die jedem Paar aus Zustand <math>q \in Q</math> und Eingabezeichen <math>a \in \Sigma</math> eine '''Menge von Folgezuständen''' zuordnet. Dabei bezeichnet <math>\mathcal{P}(Q)</math> die Potenzmenge von <math>Q</math> (die Menge aller Teilmengen von <math>Q</math>). Gibt es für ein Zeichen keinen Übergang, liefert die Funktion die leere Menge <math>\emptyset</math>.
* <math>q_0 \in Q</math> ist der Startzustand.
* <math>F \subseteq Q</math> ist die Menge der akzeptierenden Endzustände.


Bonbonautomat als Mealy-Automat: <math>Q = \{q0, q1\}</math>, <math>\Sigma = \{M, H\}</math>, <math>\Omega = \{B, N\}</math>, <math>F = Q</math>
Ein Wort <math>w \in \Sigma^*</math> gehört genau dann zur akzeptierten Sprache <math>L(A)</math> des NEA, wenn '''mindestens ein''' gültiger Pfad vom Startzustand <math>q_0</math> nach dem vollständigen Lesen von <math>w</math> in einem akzeptierenden Endzustand <math>q \in F</math> endet. Dass andere Pfade in Nicht-Endzuständen enden oder vorzeitig abbrechen, verhindert die Akzeptanz nicht.


[[Datei:Mealy-Automat Bonbonautomat.png|mini|Bonbonautomat als Mealy-Automat]]
==ε-NEA==
== Übergangsfunktion ==
''Hauptartikel: [[Nichtdeterministischer endlicher Automat#ε-NEA]]''
Die Übergangsfunktion <math>\delta: Q \times \Sigma \to Q</math> ordnet jeder Kombination aus einem Zustand (erste Spalte) und einem Eingabezeichen (erste Zeile) einen Nachfolgezustand (Matrix) zu. Dies lässt sich sehr gut tabellarisch darstellen:


M: Münze einwerfen
Ein '''nichtdeterministischer endlicher Automat mit <math>\varepsilon</math>-Übergängen''' (kurz '''<math>\varepsilon</math>-NEA''') erweitert den NEA um sogenannte '''Epsilon-Übergänge''' (auch Spontanübergänge). Ein mit dem leeren Wort <math>\varepsilon</math> beschrifteter Übergang ermöglicht es dem Automaten, den Zustand zu wechseln, '''ohne''' dabei ein Zeichen des Eingabealphabets zu lesen. Dadurch lassen sich viele Automaten deutlich kompakter und übersichtlicher entwerfen.


H: Hebel drehen
Formal ist ein <math>\varepsilon</math>-NEA definiert als 5-Tupel <math>A = (Q, \Sigma, \delta, q_0, F)</math>, wobei die Übergangsfunktion das Eingabealphabet um <math>\varepsilon</math> erweitert:
:<math>\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)</math>


B: Bonbon ausgeben
Ein Wort <math>w \in \Sigma^*</math> wird vom <math>\varepsilon</math>-NEA akzeptiert (<math>w \in L(A)</math>), wenn im Zustandsgraphen mindestens ein Pfad vom Startzustand <math>q_0</math> zu einem Endzustand <math>q \in F</math> existiert, entlang dessen Kanten (unter beliebig häufiger Nutzung von <math>\varepsilon</math>-Übergängen) genau die Zeichenfolge von <math>w</math> gelesen wird.


N: Keine Ausgabe
===Umwandlung ε-NEA zu NEA===
Ein <math>\varepsilon</math>-NEA ist genauso mächtig wie ein gewöhnlicher NEA oder ein DEA: Zu jedem <math>\varepsilon</math>-NEA existiert ein äquivalenter NEA ohne <math>\varepsilon</math>-Übergänge sowie ein äquivalenter DEA, die exakt dieselbe Sprache erkennen.


Endzustände werden in der Tabelle mit einem Stern gekennzeichnet.
Um einen <math>\varepsilon</math>-NEA in einen NEA ohne <math>\varepsilon</math>-Übergänge (oder direkt in einen DEA) umzuwandeln, bestimmt man für jeden Zustand <math>q \in Q</math> zunächst die '''<math>\varepsilon</math>-Hülle''' <math>E(q)</math>: Das ist die Menge aller Zustände, die von <math>q</math> aus ausschließlich über <math>\varepsilon</math>-Übergänge (einschließlich <math>q</math> selbst) erreichbar sind. Anschließend werden die Übergänge für die regulären Zeichen aus <math>\Sigma</math> auf diese Zustandsmengen übertragen (siehe [[Potenzmengenkonstruktion#ε-NEA in einen DEA überführen]]).


Beispiel Übergangsfunktion für den Bonbonautomaten:
==Potenzmengenkonstruktion==
{| class="wikitable" style="text-align:center"
''Hauptartikel: [[Potenzmengenkonstruktion]]''
! δ !! M !! H
|-
| q0 || q1 || q0
|-
| q1 || q1 || q0
|}


== DEA - Deterministischer endlicher Automat ==
Die '''Potenzmengenkonstruktion''' ist ein systematisches Verfahren, das jeden nichtdeterministischen endlichen Automaten (NEA oder <math>\varepsilon</math>-NEA) in einen sprachäquivalenten deterministischen endlichen Automaten (DEA) umwandelt (<math>L(\text{DEA}) = L(\text{NEA})</math>).
''Hauptartikel: [[Deterministischer endlicher Automat]]''
=== Definition ===
Ein Automat heißt deterministisch, wenn für jeden seiner Zustände für jedes Eingabezeichen genau ein Folgezustand existiert. Das Verhalten des Automaten ist somit eindeutig bestimmt. Der deterministische endliche Automat ist genau wie der Mealy-Automat dadurch gekennzeichnet, dass er eine endliche Menge an Zuständen besitzt und die Übergänge von einem Zustand zum anderen deterministisch definiert sind, es also keine Wahlmöglichkeiten für den Zustandswechsel bei einer konkreten Eingabe gibt. Er besitzt jedoch kein Ausgabealphabet und keine Ausgabefunktion, dafür aber eine Menge an akzeptierenden Endzuständen.


Solche DEA können z. B. überprüfen, ob in einer Kaffeemaschine das Kaffeesatzfach geleert werden muss. Dazu muss eine Spezifikation des Problems vorliegen, anhand derer sich das Problem als deterministischer Automat formalisieren lässt.
Die Grundidee besteht darin, alle Zustände, in denen sich der NEA nach einer bestimmten Eingabe gleichzeitig befinden kann, im DEA zu einem einzigen Mengenzustand zusammenzufassen:
* '''Zustände als Teilmengen:''' Jeder Zustand des neuen DEA ist eine Teilmenge der ursprünglichen Zustandsmenge <math>Q</math>, also ein Element der Potenzmenge <math>\mathcal{P}(Q)</math> (z. B. <math>\{q_0, q_1\}</math>).
* '''Deterministischer Übergang:''' Für einen Mengenzustand und ein Eingabezeichen <math>a \in \Sigma</math> bildet man die Vereinigung aller Folgezustände, die der NEA von den enthaltenen Einzelzuständen aus mit <math>a</math> erreichen kann. Diese Vereinigungsmenge ist der eindeutig bestimmte Folgezustand im DEA.
* '''Endzustände im DEA:''' Ein Mengenzustand des DEA ist genau dann ein akzeptierender Endzustand, wenn er mindestens einen ursprünglichen Endzustand <math>q \in F</math> des NEA enthält.


Formal definiert man einen DEA als 5-Tupel <math>A = (Q, \Sigma, \delta, q0, F)</math>:
==Beispiele==
===Bonbonautomat als Mealy-Automat modellieren===
[[Datei:Mealy-Automat Bonbonautomat.png|mini|Bonbonautomat als Mealy-Automat]]
Ein mechanischer Bonbonautomat gibt genau dann ein Bonbon aus, wenn zuerst eine Münze eingeworfen und anschließend der Hebel gedreht wird. Dreht man den Hebel ohne vorherigen Münzeinwurf, passiert nichts. Wirft man mehrere Münzen nacheinander ein, ohne zwischendurch den Hebel zu drehen, bleibt der Automat im bezahlten Zustand, gibt aber noch kein Bonbon aus.


<math>Q</math> ist eine nicht leere, endliche Menge von Zuständen
'''1. Formale Beschreibung als 7-Tupel <math>A = (Q, \Sigma, \Omega, \delta, \lambda, q_0, F)</math>:'''
* '''Zustandsmenge <math>Q = \{q_0, q_1\}</math>:'''
** <math>q_0</math>: Keine Münze eingeworfen (Wartezustand / Startzustand).
** <math>q_1</math>: Münze ist eingeworfen (Bereitschaftszustand für Bonbonausgabe).
* '''Eingabealphabet <math>\Sigma = \{M, H\}</math>:'''
** <math>M</math>: Münze einwerfen.
** <math>H</math>: Hebel drehen.
* '''Ausgabealphabet <math>\Omega = \{B, N\}</math>:'''
** <math>B</math>: Bonbon ausgeben.
** <math>N</math>: Keine Ausgabe (Nichts).
* '''Startzustand:''' <math>q_0</math>.
* '''Endzustandsmenge:''' <math>F = Q = \{q_0, q_1\}</math> (jeder Zustand ist ein zulässiger Endzustand).


<math>\Sigma</math> ist ein nicht leeres, endliches Eingabealphabet
'''2. Übergangsfunktion <math>\delta</math> und Ausgabefunktion <math>\lambda</math> in Tabellenform:'''


<math>\delta: Q \times \Sigma \to Q</math> ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.
{| class="wikitable" style="text-align:center"
|+ Übergangsfunktion <math>\delta(q, a)</math> (Folgezustand)
! <math>\delta</math> !! <math>M</math> !! <math>H</math>
|-
| <math>\rightarrow {}^*q_0</math> || <math>q_1</math> || <math>q_0</math>
|-
| <math>{}^*q_1</math> || <math>q_1</math> || <math>q_0</math>
|}


<math>q0 \in Q</math> ist der Startzustand
{| class="wikitable" style="text-align:center"
|+ Ausgabefunktion <math>\lambda(q, a)</math> (Ausgabezeichen)
! <math>\lambda</math> !! <math>M</math> !! <math>H</math>
|-
| <math>\rightarrow {}^*q_0</math> || <math>N</math> || <math>N</math>
|-
| <math>{}^*q_1</math> || <math>N</math> || <math>B</math>
|}
 
'''3. Verarbeitung konkreter Eingabefolgen prüfen:'''
* '''Eingabewort <math>w_1 = MH</math> (korrekte Bedienung):'''
** Start in <math>q_0</math>. Beim Lesen von <math>M</math> wechselt der Automat nach <math>\delta(q_0, M) = q_1</math> und gibt <math>\lambda(q_0, M) = N</math> aus.
** In <math>q_1</math> wird <math>H</math> gelesen: Der Automat wechselt zurück nach <math>\delta(q_1, H) = q_0</math> und gibt <math>\lambda(q_1, H) = B</math> (Bonbon) aus. Die gesamte Ausgabefolge lautet <math>NB</math>.
* '''Eingabewort <math>w_2 = HM</math> (falsche Reihenfolge):'''
** Start in <math>q_0</math>. Beim Lesen von <math>H</math> bleibt der Automat in <math>\delta(q_0, H) = q_0</math> und gibt <math>\lambda(q_0, H) = N</math> aus (Hebel dreht leer durch).
** Anschließend wird in <math>q_0</math> das Zeichen <math>M</math> gelesen: Der Automat wechselt nach <math>q_1</math> und gibt erneut <math>N</math> aus. Die Ausgabefolge lautet <math>NN</math> (kein Bonbon).


<math>F \subseteq Q</math> ist die Menge der zu akzeptierenden Endzustände
===Kaffeeautomat als deterministischen endlichen Automaten (DEA) angeben===
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]]
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]]
Ein Kaffeeautomat sammelt den Kaffeesatz in einem Satzfach, das genau 4 Einheiten fasst. Ein Kaffee (<math>K</math>) erzeugt 1 Einheit Kaffeesatz, ein Espresso (<math>E</math>) erzeugt 2 Einheiten. Der Automat soll genau die Tastenkombinationen akzeptieren, nach denen das Satzfach exakt mit 4 Einheiten gefüllt ist.


== Nichtdeterministischer endlicher Automat ==
'''1. Formale Beschreibung als 5-Tupel <math>A = (Q, \Sigma, \delta, q_0, F)</math>:'''
''Hauptartikel: [[Nichtdeterministischer endlicher Automat]]''
* '''Zustandsmenge <math>Q = \{q_0, q_1, q_2, q_3, q_4, q_5\}</math>:''' Die Zustände <math>q_0</math> bis <math>q_4</math> speichern den aktuellen Füllstand des Satzfachs (0 bis 4 Einheiten). Der Zustand <math>q_5</math> ist ein sogenannter '''Fangzustand''' (Fehlerzustand) für einen Überlauf (mehr als 4 Einheiten), der nicht mehr verlassen werden kann.
=== Definition ===
* '''Eingabealphabet <math>\Sigma = \{K, E\}</math>:''' <math>K</math> steht für Kaffee (+1 Einheit), <math>E</math> für Espresso (+2 Einheiten).
Ein nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.
* '''Startzustand <math>q_0</math>:''' Zu Beginn ist das Satzfach leer (0 Einheiten).
 
* '''Endzustandsmenge <math>F = \{q_4\}</math>:''' Nur bei exakt 4 Einheiten (<math>q_4</math>) ist das Satzfach planmäßig voll.
Formal kann ein NEA als 5-Tupel <math>A = (Q, \Sigma, \delta, q0, F)</math> definiert werden. Hierbei gilt Folgendes:
 
<math>Q</math> ist eine nicht leere, endliche Menge von Zuständen
 
<math>\Sigma</math> ist ein nicht leeres, endliches Eingabealphabet
 
<math>\delta: Q \times \Sigma \to P(Q)</math> ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen eine Menge von Folgezuständen zuordnet. <math>P(Q)</math> ist die Potenzmenge von <math>Q</math>.
 
<math>q0 \in Q</math> ist der Startzustand
 
<math>F \subseteq Q</math> ist die Menge der zu akzeptierenden Endzustände


Ein Wort <math>w \in \Sigma^*</math> gehört zur Sprache des Automaten, wenn mindestens ein Pfad nach dem Lesen von <math>w</math> in einem Endzustand endet.
'''2. Wortverarbeitung und akzeptierte Sprache:'''
* Für das Eingabewort <math>w_1 = KEK</math> durchläuft der DEA eindeutig die Zustandsfolge:
:<math>q_0 \xrightarrow{K} q_1 \xrightarrow{E} q_3 \xrightarrow{K} q_4 \in F</math>
:Da <math>q_4</math> ein Endzustand ist, wird <math>KEK</math> akzeptiert (<math>KEK \in L(A)</math>).
* Für das Eingabewort <math>w_2 = EEK</math> lautet die Zustandsfolge:
:<math>q_0 \xrightarrow{E} q_2 \xrightarrow{E} q_4 \xrightarrow{K} q_5 \notin F</math>
:Da der Automat im Fehlerzustand <math>q_5</math> endet, wird <math>EEK</math> abgelehnt (<math>EEK \notin L(A)</math>).
* Insgesamt akzeptiert der DEA genau die endliche Sprache <math>L(A) = \{KKKK, EE, EKK, KEK, KKE\}</math>.


=== Beispiel ===
===Spam-Filter als NEA und DEA gegenüberstellen===
[[Datei:NEA Spam-Filter.png|mini|Spam-Filter als NEA]]
[[Datei:NEA Spam-Filter.png|mini|Spam-Filter als NEA]]
[[Datei:DEA Spam-Filter.png|mini|Spam-Filter als DEA]]
[[Datei:DEA Spam-Filter.png|mini|Spam-Filter als DEA]]
Folgende Diagramme stellen NEA und DEA gegenüber. Es wurde ein einfacher Spam-Filter als Automat entwickelt, der E-Mails mit der Zeichenfolge UML erkennt.
Ein einfacher Spam-Filter durchsucht Texte über dem Eingabealphabet <math>\Sigma = \{A, \dots, Z\}</math> nach der Zeichenfolge <code>UML</code>. Sobald ein Wort die Teilzeichenfolge <code>UML</code> an beliebiger Stelle enthält (also zur Sprache <math>L = \{w \in \Sigma^* \mid w \text{ enthält } UML\}</math> gehört), soll der Automat im Endzustand <math>q_3</math> akzeptieren.
 
 
== Potenzmengenkonstruktion ==
''Hauptartikel: [[Potenzmengenkonstruktion]]''
Die Potenzmengenkonstruktion ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt.
 
Die Zustände des aus dem NEA abzuleitenden DEA sind Mengen von Zuständen des NEA. Ein Zustand des DEA kodiert dabei all diejenigen Zustände, in denen sich der äquivalente nichtdeterministische Automat NEA zu einem bestimmten Zeitpunkt befinden könnte. Ein Zustandsübergang im DEA ist deterministisch, da sein Folgezustand aus der Menge aller möglichen Folgezustände besteht, in die ein NEA unter einer bestimmten Eingabe gelangen kann. Das Verfahren heißt Potenzmengenkonstruktion, weil die Zustände des konstruierten Automaten Mengen von Zuständen des Ausgangsautomaten sind und daher die konstruierte Zustandsmenge Teil der Potenzmenge der Zustandsmenge des Ausgangsautomaten ist.  


== ε-NEA ==
Der direkte Vergleich der beiden Diagramme zeigt den praktischen Vorteil des Nichtdeterminismus beim Entwurf:
''Hauptartikel: [[Nichtdeterministischer endlicher Automat#ε-NEA]]''
* '''Modellierung als NEA (oberes Bild):'''
ε-NEAs sind ein nützliches Werkzeug in der Theorie formaler Sprachen und Automatentheorie. Sie bieten Flexibilität und können in vielen Fällen den Design- und Analyseprozess vereinfachen, da sie es ermöglichen, Zustände ohne das Verarbeiten eines Symbols zu wechseln. Das kann in manchen Situationen die Konstruktion eines Automaten erleichtern. In manchen Fällen kann ein ε-NEA eine kompaktere und klarere Darstellung eines Problems oder einer Sprache bieten als ein NEA oder DEA.
** Im Startzustand <math>q_0</math> besitzt der NEA eine Schleife für '''alle''' Zeichen <math>A \dots Z</math> (also auch für <math>U</math>) und zusätzlich einen Übergang mit <math>U</math> nach <math>q_1</math>. Für das Paar <math>(q_0, U)</math> gibt es somit zwei mögliche Folgezustände: <math>\delta(q_0, U) = \{q_0, q_1\}</math>.
** In den Zuständen <math>q_1</math> und <math>q_2</math> müssen '''keine''' Rücksprungkanten für falsche Buchstaben gezeichnet werden: Folgt auf ein <math>U</math> kein <math>M</math>, stirbt der Pfad in <math>q_1</math> einfach ab, während der parallele Pfad in <math>q_0</math> weiterläuft und auf das nächste <math>U</math> wartet.
** Sobald irgendwo im Wort die Folge <code>UML</code> auftritt, erreicht ein Pfad über <math>q_0 \xrightarrow{U} q_1 \xrightarrow{M} q_2 \xrightarrow{L} q_3</math> den Endzustand <math>q_3</math> und verbleibt dort für alle weiteren Zeichen.
* '''Modellierung als DEA (unteres Bild):'''
** Da beim DEA in jedem Zustand für jedes Zeichen genau ein Folgezustand festgelegt sein muss, darf <math>q_0</math> die Schleife nur für <math>\Sigma \setminus \{U\}</math> besitzen.
** Bricht die Teilfolge <code>UML</code> in <math>q_1</math> oder <math>q_2</math> ab, muss der DEA exakt unterscheiden, wohin er zurückspringt: Liest er in <math>q_1</math> (nach einem <math>U</math>) ein weiteres <math>U</math> (z. B. beim Wort <code>UUML</code>), muss er in <math>q_1</math> bleiben; bei jedem anderen Zeichen außer <math>M</math> und <math>U</math> fällt er nach <math>q_0</math> zurück. Analog führt in <math>q_2</math> (nach <code>UM</code>) ein <math>U</math> zurück nach <math>q_1</math> (da dieses <math>U</math> bereits der Beginn eines neuen <code>UML</code> sein kann, wie in <code>UMUML</code>), während alle Zeichen außer <math>L</math> und <math>U</math> ganz nach <math>q_0</math> zurückführen.


Um die Darstellung von endlichen Automaten zu vereinfachen, können Zustandsübergänge ohne Einlesen eines Zeichens ausgelöst werden. Diese Zustandsübergänge bezeichnet man als Epsilon-Übergänge. Für jeden nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen gibt es einen nichtdeterministischen endlichen Automaten ohne Epsilon-Übergänge, der dieselbe Sprache erkennt, und umgekehrt. Die beiden Maschinenmodelle sind also äquivalent. Genau wie der normale nichtdeterministische endliche Automat erkennt ein nichtdeterministischer endlicher Automat mit Epsilon-Übergängen ein Wort w, wenn es in seinem Zustandsgraphen einen Pfad vom Startzustand zu einem Endzustand gibt, der genau die Zeichen von w liest.
Beide Automaten akzeptieren exakt dieselbe Sprache <math>L</math>, der NEA ist jedoch deutlich einfacher zu konstruieren.


=== Umwandlung ε-NEA zu NEA ===
===Wörter mit einem ε-NEA akzeptieren===
[[Datei:ε-NEA Nur a oder nur b.png|mini|ε-NEA für Wörter nur aus a oder nur aus b]]
Gesucht ist ein Automat über dem Alphabet <math>\Sigma = \{a, b\}</math>, der alle Wörter akzeptiert, die '''entweder nur aus <math>a</math>''' oder '''nur aus <math>b</math>''' bestehen (einschließlich des leeren Wortes <math>\varepsilon</math>). Wörter, in denen sowohl <math>a</math> als auch <math>b</math> vorkommen (wie <math>ab</math> oder <math>ba</math>), sollen abgelehnt werden:


Jeder ε-NEA lässt sich in einen NEA ohne ε-Übergänge umwandeln. Hierfür entfernt man die ε-Übergänge und betrachtet die Zustandsmengen, die von den Zuständen aus Q über ε-Übergänge erreicht werden können. Für diese resultierenden Zustandsmengen wird analog zum Verfahren der Potenzmengenkonstruktion ein NEA ohne ε-Übergänge abgeleitet.
:<math>L = \{a^n \mid n \ge 0\} \cup \{b^n \mid n \ge 0\} = \{\varepsilon, a, b, aa, bb, aaa, bbb, \dots\}</math>


=== Beispiel ===
'''1. Aufbau des <math>\varepsilon</math>-NEA:'''
* Vom Startzustand <math>q_0</math> führen zwei <math>\varepsilon</math>-Übergänge ohne Lesen eines Zeichens direkt in die beiden Endzustände <math>q_1</math> und <math>q_2</math> (<math>F = \{q_1, q_2\}</math>).
* Im Endzustand <math>q_1</math> existiert ausschließlich eine Schleife für das Zeichen <math>a</math>; im Endzustand <math>q_2</math> existiert ausschließlich eine Schleife für das Zeichen <math>b</math>.
* Durch die <math>\varepsilon</math>-Übergänge verzweigt der Automat bereits vor dem ersten Zeichen in zwei getrennte Zweige („nur <math>a</math>-Wörter“ in <math>q_1</math> und „nur <math>b</math>-Wörter“ in <math>q_2</math>).


[[Datei:ε-NEA Nur a oder nur b.png|mini|ε-NEA]]
'''2. Wortzugehörigkeit am <math>\varepsilon</math>-NEA nachvollziehen:'''
Das Diagramm zeigt einen ε-NEA, der Wörter akzeptiert, die nur aus a oder nur aus b bestehen, auch das leere Wort. Von q0 führen ε-Übergänge nach q1 und q2, die beide Endzustände sind.
* '''Leeres Wort <math>\varepsilon \in L</math>:''' Obwohl der Startzustand <math>q_0</math> selbst kein Endzustand ist, gelangt der Automat ohne Zeicheneingabe über <math>q_0 \xrightarrow{\varepsilon} q_1 \in F</math> (oder <math>q_0 \xrightarrow{\varepsilon} q_2 \in F</math>) sofort in einen Endzustand. Das leere Wort wird akzeptiert.
* '''Wort <math>bb \in L</math>:''' Über den Pfad <math>q_0 \xrightarrow{\varepsilon} q_2 \xrightarrow{b} q_2 \xrightarrow{b} q_2 \in F</math> wird das Wort vollständig gelesen und im Endzustand <math>q_2</math> akzeptiert.
* '''Wort <math>ab \notin L</math>:''' Wechselt der Automat über <math>\varepsilon</math> nach <math>q_1</math>, kann er zwar das <math>a</math> lesen, bleibt aber beim anschließenden <math>b</math> stecken (kein <math>b</math>-Übergang in <math>q_1</math>). Wechselt er über <math>\varepsilon</math> nach <math>q_2</math>, scheitert er bereits am ersten Zeichen <math>a</math>. Da kein Pfad zum Ziel führt, wird <math>ab</math> abgelehnt.


Die Umwandlung in einen DEA zeigt [[Potenzmengenkonstruktion#ε-NEA in einen DEA überführen]].
Die schrittweise Umwandlung dieses <math>\varepsilon</math>-NEA in einen äquivalenten DEA wird im Artikel [[Potenzmengenkonstruktion#ε-NEA in einen DEA überführen]] durchgeführt.


[[Kategorie:Automaten]]
[[Kategorie:Automaten]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:Formale Sprachen]]
[[Kategorie:AHR I Informatik LK]]

Version vom 10. November 2026, 08:33 Uhr

Technische Systeme und Programme wie Getränkeautomaten, Ampelsteuerungen, Aufzüge oder Textfilter reagieren auf Eingaben nach festen Regeln. Ein endlicher Automat modelliert solche Systeme mathematisch mithilfe endlich vieler Zustände und eindeutig festgelegter Zustandsübergänge.

Definition

Ein endlicher Automat (kurz EA, auch Zustandsmaschine oder Zustandsautomat; englisch finite state machine, FSM) ist ein abstraktes Verhaltensmodell eines Systems mit diskreten Ein- und Ausgaben. Diskret bedeutet, dass der Automat ein Eingabewort schrittweise (Zeichen für Zeichen) in einzelnen Taktschritten verarbeitet.

Jeder endliche Automat besitzt folgende Grundbestandteile:

  • Endliche Zustandsmenge [math]\displaystyle{ Q }[/math]: Eine nicht leere, endliche Menge von Zuständen ([math]\displaystyle{ Q \neq \emptyset }[/math]). Das System befindet sich zu jedem Zeitpunkt in genau einem Zustand [math]\displaystyle{ q \in Q }[/math] (bzw. beim nichtdeterministischen Automaten in einer Menge möglicher Zustände).
  • Endliches Eingabealphabet [math]\displaystyle{ \Sigma }[/math]: Ein nicht leeres Alphabet ([math]\displaystyle{ \Sigma \neq \emptyset }[/math]), aus dessen Zeichen die Eingabewörter [math]\displaystyle{ w \in \Sigma^* }[/math] gebildet werden.
  • Startzustand [math]\displaystyle{ q_0 \in Q }[/math]: Der eindeutig festgelegte Ausgangszustand, in dem sich der Automat vor dem Lesen des ersten Zeichens befindet.
  • Übergangsfunktion [math]\displaystyle{ \delta }[/math]: Eine Zuordnungsvorschrift, die festlegt, in welchen Folgezustand der Automat wechselt, wenn er im aktuellen Zustand ein bestimmtes Eingabezeichen liest.

Nach ihrem Verwendungszweck unterscheidet man zwei Grundtypen endlicher Automaten:

  • Akzeptoren (Spracherkenner, z. B. DEA und NEA): Sie besitzen keine eigene Ausgabe, sondern eine Menge akzeptierender Endzustände [math]\displaystyle{ F \subseteq Q }[/math]. Nach dem vollständigen Lesen eines Wortes [math]\displaystyle{ w \in \Sigma^* }[/math] entscheidet der erreichte Zustand darüber, ob das Wort akzeptiert wird und damit zur formalen Sprache [math]\displaystyle{ L(A) }[/math] des Automaten gehört ([math]\displaystyle{ w \in L(A) }[/math]) oder ob es abgelehnt wird ([math]\displaystyle{ w \notin L(A) }[/math]).
  • Transduktoren (Automaten mit Ausgabe, z. B. Mealy-Automat): Sie besitzen zusätzlich ein endliches Ausgabealphabet [math]\displaystyle{ \Omega }[/math] und eine Ausgabefunktion [math]\displaystyle{ \lambda }[/math], die bei jedem Zustandsübergang ein Ausgabezeichen erzeugt.

Übergangsfunktion

Die Übergangsfunktion [math]\displaystyle{ \delta }[/math] beschreibt das Verhalten eines endlichen Automaten vollständig. Sie lässt sich auf zwei gleichwertige Arten darstellen:

  • Übergangsgraph (UML-Zustandsdiagramm):
    • Die Zustände [math]\displaystyle{ q \in Q }[/math] werden als Kreise gezeichnet.
    • Der Startzustand [math]\displaystyle{ q_0 }[/math] wird durch einen eingehenden Pfeil ohne Ursprungsknoten markiert.
    • Akzeptierende Endzustände [math]\displaystyle{ q \in F }[/math] werden durch einen Doppelkreis gekennzeichnet.
    • Zustandsübergänge werden als gerichtete Pfeile (Kanten) zwischen den Zuständen dargestellt und mit dem auslösenden Eingabezeichen [math]\displaystyle{ a \in \Sigma }[/math] beschriftet (beim Mealy-Automaten ergänzt um die Ausgabe in der Form Eingabe / Ausgabe).
  • Übergangstabelle:
    • Die Zeilen der Tabelle entsprechen den aktuellen Zuständen [math]\displaystyle{ q \in Q }[/math], die Spalten den Eingabezeichen [math]\displaystyle{ a \in \Sigma }[/math].
    • Im Schnittpunkt einer Zeile [math]\displaystyle{ q }[/math] und einer Spalte [math]\displaystyle{ a }[/math] steht der Folgezustand [math]\displaystyle{ \delta(q, a) }[/math] (bzw. beim NEA die Menge der Folgezustände).
    • In der ersten Spalte wird der Startzustand häufig mit einem Pfeil ([math]\displaystyle{ \rightarrow q_0 }[/math]) und jeder Endzustand mit einem Stern ([math]\displaystyle{ {}^*q }[/math]) markiert.

Mealy-Automat

Hauptartikel: Mealy-Automat

Definition

Ein Mealy-Automat ist ein deterministischer endlicher Automat mit Ausgabe. Zu jedem gelesenen Zeichen des Eingabealphabets wechselt er abhängig vom aktuellen Zustand in einen eindeutig bestimmten Folgezustand und gibt gleichzeitig ein Zeichen des Ausgabealphabets aus.

Formal ist ein Mealy-Automat definiert als 7-Tupel [math]\displaystyle{ A = (Q, \Sigma, \Omega, \delta, \lambda, q_0, F) }[/math]:

  • [math]\displaystyle{ Q }[/math] ist eine endliche, nicht leere Menge von Zuständen ([math]\displaystyle{ Q \neq \emptyset }[/math]).
  • [math]\displaystyle{ \Sigma }[/math] ist ein endliches, nicht leeres Eingabealphabet ([math]\displaystyle{ \Sigma \neq \emptyset }[/math]).
  • [math]\displaystyle{ \Omega }[/math] ist ein endliches, nicht leeres Ausgabealphabet ([math]\displaystyle{ \Omega \neq \emptyset }[/math]).
  • [math]\displaystyle{ \delta: Q \times \Sigma \to Q }[/math] ist die Übergangsfunktion, die jedem Paar aus aktuellem Zustand [math]\displaystyle{ q \in Q }[/math] und Eingabezeichen [math]\displaystyle{ a \in \Sigma }[/math] genau einen Folgezustand [math]\displaystyle{ \delta(q, a) \in Q }[/math] zuordnet.
  • [math]\displaystyle{ \lambda: Q \times \Sigma \to \Omega }[/math] ist die Ausgabefunktion, die jedem Paar aus aktuellem Zustand [math]\displaystyle{ q \in Q }[/math] und Eingabezeichen [math]\displaystyle{ a \in \Sigma }[/math] genau ein Ausgabezeichen [math]\displaystyle{ \lambda(q, a) \in \Omega }[/math] zuordnet.
  • [math]\displaystyle{ q_0 \in Q }[/math] ist der Startzustand.
  • [math]\displaystyle{ F \subseteq Q }[/math] ist die Menge der Endzustände. Da ein Mealy-Automat primär zur fortlaufenden Ausgabe dient, ist oft jeder Zustand ein Endzustand ([math]\displaystyle{ F = Q }[/math]). In der Fachliteratur wird der Mealy-Automat daher häufig auch als 6-Tupel [math]\displaystyle{ A = (Q, \Sigma, \Omega, \delta, \lambda, q_0) }[/math] ohne [math]\displaystyle{ F }[/math] definiert.

DEA - Deterministischer endlicher Automat

Hauptartikel: Deterministischer endlicher Automat

Definition

Ein endlicher Automat heißt deterministisch (kurz DEA; englisch deterministic finite automaton, DFA), wenn für jeden Zustand [math]\displaystyle{ q \in Q }[/math] und jedes Eingabezeichen [math]\displaystyle{ a \in \Sigma }[/math] höchstens ein (bei einem vollständigen DEA genau ein) Folgezustand existiert. Das Verhalten des Automaten ist für jede Eingabe eindeutig vorbestimmt; es gibt keine Wahlmöglichkeiten beim Zustandswechsel. Im Unterschied zum Mealy-Automaten besitzt ein DEA keine Ausgabefunktion, sondern entscheidet über die Zugehörigkeit eines Wortes zu einer formalen Sprache.

Formal ist ein deterministischer endlicher Automat definiert als 5-Tupel [math]\displaystyle{ A = (Q, \Sigma, \delta, q_0, F) }[/math]:

  • [math]\displaystyle{ Q }[/math] ist eine endliche, nicht leere Menge von Zuständen ([math]\displaystyle{ Q \neq \emptyset }[/math]).
  • [math]\displaystyle{ \Sigma }[/math] ist ein endliches, nicht leeres Eingabealphabet ([math]\displaystyle{ \Sigma \neq \emptyset }[/math]).
  • [math]\displaystyle{ \delta: Q \times \Sigma \to Q }[/math] ist die Übergangsfunktion, die jedem Paar aus Zustand [math]\displaystyle{ q \in Q }[/math] und Eingabezeichen [math]\displaystyle{ a \in \Sigma }[/math] eindeutig einen Folgezustand zuordnet.
  • [math]\displaystyle{ q_0 \in Q }[/math] ist der Startzustand.
  • [math]\displaystyle{ F \subseteq Q }[/math] ist die Menge der akzeptierenden Endzustände.

Ein Wort [math]\displaystyle{ w \in \Sigma^* }[/math] wird vom DEA akzeptiert (es gilt [math]\displaystyle{ w \in L(A) }[/math]), wenn sich der Automat nach dem vollständigen Lesen aller Zeichen von [math]\displaystyle{ w }[/math] (beginnend bei [math]\displaystyle{ q_0 }[/math]) in einem Endzustand [math]\displaystyle{ q \in F }[/math] befindet. Die Menge aller akzeptierten Wörter bildet die vom Automaten erkannte Sprache [math]\displaystyle{ L(A) }[/math].

Nichtdeterministischer endlicher Automat

Hauptartikel: Nichtdeterministischer endlicher Automat

Definition

Ein nichtdeterministischer endlicher Automat (kurz NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem für denselben Zustand und dasselbe Eingabezeichen mehrere gleichwertige Folgezustände oder auch gar kein Folgezustand existieren können. Der Automat ist beim Lesen eines Zeichens also nicht auf einen einzigen Pfad festgelegt, sondern kann mehrere Berechnungswege parallel verfolgen.

Formal ist ein nichtdeterministischer endlicher Automat definiert als 5-Tupel [math]\displaystyle{ A = (Q, \Sigma, \delta, q_0, F) }[/math]:

  • [math]\displaystyle{ Q }[/math] ist eine endliche, nicht leere Menge von Zuständen ([math]\displaystyle{ Q \neq \emptyset }[/math]).
  • [math]\displaystyle{ \Sigma }[/math] ist ein endliches, nicht leeres Eingabealphabet ([math]\displaystyle{ \Sigma \neq \emptyset }[/math]).
  • [math]\displaystyle{ \delta: Q \times \Sigma \to \mathcal{P}(Q) }[/math] ist die Übergangsfunktion, die jedem Paar aus Zustand [math]\displaystyle{ q \in Q }[/math] und Eingabezeichen [math]\displaystyle{ a \in \Sigma }[/math] eine Menge von Folgezuständen zuordnet. Dabei bezeichnet [math]\displaystyle{ \mathcal{P}(Q) }[/math] die Potenzmenge von [math]\displaystyle{ Q }[/math] (die Menge aller Teilmengen von [math]\displaystyle{ Q }[/math]). Gibt es für ein Zeichen keinen Übergang, liefert die Funktion die leere Menge [math]\displaystyle{ \emptyset }[/math].
  • [math]\displaystyle{ q_0 \in Q }[/math] ist der Startzustand.
  • [math]\displaystyle{ F \subseteq Q }[/math] ist die Menge der akzeptierenden Endzustände.

Ein Wort [math]\displaystyle{ w \in \Sigma^* }[/math] gehört genau dann zur akzeptierten Sprache [math]\displaystyle{ L(A) }[/math] des NEA, wenn mindestens ein gültiger Pfad vom Startzustand [math]\displaystyle{ q_0 }[/math] nach dem vollständigen Lesen von [math]\displaystyle{ w }[/math] in einem akzeptierenden Endzustand [math]\displaystyle{ q \in F }[/math] endet. Dass andere Pfade in Nicht-Endzuständen enden oder vorzeitig abbrechen, verhindert die Akzeptanz nicht.

ε-NEA

Hauptartikel: Nichtdeterministischer endlicher Automat#ε-NEA

Ein nichtdeterministischer endlicher Automat mit [math]\displaystyle{ \varepsilon }[/math]-Übergängen (kurz [math]\displaystyle{ \varepsilon }[/math]-NEA) erweitert den NEA um sogenannte Epsilon-Übergänge (auch Spontanübergänge). Ein mit dem leeren Wort [math]\displaystyle{ \varepsilon }[/math] beschrifteter Übergang ermöglicht es dem Automaten, den Zustand zu wechseln, ohne dabei ein Zeichen des Eingabealphabets zu lesen. Dadurch lassen sich viele Automaten deutlich kompakter und übersichtlicher entwerfen.

Formal ist ein [math]\displaystyle{ \varepsilon }[/math]-NEA definiert als 5-Tupel [math]\displaystyle{ A = (Q, \Sigma, \delta, q_0, F) }[/math], wobei die Übergangsfunktion das Eingabealphabet um [math]\displaystyle{ \varepsilon }[/math] erweitert:

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

Ein Wort [math]\displaystyle{ w \in \Sigma^* }[/math] wird vom [math]\displaystyle{ \varepsilon }[/math]-NEA akzeptiert ([math]\displaystyle{ w \in L(A) }[/math]), wenn im Zustandsgraphen mindestens ein Pfad vom Startzustand [math]\displaystyle{ q_0 }[/math] zu einem Endzustand [math]\displaystyle{ q \in F }[/math] existiert, entlang dessen Kanten (unter beliebig häufiger Nutzung von [math]\displaystyle{ \varepsilon }[/math]-Übergängen) genau die Zeichenfolge von [math]\displaystyle{ w }[/math] gelesen wird.

Umwandlung ε-NEA zu NEA

Ein [math]\displaystyle{ \varepsilon }[/math]-NEA ist genauso mächtig wie ein gewöhnlicher NEA oder ein DEA: Zu jedem [math]\displaystyle{ \varepsilon }[/math]-NEA existiert ein äquivalenter NEA ohne [math]\displaystyle{ \varepsilon }[/math]-Übergänge sowie ein äquivalenter DEA, die exakt dieselbe Sprache erkennen.

Um einen [math]\displaystyle{ \varepsilon }[/math]-NEA in einen NEA ohne [math]\displaystyle{ \varepsilon }[/math]-Übergänge (oder direkt in einen DEA) umzuwandeln, bestimmt man für jeden Zustand [math]\displaystyle{ q \in Q }[/math] zunächst die [math]\displaystyle{ \varepsilon }[/math]-Hülle [math]\displaystyle{ E(q) }[/math]: Das ist die Menge aller Zustände, die von [math]\displaystyle{ q }[/math] aus ausschließlich über [math]\displaystyle{ \varepsilon }[/math]-Übergänge (einschließlich [math]\displaystyle{ q }[/math] selbst) erreichbar sind. Anschließend werden die Übergänge für die regulären Zeichen aus [math]\displaystyle{ \Sigma }[/math] auf diese Zustandsmengen übertragen (siehe Potenzmengenkonstruktion#ε-NEA in einen DEA überführen).

Potenzmengenkonstruktion

Hauptartikel: Potenzmengenkonstruktion

Die Potenzmengenkonstruktion ist ein systematisches Verfahren, das jeden nichtdeterministischen endlichen Automaten (NEA oder [math]\displaystyle{ \varepsilon }[/math]-NEA) in einen sprachäquivalenten deterministischen endlichen Automaten (DEA) umwandelt ([math]\displaystyle{ L(\text{DEA}) = L(\text{NEA}) }[/math]).

Die Grundidee besteht darin, alle Zustände, in denen sich der NEA nach einer bestimmten Eingabe gleichzeitig befinden kann, im DEA zu einem einzigen Mengenzustand zusammenzufassen:

  • Zustände als Teilmengen: Jeder Zustand des neuen DEA ist eine Teilmenge der ursprünglichen Zustandsmenge [math]\displaystyle{ Q }[/math], also ein Element der Potenzmenge [math]\displaystyle{ \mathcal{P}(Q) }[/math] (z. B. [math]\displaystyle{ \{q_0, q_1\} }[/math]).
  • Deterministischer Übergang: Für einen Mengenzustand und ein Eingabezeichen [math]\displaystyle{ a \in \Sigma }[/math] bildet man die Vereinigung aller Folgezustände, die der NEA von den enthaltenen Einzelzuständen aus mit [math]\displaystyle{ a }[/math] erreichen kann. Diese Vereinigungsmenge ist der eindeutig bestimmte Folgezustand im DEA.
  • Endzustände im DEA: Ein Mengenzustand des DEA ist genau dann ein akzeptierender Endzustand, wenn er mindestens einen ursprünglichen Endzustand [math]\displaystyle{ q \in F }[/math] des NEA enthält.

Beispiele

Bonbonautomat als Mealy-Automat modellieren

Bonbonautomat als Mealy-Automat

Ein mechanischer Bonbonautomat gibt genau dann ein Bonbon aus, wenn zuerst eine Münze eingeworfen und anschließend der Hebel gedreht wird. Dreht man den Hebel ohne vorherigen Münzeinwurf, passiert nichts. Wirft man mehrere Münzen nacheinander ein, ohne zwischendurch den Hebel zu drehen, bleibt der Automat im bezahlten Zustand, gibt aber noch kein Bonbon aus.

1. Formale Beschreibung als 7-Tupel [math]\displaystyle{ A = (Q, \Sigma, \Omega, \delta, \lambda, q_0, F) }[/math]:

  • Zustandsmenge [math]\displaystyle{ Q = \{q_0, q_1\} }[/math]:
    • [math]\displaystyle{ q_0 }[/math]: Keine Münze eingeworfen (Wartezustand / Startzustand).
    • [math]\displaystyle{ q_1 }[/math]: Münze ist eingeworfen (Bereitschaftszustand für Bonbonausgabe).
  • Eingabealphabet [math]\displaystyle{ \Sigma = \{M, H\} }[/math]:
    • [math]\displaystyle{ M }[/math]: Münze einwerfen.
    • [math]\displaystyle{ H }[/math]: Hebel drehen.
  • Ausgabealphabet [math]\displaystyle{ \Omega = \{B, N\} }[/math]:
    • [math]\displaystyle{ B }[/math]: Bonbon ausgeben.
    • [math]\displaystyle{ N }[/math]: Keine Ausgabe (Nichts).
  • Startzustand: [math]\displaystyle{ q_0 }[/math].
  • Endzustandsmenge: [math]\displaystyle{ F = Q = \{q_0, q_1\} }[/math] (jeder Zustand ist ein zulässiger Endzustand).

2. Übergangsfunktion [math]\displaystyle{ \delta }[/math] und Ausgabefunktion [math]\displaystyle{ \lambda }[/math] in Tabellenform:

Übergangsfunktion [math]\displaystyle{ \delta(q, a) }[/math] (Folgezustand)
[math]\displaystyle{ \delta }[/math] [math]\displaystyle{ M }[/math] [math]\displaystyle{ H }[/math]
[math]\displaystyle{ \rightarrow {}^*q_0 }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ q_0 }[/math]
[math]\displaystyle{ {}^*q_1 }[/math] [math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ q_0 }[/math]
Ausgabefunktion [math]\displaystyle{ \lambda(q, a) }[/math] (Ausgabezeichen)
[math]\displaystyle{ \lambda }[/math] [math]\displaystyle{ M }[/math] [math]\displaystyle{ H }[/math]
[math]\displaystyle{ \rightarrow {}^*q_0 }[/math] [math]\displaystyle{ N }[/math] [math]\displaystyle{ N }[/math]
[math]\displaystyle{ {}^*q_1 }[/math] [math]\displaystyle{ N }[/math] [math]\displaystyle{ B }[/math]

3. Verarbeitung konkreter Eingabefolgen prüfen:

  • Eingabewort [math]\displaystyle{ w_1 = MH }[/math] (korrekte Bedienung):
    • Start in [math]\displaystyle{ q_0 }[/math]. Beim Lesen von [math]\displaystyle{ M }[/math] wechselt der Automat nach [math]\displaystyle{ \delta(q_0, M) = q_1 }[/math] und gibt [math]\displaystyle{ \lambda(q_0, M) = N }[/math] aus.
    • In [math]\displaystyle{ q_1 }[/math] wird [math]\displaystyle{ H }[/math] gelesen: Der Automat wechselt zurück nach [math]\displaystyle{ \delta(q_1, H) = q_0 }[/math] und gibt [math]\displaystyle{ \lambda(q_1, H) = B }[/math] (Bonbon) aus. Die gesamte Ausgabefolge lautet [math]\displaystyle{ NB }[/math].
  • Eingabewort [math]\displaystyle{ w_2 = HM }[/math] (falsche Reihenfolge):
    • Start in [math]\displaystyle{ q_0 }[/math]. Beim Lesen von [math]\displaystyle{ H }[/math] bleibt der Automat in [math]\displaystyle{ \delta(q_0, H) = q_0 }[/math] und gibt [math]\displaystyle{ \lambda(q_0, H) = N }[/math] aus (Hebel dreht leer durch).
    • Anschließend wird in [math]\displaystyle{ q_0 }[/math] das Zeichen [math]\displaystyle{ M }[/math] gelesen: Der Automat wechselt nach [math]\displaystyle{ q_1 }[/math] und gibt erneut [math]\displaystyle{ N }[/math] aus. Die Ausgabefolge lautet [math]\displaystyle{ NN }[/math] (kein Bonbon).

Kaffeeautomat als deterministischen endlichen Automaten (DEA) angeben

Vollständiger DEA des Kaffeeautomaten

Ein Kaffeeautomat sammelt den Kaffeesatz in einem Satzfach, das genau 4 Einheiten fasst. Ein Kaffee ([math]\displaystyle{ K }[/math]) erzeugt 1 Einheit Kaffeesatz, ein Espresso ([math]\displaystyle{ E }[/math]) erzeugt 2 Einheiten. Der Automat soll genau die Tastenkombinationen akzeptieren, nach denen das Satzfach exakt mit 4 Einheiten gefüllt ist.

1. Formale Beschreibung als 5-Tupel [math]\displaystyle{ A = (Q, \Sigma, \delta, q_0, F) }[/math]:

  • Zustandsmenge [math]\displaystyle{ Q = \{q_0, q_1, q_2, q_3, q_4, q_5\} }[/math]: Die Zustände [math]\displaystyle{ q_0 }[/math] bis [math]\displaystyle{ q_4 }[/math] speichern den aktuellen Füllstand des Satzfachs (0 bis 4 Einheiten). Der Zustand [math]\displaystyle{ q_5 }[/math] ist ein sogenannter Fangzustand (Fehlerzustand) für einen Überlauf (mehr als 4 Einheiten), der nicht mehr verlassen werden kann.
  • Eingabealphabet [math]\displaystyle{ \Sigma = \{K, E\} }[/math]: [math]\displaystyle{ K }[/math] steht für Kaffee (+1 Einheit), [math]\displaystyle{ E }[/math] für Espresso (+2 Einheiten).
  • Startzustand [math]\displaystyle{ q_0 }[/math]: Zu Beginn ist das Satzfach leer (0 Einheiten).
  • Endzustandsmenge [math]\displaystyle{ F = \{q_4\} }[/math]: Nur bei exakt 4 Einheiten ([math]\displaystyle{ q_4 }[/math]) ist das Satzfach planmäßig voll.

2. Wortverarbeitung und akzeptierte Sprache:

  • Für das Eingabewort [math]\displaystyle{ w_1 = KEK }[/math] durchläuft der DEA eindeutig die Zustandsfolge:
[math]\displaystyle{ q_0 \xrightarrow{K} q_1 \xrightarrow{E} q_3 \xrightarrow{K} q_4 \in F }[/math]
Da [math]\displaystyle{ q_4 }[/math] ein Endzustand ist, wird [math]\displaystyle{ KEK }[/math] akzeptiert ([math]\displaystyle{ KEK \in L(A) }[/math]).
  • Für das Eingabewort [math]\displaystyle{ w_2 = EEK }[/math] lautet die Zustandsfolge:
[math]\displaystyle{ q_0 \xrightarrow{E} q_2 \xrightarrow{E} q_4 \xrightarrow{K} q_5 \notin F }[/math]
Da der Automat im Fehlerzustand [math]\displaystyle{ q_5 }[/math] endet, wird [math]\displaystyle{ EEK }[/math] abgelehnt ([math]\displaystyle{ EEK \notin L(A) }[/math]).
  • Insgesamt akzeptiert der DEA genau die endliche Sprache [math]\displaystyle{ L(A) = \{KKKK, EE, EKK, KEK, KKE\} }[/math].

Spam-Filter als NEA und DEA gegenüberstellen

Spam-Filter als NEA
Spam-Filter als DEA

Ein einfacher Spam-Filter durchsucht Texte über dem Eingabealphabet [math]\displaystyle{ \Sigma = \{A, \dots, Z\} }[/math] nach der Zeichenfolge UML. Sobald ein Wort die Teilzeichenfolge UML an beliebiger Stelle enthält (also zur Sprache [math]\displaystyle{ L = \{w \in \Sigma^* \mid w \text{ enthält } UML\} }[/math] gehört), soll der Automat im Endzustand [math]\displaystyle{ q_3 }[/math] akzeptieren.

Der direkte Vergleich der beiden Diagramme zeigt den praktischen Vorteil des Nichtdeterminismus beim Entwurf:

  • Modellierung als NEA (oberes Bild):
    • Im Startzustand [math]\displaystyle{ q_0 }[/math] besitzt der NEA eine Schleife für alle Zeichen [math]\displaystyle{ A \dots Z }[/math] (also auch für [math]\displaystyle{ U }[/math]) und zusätzlich einen Übergang mit [math]\displaystyle{ U }[/math] nach [math]\displaystyle{ q_1 }[/math]. Für das Paar [math]\displaystyle{ (q_0, U) }[/math] gibt es somit zwei mögliche Folgezustände: [math]\displaystyle{ \delta(q_0, U) = \{q_0, q_1\} }[/math].
    • In den Zuständen [math]\displaystyle{ q_1 }[/math] und [math]\displaystyle{ q_2 }[/math] müssen keine Rücksprungkanten für falsche Buchstaben gezeichnet werden: Folgt auf ein [math]\displaystyle{ U }[/math] kein [math]\displaystyle{ M }[/math], stirbt der Pfad in [math]\displaystyle{ q_1 }[/math] einfach ab, während der parallele Pfad in [math]\displaystyle{ q_0 }[/math] weiterläuft und auf das nächste [math]\displaystyle{ U }[/math] wartet.
    • Sobald irgendwo im Wort die Folge UML auftritt, erreicht ein Pfad über [math]\displaystyle{ q_0 \xrightarrow{U} q_1 \xrightarrow{M} q_2 \xrightarrow{L} q_3 }[/math] den Endzustand [math]\displaystyle{ q_3 }[/math] und verbleibt dort für alle weiteren Zeichen.
  • Modellierung als DEA (unteres Bild):
    • Da beim DEA in jedem Zustand für jedes Zeichen genau ein Folgezustand festgelegt sein muss, darf [math]\displaystyle{ q_0 }[/math] die Schleife nur für [math]\displaystyle{ \Sigma \setminus \{U\} }[/math] besitzen.
    • Bricht die Teilfolge UML in [math]\displaystyle{ q_1 }[/math] oder [math]\displaystyle{ q_2 }[/math] ab, muss der DEA exakt unterscheiden, wohin er zurückspringt: Liest er in [math]\displaystyle{ q_1 }[/math] (nach einem [math]\displaystyle{ U }[/math]) ein weiteres [math]\displaystyle{ U }[/math] (z. B. beim Wort UUML), muss er in [math]\displaystyle{ q_1 }[/math] bleiben; bei jedem anderen Zeichen außer [math]\displaystyle{ M }[/math] und [math]\displaystyle{ U }[/math] fällt er nach [math]\displaystyle{ q_0 }[/math] zurück. Analog führt in [math]\displaystyle{ q_2 }[/math] (nach UM) ein [math]\displaystyle{ U }[/math] zurück nach [math]\displaystyle{ q_1 }[/math] (da dieses [math]\displaystyle{ U }[/math] bereits der Beginn eines neuen UML sein kann, wie in UMUML), während alle Zeichen außer [math]\displaystyle{ L }[/math] und [math]\displaystyle{ U }[/math] ganz nach [math]\displaystyle{ q_0 }[/math] zurückführen.

Beide Automaten akzeptieren exakt dieselbe Sprache [math]\displaystyle{ L }[/math], der NEA ist jedoch deutlich einfacher zu konstruieren.

Wörter mit einem ε-NEA akzeptieren

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

Gesucht ist ein Automat über dem Alphabet [math]\displaystyle{ \Sigma = \{a, b\} }[/math], der alle Wörter akzeptiert, die entweder nur aus [math]\displaystyle{ a }[/math] oder nur aus [math]\displaystyle{ b }[/math] bestehen (einschließlich des leeren Wortes [math]\displaystyle{ \varepsilon }[/math]). Wörter, in denen sowohl [math]\displaystyle{ a }[/math] als auch [math]\displaystyle{ b }[/math] vorkommen (wie [math]\displaystyle{ ab }[/math] oder [math]\displaystyle{ ba }[/math]), sollen abgelehnt werden:

[math]\displaystyle{ L = \{a^n \mid n \ge 0\} \cup \{b^n \mid n \ge 0\} = \{\varepsilon, a, b, aa, bb, aaa, bbb, \dots\} }[/math]

1. Aufbau des [math]\displaystyle{ \varepsilon }[/math]-NEA:

  • Vom Startzustand [math]\displaystyle{ q_0 }[/math] führen zwei [math]\displaystyle{ \varepsilon }[/math]-Übergänge ohne Lesen eines Zeichens direkt in die beiden Endzustände [math]\displaystyle{ q_1 }[/math] und [math]\displaystyle{ q_2 }[/math] ([math]\displaystyle{ F = \{q_1, q_2\} }[/math]).
  • Im Endzustand [math]\displaystyle{ q_1 }[/math] existiert ausschließlich eine Schleife für das Zeichen [math]\displaystyle{ a }[/math]; im Endzustand [math]\displaystyle{ q_2 }[/math] existiert ausschließlich eine Schleife für das Zeichen [math]\displaystyle{ b }[/math].
  • Durch die [math]\displaystyle{ \varepsilon }[/math]-Übergänge verzweigt der Automat bereits vor dem ersten Zeichen in zwei getrennte Zweige („nur [math]\displaystyle{ a }[/math]-Wörter“ in [math]\displaystyle{ q_1 }[/math] und „nur [math]\displaystyle{ b }[/math]-Wörter“ in [math]\displaystyle{ q_2 }[/math]).

2. Wortzugehörigkeit am [math]\displaystyle{ \varepsilon }[/math]-NEA nachvollziehen:

  • Leeres Wort [math]\displaystyle{ \varepsilon \in L }[/math]: Obwohl der Startzustand [math]\displaystyle{ q_0 }[/math] selbst kein Endzustand ist, gelangt der Automat ohne Zeicheneingabe über [math]\displaystyle{ q_0 \xrightarrow{\varepsilon} q_1 \in F }[/math] (oder [math]\displaystyle{ q_0 \xrightarrow{\varepsilon} q_2 \in F }[/math]) sofort in einen Endzustand. Das leere Wort wird akzeptiert.
  • Wort [math]\displaystyle{ bb \in L }[/math]: Über den Pfad [math]\displaystyle{ q_0 \xrightarrow{\varepsilon} q_2 \xrightarrow{b} q_2 \xrightarrow{b} q_2 \in F }[/math] wird das Wort vollständig gelesen und im Endzustand [math]\displaystyle{ q_2 }[/math] akzeptiert.
  • Wort [math]\displaystyle{ ab \notin L }[/math]: Wechselt der Automat über [math]\displaystyle{ \varepsilon }[/math] nach [math]\displaystyle{ q_1 }[/math], kann er zwar das [math]\displaystyle{ a }[/math] lesen, bleibt aber beim anschließenden [math]\displaystyle{ b }[/math] stecken (kein [math]\displaystyle{ b }[/math]-Übergang in [math]\displaystyle{ q_1 }[/math]). Wechselt er über [math]\displaystyle{ \varepsilon }[/math] nach [math]\displaystyle{ q_2 }[/math], scheitert er bereits am ersten Zeichen [math]\displaystyle{ a }[/math]. Da kein Pfad zum Ziel führt, wird [math]\displaystyle{ ab }[/math] abgelehnt.

Die schrittweise Umwandlung dieses [math]\displaystyle{ \varepsilon }[/math]-NEA in einen äquivalenten DEA wird im Artikel Potenzmengenkonstruktion#ε-NEA in einen DEA überführen durchgeführt.