Zum Inhalt springen

Potenzmengenkonstruktion: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Keine Bearbeitungszusammenfassung
Markierung: Zurückgesetzt
Keine Bearbeitungszusammenfassung
Markierung: Manuelle Zurücksetzung
 
Zeile 1: Zeile 1:
Reguläre Grammatiken beschreiben mit einfachen Regeln genau die Sprachen, die [[Endlicher Automat|endliche Automaten]] erkennen.
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==
Eine '''reguläre Grammatik''' ist eine [[Formale Grammatik|formale Grammatik]] <math>G = (N; T; P; S)</math>, deren Regeln nur die Formen <math>A \to aB</math> und <math>A \to a</math> haben. Dabei sind <math>A</math> und <math>B</math> Nichtterminale, und <math>a</math> ist ein Terminal. Zusätzlich ist die Regel <math>S \to \varepsilon</math> erlaubt, wenn <math>S</math> auf keiner rechten Regelseite vorkommt. Das leere Wort entsteht dann nur direkt aus dem Startsymbol.
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.


Reguläre Grammatiken erzeugen genau die Sprachen, die ein endlicher Automat erkennt. Diese Sprachen heißen '''reguläre Sprachen'''. Sie bilden Typ 3 der [[Chomsky-Hierarchie]]. Was sie nicht leisten, zeigt der Abschnitt [[Kontextfreie Grammatik#Grenzen regulärer Sprachen|Grenzen regulärer Sprachen]].
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.


==Rechtslineare Grammatik==
==Verfahren==
Eine '''rechtslineare Grammatik''' ist allgemeiner: Ihre Regeln haben die Form <math>A \to wB</math> oder <math>A \to w</math>, wobei <math>w</math> ein beliebiges Wort aus Terminalen ist, auch das leere. Das Nichtterminal steht höchstens am rechten Ende der rechten Seite. Mit <math>w = \varepsilon</math> sind auch die Regeln <math>A \to B</math> und <math>A \to \varepsilon</math> erlaubt, bei jedem Nichtterminal. Auch rechtslineare Grammatiken erzeugen genau die regulären Sprachen.
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]].


Jede rechtslineare Grammatik lässt sich in eine gleichwertige reguläre Grammatik umformen. Drei Arten von Regeln werden dafür nacheinander ersetzt:
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.


# '''Regel mit mehreren Terminalen:''' Für lange Terminalfolgen werden Hilfs-Nichtterminale eingeführt. Eine Regel <math>A \to a_1 a_2 \dots a_k B</math> mit <math>k \geq 2</math> Terminalen wird durch <math>k</math> Regeln ersetzt:
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.
#:<math>A \to a_1 H_1; \quad H_1 \to a_2 H_2; \quad \dots; \quad H_{k-1} \to a_k B</math>
#:<math>H_1</math> bis <math>H_{k-1}</math> sind neue Nichtterminale. Jedes steht für den noch fehlenden Rest der Terminalfolge. Bei einer Regel <math>A \to a_1 \dots a_k</math> ohne Nichtterminal endet die Kette mit <math>H_{k-1} \to a_k</math>.
# '''Regel ohne Terminal:''' Eine Regel <math>A \to B</math> wird gestrichen. Dafür erhält <math>A</math> alle rechten Seiten von <math>B</math>: Was <math>B</math> erzeugt, erzeugt <math>A</math> dann direkt. Entsteht dabei wieder eine Regel ohne Terminal, wird der Schritt wiederholt. Eine Regel, die schon gestrichen wurde, kommt dabei nicht wieder hinzu.
# '''Regel mit dem leeren Wort:''' Eine Regel <math>B \to \varepsilon</math> wird gestrichen. Dafür kommt zu jeder Regel <math>A \to aB</math> die Regel <math>A \to a</math> hinzu: Das Wort darf an dieser Stelle enden. Die Regel <math>A \to aB</math> bleibt bestehen, wenn <math>B</math> noch andere Regeln hat.


