Potenzmengenkonstruktion: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung Markierung: Zurückgesetzt |
Keine Bearbeitungszusammenfassung Markierung: Manuelle Zurücksetzung |
||
| Zeile 1: | Zeile 1: | ||
Ein [[Nichtdeterministischer endlicher Automat|NEA]] hält mehrere Wege gleichzeitig offen, eine Steuerung oder ein Programm braucht dagegen in jedem Schritt genau einen Zustand. Die Potenzmengenkonstruktion macht aus dem NEA einen [[Deterministischer endlicher Automat|DEA]], der dasselbe leistet. | |||
==Definition== | ==Definition== | ||
Die '''Potenzmengenkonstruktion''' ist ein Verfahren, das zu einem [[Nichtdeterministischer endlicher Automat|NEA]] einen gleichwertigen [[Deterministischer endlicher Automat|DEA]] konstruiert. Gleichwertig bedeutet: Beide Automaten akzeptieren dieselbe Sprache. | |||
Jeder Zustand des DEA ist eine Menge von NEA-Zuständen, also ein Element der Potenzmenge <math>\mathcal{P}(Q)</math> der Zustandsmenge <math>Q</math> (siehe [[Nichtdeterministischer endlicher Automat#Potenzmenge einer Zustandsmenge angeben|Potenzmenge einer Zustandsmenge angeben]]). Daher hat das Verfahren seinen Namen. Es heißt auch Teilmengenkonstruktion oder Myhill-Teilmengen-Verfahren. | |||
== | ==Verfahren== | ||
Gegeben ist ein NEA <math>A = (Q; \Sigma; \delta; q_0; F)</math>. Der DEA mit der Übergangsfunktion <math>\delta'</math> entsteht in fünf Schritten: | |||
# Der Startzustand des DEA ist die Menge <math>\{q_0\}</math>. | |||
# Für jede neue Menge <math>Z</math> und jedes Zeichen <math>a \in \Sigma</math> wird die Vereinigung aller Folgezustände gebildet: <math>\delta'(Z; a) = \bigcup_{q \in Z} \delta(q; a)</math>. | |||
# Jede neue Menge, die dabei entsteht, wird als Zeile in die Tabelle aufgenommen. Das wiederholt sich, bis keine neue Menge mehr entsteht. | |||
# Endzustände sind alle Mengen, die mindestens einen Endzustand des NEA enthalten. | |||
# Die Tabelle wird in einen Übergangsgraphen überführt, siehe [[Deterministischer endlicher Automat#Graph und Tabelle ineinander überführen|Graph und Tabelle ineinander überführen]]. | |||
Das Zeichen <math>\bigcup</math> in Schritt 2 steht für die [[Menge#Vereinigungsmenge|Vereinigung]] über alle Zustände <math>q</math> der Menge <math>Z</math>: Für jeden Zustand aus <math>Z</math> wird nachgesehen, wohin er mit dem Zeichen <math>a</math> führt, und alle diese Folgezustände werden zu einer Menge zusammengefasst. | |||
Die Tabelle wird wie die Übergangstabelle eines DEA gelesen. Oben links steht <math>\delta'</math>, die Übergangsfunktion des DEA. Der Pfeil <math>\rightarrow</math> markiert den Startzustand, der hochgestellte Stern <math>{}^*</math> die Endzustände. Ist der Startzustand zugleich Endzustand, stehen beide Zeichen davor. | |||
Der entstandene DEA ist nicht immer der kleinste. Verhalten sich mehrere seiner Zustände gleich, lassen sie sich anschließend zusammenlegen, siehe [[Deterministischer endlicher Automat#Minimierung|Minimierung]]. | |||
==Fehlerzustand== | |||
Hat kein Zustand einer Menge für ein Zeichen einen Folgezustand, ist die Vereinigung die leere Menge <math>\emptyset</math>. Sie wird als Zustand <math>q_F</math> geführt. Alle Zeichen bleiben in <math>q_F</math>. <math>q_F</math> ist kein Endzustand, denn von dort kann kein Pfad des NEA mehr erfolgreich sein. | |||
Entsteht die leere Menge, gehört <math>q_F</math> als Zustand zum DEA. Erst mit ihm ist der DEA [[Deterministischer endlicher Automat#Vollständiger DEA und Fehlerzustand|vollständig]]. Entsteht sie bei keiner Menge und keinem Zeichen, ist der DEA auch ohne <math>q_F</math> vollständig. | |||
==Gleichwertigkeit von NEA und DEA== | |||
Nach dem Lesen eines Wortes <math>w</math> enthält die Menge, in der der DEA steht, genau die Zustände, die der NEA nach <math>w</math> erreichen kann. Deshalb erreicht der DEA einen Endzustand genau dann, wenn ein [[Nichtdeterministischer endlicher Automat#Wortakzeptanz|Pfad]] des NEA das tut. Der DEA akzeptiert <math>w</math> also genau dann, wenn der NEA es akzeptiert. | |||
Umgekehrt ist jeder DEA ein NEA, bei dem jede Menge von Folgezuständen höchstens ein Element hat. Beide Automatenarten erkennen damit dieselben Sprachen. | |||
Hat der NEA <math>n</math> Zustände, hat seine Potenzmenge <math>2^n</math> Elemente. Der DEA kann deshalb bis zu <math>2^n</math> Zustände haben. Meist entstehen weniger, weil nur die vom Start aus erreichbaren Mengen aufgenommen werden. | |||
==Umwandlung eines ε-NEA== | |||
Bei einem <math>\varepsilon</math>-NEA ist die Startmenge <math>E(q_0)</math>, der [[Nichtdeterministischer endlicher Automat#ε-Abschluss|ε-Abschluss]] des Startzustands. Nach jedem Schritt wird der <math>\varepsilon</math>-Abschluss gebildet: | |||
:<math>\delta'(Z; a) = E\left(\bigcup_{q \in Z} \delta(q; a)\right)</math> | |||
Zu den Zuständen, die mit dem Zeichen <math>a</math> erreicht werden, kommen also alle Zustände hinzu, die von dort über <math>\varepsilon</math>-Übergänge erreichbar sind. Alle übrigen Schritte bleiben wie im Abschnitt [[#Verfahren|Verfahren]]. Der DEA hat keine <math>\varepsilon</math>-Übergänge mehr. | |||
==Beispiele== | |||
===Spam-Filter in einen DEA überführen=== | |||
[[Datei:NEA Spam-Filter.png|mini|Spam-Filter als NEA]] | |||
Der NEA erkennt Nachrichten, die die Zeichenfolge <code>UML</code> enthalten. Seine Übergangstabelle steht im Beispiel [[Nichtdeterministischer endlicher Automat#Spam-Filter als NEA modellieren|Spam-Filter als NEA modellieren]]. Im Bild gilt: <math>q_0</math> führt bei <math>U</math> nach <math>q_0</math> und <math>q_1</math>, bei <math>M</math>, <math>L</math> und <math>x</math> nur nach <math>q_0</math>. <math>q_1</math> führt bei <math>M</math> nach <math>q_2</math>, <math>q_2</math> führt bei <math>L</math> nach <math>q_3</math>. <math>q_3</math> bleibt bei jedem Zeichen in <math>q_3</math>. | |||
Die | '''Startmenge.''' Die erste Zeile der Tabelle ist die Startmenge <math>\{q_0\}</math>. | ||
:<math> | '''Zeile der Startmenge.''' Die Menge enthält nur <math>q_0</math>. Die Mengen der Folgezustände, kurz Folgemengen, lassen sich deshalb direkt aus der Tabelle des NEA ablesen: | ||
* <math>\delta'(\{q_0\}; U) = \{q_0; q_1\}</math> | |||
* <math>\delta'(\{q_0\}; M) = \{q_0\}</math>, ebenso bei <math>L</math> und <math>x</math> | |||
Neu ist die Menge <math>\{q_0; q_1\}</math>. Sie wird die zweite Zeile. | |||
:<math> | '''Zeile der Menge <math>\{q_0; q_1\}</math>.''' Jetzt werden für jedes Zeichen die Folgezustände von <math>q_0</math> und von <math>q_1</math> vereinigt. Hat ein Zustand für ein Zeichen keinen Folgezustand, trägt er die leere Menge bei: | ||
* <math>\delta'(\{q_0; q_1\}; U) = \{q_0; q_1\} \cup \emptyset = \{q_0; q_1\}</math> | |||
* <math>\delta'(\{q_0; q_1\}; M) = \{q_0\} \cup \{q_2\} = \{q_0; q_2\}</math> | |||
* <math>\delta'(\{q_0; q_1\}; L) = \{q_0\} \cup \emptyset = \{q_0\}</math> | |||
* <math>\delta'(\{q_0; q_1\}; x) = \{q_0\} \cup \emptyset = \{q_0\}</math> | |||
Neu ist die Menge <math>\{q_0; q_2\}</math>. | |||
'''Übrige Zeilen.''' Alle weiteren Zeilen entstehen auf dieselbe Weise, bis keine neue Menge mehr hinzukommt. Drei der Rechnungen: | |||
* <math>\delta'(\{q_0; q_2\}; L) = \{q_0\} \cup \{q_3\} = \{q_0; q_3\}</math> | |||
* <math>\delta'(\{q_0; q_3\}; U) = \{q_0; q_1\} \cup \{q_3\} = \{q_0; q_1; q_3\}</math> | |||
* <math>\delta'(\{q_0; q_1; q_3\}; M) = \{q_0\} \cup \{q_2\} \cup \{q_3\} = \{q_0; q_2; q_3\}</math> | |||
Insgesamt ergeben sich sechs Zustände: | |||
{| class="wikitable" style="text-align:center" | |||
! <math>\delta'</math> !! <math>U</math> !! <math>M</math> !! <math>L</math> !! <math>x</math> | |||
* <math>q_2</math> | |- | ||
| <math>\rightarrow \{q_0\}</math> || <math>\{q_0; q_1\}</math> || <math>\{q_0\}</math> || <math>\{q_0\}</math> || <math>\{q_0\}</math> | |||
|- | |||
| <math>\{q_0; q_1\}</math> || <math>\{q_0; q_1\}</math> || <math>\{q_0; q_2\}</math> || <math>\{q_0\}</math> || <math>\{q_0\}</math> | |||
|- | |||
| <math>\{q_0; q_2\}</math> || <math>\{q_0; q_1\}</math> || <math>\{q_0\}</math> || <math>\{q_0; q_3\}</math> || <math>\{q_0\}</math> | |||
|- | |||
| <math>{}^*\{q_0; q_3\}</math> || <math>\{q_0; q_1; q_3\}</math> || <math>\{q_0; q_3\}</math> || <math>\{q_0; q_3\}</math> || <math>\{q_0; q_3\}</math> | |||
|- | |||
| <math>{}^*\{q_0; q_1; q_3\}</math> || <math>\{q_0; q_1; q_3\}</math> || <math>\{q_0; q_2; q_3\}</math> || <math>\{q_0; q_3\}</math> || <math>\{q_0; q_3\}</math> | |||
|- | |||
| <math>{}^*\{q_0; q_2; q_3\}</math> || <math>\{q_0; q_1; q_3\}</math> || <math>\{q_0; q_3\}</math> || <math>\{q_0; q_3\}</math> || <math>\{q_0; q_3\}</math> | |||
|} | |||
'''Endzustände.''' Endzustände sind alle Mengen mit <math>q_3</math>, also <math>\{q_0; q_3\}</math>, <math>\{q_0; q_1; q_3\}</math> und <math>\{q_0; q_2; q_3\}</math>. Alle sechs Mengen enthalten <math>q_0</math>, weil <math>q_0</math> bei jedem Zeichen wieder nach <math>q_0</math> führt. Die leere Menge entsteht nie, ein Fehlerzustand <math>q_F</math> ist nicht nötig. | |||
Die | '''Zustände zusammenlegen.''' Die drei Endzustände verhalten sich gleich: Jedes Zeichen führt wieder zu einer Menge mit <math>q_3</math>. Sie lassen sich zu einem Zustand <math>q_3</math> zusammenlegen. Das Zusammenlegen gleichwertiger Zustände ist die [[Deterministischer endlicher Automat#Minimierung|Minimierung]]. Die anderen Mengen heißen dann <math>q_0</math> für <math>\{q_0\}</math>, <math>q_1</math> für <math>\{q_0; q_1\}</math> und <math>q_2</math> für <math>\{q_0; q_2\}</math>. | ||
:<math> | {| class="wikitable" style="text-align:center" | ||
! <math>\delta'</math> !! <math>U</math> !! <math>M</math> !! <math>L</math> !! <math>x</math> | |||
|- | |||
| <math>\rightarrow q_0</math> || <math>q_1</math> || <math>q_0</math> || <math>q_0</math> || <math>q_0</math> | |||
|- | |||
| <math>q_1</math> || <math>q_1</math> || <math>q_2</math> || <math>q_0</math> || <math>q_0</math> | |||
|- | |||
| <math>q_2</math> || <math>q_1</math> || <math>q_0</math> || <math>q_3</math> || <math>q_0</math> | |||
|- | |||
| <math>{}^*q_3</math> || <math>q_3</math> || <math>q_3</math> || <math>q_3</math> || <math>q_3</math> | |||
|} | |||
[[Datei:DEA Spam-Filter.png|mini|Spam-Filter als DEA]] | |||
Der DEA hat vier Zustände und akzeptiert dieselben Nachrichten wie der NEA, nämlich alle mit der Zeichenfolge <code>UML</code>. | |||
:<math> | ===NEA mit Fehlerzustand in einen DEA überführen=== | ||
[[Datei:NEA Wartungsmenü.png|mini|NEA für das Wartungsmenü]] | |||
Der NEA aus dem Beispiel [[Nichtdeterministischer endlicher Automat#NEA entwerfen|NEA entwerfen]] akzeptiert alle Tastenfolgen über <math>\Sigma = \{K; E\}</math>, die mit <math>KK</math> oder mit <math>KEK</math> beginnen: | |||
{| class="wikitable" style="text-align:center" | |||
! <math>\delta</math> !! <math>K</math> !! <math>E</math> | |||
|- | |||
| <math>\rightarrow q_0</math> || <math>\{q_1; q_2\}</math> || – | |||
|- | |||
| <math>q_1</math> || <math>\{q_4\}</math> || – | |||
|- | |||
| <math>q_2</math> || – || <math>\{q_3\}</math> | |||
|- | |||
| <math>q_3</math> || <math>\{q_4\}</math> || – | |||
|- | |||
| <math>{}^*q_4</math> || <math>\{q_4\}</math> || <math>\{q_4\}</math> | |||
|} | |||
'''Startmenge.''' Die erste Zeile ist <math>\{q_0\}</math>. | |||
''' | '''Zeile der Startmenge.''' | ||
* <math>\delta'(\{q_0\}; K) = \{q_1; q_2\}</math> | |||
* <math>\delta'(\{q_0\}; E) = \emptyset</math> | |||
Bei <math>E</math> entsteht die leere Menge: Kein Pfad des NEA kann weiterlaufen. Sie wird als Fehlerzustand <math>q_F</math> eingetragen. | |||
:<math> | |||
'''Zeile der Menge <math>\{q_1; q_2\}</math>.''' | |||
* <math>\delta'(\{q_1; q_2\}; K) = \{q_4\} \cup \emptyset = \{q_4\}</math> | |||
* <math>\delta'(\{q_1; q_2\}; E) = \emptyset \cup \{q_3\} = \{q_3\}</math> | |||
''' | '''Übrige Zeilen.''' Neu sind <math>\{q_4\}</math> und <math>\{q_3\}</math>: | ||
* <math>\delta'(\{q_4\}; K) = \{q_4\}</math>, ebenso bei <math>E</math> | |||
* <math>\delta'(\{q_3\}; K) = \{q_4\}</math> | |||
* <math>\delta'(\{q_3\}; E) = \emptyset</math> | |||
* Von <math>q_F</math> führen <math>K</math> und <math>E</math> wieder nach <math>q_F</math>. | |||
Danach entsteht keine neue Menge mehr. | |||
''' | '''Endzustände.''' Nur die Menge <math>\{q_4\}</math> enthält den Endzustand <math>q_4</math> des NEA. | ||
:<math> | [[Datei:DEA Wartungsmenü.png|mini|DEA für das Wartungsmenü mit Fehlerzustand]] | ||
{| class="wikitable" style="text-align:center" | |||
! <math>\delta'</math> !! <math>K</math> !! <math>E</math> | |||
|- | |||
| <math>\rightarrow \{q_0\}</math> || <math>\{q_1; q_2\}</math> || <math>q_F</math> | |||
|- | |||
| <math>\{q_1; q_2\}</math> || <math>\{q_4\}</math> || <math>\{q_3\}</math> | |||
|- | |||
| <math>{}^*\{q_4\}</math> || <math>\{q_4\}</math> || <math>\{q_4\}</math> | |||
|- | |||
| <math>\{q_3\}</math> || <math>\{q_4\}</math> || <math>q_F</math> | |||
|- | |||
| <math>q_F</math> || <math>q_F</math> || <math>q_F</math> | |||
|} | |||
'''Probe.''' NEA und DEA müssen zum selben Ergebnis kommen: | |||
* <math>KEKE</math>: Im NEA endet der Pfad <math>q_0 \xrightarrow{K} q_2 \xrightarrow{E} q_3 \xrightarrow{K} q_4 \xrightarrow{E} q_4</math> im Endzustand. Der DEA durchläuft <math>\{q_0\} \xrightarrow{K} \{q_1; q_2\} \xrightarrow{E} \{q_3\} \xrightarrow{K} \{q_4\} \xrightarrow{E} \{q_4\}</math> und endet im Endzustand <math>\{q_4\}</math>. Beide akzeptieren. | |||
* <math>KEE</math>: Im NEA brechen alle Pfade ab. Der DEA durchläuft <math>\{q_0\} \xrightarrow{K} \{q_1; q_2\} \xrightarrow{E} \{q_3\} \xrightarrow{E} q_F</math> und endet im Fehlerzustand. Beide lehnen ab. | |||
Der DEA liest anders als der NEA jedes Wort bis zum Ende. | |||
===ε-NEA in einen DEA überführen=== | |||
[[Datei:DEA aus ε-NEA.png|mini|DEA aus dem ε-NEA mit Fehlerzustand]] | |||
Der Automat stammt aus dem Beispiel [[Nichtdeterministischer endlicher Automat#ε-Abschluss bestimmen|ε-Abschluss bestimmen]]. Von <math>q_0</math> führen <math>\varepsilon</math>-Übergänge nach <math>q_1</math> und <math>q_2</math>. <math>q_1</math> liest <math>a</math> und bleibt in <math>q_1</math>, <math>q_2</math> liest <math>b</math> und bleibt in <math>q_2</math>. <math>q_1</math> und <math>q_2</math> sind Endzustände. | |||
''' | '''Startmenge.''' Die erste Zeile ist <math>E(q_0) = \{q_0; q_1; q_2\}</math>. | ||
:<math> | '''Zeile der Startmenge.''' | ||
:<math> | * Bei <math>a</math> hat nur <math>q_1</math> einen Übergang, er führt nach <math>q_1</math>: <math>\delta'(\{q_0; q_1; q_2\}; a) = E(\{q_1\}) = \{q_1\}</math> | ||
* Bei <math>b</math> hat nur <math>q_2</math> einen Übergang, er führt nach <math>q_2</math>: <math>\delta'(\{q_0; q_1; q_2\}; b) = E(\{q_2\}) = \{q_2\}</math> | |||
''' | '''Übrige Zeilen.''' Neue Mengen sind <math>\{q_1\}</math> und <math>\{q_2\}</math>. <math>\{q_1\}</math> bleibt bei <math>a</math> in <math>\{q_1\}</math>, bei <math>b</math> entsteht die leere Menge, also <math>q_F</math>. <math>\{q_2\}</math> führt bei <math>a</math> nach <math>q_F</math> und bleibt bei <math>b</math> in <math>\{q_2\}</math>. <math>q_F</math> führt bei jedem Zeichen nach <math>q_F</math>. | ||
'''Endzustände.''' Jede Menge außer <math>q_F</math> enthält <math>q_1</math> oder <math>q_2</math> und ist deshalb ein Endzustand. | |||
{| class="wikitable" style="text-align:center" | |||
! <math>\delta'</math> !! <math>a</math> !! <math>b</math> | |||
|- | |||
| <math>\rightarrow {}^*\{q_0; q_1; q_2\}</math> || <math>\{q_1\}</math> || <math>\{q_2\}</math> | |||
|- | |||
| <math>{}^*\{q_1\}</math> || <math>\{q_1\}</math> || <math>q_F</math> | |||
|- | |||
| <math>{}^*\{q_2\}</math> || <math>q_F</math> || <math>\{q_2\}</math> | |||
|- | |||
| <math>q_F</math> || <math>q_F</math> || <math>q_F</math> | |||
|} | |||
Der DEA akzeptiert Wörter, die nur aus <math>a</math> oder nur aus <math>b</math> bestehen. Der Startzustand ist zugleich Endzustand, deshalb wird auch das leere Wort akzeptiert. | |||
:<math> | ===ε-Abschluss nach jedem Schritt bilden=== | ||
[[Datei:ε-NEA Erst a dann b dann c.png|mini|ε-NEA für Wörter aus erst a, dann b, dann c]] | |||
Der <math>\varepsilon</math>-NEA aus dem Beispiel [[Nichtdeterministischer endlicher Automat#Wörter mit einem ε-NEA prüfen|Wörter mit einem ε-NEA prüfen]] akzeptiert alle Wörter über <math>\Sigma = \{a; b; c\}</math>, in denen zuerst beliebig viele <math>a</math>, dann beliebig viele <math>b</math> und zuletzt beliebig viele <math>c</math> stehen. Zwei <math>\varepsilon</math>-Übergänge führen von <math>q_0</math> nach <math>q_1</math> und von <math>q_1</math> nach <math>q_2</math>. <math>q_2</math> ist der Endzustand. | |||
{| class="wikitable" style="text-align:center" | |||
! <math>\delta</math> !! <math>a</math> !! <math>b</math> !! <math>c</math> !! <math>\varepsilon</math> | |||
|- | |||
| <math>\rightarrow q_0</math> || <math>\{q_0\}</math> || – || – || <math>\{q_1\}</math> | |||
|- | |||
| <math>q_1</math> || – || <math>\{q_1\}</math> || – || <math>\{q_2\}</math> | |||
|- | |||
| <math>{}^*q_2</math> || – || – || <math>\{q_2\}</math> || – | |||
|} | |||
'''Startmenge.''' Von <math>q_0</math> ist über einen <math>\varepsilon</math>-Übergang <math>q_1</math> und über einen weiteren <math>q_2</math> erreichbar, also gilt <math>E(q_0) = \{q_0; q_1; q_2\}</math>. | |||
'''Zeile der Startmenge.''' | |||
* Bei <math>a</math> führt nur <math>q_0</math> weiter, und zwar nach <math>q_0</math>. Von <math>q_0</math> sind aber über <math>\varepsilon</math>-Übergänge auch <math>q_1</math> und <math>q_2</math> erreichbar. Der <math>\varepsilon</math>-Abschluss ergänzt diese Zustände: <math>\delta'(\{q_0; q_1; q_2\}; a) = E(\{q_0\}) = \{q_0; q_1; q_2\}</math> | |||
* Bei <math>b</math> führt nur <math>q_1</math> weiter, und zwar nach <math>q_1</math>. Der <math>\varepsilon</math>-Abschluss ergänzt <math>q_2</math>: <math>\delta'(\{q_0; q_1; q_2\}; b) = E(\{q_1\}) = \{q_1; q_2\}</math> | |||
* Bei <math>c</math> führt nur <math>q_2</math> weiter: <math>\delta'(\{q_0; q_1; q_2\}; c) = E(\{q_2\}) = \{q_2\}</math> | |||
== | '''Zeile der Menge <math>\{q_1; q_2\}</math>.''' | ||
* <math>\delta'(\{q_1; q_2\}; a) = E(\emptyset) = \emptyset</math>. Nach einem <math>b</math> ist kein <math>a</math> mehr erlaubt, die leere Menge wird zu <math>q_F</math>. | |||
* <math>\delta'(\{q_1; q_2\}; b) = E(\{q_1\}) = \{q_1; q_2\}</math> | |||
* <math>\delta'(\{q_1; q_2\}; c) = E(\{q_2\}) = \{q_2\}</math> | |||
'''Zeile der Menge <math>\{q_2\}</math>.''' | |||
* <math>\delta'(\{q_2\}; c) = E(\{q_2\}) = \{q_2\}</math> | |||
* Bei <math>a</math> und bei <math>b</math> entsteht die leere Menge, also <math>q_F</math>. | |||
'''Endzustände.''' Die drei Mengen <math>\{q_0; q_1; q_2\}</math>, <math>\{q_1; q_2\}</math> und <math>\{q_2\}</math> enthalten den Endzustand <math>q_2</math> des <math>\varepsilon</math>-NEA und sind deshalb Endzustände. Der Fehlerzustand <math>q_F</math> ist kein Endzustand. | |||
{| class="wikitable" style="text-align:center" | {| class="wikitable" style="text-align:center" | ||
! <math>\delta</math> !! <math> | ! <math>\delta'</math> !! <math>a</math> !! <math>b</math> !! <math>c</math> | ||
|- | |- | ||
| <math>\rightarrow | | <math>\rightarrow {}^*\{q_0; q_1; q_2\}</math> || <math>\{q_0; q_1; q_2\}</math> || <math>\{q_1; q_2\}</math> || <math>\{q_2\}</math> | ||
|- | |- | ||
| <math> | | <math>{}^*\{q_1; q_2\}</math> || <math>q_F</math> || <math>\{q_1; q_2\}</math> || <math>\{q_2\}</math> | ||
|- | |- | ||
| <math> | | <math>{}^*\{q_2\}</math> || <math>q_F</math> || <math>q_F</math> || <math>\{q_2\}</math> | ||
|- | |- | ||
| <math> | | <math>q_F</math> || <math>q_F</math> || <math>q_F</math> || <math>q_F</math> | ||
|} | |} | ||
Ohne den <math>\varepsilon</math>-Abschluss stünde in der ersten Zeile bei <math>a</math> nur <math>\{q_0\}</math>. Der DEA wüsste dann nicht, dass nach einem <math>a</math> sofort ein <math>b</math> oder ein <math>c</math> folgen darf. Weil schon der Startzustand ein Endzustand ist, wird auch das leere Wort akzeptiert. | |||
[[Kategorie: | [[Kategorie:Automaten]] | ||
[[Kategorie:AHR I Informatik LK]] | [[Kategorie:AHR I Informatik LK]] | ||
Aktuelle Version vom 12. November 2026, 05:07 Uhr
Ein NEA hält mehrere Wege gleichzeitig offen, eine Steuerung oder ein Programm braucht dagegen in jedem Schritt genau einen Zustand. Die Potenzmengenkonstruktion macht aus dem NEA einen DEA, der dasselbe leistet.
Definition
Die Potenzmengenkonstruktion ist ein Verfahren, das zu einem NEA einen gleichwertigen DEA konstruiert. Gleichwertig bedeutet: Beide Automaten akzeptieren dieselbe Sprache.
Jeder Zustand des DEA ist eine Menge von NEA-Zuständen, also ein Element der Potenzmenge [math]\displaystyle{ \mathcal{P}(Q) }[/math] der Zustandsmenge [math]\displaystyle{ Q }[/math] (siehe Potenzmenge einer Zustandsmenge angeben). Daher hat das Verfahren seinen Namen. Es heißt auch Teilmengenkonstruktion oder Myhill-Teilmengen-Verfahren.
Verfahren
Gegeben ist ein NEA [math]\displaystyle{ A = (Q; \Sigma; \delta; q_0; F) }[/math]. Der DEA mit der Übergangsfunktion [math]\displaystyle{ \delta' }[/math] entsteht in fünf Schritten:
- Der Startzustand des DEA ist die Menge [math]\displaystyle{ \{q_0\} }[/math].
- Für jede neue Menge [math]\displaystyle{ Z }[/math] und jedes Zeichen [math]\displaystyle{ a \in \Sigma }[/math] wird die Vereinigung aller Folgezustände gebildet: [math]\displaystyle{ \delta'(Z; a) = \bigcup_{q \in Z} \delta(q; a) }[/math].
- Jede neue Menge, die dabei entsteht, wird als Zeile in die Tabelle aufgenommen. Das wiederholt sich, bis keine neue Menge mehr entsteht.
- Endzustände sind alle Mengen, die mindestens einen Endzustand des NEA enthalten.
- Die Tabelle wird in einen Übergangsgraphen überführt, siehe Graph und Tabelle ineinander überführen.
Das Zeichen [math]\displaystyle{ \bigcup }[/math] in Schritt 2 steht für die Vereinigung über alle Zustände [math]\displaystyle{ q }[/math] der Menge [math]\displaystyle{ Z }[/math]: Für jeden Zustand aus [math]\displaystyle{ Z }[/math] wird nachgesehen, wohin er mit dem Zeichen [math]\displaystyle{ a }[/math] führt, und alle diese Folgezustände werden zu einer Menge zusammengefasst.
Die Tabelle wird wie die Übergangstabelle eines DEA gelesen. Oben links steht [math]\displaystyle{ \delta' }[/math], die Übergangsfunktion des DEA. Der Pfeil [math]\displaystyle{ \rightarrow }[/math] markiert den Startzustand, der hochgestellte Stern [math]\displaystyle{ {}^* }[/math] die Endzustände. Ist der Startzustand zugleich Endzustand, stehen beide Zeichen davor.
Der entstandene DEA ist nicht immer der kleinste. Verhalten sich mehrere seiner Zustände gleich, lassen sie sich anschließend zusammenlegen, siehe Minimierung.
Fehlerzustand
Hat kein Zustand einer Menge für ein Zeichen einen Folgezustand, ist die Vereinigung die leere Menge [math]\displaystyle{ \emptyset }[/math]. Sie wird als Zustand [math]\displaystyle{ q_F }[/math] geführt. Alle Zeichen bleiben in [math]\displaystyle{ q_F }[/math]. [math]\displaystyle{ q_F }[/math] ist kein Endzustand, denn von dort kann kein Pfad des NEA mehr erfolgreich sein.
Entsteht die leere Menge, gehört [math]\displaystyle{ q_F }[/math] als Zustand zum DEA. Erst mit ihm ist der DEA vollständig. Entsteht sie bei keiner Menge und keinem Zeichen, ist der DEA auch ohne [math]\displaystyle{ q_F }[/math] vollständig.
Gleichwertigkeit von NEA und DEA
Nach dem Lesen eines Wortes [math]\displaystyle{ w }[/math] enthält die Menge, in der der DEA steht, genau die Zustände, die der NEA nach [math]\displaystyle{ w }[/math] erreichen kann. Deshalb erreicht der DEA einen Endzustand genau dann, wenn ein Pfad des NEA das tut. Der DEA akzeptiert [math]\displaystyle{ w }[/math] also genau dann, wenn der NEA es akzeptiert.
Umgekehrt ist jeder DEA ein NEA, bei dem jede Menge von Folgezuständen höchstens ein Element hat. Beide Automatenarten erkennen damit dieselben Sprachen.
Hat der NEA [math]\displaystyle{ n }[/math] Zustände, hat seine Potenzmenge [math]\displaystyle{ 2^n }[/math] Elemente. Der DEA kann deshalb bis zu [math]\displaystyle{ 2^n }[/math] Zustände haben. Meist entstehen weniger, weil nur die vom Start aus erreichbaren Mengen aufgenommen werden.
Umwandlung eines ε-NEA
Bei einem [math]\displaystyle{ \varepsilon }[/math]-NEA ist die Startmenge [math]\displaystyle{ E(q_0) }[/math], der ε-Abschluss des Startzustands. Nach jedem Schritt wird der [math]\displaystyle{ \varepsilon }[/math]-Abschluss gebildet:
- [math]\displaystyle{ \delta'(Z; a) = E\left(\bigcup_{q \in Z} \delta(q; a)\right) }[/math]
Zu den Zuständen, die mit dem Zeichen [math]\displaystyle{ a }[/math] erreicht werden, kommen also alle Zustände hinzu, die von dort über [math]\displaystyle{ \varepsilon }[/math]-Übergänge erreichbar sind. Alle übrigen Schritte bleiben wie im Abschnitt Verfahren. Der DEA hat keine [math]\displaystyle{ \varepsilon }[/math]-Übergänge mehr.
Beispiele
Spam-Filter in einen DEA überführen

Der NEA erkennt Nachrichten, die die Zeichenfolge UML enthalten. Seine Übergangstabelle steht im Beispiel Spam-Filter als NEA modellieren. Im Bild gilt: [math]\displaystyle{ q_0 }[/math] führt bei [math]\displaystyle{ U }[/math] nach [math]\displaystyle{ q_0 }[/math] und [math]\displaystyle{ q_1 }[/math], bei [math]\displaystyle{ M }[/math], [math]\displaystyle{ L }[/math] und [math]\displaystyle{ x }[/math] nur nach [math]\displaystyle{ q_0 }[/math]. [math]\displaystyle{ q_1 }[/math] führt bei [math]\displaystyle{ M }[/math] nach [math]\displaystyle{ q_2 }[/math], [math]\displaystyle{ q_2 }[/math] führt bei [math]\displaystyle{ L }[/math] nach [math]\displaystyle{ q_3 }[/math]. [math]\displaystyle{ q_3 }[/math] bleibt bei jedem Zeichen in [math]\displaystyle{ q_3 }[/math].
Startmenge. Die erste Zeile der Tabelle ist die Startmenge [math]\displaystyle{ \{q_0\} }[/math].
Zeile der Startmenge. Die Menge enthält nur [math]\displaystyle{ q_0 }[/math]. Die Mengen der Folgezustände, kurz Folgemengen, lassen sich deshalb direkt aus der Tabelle des NEA ablesen:
- [math]\displaystyle{ \delta'(\{q_0\}; U) = \{q_0; q_1\} }[/math]
- [math]\displaystyle{ \delta'(\{q_0\}; M) = \{q_0\} }[/math], ebenso bei [math]\displaystyle{ L }[/math] und [math]\displaystyle{ x }[/math]
Neu ist die Menge [math]\displaystyle{ \{q_0; q_1\} }[/math]. Sie wird die zweite Zeile.
Zeile der Menge [math]\displaystyle{ \{q_0; q_1\} }[/math]. Jetzt werden für jedes Zeichen die Folgezustände von [math]\displaystyle{ q_0 }[/math] und von [math]\displaystyle{ q_1 }[/math] vereinigt. Hat ein Zustand für ein Zeichen keinen Folgezustand, trägt er die leere Menge bei:
- [math]\displaystyle{ \delta'(\{q_0; q_1\}; U) = \{q_0; q_1\} \cup \emptyset = \{q_0; q_1\} }[/math]
- [math]\displaystyle{ \delta'(\{q_0; q_1\}; M) = \{q_0\} \cup \{q_2\} = \{q_0; q_2\} }[/math]
- [math]\displaystyle{ \delta'(\{q_0; q_1\}; L) = \{q_0\} \cup \emptyset = \{q_0\} }[/math]
- [math]\displaystyle{ \delta'(\{q_0; q_1\}; x) = \{q_0\} \cup \emptyset = \{q_0\} }[/math]
Neu ist die Menge [math]\displaystyle{ \{q_0; q_2\} }[/math].
Übrige Zeilen. Alle weiteren Zeilen entstehen auf dieselbe Weise, bis keine neue Menge mehr hinzukommt. Drei der Rechnungen:
- [math]\displaystyle{ \delta'(\{q_0; q_2\}; L) = \{q_0\} \cup \{q_3\} = \{q_0; q_3\} }[/math]
- [math]\displaystyle{ \delta'(\{q_0; q_3\}; U) = \{q_0; q_1\} \cup \{q_3\} = \{q_0; q_1; q_3\} }[/math]
- [math]\displaystyle{ \delta'(\{q_0; q_1; q_3\}; M) = \{q_0\} \cup \{q_2\} \cup \{q_3\} = \{q_0; q_2; q_3\} }[/math]
Insgesamt ergeben sich sechs Zustände:
| [math]\displaystyle{ \delta' }[/math] | [math]\displaystyle{ U }[/math] | [math]\displaystyle{ M }[/math] | [math]\displaystyle{ L }[/math] | [math]\displaystyle{ x }[/math] |
|---|---|---|---|---|
| [math]\displaystyle{ \rightarrow \{q_0\} }[/math] | [math]\displaystyle{ \{q_0; q_1\} }[/math] | [math]\displaystyle{ \{q_0\} }[/math] | [math]\displaystyle{ \{q_0\} }[/math] | [math]\displaystyle{ \{q_0\} }[/math] |
| [math]\displaystyle{ \{q_0; q_1\} }[/math] | [math]\displaystyle{ \{q_0; q_1\} }[/math] | [math]\displaystyle{ \{q_0; q_2\} }[/math] | [math]\displaystyle{ \{q_0\} }[/math] | [math]\displaystyle{ \{q_0\} }[/math] |
| [math]\displaystyle{ \{q_0; q_2\} }[/math] | [math]\displaystyle{ \{q_0; q_1\} }[/math] | [math]\displaystyle{ \{q_0\} }[/math] | [math]\displaystyle{ \{q_0; q_3\} }[/math] | [math]\displaystyle{ \{q_0\} }[/math] |
| [math]\displaystyle{ {}^*\{q_0; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_1; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_3\} }[/math] |
| [math]\displaystyle{ {}^*\{q_0; q_1; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_1; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_2; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_3\} }[/math] |
| [math]\displaystyle{ {}^*\{q_0; q_2; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_1; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_3\} }[/math] | [math]\displaystyle{ \{q_0; q_3\} }[/math] |
Endzustände. Endzustände sind alle Mengen mit [math]\displaystyle{ q_3 }[/math], also [math]\displaystyle{ \{q_0; q_3\} }[/math], [math]\displaystyle{ \{q_0; q_1; q_3\} }[/math] und [math]\displaystyle{ \{q_0; q_2; q_3\} }[/math]. Alle sechs Mengen enthalten [math]\displaystyle{ q_0 }[/math], weil [math]\displaystyle{ q_0 }[/math] bei jedem Zeichen wieder nach [math]\displaystyle{ q_0 }[/math] führt. Die leere Menge entsteht nie, ein Fehlerzustand [math]\displaystyle{ q_F }[/math] ist nicht nötig.
Zustände zusammenlegen. Die drei Endzustände verhalten sich gleich: Jedes Zeichen führt wieder zu einer Menge mit [math]\displaystyle{ q_3 }[/math]. Sie lassen sich zu einem Zustand [math]\displaystyle{ q_3 }[/math] zusammenlegen. Das Zusammenlegen gleichwertiger Zustände ist die Minimierung. Die anderen Mengen heißen dann [math]\displaystyle{ q_0 }[/math] für [math]\displaystyle{ \{q_0\} }[/math], [math]\displaystyle{ q_1 }[/math] für [math]\displaystyle{ \{q_0; q_1\} }[/math] und [math]\displaystyle{ q_2 }[/math] für [math]\displaystyle{ \{q_0; q_2\} }[/math].
| [math]\displaystyle{ \delta' }[/math] | [math]\displaystyle{ U }[/math] | [math]\displaystyle{ M }[/math] | [math]\displaystyle{ L }[/math] | [math]\displaystyle{ x }[/math] |
|---|---|---|---|---|
| [math]\displaystyle{ \rightarrow q_0 }[/math] | [math]\displaystyle{ q_1 }[/math] | [math]\displaystyle{ q_0 }[/math] | [math]\displaystyle{ q_0 }[/math] | [math]\displaystyle{ q_0 }[/math] |
| [math]\displaystyle{ q_1 }[/math] | [math]\displaystyle{ q_1 }[/math] | [math]\displaystyle{ q_2 }[/math] | [math]\displaystyle{ q_0 }[/math] | [math]\displaystyle{ q_0 }[/math] |
| [math]\displaystyle{ q_2 }[/math] | [math]\displaystyle{ q_1 }[/math] | [math]\displaystyle{ q_0 }[/math] | [math]\displaystyle{ q_3 }[/math] | [math]\displaystyle{ q_0 }[/math] |
| [math]\displaystyle{ {}^*q_3 }[/math] | [math]\displaystyle{ q_3 }[/math] | [math]\displaystyle{ q_3 }[/math] | [math]\displaystyle{ q_3 }[/math] | [math]\displaystyle{ q_3 }[/math] |

Der DEA hat vier Zustände und akzeptiert dieselben Nachrichten wie der NEA, nämlich alle mit der Zeichenfolge UML.
NEA mit Fehlerzustand in einen DEA überführen

Der NEA aus dem Beispiel NEA entwerfen akzeptiert alle Tastenfolgen über [math]\displaystyle{ \Sigma = \{K; E\} }[/math], die mit [math]\displaystyle{ KK }[/math] oder mit [math]\displaystyle{ KEK }[/math] beginnen:
| [math]\displaystyle{ \delta }[/math] | [math]\displaystyle{ K }[/math] | [math]\displaystyle{ E }[/math] |
|---|---|---|
| [math]\displaystyle{ \rightarrow q_0 }[/math] | [math]\displaystyle{ \{q_1; q_2\} }[/math] | – |
| [math]\displaystyle{ q_1 }[/math] | [math]\displaystyle{ \{q_4\} }[/math] | – |
| [math]\displaystyle{ q_2 }[/math] | – | [math]\displaystyle{ \{q_3\} }[/math] |
| [math]\displaystyle{ q_3 }[/math] | [math]\displaystyle{ \{q_4\} }[/math] | – |
| [math]\displaystyle{ {}^*q_4 }[/math] | [math]\displaystyle{ \{q_4\} }[/math] | [math]\displaystyle{ \{q_4\} }[/math] |
Startmenge. Die erste Zeile ist [math]\displaystyle{ \{q_0\} }[/math].
Zeile der Startmenge.
- [math]\displaystyle{ \delta'(\{q_0\}; K) = \{q_1; q_2\} }[/math]
- [math]\displaystyle{ \delta'(\{q_0\}; E) = \emptyset }[/math]
Bei [math]\displaystyle{ E }[/math] entsteht die leere Menge: Kein Pfad des NEA kann weiterlaufen. Sie wird als Fehlerzustand [math]\displaystyle{ q_F }[/math] eingetragen.
Zeile der Menge [math]\displaystyle{ \{q_1; q_2\} }[/math].
- [math]\displaystyle{ \delta'(\{q_1; q_2\}; K) = \{q_4\} \cup \emptyset = \{q_4\} }[/math]
- [math]\displaystyle{ \delta'(\{q_1; q_2\}; E) = \emptyset \cup \{q_3\} = \{q_3\} }[/math]
Übrige Zeilen. Neu sind [math]\displaystyle{ \{q_4\} }[/math] und [math]\displaystyle{ \{q_3\} }[/math]:
- [math]\displaystyle{ \delta'(\{q_4\}; K) = \{q_4\} }[/math], ebenso bei [math]\displaystyle{ E }[/math]
- [math]\displaystyle{ \delta'(\{q_3\}; K) = \{q_4\} }[/math]
- [math]\displaystyle{ \delta'(\{q_3\}; E) = \emptyset }[/math]
- Von [math]\displaystyle{ q_F }[/math] führen [math]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math] wieder nach [math]\displaystyle{ q_F }[/math].
Danach entsteht keine neue Menge mehr.
Endzustände. Nur die Menge [math]\displaystyle{ \{q_4\} }[/math] enthält den Endzustand [math]\displaystyle{ q_4 }[/math] des NEA.

| [math]\displaystyle{ \delta' }[/math] | [math]\displaystyle{ K }[/math] | [math]\displaystyle{ E }[/math] |
|---|---|---|
| [math]\displaystyle{ \rightarrow \{q_0\} }[/math] | [math]\displaystyle{ \{q_1; q_2\} }[/math] | [math]\displaystyle{ q_F }[/math] |
| [math]\displaystyle{ \{q_1; q_2\} }[/math] | [math]\displaystyle{ \{q_4\} }[/math] | [math]\displaystyle{ \{q_3\} }[/math] |
| [math]\displaystyle{ {}^*\{q_4\} }[/math] | [math]\displaystyle{ \{q_4\} }[/math] | [math]\displaystyle{ \{q_4\} }[/math] |
| [math]\displaystyle{ \{q_3\} }[/math] | [math]\displaystyle{ \{q_4\} }[/math] | [math]\displaystyle{ q_F }[/math] |
| [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ q_F }[/math] |
Probe. NEA und DEA müssen zum selben Ergebnis kommen:
- [math]\displaystyle{ KEKE }[/math]: Im NEA endet der Pfad [math]\displaystyle{ q_0 \xrightarrow{K} q_2 \xrightarrow{E} q_3 \xrightarrow{K} q_4 \xrightarrow{E} q_4 }[/math] im Endzustand. Der DEA durchläuft [math]\displaystyle{ \{q_0\} \xrightarrow{K} \{q_1; q_2\} \xrightarrow{E} \{q_3\} \xrightarrow{K} \{q_4\} \xrightarrow{E} \{q_4\} }[/math] und endet im Endzustand [math]\displaystyle{ \{q_4\} }[/math]. Beide akzeptieren.
- [math]\displaystyle{ KEE }[/math]: Im NEA brechen alle Pfade ab. Der DEA durchläuft [math]\displaystyle{ \{q_0\} \xrightarrow{K} \{q_1; q_2\} \xrightarrow{E} \{q_3\} \xrightarrow{E} q_F }[/math] und endet im Fehlerzustand. Beide lehnen ab.
Der DEA liest anders als der NEA jedes Wort bis zum Ende.
ε-NEA in einen DEA überführen

Der Automat stammt aus dem Beispiel ε-Abschluss bestimmen. Von [math]\displaystyle{ q_0 }[/math] führen [math]\displaystyle{ \varepsilon }[/math]-Übergänge nach [math]\displaystyle{ q_1 }[/math] und [math]\displaystyle{ q_2 }[/math]. [math]\displaystyle{ q_1 }[/math] liest [math]\displaystyle{ a }[/math] und bleibt in [math]\displaystyle{ q_1 }[/math], [math]\displaystyle{ q_2 }[/math] liest [math]\displaystyle{ b }[/math] und bleibt in [math]\displaystyle{ q_2 }[/math]. [math]\displaystyle{ q_1 }[/math] und [math]\displaystyle{ q_2 }[/math] sind Endzustände.
Startmenge. Die erste Zeile ist [math]\displaystyle{ E(q_0) = \{q_0; q_1; q_2\} }[/math].
Zeile der Startmenge.
- Bei [math]\displaystyle{ a }[/math] hat nur [math]\displaystyle{ q_1 }[/math] einen Übergang, er führt nach [math]\displaystyle{ q_1 }[/math]: [math]\displaystyle{ \delta'(\{q_0; q_1; q_2\}; a) = E(\{q_1\}) = \{q_1\} }[/math]
- Bei [math]\displaystyle{ b }[/math] hat nur [math]\displaystyle{ q_2 }[/math] einen Übergang, er führt nach [math]\displaystyle{ q_2 }[/math]: [math]\displaystyle{ \delta'(\{q_0; q_1; q_2\}; b) = E(\{q_2\}) = \{q_2\} }[/math]
Übrige Zeilen. Neue Mengen sind [math]\displaystyle{ \{q_1\} }[/math] und [math]\displaystyle{ \{q_2\} }[/math]. [math]\displaystyle{ \{q_1\} }[/math] bleibt bei [math]\displaystyle{ a }[/math] in [math]\displaystyle{ \{q_1\} }[/math], bei [math]\displaystyle{ b }[/math] entsteht die leere Menge, also [math]\displaystyle{ q_F }[/math]. [math]\displaystyle{ \{q_2\} }[/math] führt bei [math]\displaystyle{ a }[/math] nach [math]\displaystyle{ q_F }[/math] und bleibt bei [math]\displaystyle{ b }[/math] in [math]\displaystyle{ \{q_2\} }[/math]. [math]\displaystyle{ q_F }[/math] führt bei jedem Zeichen nach [math]\displaystyle{ q_F }[/math].
Endzustände. Jede Menge außer [math]\displaystyle{ q_F }[/math] enthält [math]\displaystyle{ q_1 }[/math] oder [math]\displaystyle{ q_2 }[/math] und ist deshalb ein Endzustand.
| [math]\displaystyle{ \delta' }[/math] | [math]\displaystyle{ a }[/math] | [math]\displaystyle{ b }[/math] |
|---|---|---|
| [math]\displaystyle{ \rightarrow {}^*\{q_0; q_1; q_2\} }[/math] | [math]\displaystyle{ \{q_1\} }[/math] | [math]\displaystyle{ \{q_2\} }[/math] |
| [math]\displaystyle{ {}^*\{q_1\} }[/math] | [math]\displaystyle{ \{q_1\} }[/math] | [math]\displaystyle{ q_F }[/math] |
| [math]\displaystyle{ {}^*\{q_2\} }[/math] | [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ \{q_2\} }[/math] |
| [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ q_F }[/math] |
Der DEA akzeptiert Wörter, die nur aus [math]\displaystyle{ a }[/math] oder nur aus [math]\displaystyle{ b }[/math] bestehen. Der Startzustand ist zugleich Endzustand, deshalb wird auch das leere Wort akzeptiert.
ε-Abschluss nach jedem Schritt bilden

Der [math]\displaystyle{ \varepsilon }[/math]-NEA aus dem Beispiel Wörter mit einem ε-NEA prüfen akzeptiert alle Wörter über [math]\displaystyle{ \Sigma = \{a; b; c\} }[/math], in denen zuerst beliebig viele [math]\displaystyle{ a }[/math], dann beliebig viele [math]\displaystyle{ b }[/math] und zuletzt beliebig viele [math]\displaystyle{ c }[/math] stehen. Zwei [math]\displaystyle{ \varepsilon }[/math]-Übergänge führen von [math]\displaystyle{ q_0 }[/math] nach [math]\displaystyle{ q_1 }[/math] und von [math]\displaystyle{ q_1 }[/math] nach [math]\displaystyle{ q_2 }[/math]. [math]\displaystyle{ q_2 }[/math] ist der Endzustand.
| [math]\displaystyle{ \delta }[/math] | [math]\displaystyle{ a }[/math] | [math]\displaystyle{ b }[/math] | [math]\displaystyle{ c }[/math] | [math]\displaystyle{ \varepsilon }[/math] |
|---|---|---|---|---|
| [math]\displaystyle{ \rightarrow q_0 }[/math] | [math]\displaystyle{ \{q_0\} }[/math] | – | – | [math]\displaystyle{ \{q_1\} }[/math] |
| [math]\displaystyle{ q_1 }[/math] | – | [math]\displaystyle{ \{q_1\} }[/math] | – | [math]\displaystyle{ \{q_2\} }[/math] |
| [math]\displaystyle{ {}^*q_2 }[/math] | – | – | [math]\displaystyle{ \{q_2\} }[/math] | – |
Startmenge. Von [math]\displaystyle{ q_0 }[/math] ist über einen [math]\displaystyle{ \varepsilon }[/math]-Übergang [math]\displaystyle{ q_1 }[/math] und über einen weiteren [math]\displaystyle{ q_2 }[/math] erreichbar, also gilt [math]\displaystyle{ E(q_0) = \{q_0; q_1; q_2\} }[/math].
Zeile der Startmenge.
- Bei [math]\displaystyle{ a }[/math] führt nur [math]\displaystyle{ q_0 }[/math] weiter, und zwar nach [math]\displaystyle{ q_0 }[/math]. Von [math]\displaystyle{ q_0 }[/math] sind aber über [math]\displaystyle{ \varepsilon }[/math]-Übergänge auch [math]\displaystyle{ q_1 }[/math] und [math]\displaystyle{ q_2 }[/math] erreichbar. Der [math]\displaystyle{ \varepsilon }[/math]-Abschluss ergänzt diese Zustände: [math]\displaystyle{ \delta'(\{q_0; q_1; q_2\}; a) = E(\{q_0\}) = \{q_0; q_1; q_2\} }[/math]
- Bei [math]\displaystyle{ b }[/math] führt nur [math]\displaystyle{ q_1 }[/math] weiter, und zwar nach [math]\displaystyle{ q_1 }[/math]. Der [math]\displaystyle{ \varepsilon }[/math]-Abschluss ergänzt [math]\displaystyle{ q_2 }[/math]: [math]\displaystyle{ \delta'(\{q_0; q_1; q_2\}; b) = E(\{q_1\}) = \{q_1; q_2\} }[/math]
- Bei [math]\displaystyle{ c }[/math] führt nur [math]\displaystyle{ q_2 }[/math] weiter: [math]\displaystyle{ \delta'(\{q_0; q_1; q_2\}; c) = E(\{q_2\}) = \{q_2\} }[/math]
Zeile der Menge [math]\displaystyle{ \{q_1; q_2\} }[/math].
- [math]\displaystyle{ \delta'(\{q_1; q_2\}; a) = E(\emptyset) = \emptyset }[/math]. Nach einem [math]\displaystyle{ b }[/math] ist kein [math]\displaystyle{ a }[/math] mehr erlaubt, die leere Menge wird zu [math]\displaystyle{ q_F }[/math].
- [math]\displaystyle{ \delta'(\{q_1; q_2\}; b) = E(\{q_1\}) = \{q_1; q_2\} }[/math]
- [math]\displaystyle{ \delta'(\{q_1; q_2\}; c) = E(\{q_2\}) = \{q_2\} }[/math]
Zeile der Menge [math]\displaystyle{ \{q_2\} }[/math].
- [math]\displaystyle{ \delta'(\{q_2\}; c) = E(\{q_2\}) = \{q_2\} }[/math]
- Bei [math]\displaystyle{ a }[/math] und bei [math]\displaystyle{ b }[/math] entsteht die leere Menge, also [math]\displaystyle{ q_F }[/math].
Endzustände. Die drei Mengen [math]\displaystyle{ \{q_0; q_1; q_2\} }[/math], [math]\displaystyle{ \{q_1; q_2\} }[/math] und [math]\displaystyle{ \{q_2\} }[/math] enthalten den Endzustand [math]\displaystyle{ q_2 }[/math] des [math]\displaystyle{ \varepsilon }[/math]-NEA und sind deshalb Endzustände. Der Fehlerzustand [math]\displaystyle{ q_F }[/math] ist kein Endzustand.
| [math]\displaystyle{ \delta' }[/math] | [math]\displaystyle{ a }[/math] | [math]\displaystyle{ b }[/math] | [math]\displaystyle{ c }[/math] |
|---|---|---|---|
| [math]\displaystyle{ \rightarrow {}^*\{q_0; q_1; q_2\} }[/math] | [math]\displaystyle{ \{q_0; q_1; q_2\} }[/math] | [math]\displaystyle{ \{q_1; q_2\} }[/math] | [math]\displaystyle{ \{q_2\} }[/math] |
| [math]\displaystyle{ {}^*\{q_1; q_2\} }[/math] | [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ \{q_1; q_2\} }[/math] | [math]\displaystyle{ \{q_2\} }[/math] |
| [math]\displaystyle{ {}^*\{q_2\} }[/math] | [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ \{q_2\} }[/math] |
| [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ q_F }[/math] | [math]\displaystyle{ q_F }[/math] |
Ohne den [math]\displaystyle{ \varepsilon }[/math]-Abschluss stünde in der ersten Zeile bei [math]\displaystyle{ a }[/math] nur [math]\displaystyle{ \{q_0\} }[/math]. Der DEA wüsste dann nicht, dass nach einem [math]\displaystyle{ a }[/math] sofort ein [math]\displaystyle{ b }[/math] oder ein [math]\displaystyle{ c }[/math] folgen darf. Weil schon der Startzustand ein Endzustand ist, wird auch das leere Wort akzeptiert.