Endlicher Automat: Unterschied zwischen den Versionen

Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
Zeile 1: Zeile 1:
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.
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 fest vorgegebener Zustandsübergänge.


==Definition==
==Definition==
Zeile 11: Zeile 11:


Nach ihrem Verwendungszweck unterscheidet man zwei Grundtypen endlicher Automaten:
Nach ihrem Verwendungszweck unterscheidet man zwei Grundtypen endlicher Automaten:
* '''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>).
* '''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 (beim nichtdeterministischen Automaten die Menge der erreichbaren Zustände) 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.
* '''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 die Ausgabezeichen festlegt. Beim Mealy-Automaten entsteht bei jedem Zustandsübergang ein Ausgabezeichen.
 
Formal wird ein endlicher Automat als '''Tupel''' angegeben: Das ist eine geordnete Zusammenstellung seiner Bestandteile in runden Klammern, getrennt durch Semikolons. Die Schreibweise <math>Q \times \Sigma</math> bezeichnet die Menge aller Paare <math>(q; a)</math> aus einem Zustand <math>q \in Q</math> und einem Zeichen <math>a \in \Sigma</math>.


==Übergangsfunktion==
==Übergangsfunktion==
Die Übergangsfunktion <math>\delta</math> beschreibt das Verhalten eines endlichen Automaten vollständig. Sie lässt sich auf zwei gleichwertige Arten darstellen:
Die Übergangsfunktion <math>\delta</math> legt fest, wie ein endlicher Automat auf jedes Eingabezeichen reagiert. Sie lässt sich auf zwei gleichwertige Arten darstellen:


* '''Übergangsgraph ([[Zustandsdiagramm|UML-Zustandsdiagramm]]):'''
* '''Übergangsgraph (auch Zustandsgraph):'''
** Die Zustände <math>q \in Q</math> werden als Kreise gezeichnet.
** 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.
** Der Startzustand <math>q_0</math> wird durch einen eingehenden Pfeil ohne Ursprungsknoten markiert. In den Bildern dieses Wikis trägt der Pfeil die Beschriftung „Start“.
** Akzeptierende Endzustände <math>q \in F</math> werden durch einen Doppelkreis gekennzeichnet.
** 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>).
** 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>). Führen mehrere Zeichen vom selben Zustand in denselben Folgezustand, steht ein Pfeil mit allen Zeichen, durch Semikolon getrennt.
* '''Übergangstabelle:'''
* '''Übergangstabelle:'''
** Die Zeilen der Tabelle entsprechen den aktuellen Zuständen <math>q \in Q</math>, die Spalten den Eingabezeichen <math>a \in \Sigma</math>.
** 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).
** 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.
** 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.
Im Fließtext wird ein einzelner Übergang als beschrifteter Pfeil geschrieben: <math>p \xrightarrow{a} q</math> bedeutet, dass der Automat im Zustand <math>p</math> das Zeichen <math>a</math> liest und in den Zustand <math>q</math> wechselt. Mehrere solche Pfeile hintereinander zeigen die Zustandsfolge für ein ganzes Wort. Steht <math>\varepsilon</math> über dem Pfeil, wechselt der Automat den Zustand, ohne ein Zeichen zu lesen (siehe [[#ε-NEA|ε-NEA]]).
Das [[Zustandsdiagramm]] der UML zeichnet ebenfalls Zustände und Übergänge. Es ist aber eine eigene Notation mit anderen Symbolen und beschreibt nicht das Erkennen von Wörtern.


==Mealy-Automat==
==Mealy-Automat==
Zeile 33: Zeile 39:
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.
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>A = (Q, \Sigma, \Omega, \delta, \lambda, q_0, F)</math>:
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>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>\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>\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>\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>\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>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>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>). Im Übergangsgraphen ist dann jeder Zustand ein Doppelkreis. 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.


==DEA - Deterministischer endlicher Automat==
==DEA - Deterministischer endlicher Automat==
Zeile 48: Zeile 54:
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]].
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]].


Formal ist ein deterministischer endlicher Automat definiert als 5-Tupel <math>A = (Q, \Sigma, \delta, q_0, F)</math>:
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>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>\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>\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> höchstens einen Folgezustand zuordnet (bei einem vollständigen DEA genau einen).
* <math>q_0 \in Q</math> ist der Startzustand.
* <math>q_0 \in Q</math> ist der Startzustand.
* <math>F \subseteq Q</math> ist die Menge der akzeptierenden Endzustände.
* <math>F \subseteq Q</math> ist die Menge der akzeptierenden Endzustände.
Zeile 61: Zeile 67:


===Definition===
===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.
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 mögliche 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>A = (Q, \Sigma, \delta, q_0, F)</math>:
Formal ist ein nichtdeterministischer 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>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>\Sigma</math> ist ein endliches, nicht leeres Eingabealphabet (<math>\Sigma \neq \emptyset</math>).
Zeile 70: Zeile 76:
* <math>F \subseteq Q</math> ist die Menge der akzeptierenden Endzustände.
* <math>F \subseteq Q</math> ist die Menge der akzeptierenden Endzustände.


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.
Ein Wort <math>w \in \Sigma^*</math> gehört genau dann zur akzeptierten Sprache <math>L(A)</math> des NEA, wenn '''mindestens ein''' [[Nichtdeterministischer endlicher Automat#Wortakzeptanz|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.


==ε-NEA==
==ε-NEA==
''Hauptartikel: [[Nichtdeterministischer endlicher Automat#ε-NEA]]''
''Hauptartikel: [[Nichtdeterministischer endlicher Automat#ε-NEA|ε-NEA]]''


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.
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 [[Wort#Leeres Wort|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.


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:
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>
:<math>\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)</math>


Zeile 85: Zeile 91:
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.
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.


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]]).
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 den '''<math>\varepsilon</math>-Abschluss''' <math>E(q)</math> (auch <math>\varepsilon</math>-Hülle): Das ist die Menge aller Zustände, die von <math>q</math> aus ausschließlich über <math>\varepsilon</math>-Übergänge erreichbar sind, einschließlich <math>q</math> selbst. Anschließend werden die Übergänge für die regulären Zeichen aus <math>\Sigma</math> auf diese Zustandsmengen übertragen (siehe [[Potenzmengenkonstruktion#Umwandlung eines ε-NEA|Umwandlung eines ε-NEA]]).
 
Der NEA ohne <math>\varepsilon</math>-Übergänge behält alle Zustände und den Startzustand. Seine Übergänge und Endzustände ergeben sich so:
* '''Übergänge:''' Für ein Zeichen <math>a \in \Sigma</math> führt ein Übergang von <math>p</math> nach <math>q</math>, wenn der <math>\varepsilon</math>-NEA von <math>p</math> aus zuerst über beliebig viele <math>\varepsilon</math>-Übergänge, dann mit <math>a</math> und danach wieder über beliebig viele <math>\varepsilon</math>-Übergänge nach <math>q</math> gelangt.
* '''Endzustände:''' Endzustand ist jeder Zustand, dessen <math>\varepsilon</math>-Abschluss einen Endzustand des <math>\varepsilon</math>-NEA enthält.
 
Ein durchgerechnetes Beispiel steht unter [[Nichtdeterministischer endlicher Automat#ε-Übergänge entfernen|ε-Übergänge entfernen]].


==Potenzmengenkonstruktion==
==Potenzmengenkonstruktion==
Zeile 93: Zeile 105:


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:
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>).
* '''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.
* '''Startzustand:''' Der DEA beginnt im Mengenzustand <math>\{q_0\}</math>, bei einem <math>\varepsilon</math>-NEA im <math>\varepsilon</math>-Abschluss <math>E(q_0)</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. Bei einem <math>\varepsilon</math>-NEA wird nach jedem solchen Schritt zusätzlich der <math>\varepsilon</math>-Abschluss der Menge gebildet, also die Vereinigung der <math>\varepsilon</math>-Abschlüsse ihrer Zustände.
* '''Fehlerzustand:''' Ist die Vereinigung die leere Menge <math>\emptyset</math>, kann kein Pfad des NEA mehr fortgesetzt werden. Die leere Menge wird als Fehlerzustand <math>q_F</math> geführt, den der DEA nicht mehr verlässt.
* '''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.
* '''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.