Für das Startsymbol gilt im dritten Schritt eine Ausnahme: Die Regel <math>S \to \varepsilon</math> bleibt erhalten, sonst ginge das leere Wort verloren. Das ist nur erlaubt, wenn <math>S</math> auf keiner rechten Regelseite vorkommt. Kommt <math>S</math> dort vor, erhält die Grammatik ein neues Startsymbol <math>S'</math>. Es bekommt alle Regeln von <math>S</math> und die Regel <math>S' \to \varepsilon</math>. Die Regel <math>S \to \varepsilon</math> wird danach wie bei jedem anderen Nichtterminal gestrichen und ausgeglichen.
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]].


Steht in einer Regel ein Nichtterminal nicht am rechten Ende, etwa in <math>S \to AB</math>, ist die Grammatik nicht rechtslinear. Erzeugt sie trotzdem eine reguläre Sprache, gibt es eine gleichwertige rechtslineare Grammatik. Sie entsteht in zwei Schritten: Zuerst wird beschrieben, welche Wörter jedes Nichtterminal erzeugt. Danach werden neue Regeln aufgestellt, die diese Wörter von links nach rechts aufbauen, sodass in jeder Regel höchstens ein Nichtterminal am rechten Ende steht.
==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.


==Vom Automaten zur Grammatik==
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.
Aus einem [[Deterministischer endlicher Automat|DEA]] entsteht eine reguläre Grammatik, die dieselbe Sprache erzeugt:


# Jeder Zustand wird zu einem Nichtterminal. Zum Zustand <math>p</math> gehört das Nichtterminal <math>P</math>. Der Startzustand <math>q_0</math> wird zum Startsymbol <math>S</math>.
==Gleichwertigkeit von NEA und DEA==
# Aus jedem Übergang <math>\delta(p; a) = q</math> wird die Regel <math>P \to aQ</math>.
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.
# Ist <math>q</math> ein Endzustand, kommt zusätzlich die Regel <math>P \to a</math> hinzu. Mit ihr endet das Wort im Endzustand, mit <math>P \to aQ</math> geht es von dort aus weiter.
# Ist <math>q_0</math> ein Endzustand, kommt zusätzlich die Regel <math>S \to \varepsilon</math> hinzu. Kommt <math>S</math> auf einer rechten Regelseite vor, braucht die Grammatik dafür ein neues Startsymbol <math>S'</math> mit denselben rechten Seiten wie <math>S</math>. Nur <math>S'</math> erhält dann die Regel <math>S' \to \varepsilon</math>.
# Zustände, von denen aus kein Endzustand mehr erreichbar ist, brauchen kein Nichtterminal. Das gilt für den [[Deterministischer endlicher Automat#Vollständiger DEA und Fehlerzustand|Fehlerzustand]] <math>q_F</math>. Alle Regeln <math>P \to aQ</math> mit einem solchen Zustand <math>Q</math> entfallen. Führen von einem Endzustand <math>q</math> alle Übergänge in den Fehlerzustand, braucht auch <math>q</math> kein Nichtterminal: Von einem Übergang <math>\delta(p; a) = q</math> bleibt dann nur die Regel <math>P \to a</math>.


==Von der Grammatik zum Automaten==
Umgekehrt ist jeder DEA ein NEA, bei dem jede Menge von Folgezuständen höchstens ein Element hat. Beide Automatenarten erkennen damit dieselben Sprachen.
Aus einer regulären Grammatik entsteht ein endlicher Automat, der dieselbe Sprache erkennt:


# Jedes Nichtterminal wird zu einem Zustand. Dazu kommt ein neuer Endzustand. Das Startsymbol wird zum Startzustand.
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.
# Aus jeder Regel <math>A \to aB</math> wird ein Übergang von <math>A</math> nach <math>B</math> mit dem Zeichen <math>a</math>.
# Aus jeder Regel <math>A \to a</math> wird ein Übergang von <math>A</math> in den neuen Endzustand mit dem Zeichen <math>a</math>.
# Gehört <math>S \to \varepsilon</math> zur Grammatik, ist auch der Startzustand ein Endzustand.


Es entsteht meist ein [[Nichtdeterministischer endlicher Automat|NEA]], weil ein Nichtterminal mehrere Regeln mit demselben Terminal haben kann. Die [[Potenzmengenkonstruktion]] macht daraus einen DEA.
==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:


