Potenzmengenkonstruktion: Unterschied zwischen den Versionen
Die Seite wurde neu angelegt: „Ein NEA lässt sich nicht direkt programmieren, weil er mehrere Wege gleichzeitig verfolgt. Die Potenzmengenkonstruktion macht daraus einen eindeutigen DEA. ==Definition== Die Potenzmengenkonstruktion ist ein Verfahren, das zu einem NEA einen gleichwertigen DEA konstruiert. Jeder Zustand…“ |
Keine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
Ein [[Nichtdeterministischer endlicher Automat|NEA]] | 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. Jeder Zustand des DEA ist eine Menge von NEA-Zuständen. | 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== | ==Verfahren== | ||
Gegeben ist ein NEA <math>A = (Q | 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>\{ | # Der Startzustand des DEA ist die Menge <math>\{q_0\}</math>. | ||
# Für jede neue Menge <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. | # 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. | # Endzustände sind alle Mengen, die mindestens einen Endzustand des NEA enthalten. | ||
# Die Tabelle wird in einen Übergangsgraphen | # 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== | ==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 | 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== | ==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 Pfad des NEA das tut. Der DEA akzeptiert <math>w</math> also genau dann, wenn der NEA es akzeptiert. | 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 | 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. | 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== | ==Umwandlung eines ε-NEA== | ||
Bei einem | 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'( | :<math>\delta'(Z; a) = E\left(\bigcup_{q \in Z} \delta(q; a)\right)</math> | ||
Alle übrigen Schritte bleiben wie im Abschnitt [[#Verfahren|Verfahren]]. Der DEA hat keine | 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== | ==Beispiele== | ||
===Spam-Filter in einen DEA überführen=== | ===Spam-Filter in einen DEA überführen=== | ||
[[Datei:NEA Spam-Filter.png|mini|Spam-Filter als NEA]] | [[Datei:NEA Spam-Filter.png|mini|Spam-Filter als NEA]] | ||
Der NEA erkennt Nachrichten, die die Zeichenfolge UML enthalten. Seine Übergangstabelle steht im Beispiel [[Nichtdeterministischer endlicher Automat#Spam-Filter als NEA modellieren|Spam-Filter als NEA modellieren]]. Im Bild gilt: | 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>. | ||
'''Startmenge.''' Die erste Zeile der Tabelle ist die Startmenge <math>\{q_0\}</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. | |||
'''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" | {| 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_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> | ||
|} | |} | ||
Alle sechs Mengen enthalten | '''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 drei Endzustände verhalten sich gleich: Jedes Zeichen führt wieder zu einer Menge mit | '''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>. | ||
{| class="wikitable" style="text-align:center" | {| 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]] | [[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 UML. | Der DEA hat vier Zustände und akzeptiert dieselben Nachrichten wie der NEA, nämlich alle mit der Zeichenfolge <code>UML</code>. | ||
===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. | |||
'''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. | |||
[[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=== | ===ε-NEA in einen DEA überführen=== | ||
[[Datei:DEA aus ε-NEA.png|mini|DEA aus dem ε-NEA mit Fehlerzustand | [[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 | 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>. | |||
'''Zeile der Startmenge.''' | |||
* 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. | |||
===ε-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>. | |||
'''Startmenge.''' | '''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.''' | '''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>a</math> !! <math>b</math> !! <math>c</math> | ||
|- | |- | ||
| | | <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>{}^*\{q_1; q_2\}</math> || <math>q_F</math> || <math>\{q_1; q_2\}</math> || <math>\{q_2\}</math> | ||
|- | |- | ||
| * { | | <math>{}^*\{q_2\}</math> || <math>q_F</math> || <math>q_F</math> || <math>\{q_2\}</math> | ||
|- | |- | ||
| | | <math>q_F</math> || <math>q_F</math> || <math>q_F</math> || <math>q_F</math> | ||
|} | |} | ||
Der DEA | 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:Automaten]] | [[Kategorie:Automaten]] | ||
[[Kategorie:AHR I Informatik LK]] | [[Kategorie:AHR I Informatik LK]] | ||