Zeile 102: Zeile 116:
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.
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>A = (Q, \Sigma, \Omega, \delta, \lambda, q_0, F)</math>:'''
'''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>:'''
* '''Zustandsmenge <math>Q = \{q_0; q_1\}</math>:'''
** <math>q_0</math>: Keine Münze eingeworfen (Wartezustand / Startzustand).
** <math>q_0</math>: Keine Münze eingeworfen (Wartezustand / Startzustand).
** <math>q_1</math>: Münze ist eingeworfen (Bereitschaftszustand für Bonbonausgabe).
** <math>q_1</math>: Münze ist eingeworfen (Bereitschaftszustand für Bonbonausgabe).
* '''Eingabealphabet <math>\Sigma = \{M, H\}</math>:'''
* '''Eingabealphabet <math>\Sigma = \{M; H\}</math>:'''
** <math>M</math>: Münze einwerfen.
** <math>M</math>: Münze einwerfen.
** <math>H</math>: Hebel drehen.
** <math>H</math>: Hebel drehen.
* '''Ausgabealphabet <math>\Omega = \{B, N\}</math>:'''
* '''Ausgabealphabet <math>\Omega = \{B; N\}</math>:'''
** <math>B</math>: Bonbon ausgeben.
** <math>B</math>: Bonbon ausgeben.
** <math>N</math>: Keine Ausgabe (Nichts).
** <math>N</math>: Keine Ausgabe (Nichts).
* '''Startzustand:''' <math>q_0</math>.
* '''Startzustand:''' <math>q_0</math>.
* '''Endzustandsmenge:''' <math>F = Q = \{q_0, q_1\}</math> (jeder Zustand ist ein zulässiger Endzustand).
* '''Endzustandsmenge:''' <math>F = Q = \{q_0; q_1\}</math> (jeder Zustand ist ein zulässiger Endzustand, im Bild sind deshalb beide Zustände doppelt umkreist).


'''2. Übergangsfunktion <math>\delta</math> und Ausgabefunktion <math>\lambda</math> in Tabellenform:'''
'''2. Übergangsfunktion <math>\delta</math> und Ausgabefunktion <math>\lambda</math> in Tabellenform:'''


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
|+ Übergangsfunktion <math>\delta(q, a)</math> (Folgezustand)
|+ style="white-space:nowrap" | Übergangsfunktion <math>\delta(q; a)</math> (Folgezustand)
! <math>\delta</math> !! <math>M</math> !! <math>H</math>
! <math>\delta</math> !! <math>M</math> !! <math>H</math>
|-
|-
Zeile 127: Zeile 141:


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
|+ Ausgabefunktion <math>\lambda(q, a)</math> (Ausgabezeichen)
|+ style="white-space:nowrap" | Ausgabefunktion <math>\lambda(q; a)</math> (Ausgabezeichen)
! <math>\lambda</math> !! <math>M</math> !! <math>H</math>
! <math>\lambda</math> !! <math>M</math> !! <math>H</math>
|-
|-
Zeile 137: Zeile 151:
'''3. Verarbeitung konkreter Eingabefolgen prüfen:'''
'''3. Verarbeitung konkreter Eingabefolgen prüfen:'''
* '''Eingabewort <math>w_1 = MH</math> (korrekte Bedienung):'''
* '''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.
** 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>.
** 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):'''
* '''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).
** 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).
** 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).