==Beispiele==
:<math>\delta'(Z; a) = E\left(\bigcup_{q \in Z} \delta(q; a)\right)</math>
===Grammatik zum Kaffeeautomaten angeben===
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]]
Gesucht ist eine reguläre Grammatik für den DEA im Bild. Der Kaffeeautomat akzeptiert Wörter aus <math>K</math> (Kaffee, zählt 1) und <math>E</math> (Espresso, zählt 2), die zusammen genau vier Einheiten ergeben, siehe [[Formale Sprache#Sprache als Menge angeben|Sprache als Menge angeben]].


Die Zustände werden zu Nichtterminalen: <math>q_0</math> wird <math>S</math>, <math>q_1</math> wird <math>A</math>, <math>q_2</math> wird <math>B</math>, <math>q_3</math> wird <math>C</math>. Vom Endzustand <math>q_4</math> führen alle Übergänge in den Fehlerzustand <math>q_F</math>. Der Endzustand <math>q_4</math> braucht deshalb kein Nichtterminal: Die Übergänge nach <math>q_4</math> ergeben Regeln mit nur einem Terminal. Auch der Fehlerzustand <math>q_F</math> erhält kein Nichtterminal.
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.


* <math>q_0</math> liest <math>K</math> und geht nach <math>q_1</math>, liest <math>E</math> und geht nach <math>q_2</math>. Das ergibt <math>S \to KA \mid EB</math>.
==Beispiele==
* <math>q_1</math> liest <math>K</math> und geht nach <math>q_2</math>, liest <math>E</math> und geht nach <math>q_3</math>. Das ergibt <math>A \to KB \mid EC</math>.
===Spam-Filter in einen DEA überführen===
* <math>q_2</math> liest <math>K</math> und geht nach <math>q_3</math>, liest <math>E</math> und geht nach <math>q_4</math>. Das ergibt <math>B \to KC \mid E</math>.
[[Datei:NEA Spam-Filter.png|mini|Spam-Filter als NEA]]
* <math>q_3</math> liest <math>K</math> und geht nach <math>q_4</math>. Das ergibt <math>C \to K</math>. Bei <math>E</math> geht <math>q_3</math> nach <math>q_F</math>, dieser Übergang entfällt.
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 Grammatik hat die Regeln:
'''Startmenge.''' Die erste Zeile der Tabelle ist die Startmenge <math>\{q_0\}</math>.


:<math>S \to KA \mid EB</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>A \to KB \mid EC</math>
* <math>\delta'(\{q_0\}; U) = \{q_0; q_1\}</math>
:<math>B \to KC \mid E</math>
* <math>\delta'(\{q_0\}; M) = \{q_0\}</math>, ebenso bei <math>L</math> und <math>x</math>
:<math>C \to K</math>


Das Wort <math>KEK</math> wird so abgeleitet:
Neu ist die Menge <math>\{q_0; q_1\}</math>. Sie wird die zweite Zeile.


:<math>S \Rightarrow KA \Rightarrow KEC \Rightarrow KEK</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>


Die Ableitung folgt dem Lauf des Automaten: Von <math>q_0</math> führt <math>K</math> nach <math>q_1</math> (<math>S \to KA</math>), von <math>q_1</math> führt <math>E</math> nach <math>q_3</math> (<math>A \to EC</math>), von <math>q_3</math> führt <math>K</math> in den Endzustand <math>q_4</math> (<math>C \to K</math>).
Neu ist die Menge <math>\{q_0; q_2\}</math>.


===Grammatik zu einem DEA mit weiterführendem Endzustand angeben===
'''Übrige Zeilen.''' Alle weiteren Zeilen entstehen auf dieselbe Weise, bis keine neue Menge mehr hinzukommt. Drei der Rechnungen:
[[Datei:DEA Teilwort KE.png|mini|DEA für Wörter mit dem Teilwort KE]]
* <math>\delta'(\{q_0; q_2\}; L) = \{q_0\} \cup \{q_3\} = \{q_0; q_3\}</math>
Der DEA im Bild akzeptiert alle Wörter über <math>\Sigma = \{K; E\}</math>, die das Teilwort <math>KE</math> enthalten, siehe [[Deterministischer endlicher Automat#DEA entwerfen|DEA entwerfen]]. Anders als beim Kaffeeautomaten geht es im Endzustand <math>q_2</math> weiter: Er hat eine Schleife für <math>K</math> und <math>E</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>


Die Zustände werden zu Nichtterminalen: <math>q_0</math> wird <math>S</math>, <math>q_1</math> wird <math>A</math>, <math>q_2</math> wird <math>B</math>. Jeder Übergang ergibt eine Regel. Zu jedem Übergang in den Endzustand <math>q_2</math> kommt eine zweite Regel ohne Nichtterminal hinzu:
Insgesamt ergeben sich sechs Zustände:


* <math>q_0</math>: <math>K</math> führt nach <math>q_1</math>, <math>E</math> führt nach <math>q_0</math>. Das ergibt <math>S \to KA \mid ES</math>.
{| class="wikitable" style="text-align:center"
* <math>q_1</math>: <math>K</math> führt nach <math>q_1</math>, <math>E</math> führt in den Endzustand <math>q_2</math>. Das ergibt <math>A \to KA \mid EB \mid E</math>.
! <math>\delta'</math> !! <math>U</math> !! <math>M</math> !! <math>L</math> !! <math>x</math>
* <math>q_2</math>: <math>K</math> und <math>E</math> führen in den Endzustand <math>q_2</math>. Das ergibt <math>B \to KB \mid EB \mid K \mid E</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>
|}


:<math>S \to KA \mid ES</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.
:<math>A \to KA \mid EB \mid E</math>
:<math>B \to KB \mid EB \mid K \mid E</math>


Die Regel <math>A \to E</math> beendet ein Wort direkt nach dem ersten <math>KE</math>. So entsteht das kürzeste Wort der Sprache:
'''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>S \Rightarrow KA \Rightarrow KE</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>
|}


Die Regel <math>A \to EB</math> lässt weitere Zeichen folgen. Das Wort <math>EKEK</math> braucht sie, weil nach dem <math>KE</math> noch ein Zeichen kommt:
[[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>S \Rightarrow ES \Rightarrow EKA \Rightarrow EKEB \Rightarrow EKEK</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:


Der Startzustand ist kein Endzustand, deshalb gibt es keine Regel <math>S \to \varepsilon</math>.
{| 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>
|}


===Grammatik zu einem DEA angeben, der das leere Wort akzeptiert===
'''Startmenge.''' Die erste Zeile ist <math>\{q_0\}</math>.
[[Datei:DEA Reste der Einheiten.png|mini|DEA für die Reste 0, 1 und 2]]
Der DEA im Bild akzeptiert alle Bestellfolgen, deren Summe der Einheiten durch 3 teilbar ist, siehe [[Deterministischer endlicher Automat#DEA für Reste entwerfen|DEA für Reste entwerfen]]. Sein Startzustand <math>q_0</math> ist zugleich der einzige Endzustand. Der DEA akzeptiert deshalb auch das leere Wort.


'''Schritt 1: Zustände und Übergänge übertragen.''' <math>q_0</math> wird <math>S</math>, <math>q_1</math> wird <math>A</math>, <math>q_2</math> wird <math>B</math>. Jeder Übergang ergibt eine Regel. Die beiden Übergänge in den Endzustand <math>q_0</math> ergeben zusätzlich je eine Regel ohne Nichtterminal: <math>A \to E</math> und <math>B \to K</math>.
'''Zeile der Startmenge.'''
* <math>\delta'(\{q_0\}; K) = \{q_1; q_2\}</math>
* <math>\delta'(\{q_0\}; E) = \emptyset</math>


:<math>S \to KA \mid EB</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>A \to KB \mid ES \mid E</math>
:<math>B \to KS \mid K \mid EA</math>


Diese Grammatik erzeugt alle Wörter des Automaten außer dem leeren Wort.
'''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>


'''Schritt 2: Leeres Wort ergänzen.''' Die Regel <math>S \to \varepsilon</math> ist in einer regulären Grammatik nur erlaubt, wenn <math>S</math> auf keiner rechten Regelseite vorkommt. Hier kommt <math>S</math> in <math>A \to ES</math> und in <math>B \to KS</math> vor. Die Grammatik erhält deshalb ein neues Startsymbol <math>S'</math> mit denselben rechten Seiten wie <math>S</math> und der zusätzlichen Regel <math>S' \to \varepsilon</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>.


:<math>S' \to KA \mid EB \mid \varepsilon</math>
Danach entsteht keine neue Menge mehr.
:<math>S \to KA \mid EB</math>
:<math>A \to KB \mid ES \mid E</math>
:<math>B \to KS \mid K \mid EA</math>


'''Schritt 3: Prüfen.''' Das leere Wort entsteht direkt mit <math>S' \Rightarrow \varepsilon</math>. Für <math>KE</math> mit 1 + 2 = 3 Einheiten gilt:
'''Endzustände.''' Nur die Menge <math>\{q_4\}</math> enthält den Endzustand <math>q_4</math> des NEA.


:<math>S' \Rightarrow KA \Rightarrow KE</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>
|}


Das Wort <math>KK</math> mit 2 Einheiten ist nicht ableitbar: Nach <math>S' \Rightarrow KA \Rightarrow KKB</math> steht noch das Nichtterminal <math>B</math> da, und jede Regel für <math>B</math> erzeugt mindestens ein weiteres Zeichen.
'''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.


===Rechtslineare Grammatik konstruieren===
Der DEA liest anders als der NEA jedes Wort bis zum Ende.
Gesucht ist eine rechtslineare Grammatik für alle Wörter über <math>\{K; E\}</math>, die mindestens ein <math>E</math> enthalten, zum Beispiel <math>E</math>, <math>KE</math>, <math>EK</math> und <math>KEKE</math>.


'''Schritt 1: Gedächtnis festlegen.''' Wie die Zustände eines DEA merken sich die Nichtterminale, was bisher erzeugt wurde: <math>S</math> steht für „noch kein <math>E</math> erzeugt“, <math>A</math> steht für „mindestens ein <math>E</math> erzeugt“.
===ε-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.


'''Schritt 2: Regeln aufstellen.''' Solange noch kein <math>E</math> erzeugt ist, darf ein <math>K</math> folgen (<math>S \to KS</math>) oder das erste <math>E</math> (<math>S \to EA</math>). Danach dürfen beliebige Zeichen folgen (<math>A \to KA</math> und <math>A \to EA</math>), oder das Wort endet (<math>A \to \varepsilon</math>):
'''Startmenge.''' Die erste Zeile ist <math>E(q_0) = \{q_0; q_1; q_2\}</math>.


:<math>S \to KS \mid EA</math>
'''Zeile der Startmenge.'''
:<math>A \to KA \mid EA \mid \varepsilon</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>


'''Schritt 3: Prüfen.''' Das Wort <math>KEK</math> ist ableitbar:
'''Ü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>.


:<math>S \Rightarrow KS \Rightarrow KEA \Rightarrow KEKA \Rightarrow KEK</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.


Ein Wort ohne <math>E</math> lässt sich nicht ableiten: Nur die Regel <math>S \to EA</math> führt zu <math>A</math>, und nur bei <math>A</math> kann eine Ableitung enden.
{| 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>
|}


'''Schritt 4: In die reguläre Form bringen.''' Die Regel <math>A \to \varepsilon</math> ist in einer regulären Grammatik nicht erlaubt. Sie wird gestrichen. Zum Ausgleich kommt zu jeder Regel, deren rechte Seite mit <math>A</math> endet, eine Regel ohne <math>A</math> hinzu: zu <math>S \to EA</math> die Regel <math>S \to E</math>, zu <math>A \to KA</math> die Regel <math>A \to K</math> und zu <math>A \to EA</math> die Regel <math>A \to E</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>S \to KS \mid EA \mid E</math>
===ε-Abschluss nach jedem Schritt bilden===
:<math>A \to KA \mid EA \mid K \mid E</math>
[[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.


Das Wort <math>KEK</math> braucht jetzt einen Schritt weniger, weil die Ableitung mit <math>A \to K</math> endet:
{| 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> || –
|}


:<math>S \Rightarrow KS \Rightarrow KEA \Rightarrow KEK</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>.


Dieselbe reguläre Grammatik entsteht auch aus dem DEA im Beispiel [[Deterministischer endlicher Automat#Akzeptierte Sprache eines DEA beschreiben|Akzeptierte Sprache eines DEA beschreiben]]: <math>S</math> entspricht dort dem Zustand <math>q_0</math>, <math>A</math> dem Zustand <math>q_1</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>


===Regel ohne Terminal ersetzen===
'''Zeile der Menge <math>\{q_1; q_2\}</math>.'''
Die folgende rechtslineare Grammatik erzeugt alle Wörter aus beliebig vielen <math>K</math>, auf die mindestens ein <math>E</math> folgt:
* <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>


:<math>S \to KS \mid A</math>
'''Zeile der Menge <math>\{q_2\}</math>.'''
:<math>A \to EA \mid E</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>.


Die Regel <math>S \to A</math> hat rechts kein Terminal und ist deshalb in einer regulären Grammatik nicht erlaubt. Sie wird gestrichen. Dafür erhält <math>S</math> die rechten Seiten von <math>A</math>, also <math>EA</math> und <math>E</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.
 
:<math>S \to KS \mid EA \mid E</math>
:<math>A \to EA \mid E</math>
 
Das Wort <math>KEE</math> zeigt den Unterschied. Die erste Grammatik braucht den Zwischenschritt von <math>S</math> nach <math>A</math>, die zweite nicht:
 
:<math>S \Rightarrow KS \Rightarrow KA \Rightarrow KEA \Rightarrow KEE</math>
:<math>S \Rightarrow KS \Rightarrow KEA \Rightarrow KEE</math>
 
===Rechtslineare Grammatik umformen===
Die folgende Grammatik ist rechtslinear, hat aber noch nicht die Form einer regulären Grammatik:
 
:<math>S \to KEA \mid K</math>
:<math>A \to EA \mid E</math>
 
Die Regel <math>S \to KEA</math> hat zwei Terminale vor dem Nichtterminal. Ein Hilfs-Nichtterminal <math>B</math> übernimmt das zweite Terminal: Aus <math>S \to KEA</math> werden <math>S \to KB</math> und <math>B \to EA</math>. Die übrigen Regeln haben schon die reguläre Form und bleiben. Es entsteht:
 
:<math>S \to KB \mid K</math>
:<math>B \to EA</math>
:<math>A \to EA \mid E</math>
 
Beide Grammatiken erzeugen dieselbe Sprache: <math>K</math> allein oder <math>KE</math> gefolgt von mindestens einem weiteren <math>E</math>. Die Wörter sind <math>K</math>, <math>KEE</math>, <math>KEEE</math> und so weiter. Das Wort <math>KEE</math> zeigt den Unterschied der Ableitungen. Die erste Grammatik braucht zwei Schritte, die zweite einen zusätzlichen Schritt über <math>B</math>:
 
:<math>S \Rightarrow KEA \Rightarrow KEE</math>
:<math>S \Rightarrow KB \Rightarrow KEA \Rightarrow KEE</math>
 
===Automaten zu einer regulären Grammatik konstruieren===
[[Datei:NEA aus regulärer Grammatik.png|mini|NEA zur regulären Grammatik]]
Gesucht ist ein endlicher Automat für die reguläre Grammatik aus dem vorigen Beispiel:
 
:<math>S \to KB \mid K</math>
:<math>B \to EA</math>
:<math>A \to EA \mid E</math>
 
'''Schritt 1: Zustände anlegen.''' Die Nichtterminale <math>S</math>, <math>B</math> und <math>A</math> werden zu Zuständen. Dazu kommt der neue Endzustand <math>X</math>. Der Startzustand ist <math>S</math>.
 
'''Schritt 2: Regeln mit Nichtterminal übertragen.''' <math>S \to KB</math> ergibt einen Übergang von <math>S</math> nach <math>B</math> mit <math>K</math>. <math>B \to EA</math> ergibt einen Übergang von <math>B</math> nach <math>A</math> mit <math>E</math>. <math>A \to EA</math> ergibt eine Schleife an <math>A</math> mit <math>E</math>.
 
'''Schritt 3: Regeln ohne Nichtterminal übertragen.''' <math>S \to K</math> ergibt einen Übergang von <math>S</math> nach <math>X</math> mit <math>K</math>. <math>A \to E</math> ergibt einen Übergang von <math>A</math> nach <math>X</math> mit <math>E</math>.


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
! <math>\delta'</math> !! <math>a</math> !! <math>b</math> !! <math>c</math>
|-
|-
| <math>\rightarrow S</math> || <math>\{B; X\}</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>B</math> || – || <math>\{A\}</math>
| <math>{}^*\{q_1; q_2\}</math> || <math>q_F</math> || <math>\{q_1; q_2\}</math> || <math>\{q_2\}</math>
|-
|-
| <math>A</math> || – || <math>\{A; X\}</math>
| <math>{}^*\{q_2\}</math> || <math>q_F</math> || <math>q_F</math> || <math>\{q_2\}</math>
|-
|-
| <math>{}^*X</math> || – || –
| <math>q_F</math> || <math>q_F</math> || <math>q_F</math> || <math>q_F</math>
|}
|}


Der Automat ist ein NEA: In <math>S</math> gibt es für <math>K</math> zwei Folgezustände, in <math>A</math> für <math>E</math> ebenfalls. Für das Wort <math>KEE</math> gibt es diese Pfade:
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.
 
* <math>S \xrightarrow{K} B \xrightarrow{E} A \xrightarrow{E} A</math> (kein Endzustand)
* <math>S \xrightarrow{K} B \xrightarrow{E} A \xrightarrow{E} X</math> (akzeptiert)
* <math>S \xrightarrow{K} X</math> (bricht ab)
 
Ein Pfad liest das ganze Wort und endet im Endzustand <math>X</math>. Der Automat akzeptiert <math>KEE</math>, so wie die Grammatik das Wort erzeugt.
 
===Grammatik in eine rechtslineare Grammatik umformen===
Die folgende Grammatik ist nicht rechtslinear, denn in der Regel für <math>S</math> steht das Nichtterminal <math>A</math> am Anfang:
 
:<math>S \to AE</math>
:<math>A \to KA \mid K</math>
 
'''Schritt 1: Sprache beschreiben.''' <math>A</math> erzeugt ein oder mehrere <math>K</math>: Die Regel <math>A \to KA</math> setzt ein weiteres <math>K</math> davor, die Regel <math>A \to K</math> beendet die Folge. <math>S \to AE</math> hängt genau ein <math>E</math> an. Die Sprache ist <math>\{K^n E \mid n \geq 1\}</math>, dabei ist <math>K^n</math> eine [[Wort#Wortpotenz|Wortpotenz]].
 
'''Schritt 2: Wörter von links nach rechts aufbauen.''' Jedes Wort beginnt mit <math>K</math>. Danach folgt entweder ein weiteres Wort derselben Sprache oder das abschließende <math>E</math>:
 
:<math>S \to KS \mid KE</math>
 
'''Schritt 3: Vergleichen.''' Das Wort <math>KKE</math> lässt sich mit beiden Grammatiken ableiten:
 
:<math>S \Rightarrow AE \Rightarrow KAE \Rightarrow KKE</math>
:<math>S \Rightarrow KS \Rightarrow KKE</math>
 
Die neue Grammatik ist rechtslinear. Die Regel <math>S \to KE</math> hat noch zwei Terminale. Für die reguläre Form wird sie wie im Beispiel [[#Rechtslineare Grammatik umformen|Rechtslineare Grammatik umformen]] durch <math>S \to KB</math> und <math>B \to E</math> ersetzt.


[[Kategorie:Formale Sprachen]]
[[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:

  1. Der Startzustand des DEA ist die Menge [math]\displaystyle{ \{q_0\} }[/math].
  2. 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].
  3. Jede neue Menge, die dabei entsteht, wird als Zeile in die Tabelle aufgenommen. Das wiederholt sich, bis keine neue Menge mehr entsteht.
  4. Endzustände sind alle Mengen, die mindestens einen Endzustand des NEA enthalten.
  5. 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

Spam-Filter als NEA

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]
Spam-Filter als DEA

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

NEA für das Wartungsmenü

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.

DEA für das Wartungsmenü mit Fehlerzustand
[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

DEA aus dem ε-NEA mit Fehlerzustand

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

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

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.