Zeile 147: Zeile 161:
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.
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.


'''1. Formale Beschreibung als 5-Tupel <math>A = (Q, \Sigma, \delta, q_0, F)</math>:'''
'''1. Formale Beschreibung als 5-Tupel <math>A = (Q; \Sigma; \delta; q_0; F)</math>:'''
* '''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.
* '''Zustandsmenge <math>Q = \{q_0; q_1; q_2; q_3; q_4; q_F\}</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_F</math> ist ein sogenannter '''Fangzustand''' (Fehlerzustand) für einen Überlauf (mehr als 4 Einheiten), der nicht mehr verlassen werden kann. Der Index <math>F</math> steht hier für Fehler, <math>q_F</math> gehört nicht zur Endzustandsmenge <math>F</math>.
* '''Eingabealphabet <math>\Sigma = \{K, E\}</math>:''' <math>K</math> steht für Kaffee (+1 Einheit), <math>E</math> für Espresso (+2 Einheiten).
* '''Eingabealphabet <math>\Sigma = \{K; E\}</math>:''' <math>K</math> steht für Kaffee (+1 Einheit), <math>E</math> für Espresso (+2 Einheiten).
* '''Startzustand <math>q_0</math>:''' Zu Beginn ist das Satzfach leer (0 Einheiten).
* '''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.
* '''Endzustandsmenge <math>F = \{q_4\}</math>:''' Nur bei exakt 4 Einheiten (<math>q_4</math>) ist das Satzfach planmäßig voll.
* '''Übergangsfunktion <math>\delta</math>:''' Jedes <math>K</math> erhöht den Füllstand um 1, jedes <math>E</math> um 2. Die Übergangstabelle enthält alle Werte:
{| class="wikitable" style="text-align:center"
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
|-
| <math>\rightarrow q_0</math> || <math>q_1</math> || <math>q_2</math>
|-
| <math>q_1</math> || <math>q_2</math> || <math>q_3</math>
|-
| <math>q_2</math> || <math>q_3</math> || <math>q_4</math>
|-
| <math>q_3</math> || <math>q_4</math> || <math>q_F</math>
|-
| <math>{}^*q_4</math> || <math>q_F</math> || <math>q_F</math>
|-
| <math>q_F</math> || <math>q_F</math> || <math>q_F</math>
|}


'''2. Wortverarbeitung und akzeptierte Sprache:'''
'''2. Wortverarbeitung und akzeptierte Sprache:'''
* Für das Eingabewort <math>w_1 = KEK</math> durchläuft der DEA eindeutig die Zustandsfolge:
* 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>
*:<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>).
*: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:
* 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>
*:<math>q_0 \xrightarrow{E} q_2 \xrightarrow{E} q_4 \xrightarrow{K} q_F \notin F</math>
:Da der Automat im Fehlerzustand <math>q_5</math> endet, wird <math>EEK</math> abgelehnt (<math>EEK \notin L(A)</math>).
*:Da der Automat im Fehlerzustand <math>q_F</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>.
* Insgesamt akzeptiert der DEA genau die endliche Sprache <math>L(A) = \{KKKK; EE; EKK; KEK; KKE\}</math>.


===Spam-Filter als NEA und DEA gegenüberstellen===
===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]]
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.
Ein einfacher Spam-Filter durchsucht Texte nach der Zeichenfolge <code>UML</code>. Das Eingabealphabet ist <math>\Sigma = \{U; M; L; x\}</math>, dabei steht <math>x</math> für jedes andere Zeichen. Sobald ein Wort die Teilzeichenfolge <code>UML</code> an beliebiger Stelle enthält (also zur Sprache <math>L_{UML} = \{w \in \Sigma^* \mid w \text{ enthält } UML\}</math> gehört), soll der Automat im Endzustand <math>q_3</math> akzeptieren.


Der direkte Vergleich der beiden Diagramme zeigt den praktischen Vorteil des Nichtdeterminismus beim Entwurf:
Der direkte Vergleich der beiden Diagramme zeigt den praktischen Vorteil des Nichtdeterminismus beim Entwurf:
* '''Modellierung als NEA (oberes Bild):'''
* '''Modellierung als NEA (oberes Bild):'''
** 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>.
** Im Startzustand <math>q_0</math> besitzt der NEA eine Schleife für '''alle''' Zeichen (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.
** In den Zuständen <math>q_1</math> und <math>q_2</math> müssen '''keine''' Rücksprungkanten für falsche Zeichen gezeichnet werden: Folgt auf ein <math>U</math> kein <math>M</math>, bricht 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.
** 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):'''
* '''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.
** Da beim vollständigen 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.
** 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.


Beide Automaten akzeptieren exakt dieselbe Sprache <math>L</math>, der NEA ist jedoch deutlich einfacher zu konstruieren.
Beide Automaten akzeptieren exakt dieselbe Sprache <math>L_{UML}</math>, der NEA ist jedoch deutlich einfacher zu konstruieren. Wie der DEA aus dem NEA entsteht, zeigt das Beispiel [[Potenzmengenkonstruktion#Spam-Filter in einen DEA überführen|Spam-Filter in einen DEA überführen]].


===Wörter mit einem ε-NEA akzeptieren===
===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]]
[[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:
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:
 
:<math>L = \{a^n \mid n \ge 0\} \cup \{b^n \mid n \ge 0\} = \{\varepsilon; a; b; aa; bb; aaa; bbb; \dots\}</math>


:<math>L = \{a^n \mid n \ge 0\} \cup \{b^n \mid n \ge 0\} = \{\varepsilon, a, b, aa, bb, aaa, bbb, \dots\}</math>
Dabei ist <math>a^n</math> eine [[Wort#Wortpotenz|Wortpotenz]]: das Zeichen <math>a</math>, <math>n</math>-mal hintereinander.


'''1. Aufbau des <math>\varepsilon</math>-NEA:'''
'''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>).
* 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>.
* 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>).
* 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>).
Zeile 194: Zeile 227:
* '''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.
* '''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 schrittweise Umwandlung dieses <math>\varepsilon</math>-NEA in einen äquivalenten DEA wird im Artikel [[Potenzmengenkonstruktion#ε-NEA in einen DEA überführen]] durchgeführt.
Die schrittweise Umwandlung dieses <math>\varepsilon</math>-NEA in einen äquivalenten DEA wird im Beispiel [[Potenzmengenkonstruktion#ε-NEA in einen DEA überführen|ε-NEA in einen DEA überführen]] durchgeführt.


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