Deterministischer endlicher Automat: Unterschied zwischen den Versionen

Die Seite wurde neu angelegt: „Ein deterministischer endlicher Automat (DEA) prüft ein Wort Zeichen für Zeichen und hat in jedem Schritt genau einen Folgezustand. Er steckt in Automaten, Eingabeprüfungen und Compilern. ==Definition== Ein DEA liest Wörter über einem Alphabet und entscheidet, ob er sie akzeptiert. Er ist ein 5-Tupel <math>A = (Q, \Sigma, \delta, q0, F)</math>: * <math>Q</math>: endliche, nicht leere Menge der Zustände * <math>\Sigma</math…“
 
Keine Bearbeitungszusammenfassung
 
Zeile 1: Zeile 1:
Ein deterministischer endlicher Automat (DEA) prüft ein Wort Zeichen für Zeichen und hat in jedem Schritt genau einen Folgezustand. Er steckt in Automaten, Eingabeprüfungen und [[Compiler|Compilern]].
Ein deterministischer endlicher Automat (DEA) prüft ein Wort Zeichen für Zeichen und weiß in jedem Schritt eindeutig, wie es weitergeht. Er steckt in Automaten, Eingabeprüfungen und [[Compiler|Compilern]].


==Definition==
==Definition==
Ein DEA liest [[Wort|Wörter]] über einem [[Alphabet]] und entscheidet, ob er sie akzeptiert. Er ist ein 5-Tupel <math>A = (Q, \Sigma, \delta, q0, F)</math>:
Ein '''deterministischer endlicher Automat''' (kurz '''DEA''') liest [[Wort|Wörter]] über einem [[Alphabet]] und entscheidet, ob er sie akzeptiert. Er ist ein 5-Tupel <math>A = (Q; \Sigma; \delta; q_0; F)</math>:
* <math>Q</math>: endliche, nicht leere Menge der Zustände
* <math>Q</math>: endliche, nicht leere Menge der Zustände. Ein Zustand ist das Gedächtnis des Automaten: Er hält fest, was vom bisher Gelesenen noch wichtig ist.
* <math>\Sigma</math>: Eingabealphabet
* <math>\Sigma</math>: Eingabealphabet, eine endliche, nicht leere Menge von Zeichen. Aus seinen Zeichen bestehen die Wörter, die der Automat liest.
* <math>\delta: Q \times \Sigma \to Q</math>: Übergangsfunktion
* <math>\delta: Q \times \Sigma \to Q</math>: Übergangsfunktion. Sie legt fest, in welchen Zustand der Automat bei einem gelesenen Zeichen wechselt.
* <math>q0 \in Q</math>: Startzustand, auch Anfangszustand genannt
* <math>q_0 \in Q</math>: Startzustand, auch Anfangszustand genannt. In ihm beginnt der Automat.
* <math>F \subseteq Q</math>: Menge der Endzustände
* <math>F \subseteq Q</math>: Menge der Endzustände. Hat der Automat ein Wort vollständig gelesen und steht danach in einem von ihnen, ist das Wort akzeptiert.


Deterministisch bedeutet: Zu jedem Zustand und jedem Zeichen gibt es genau einen Folgezustand <math>\delta(q, a)</math>. Das Eingabewort legt den Lauf des Automaten damit eindeutig fest.
Ein '''Tupel''' ist eine geordnete Zusammenstellung: Anders als in einer [[Menge]] hat jeder Bestandteil seinen festen Platz. Die Bestandteile stehen in runden Klammern und werden durch Semikolons getrennt. Die Reihenfolge der Bestandteile ist eine Vereinbarung, manche Quellen nennen <math>\Sigma</math> zuerst.


Die Reihenfolge der Bestandteile im Tupel ist nicht entscheidend, manche Quellen nennen <math>\Sigma</math> zuerst. Nicht verwechseln: Das [[Zustandsdiagramm]] der UML zeichnet ebenfalls Zustände und Übergänge, verwendet aber andere Symbole und beschreibt kein Erkennen von Wörtern.
<math>Q \times \Sigma</math> ist die Menge aller Paare <math>(q; a)</math> aus einem Zustand <math>q \in Q</math> und einem Zeichen <math>a \in \Sigma</math>. Die Übergangsfunktion <math>\delta</math> ordnet einem solchen Paar den Folgezustand <math>\delta(q; a)</math> zu, so wie eine [[Funktion]] in der Mathematik einem Wert seinen Funktionswert zuordnet.
 
'''Deterministisch''' bedeutet: Zu jedem Zustand und jedem Zeichen gibt es höchstens einen Folgezustand. Das Eingabewort legt den Weg des Automaten durch seine Zustände, den Lauf, damit eindeutig fest. Legt <math>\delta</math> für jedes Paar einen Folgezustand fest, heißt der DEA '''vollständig'''. Andernfalls ist <math>\delta</math> für einzelne Paare nicht definiert, und der DEA heißt unvollständig, siehe [[#Vollständiger DEA und Fehlerzustand|Vollständiger DEA und Fehlerzustand]].
 
Nicht verwechseln: Das [[Zustandsdiagramm]] der UML zeichnet ebenfalls Zustände und Übergänge, verwendet aber andere Symbole und beschreibt kein Erkennen von Wörtern.


==Darstellungsformen==
==Darstellungsformen==
Zeile 21: Zeile 25:
* Ein Pfeil mit der Beschriftung „Start“ zeigt auf den Startzustand.
* Ein Pfeil mit der Beschriftung „Start“ zeigt auf den Startzustand.
* Jeder Endzustand ist ein Doppelkreis.
* Jeder Endzustand ist ein Doppelkreis.
* Jeder Übergang <math>\delta(p, a) = q</math> ist ein Pfeil von <math>p</math> nach <math>q</math>, beschriftet mit dem Eingabezeichen <math>a</math>. Führen mehrere Zeichen von <math>p</math> nach <math>q</math>, steht ein Pfeil mit allen Zeichen, durch Komma getrennt.
* Jeder Übergang <math>\delta(p; a) = q</math> ist ein Pfeil von <math>p</math> nach <math>q</math>, beschriftet mit dem Eingabezeichen <math>a</math>. Führen mehrere Zeichen von <math>p</math> nach <math>q</math>, steht ein Pfeil mit allen Zeichen, durch Semikolon getrennt.
* Ein Pfeil von einem Zustand zu sich selbst heißt Schleife.


===Übergangstabelle===
===Übergangstabelle===
Die Übergangstabelle hat für jeden Zustand eine Zeile und für jedes Zeichen des Alphabets eine Spalte. Die Zelle enthält den Folgezustand <math>\delta(q, a)</math>. Ein Pfeil → vor dem Zustand markiert den Startzustand, ein Stern * die Endzustände. Ist der Startzustand zugleich Endzustand, stehen beide Zeichen davor.
Die Übergangstabelle hat für jeden Zustand eine Zeile und für jedes Zeichen des Alphabets eine Spalte. Die Zelle enthält den Folgezustand <math>\delta(q; a)</math>. Ein Pfeil <math>\rightarrow</math> vor dem Zustand markiert den Startzustand, ein hochgestellter Stern <math>{}^*</math> die Endzustände. Ist der Startzustand zugleich Endzustand, stehen beide Zeichen davor. Fehlt ein Übergang, enthält die Zelle einen Strich.
 
===Graph und Tabelle ineinander überführen===
Beide Darstellungen lassen sich Schritt für Schritt ineinander überführen.
 
Vom Graphen zur Tabelle:
# Für jeden Kreis eine Zeile und für jedes Zeichen des Alphabets eine Spalte anlegen.
# Für jeden Pfeil von <math>p</math> nach <math>q</math> mit dem Zeichen <math>a</math> den Zustand <math>q</math> in die Zeile <math>p</math> und die Spalte <math>a</math> eintragen. Ein Pfeil mit mehreren Zeichen füllt mehrere Zellen.
# Den Startzustand mit dem Pfeil und jeden Endzustand mit dem Stern markieren.
# In jede Zelle, die leer geblieben ist, einen Strich setzen.
 
Von der Tabelle zum Graphen:
# Für jede Zeile einen Kreis zeichnen und mit dem Zustand beschriften.
# Den Startpfeil und die Doppelkreise der Endzustände ergänzen.
# Für jede gefüllte Zelle einen Pfeil vom Zustand der Zeile zum eingetragenen Zustand zeichnen und mit dem Zeichen der Spalte beschriften. Pfeile mit demselben Anfang und demselben Ende zu einem Pfeil zusammenfassen.


==Wortverarbeitung==
==Wortverarbeitung==
Der Automat startet im Zustand q0. Jedes Zeichen des Eingabewortes führt genau einen Schritt aus: Aus dem aktuellen Zustand <math>q</math> und dem gelesenen Zeichen <math>a</math> ergibt sich der Folgezustand <math>\delta(q, a)</math>. Die Zustandsfolge dokumentiert den Lauf des Automaten.
Der Automat startet im Zustand <math>q_0</math> und liest das Eingabewort Zeichen für Zeichen. Für jedes Zeichen führt er einen Schritt aus, solange <math>\delta</math> für den aktuellen Zustand und das gelesene Zeichen einen Folgezustand festlegt: Aus dem aktuellen Zustand <math>q</math> und dem gelesenen Zeichen <math>a</math> ergibt sich der Folgezustand <math>\delta(q; a)</math>. Ein solcher Schritt wird auch als beschrifteter Pfeil geschrieben: <math>p \xrightarrow{a} q</math> bedeutet <math>\delta(p; a) = q</math>.


Ein Wort wird akzeptiert, wenn der Automat nach dem letzten Zeichen in einem Endzustand steht. Sonst wird es abgelehnt. Das leere Wort <math>\varepsilon</math> wird akzeptiert, wenn <math>q0 \in F</math> gilt, denn ohne Zeichen bleibt der Automat im Startzustand.
Der Weg des Automaten durch seine Zustände heißt '''Lauf'''. Die Zustandsfolge dokumentiert ihn. Liest der Automat ein Wort aus <math>n</math> Zeichen vollständig, besteht sie aus <math>n + 1</math> Zuständen. Bricht der Lauf vorher ab, weil ein Übergang fehlt, ist sie kürzer.


Die akzeptierte Sprache <math>L(A)</math> ist die Menge aller Wörter, die der Automat akzeptiert. Sie ist eine [[Formale Sprache|formale Sprache]] über <math>\Sigma</math>.
Ein Wort wird akzeptiert, wenn der Automat es vollständig gelesen hat und danach in einem Endzustand steht. Sonst wird es abgelehnt. Abgelehnt wird ein Wort auch dann, wenn der Lauf vorzeitig abbricht, weil für ein Zeichen kein Übergang festgelegt ist. Das [[Wort#Leeres Wort|leere Wort]] <math>\varepsilon</math> wird akzeptiert, wenn <math>q_0 \in F</math> gilt, denn ohne Zeichen bleibt der Automat im Startzustand.
 
Die akzeptierte Sprache <math>L(A)</math> ist die Menge aller Wörter, die der Automat akzeptiert. Sie ist eine [[Formale Sprache|formale Sprache]] über <math>\Sigma</math>. Ein DEA ist damit eine der Möglichkeiten, eine Sprache zu beschreiben, siehe [[Formale Sprache#Beschreibung formaler Sprachen|Beschreibung formaler Sprachen]].


==Vollständiger DEA und Fehlerzustand==
==Vollständiger DEA und Fehlerzustand==
Die Übergangsfunktion <math>\delta</math> braucht für jedes Paar aus Zustand und Zeichen einen Wert. Zeichnungen lassen Übergänge oft weg, nach denen das Wort ohnehin abgelehnt wird. Dann ist der Automat noch nicht vollständig.
Ein DEA heißt '''vollständig''', wenn die Übergangsfunktion <math>\delta</math> für jedes Paar aus Zustand und Zeichen einen Folgezustand festlegt. In der Übergangstabelle ist dann jede Zelle gefüllt. Zeichnungen lassen oft die Übergänge weg, nach denen das Wort ohnehin abgelehnt wird. Ein solcher DEA ist '''unvollständig''': Trifft er auf einen fehlenden Übergang, bricht der Lauf ab, und das Wort ist abgelehnt.


Zur Ergänzung führen alle fehlenden Übergänge in einen Fehlerzustand qF. Alle Zeichen bleiben dort in qF. Ein Wort, das einmal in qF gelandet ist, wird nie akzeptiert. qF ist kein Endzustand und nicht mit der Menge <math>F</math> zu verwechseln.
Zum Vervollständigen führen alle fehlenden Übergänge in einen zusätzlichen '''Fehlerzustand''' <math>q_F</math> (auch Fangzustand). Alle Zeichen bleiben dort in <math>q_F</math>. Ein Wort, das einmal in <math>q_F</math> gelandet ist, wird nie akzeptiert. <math>q_F</math> ist kein Endzustand: Der Index <math>F</math> steht für Fehler und ist nicht mit der Menge <math>F</math> der Endzustände zu verwechseln.
 
Der vollständige DEA akzeptiert dieselbe Sprache wie der unvollständige. Er liest aber jedes Wort bis zum letzten Zeichen. Ein Programm, das den Automaten umsetzt, hat damit für jede Eingabe eine festgelegte Reaktion.
 
==Entwurfsverfahren==
Ein DEA zu einer gegebenen Sprache entsteht in fünf Schritten:
# '''Gedächtnis festlegen:''' Was muss sich der Automat vom bisher Gelesenen merken, um das nächste Zeichen richtig zu verarbeiten? Jede mögliche Antwort wird ein Zustand.
# '''Startzustand wählen:''' Er steht für die Lage, in der noch nichts gelesen wurde.
# '''Übergänge eintragen:''' Für jeden Zustand und jedes Zeichen den Folgezustand festlegen.
# '''Endzustände festlegen:''' Endzustand ist jeder Zustand, in dem das bisher Gelesene zur Sprache gehört.
# '''Prüfen:''' Den Automaten mit Wörtern testen, die zur Sprache gehören, und mit Wörtern, die nicht dazugehören. Auch das leere Wort ist ein Testfall.
 
Typische Inhalte des Gedächtnisses sind:
* ein Zähler bis zu einer festen Grenze,
* der Rest bei einer Division ([[Modulo]]), wenn nur die Teilbarkeit einer Anzahl zählt,
* der zuletzt gelesene Anfang eines gesuchten Musters,
* die Tatsache, dass das Wort nicht mehr zur Sprache gehören kann (Fehlerzustand).
 
Ein DEA kann nur endlich viele Lagen unterscheiden. Das begrenzt, was er sich merken kann, und erlaubt eine Aussage über die nötige Zahl der Zustände. Dabei heißt der schon gelesene Teil eines Wortes '''Wortanfang''' (auch Präfix, siehe [[Wort#Teilwort|Teilwort]]) und der Teil, der noch folgt, '''Fortsetzung''' oder Restwort. In einem vollständigen DEA führt jeder Wortanfang in genau einen Zustand. Führen zwei Wortanfänge in denselben Zustand, behandelt der Automat alle Fortsetzungen gleich. Gibt es eine Fortsetzung, die nur an einen der beiden Wortanfänge angehängt ein Wort der Sprache ergibt, brauchen die beiden deshalb verschiedene Zustände. Die Fortsetzung darf auch das leere Wort sein: Dann gehört der eine Wortanfang selbst zur Sprache und der andere nicht. Lassen sich <math>k</math> Wortanfänge auf diese Weise paarweise voneinander unterscheiden, braucht ein vollständiger DEA für die Sprache mindestens <math>k</math> Zustände.


==Minimierung==
==Minimierung==
Zwei Zustände sind äquivalent, wenn sie jedes Restwort gleich entscheiden. Ein Restwort ist der noch ungelesene Teil der Eingabe. Für jedes Restwort endet der Lauf ab dem einen Zustand genau dann in einem Endzustand, wenn der Lauf ab dem anderen Zustand in einem Endzustand endet.
Zwei Zustände sind '''äquivalent''', wenn von beiden aus jedes Restwort zum selben Ergebnis führt. Ein Restwort ist der noch ungelesene Teil der Eingabe. Für jedes Restwort endet der Lauf ab dem einen Zustand genau dann in einem Endzustand, wenn der Lauf ab dem anderen Zustand in einem Endzustand endet. Zwei Zustände sind '''unterscheidbar''', wenn es ein Restwort gibt, das nur von einem der beiden aus in einen Endzustand führt.


Äquivalente Zustände lassen sich zu einem Zustand zusammenlegen, ohne dass sich die akzeptierte Sprache ändert. Ein Automat ohne äquivalente und ohne nicht erreichbare Zustände ist minimal.
Äquivalente Zustände lassen sich zu einem Zustand zusammenlegen, ohne dass sich die akzeptierte Sprache ändert. Ein Zustand ist erreichbar, wenn vom Startzustand ein Weg zu ihm führt. Ein vollständiger DEA ohne äquivalente und ohne nicht erreichbare Zustände ist minimal: Kein vollständiger DEA für dieselbe Sprache hat weniger Zustände.


Das Tabellenfüllverfahren findet die äquivalenten Zustände:
Das Tabellenfüllverfahren findet die äquivalenten Zustände eines vollständigen DEA. Es betrachtet alle Paare aus zwei verschiedenen Zuständen. Auf die Reihenfolge im Paar kommt es nicht an: <math>(p; q)</math> und <math>(q; p)</math> sind dasselbe Paar. Die Paare stehen in einer Dreieckstabelle, die für jedes Paar genau eine Zelle hat.
# Nicht erreichbare Zustände entfernen.
# Nicht erreichbare Zustände entfernen.
# Alle Paare aus einem Endzustand und einem Nicht-Endzustand markieren.
# Runde 0: Alle Paare aus einem Endzustand und einem Nicht-Endzustand markieren.
# Ein Paar <math>(p, q)</math> markieren, wenn für ein Zeichen <math>a</math> das Paar <math>(\delta(p, a), \delta(q, a))</math> markiert ist. Das wiederholen, bis nichts Neues hinzukommt.
# Runde 1, Runde 2 und so weiter: Alle noch unmarkierten Paare durchgehen. Zu einem Paar <math>(p; q)</math> und einem Zeichen <math>a</math> gehört das '''Folgepaar''' <math>(\delta(p; a); \delta(q; a))</math>. Das Paar <math>(p; q)</math> wird markiert, wenn für ein Zeichen das Folgepaar schon zu Beginn der Runde markiert war. Die Runden wiederholen sich, bis eine Runde kein Paar mehr markiert.
# Unmarkierte Paare zusammenlegen.
# Unmarkierte Paare zusammenlegen.


Markierte Paare sind unterscheidbar, unmarkierte Paare sind äquivalent.
Markierte Paare sind unterscheidbar, unmarkierte Paare sind äquivalent. Führt ein Zeichen beide Zustände eines Paares in denselben Zustand, entsteht kein Folgepaar. Dieses Zeichen kann die beiden Zustände dann nicht unterscheiden. Wer ein Paar, das in der laufenden Runde markiert wurde, sofort mitzählt, kommt manchmal mit weniger Runden aus. Am Ende sind dieselben Paare markiert.
 
Beim Zusammenlegen wird aus jeder Gruppe äquivalenter Zustände ein neuer Zustand. Er trägt die Namen der zusammengelegten Zustände in Mengenklammern. Seine Übergänge werden an einem beliebigen Zustand der Gruppe abgelesen: Führt dieser Zustand mit einem Zeichen in einen Zustand <math>r</math>, führt der neue Zustand mit demselben Zeichen in die Gruppe, zu der <math>r</math> gehört. Der neue Zustand ist Startzustand, wenn seine Gruppe den Startzustand enthält, und Endzustand, wenn seine Gruppe aus Endzuständen besteht.


==Produktautomat==
==Produktautomat==
Der Produktautomat lässt zwei DEA über demselben Alphabet gleichzeitig laufen. Seine Zustände sind die Paare <math>Q_1 \times Q_2</math> der Zustandsmengen beider Automaten. Der Start besteht aus beiden Startzuständen. Jeder Übergang wird komponentenweise berechnet:
Der Produktautomat lässt zwei vollständige DEA <math>A_1</math> und <math>A_2</math> über demselben Alphabet gleichzeitig laufen. <math>A_1</math> hat die Zustandsmenge <math>Q_1</math>, die Übergangsfunktion <math>\delta_1</math> und die Endzustandsmenge <math>F_1</math>, <math>A_2</math> entsprechend <math>Q_2</math>, <math>\delta_2</math> und <math>F_2</math>. Ein Zustand des Produktautomaten ist ein Paar <math>(p; q)</math> aus einem Zustand <math>p \in Q_1</math> und einem Zustand <math>q \in Q_2</math>. <math>p</math> heißt erste Komponente, <math>q</math> zweite Komponente des Paares. Die Zustandsmenge ist die Menge aller dieser Paare, <math>Q_1 \times Q_2</math>. Startzustand ist das Paar aus den beiden Startzuständen. Jeder Übergang wird komponentenweise berechnet, also für jede Komponente mit der Übergangsfunktion ihres Automaten:


:<math>\delta((p, q), a) = (\delta_1(p, a), \delta_2(q, a))</math>
:<math>\delta((p; q); a) = (\delta_1(p; a); \delta_2(q; a))</math>


Die Endzustände richten sich nach der gewünschten Sprache:
Die Endzustände richten sich nach der gewünschten Sprache:
* Für den Schnitt beider Sprachen gilt <math>F = F_1 \times F_2</math>. Beide Komponenten müssen Endzustände sein.
* Für den Schnitt beider Sprachen (die [[Menge#Schnittmenge|Schnittmenge]]) gilt <math>F = F_1 \times F_2</math>. Beide Komponenten müssen Endzustände sein.
* Für die Vereinigung reicht ein Endzustand in einer der beiden Komponenten.
* Für die Vereinigung beider Sprachen (die [[Menge#Vereinigungsmenge|Vereinigungsmenge]]) reicht ein Endzustand in einer der beiden Komponenten: Endzustand ist jedes Paar <math>(p; q)</math> mit <math>p \in F_1</math> oder <math>q \in F_2</math>.


==Beispiele==
==Beispiele==
===Kaffeeautomat als vollständigen DEA angeben===
===Kaffeeautomat als vollständigen DEA angeben===
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]]
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]]
Der Kaffeeautomat aus dem Artikel [[Formale Sprache]] hat ein Satzfach, das bei genau vier Einheiten voll ist. Ein Kaffee K zählt 1, ein Espresso E zählt 2. Der Zustand merkt sich den Füllstand: q0 bedeutet leer, q1 bis q3 bedeuten 1 bis 3 Einheiten, q4 bedeutet voll. Mehr als vier Einheiten führen in den Fehlerzustand qF (übervoll).
Der Kaffeeautomat aus dem Artikel [[Formale Sprache]] hat ein Satzfach, das bei genau vier Einheiten voll ist. Ein Kaffee <math>K</math> zählt 1, ein Espresso <math>E</math> zählt 2. Der Zustand merkt sich den Füllstand: <math>q_0</math> bedeutet leer, <math>q_1</math> bis <math>q_3</math> bedeuten 1 bis 3 Einheiten, <math>q_4</math> bedeutet voll. Mehr als vier Einheiten führen in den Fehlerzustand <math>q_F</math> (übervoll).


Der DEA <math>A = (Q, \Sigma, \delta, q0, F)</math> hat diese Bestandteile:
Der DEA <math>A = (Q; \Sigma; \delta; q_0; F)</math> hat diese Bestandteile:
* <math>Q = \{q0, q1, q2, q3, q4, qF\}</math>
* <math>Q = \{q_0; q_1; q_2; q_3; q_4; q_F\}</math>
* <math>\Sigma = \{K, E\}</math>
* <math>\Sigma = \{K; E\}</math>
* <math>\delta</math> laut Übergangstabelle
* <math>\delta</math> laut Übergangstabelle
* Startzustand q0
* Startzustand <math>q_0</math>
* <math>F = \{q4\}</math>
* <math>F = \{q_4\}</math>


Die Übergangstabelle hat die Zustände als Zeilen und die Zeichen K und E als Spalten:
Die Übergangstabelle hat die Zustände als Zeilen und die Zeichen <math>K</math> und <math>E</math> als Spalten:


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! Zustand !! K !! E
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
|-
|-
| → q0 || q1 || q2
| <math>\rightarrow q_0</math> || <math>q_1</math> || <math>q_2</math>
|-
|-
| q1 || q2 || q3
| <math>q_1</math> || <math>q_2</math> || <math>q_3</math>
|-
|-
| q2 || q3 || q4
| <math>q_2</math> || <math>q_3</math> || <math>q_4</math>
|-
|-
| q3 || q4 || qF
| <math>q_3</math> || <math>q_4</math> || <math>q_F</math>
|-
|-
| * q4 || qF || qF
| <math>{}^*q_4</math> || <math>q_F</math> || <math>q_F</math>
|-
|-
| qF || qF || qF
| <math>q_F</math> || <math>q_F</math> || <math>q_F</math>
|}
|}


Beispiel für das Lesen der Tabelle: Im Zustand q1 führt E nach q3, denn 1 + 2 = 3 Einheiten. Es gilt also <math>\delta(q1, E) = q3</math>. Alle Zellen sind gefüllt, der Automat ist vollständig. Er akzeptiert genau die Wörter der Sprache <math>L = \{KKKK, EE, EKK, KEK, KKE\}</math>.
Beispiel für das Lesen der Tabelle: Im Zustand <math>q_1</math> führt <math>E</math> nach <math>q_3</math>, denn 1 + 2 = 3 Einheiten. Es gilt also <math>\delta(q_1; E) = q_3</math>. Alle Zellen sind gefüllt, der Automat ist vollständig. Er akzeptiert genau die Wörter der Sprache <math>L = \{KKKK; EE; EKK; KEK; KKE\}</math>.


===Wortzugehörigkeit mit einem DEA prüfen===
===Wortzugehörigkeit mit einem DEA prüfen===
Der Automat aus dem vorigen Beispiel prüft drei Wörter. Der Lauf beginnt in q0. Die Schreibweise q0 –K→ q1 bedeutet: Im Zustand q0 wird K gelesen, der Folgezustand ist q1.
Der Automat aus dem vorigen Beispiel prüft vier Wörter. Jeder Lauf beginnt in <math>q_0</math>. Die Schreibweise <math>q_0 \xrightarrow{K} q_1</math> bedeutet: Im Zustand <math>q_0</math> wird <math>K</math> gelesen, der Folgezustand ist <math>q_1</math>.
 
'''Wort <math>KEK</math>:'''
:<math>q_0 \xrightarrow{K} q_1 \xrightarrow{E} q_3 \xrightarrow{K} q_4</math>
Der Lauf endet in <math>q_4</math>. Das ist ein Endzustand, <math>KEK</math> wird akzeptiert.
 
'''Wort <math>EEK</math>:'''
:<math>q_0 \xrightarrow{E} q_2 \xrightarrow{E} q_4 \xrightarrow{K} q_F</math>
Der Lauf endet in <math>q_F</math>. Nach <math>EE</math> ist das Satzfach voll, das <math>K</math> lässt es überlaufen. <math>q_F</math> ist kein Endzustand, <math>EEK</math> wird abgelehnt.
 
'''Wort <math>KK</math>:'''
:<math>q_0 \xrightarrow{K} q_1 \xrightarrow{K} q_2</math>
Der Lauf endet in <math>q_2</math>. Das ist kein Endzustand, denn das Satzfach hat erst 2 Einheiten. <math>KK</math> wird abgelehnt.
 
'''Leeres Wort <math>\varepsilon</math>:''' Ohne Zeichen gibt es keinen Schritt, der Lauf besteht nur aus <math>q_0</math>. Der Startzustand ist kein Endzustand, das leere Wort wird abgelehnt.
 
===Übergangstabelle aus einem Übergangsgraphen aufstellen===
[[Datei:DEA Kaffeeautomat ohne Fehlerzustand.png|mini|DEA des Kaffeeautomaten ohne Fehlerzustand]]
Das Bild zeigt einen Entwurf des Kaffeeautomaten als Übergangsgraph. Gesucht ist seine Übergangstabelle.
 
# '''Zeilen und Spalten anlegen:''' Der Graph hat die fünf Kreise <math>q_0</math> bis <math>q_4</math>, die Tabelle bekommt also fünf Zeilen. Das Alphabet <math>\Sigma = \{K; E\}</math> ergibt die Spalten <math>K</math> und <math>E</math>.
# '''Pfeile eintragen:''' Jeder der sieben Pfeile füllt eine Zelle. Der Pfeil von <math>q_0</math> nach <math>q_1</math> mit <math>K</math> ergibt den Eintrag <math>q_1</math> in der Zeile <math>q_0</math> und der Spalte <math>K</math>. Der Pfeil von <math>q_0</math> nach <math>q_2</math> mit <math>E</math> ergibt den Eintrag <math>q_2</math> in derselben Zeile und der Spalte <math>E</math>. Die übrigen fünf Pfeile werden genauso eingetragen.
# '''Start und Ende markieren:''' Der Startpfeil zeigt auf <math>q_0</math>, diese Zeile erhält den Pfeil <math>\rightarrow</math>. <math>q_4</math> ist ein Doppelkreis, diese Zeile erhält den Stern.
# '''Leere Zellen kennzeichnen:''' Für drei Paare aus Zustand und Zeichen gibt es keinen Pfeil. Ihre Zellen erhalten einen Strich.
 
{| class="wikitable" style="text-align:center"
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
|-
| <math>\rightarrow q_0</math> || <math>q_1</math> || <math>q_2</math>
|-
| <math>q_1</math> || <math>q_2</math> || <math>q_3</math>
|-
| <math>q_2</math> || <math>q_3</math> || <math>q_4</math>
|-
| <math>q_3</math> || <math>q_4</math> || –
|-
| <math>{}^*q_4</math> || – || –
|}


'''KEK:''' <code>q0 –K→ q1 –E→ q3 –K→ q4</code>
Zur Kontrolle: Die Tabelle hat zehn Zellen. Sieben sind gefüllt, so viele Pfeile hat der Graph. Drei enthalten einen Strich.


Der Lauf endet in q4. Das ist ein Endzustand, KEK wird akzeptiert.
===Unvollständigen DEA vervollständigen===
Der Entwurf aus dem vorigen Beispiel zeigt den Kaffeeautomaten ohne Fehlerzustand. In seiner Übergangstabelle enthalten drei Zellen einen Strich.


'''EEK:''' <code>q0 –E→ q2 –E→ q4 –K→ qF</code>
'''Schritt 1: Fehlende Übergänge finden.''' Es fehlen die Übergänge für die Paare <math>(q_3; E)</math>, <math>(q_4; K)</math> und <math>(q_4; E)</math>. Der Automat ist unvollständig. Für das Wort <math>EEK</math> bricht der Lauf nach zwei Zeichen ab, weil in <math>q_4</math> kein Übergang für <math>K</math> festgelegt ist:
:<math>q_0 \xrightarrow{E} q_2 \xrightarrow{E} q_4</math>
Das Wort ist damit abgelehnt, aber nicht bis zum Ende gelesen.


Der Lauf endet in qF. Nach EE ist das Satzfach voll, das K lässt es überlaufen. qF ist kein Endzustand, EEK wird abgelehnt.
'''Schritt 2: Fehlerzustand ergänzen.''' Der neue Zustand <math>q_F</math> kommt hinzu. Er ist kein Endzustand.


'''KK:''' <code>q0 –K→ q1 –K→ q2</code>
'''Schritt 3: Lücken füllen.''' Alle drei fehlenden Übergänge führen nach <math>q_F</math>: <math>\delta(q_3; E) = q_F</math>, <math>\delta(q_4; K) = q_F</math> und <math>\delta(q_4; E) = q_F</math>.


Der Lauf endet in q2. Das ist kein Endzustand, denn das Satzfach hat erst 2 Einheiten. KK wird abgelehnt.
'''Schritt 4: Fehlerzustand abschließen.''' Von <math>q_F</math> führen <math>K</math> und <math>E</math> wieder nach <math>q_F</math>.
 
Das Ergebnis ist der vollständige DEA aus dem Beispiel [[#Kaffeeautomat als vollständigen DEA angeben|Kaffeeautomat als vollständigen DEA angeben]]. Er liest <math>EEK</math> bis zum Ende und endet in <math>q_F</math>. Beide Automaten akzeptieren dieselben fünf Wörter.
 
===Übergangsgraph aus einer Übergangstabelle zeichnen===
[[Datei:DEA Mindestens ein E.png|mini|Übergangsgraph zur Tabelle]]
Gegeben ist ein DEA über <math>\Sigma = \{K; E\}</math> durch seine Übergangstabelle:
 
{| class="wikitable" style="text-align:center"
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
|-
| <math>\rightarrow q_0</math> || <math>q_0</math> || <math>q_1</math>
|-
| <math>{}^*q_1</math> || <math>q_1</math> || <math>q_1</math>
|}
 
# '''Kreise zeichnen:''' Die Tabelle hat zwei Zeilen, also entstehen die Kreise <math>q_0</math> und <math>q_1</math>.
# '''Start und Ende markieren:''' Der Pfeil in der ersten Zeile zeigt: <math>q_0</math> ist der Startzustand und bekommt den Startpfeil. Der Stern in der zweiten Zeile zeigt: <math>q_1</math> ist Endzustand und wird ein Doppelkreis.
# '''Pfeile für die erste Zeile:''' In <math>q_0</math> führt <math>K</math> nach <math>q_0</math>, das ergibt eine Schleife mit <math>K</math>. <math>E</math> führt nach <math>q_1</math>, das ergibt einen Pfeil von <math>q_0</math> nach <math>q_1</math> mit <math>E</math>.
# '''Pfeile für die zweite Zeile:''' In <math>q_1</math> führen <math>K</math> und <math>E</math> nach <math>q_1</math>. Beide Pfeile haben denselben Anfang und dasselbe Ende und werden zu einer Schleife mit der Beschriftung <math>K; E</math> zusammengefasst.
 
Zur Kontrolle: Die Tabelle hat vier gefüllte Zellen. Der Graph hat drei Pfeile, an denen zusammen vier Zeichen stehen.
 
===Akzeptierte Sprache eines DEA beschreiben===
Gesucht ist die Sprache des DEA aus dem vorigen Beispiel.
 
# '''Endzustand betrachten:''' Akzeptiert wird ein Wort, wenn der Lauf in <math>q_1</math> endet.
# '''Wege in den Endzustand suchen:''' Von <math>q_0</math> nach <math>q_1</math> führt nur der Pfeil mit <math>E</math>. Solange nur <math>K</math> gelesen wird, bleibt der Automat in <math>q_0</math>. Ist <math>q_1</math> einmal erreicht, bleibt der Automat bei jedem Zeichen dort.
# '''Bedeutung der Zustände ableiten:''' In <math>q_0</math> wurde noch kein <math>E</math> gelesen. In <math>q_1</math> wurde mindestens ein <math>E</math> gelesen.
# '''Mit Wörtern prüfen:''' Für <math>KEK</math> ergibt sich <math>q_0 \xrightarrow{K} q_0 \xrightarrow{E} q_1 \xrightarrow{K} q_1</math>, das Wort wird akzeptiert. Für <math>KK</math> ergibt sich <math>q_0 \xrightarrow{K} q_0 \xrightarrow{K} q_0</math>, das Wort wird abgelehnt. Das leere Wort bleibt in <math>q_0</math> und wird abgelehnt.
 
Der DEA akzeptiert genau die Wörter, die mindestens ein <math>E</math> enthalten:
 
:<math>L(A) = \{uEv \mid u \in \Sigma^* \text{ und } v \in \Sigma^*\}</math>
 
Die Schreibweise mit den Platzhaltern <math>u</math> und <math>v</math> erklärt das Beispiel [[Formale Sprache#Unendliche Sprache in Mengenschreibweise angeben|Unendliche Sprache in Mengenschreibweise angeben]].


===DEA entwerfen===
===DEA entwerfen===
Gesucht ist ein DEA für alle Wörter über <math>\Sigma = \{K, E\}</math>, die das Teilwort KE enthalten. In diesen Wörtern folgt irgendwo ein E direkt auf ein K.
Gesucht ist ein DEA für alle Wörter über <math>\Sigma = \{K; E\}</math>, die das [[Wort#Teilwort|Teilwort]] <math>KE</math> enthalten. In diesen Wörtern folgt irgendwo ein <math>E</math> direkt auf ein <math>K</math>.


Leitidee: Jeder Zustand merkt sich das Nötige.
Leitidee: Jeder Zustand merkt sich das Nötige.
* q0: Es ist noch kein Anfang von KE gelesen.
* <math>q_0</math>: Es ist noch kein Anfang von <math>KE</math> gelesen.
* q1: Das letzte Zeichen war K. Kommt jetzt ein E, ist KE gefunden.
* <math>q_1</math>: Das letzte Zeichen war <math>K</math>. Kommt jetzt ein <math>E</math>, ist <math>KE</math> gefunden.
* q2: KE wurde gefunden. Alles Weitere ändert daran nichts, q2 ist der Endzustand.
* <math>q_2</math>: <math>KE</math> wurde gefunden. Alles Weitere ändert daran nichts, <math>q_2</math> ist der Endzustand.


Daraus ergeben sich die Übergänge:
Daraus ergeben sich die Übergänge:
* In q0 führt K nach q1, denn K kann der Anfang von KE sein. E führt zurück nach q0, denn ein E ohne vorheriges K hilft nicht.
* In <math>q_0</math> führt <math>K</math> nach <math>q_1</math>, denn <math>K</math> kann der Anfang von <math>KE</math> sein. <math>E</math> führt zurück nach <math>q_0</math>, denn ein <math>E</math> ohne vorheriges <math>K</math> hilft nicht.
* In q1 bleibt der Automat bei K in q1, denn das neue K ist ein neuer möglicher Anfang. E führt nach q2.
* In <math>q_1</math> bleibt der Automat bei <math>K</math> in <math>q_1</math>, denn das neue <math>K</math> ist ein neuer möglicher Anfang. <math>E</math> führt nach <math>q_2</math>.
* In q2 führen K und E nach q2.
* In <math>q_2</math> führen <math>K</math> und <math>E</math> nach <math>q_2</math>.


[[Datei:DEA Teilwort KE.png|mini|DEA für Wörter mit dem Teilwort KE]]
[[Datei:DEA Teilwort KE.png|mini|DEA für Wörter mit dem Teilwort KE]]
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! Zustand !! K !! E
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
|-
| <math>\rightarrow q_0</math> || <math>q_1</math> || <math>q_0</math>
|-
| <math>q_1</math> || <math>q_1</math> || <math>q_2</math>
|-
| <math>{}^*q_2</math> || <math>q_2</math> || <math>q_2</math>
|}
 
Jedes Zeichen hat in jedem Zustand einen Folgezustand. Der DEA ist vollständig, ein Fehlerzustand ist nicht nötig. Die Prüfung mit zwei Wörtern bestätigt den Entwurf: <math>EKKE</math> enthält <math>KE</math> und endet in <math>q_2</math>, <math>EEK</math> enthält <math>KE</math> nicht und endet in <math>q_1</math>.
 
===DEA für Reste entwerfen===
[[Datei:DEA Reste der Einheiten.png|mini|DEA für die Reste 0, 1 und 2]]
Ein Kaffeeautomat spült seine Brühgruppe nach je 3 Einheiten Kaffeesatz. Ein Kaffee <math>K</math> zählt 1 Einheit, ein Espresso <math>E</math> zählt 2 Einheiten. Gesucht ist ein DEA für alle Bestellfolgen, nach denen kein Rest bleibt: Die Summe der Einheiten ist durch 3 teilbar.
 
'''Schritt 1: Gedächtnis festlegen.''' Die Summe selbst kann beliebig groß werden. Für die Teilbarkeit zählt aber nur ihr Rest bei der Division durch 3, und es gibt nur die Reste 0, 1 und 2. Jeder Rest wird ein Zustand: <math>q_0</math> für Rest 0, <math>q_1</math> für Rest 1, <math>q_2</math> für Rest 2.
 
'''Schritt 2: Startzustand wählen.''' Ohne Bestellung ist die Summe 0 mit dem Rest 0. Der Startzustand ist <math>q_0</math>.
 
'''Schritt 3: Übergänge eintragen.''' Ein <math>K</math> erhöht den Rest um 1, ein <math>E</math> erhöht ihn um 2. Ab der Summe 3 beginnt die Zählung wieder beim Rest 0: In <math>q_2</math> führt <math>K</math> nach <math>q_0</math>, denn 2 + 1 = 3 lässt den Rest 0, und <math>E</math> führt nach <math>q_1</math>, denn 2 + 2 = 4 lässt den Rest 1.
 
{| class="wikitable" style="text-align:center"
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
|-
|-
| → q0 || q1 || q0
| <math>\rightarrow {}^*q_0</math> || <math>q_1</math> || <math>q_2</math>
|-
|-
| q1 || q1 || q2
| <math>q_1</math> || <math>q_2</math> || <math>q_0</math>
|-
|-
| * q2 || q2 || q2
| <math>q_2</math> || <math>q_0</math> || <math>q_1</math>
|}
|}


Jedes Zeichen hat in jedem Zustand einen Folgezustand. Der DEA ist vollständig, ein Fehlerzustand ist nicht nötig.
'''Schritt 4: Endzustände festlegen.''' Nur beim Rest 0 ist die Summe durch 3 teilbar, also gilt <math>F = \{q_0\}</math>.
 
'''Schritt 5: Prüfen.''' Für <math>KE</math> mit 1 + 2 = 3 Einheiten ergibt sich <math>q_0 \xrightarrow{K} q_1 \xrightarrow{E} q_0</math>, das Wort wird akzeptiert. Für <math>KEK</math> mit 4 Einheiten ergibt sich <math>q_0 \xrightarrow{K} q_1 \xrightarrow{E} q_0 \xrightarrow{K} q_1</math>, das Wort wird abgelehnt. Das leere Wort bleibt in <math>q_0</math> und wird akzeptiert, denn 0 ist durch 3 teilbar.
 
'''Warum genügen nicht zwei Zustände?''' Die drei Wortanfänge <math>\varepsilon</math>, <math>K</math> und <math>E</math> müssen in drei verschiedenen Zuständen enden:
* <math>\varepsilon</math> gehört zur Sprache, <math>K</math> und <math>E</math> gehören nicht dazu. <math>\varepsilon</math> braucht deshalb einen anderen Zustand als die beiden anderen.
* Hängt man an <math>K</math> und an <math>E</math> jeweils die Fortsetzung <math>K</math> an, entsteht <math>KK</math> mit 2 Einheiten und <math>EK</math> mit 3 Einheiten. Nur <math>EK</math> gehört zur Sprache. Also brauchen auch <math>K</math> und <math>E</math> verschiedene Zustände.
 
Ein vollständiger DEA für diese Sprache hat deshalb mindestens drei Zustände.


===DEA minimieren===
===DEA minimieren===
[[Datei:DEA vor der Minimierung.png|mini|DEA vor der Minimierung]]
[[Datei:DEA vor der Minimierung.png|mini|DEA vor der Minimierung]]
Der DEA vor der Minimierung hat fünf Zustände. Er akzeptiert alle Wörter gerader Länge mit mindestens 2 Zeichen.
Der DEA vor der Minimierung hat fünf Zustände. Er akzeptiert alle nicht leeren Wörter über <math>\Sigma = \{K; E\}</math>, in denen die Anzahl der <math>K</math> gerade ist. Dabei merkt er sich mehr als nötig: Die Zustände in der linken Spalte des Bildes stehen für eine ungerade, die in der rechten Spalte für eine gerade Anzahl <math>K</math>. Zusätzlich unterscheidet er, ob die Anzahl der <math>E</math> gerade (obere Zeile) oder ungerade ist (untere Zeile). Der Startzustand <math>q_0</math> in der Mitte steht für das leere Wort.


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! Zustand !! K !! E
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
|-
|-
| → q0 || q1 || q2
| <math>\rightarrow q_0</math> || <math>q_1</math> || <math>q_4</math>
|-
|-
| q1 || q3 || q4
| <math>q_1</math> || <math>q_3</math> || <math>q_2</math>
|-
|-
| q2 || q4 || q3
| <math>q_2</math> || <math>q_4</math> || <math>q_1</math>
|-
|-
| * q3 || q1 || q2
| <math>{}^*q_3</math> || <math>q_1</math> || <math>q_4</math>
|-
|-
| * q4 || q2 || q1
| <math>{}^*q_4</math> || <math>q_2</math> || <math>q_3</math>
|}
|}


'''Schritt 1: Nicht erreichbare Zustände entfernen.''' Von q0 aus sind alle fünf Zustände erreichbar. Es entfällt keiner.
'''Schritt 1: Nicht erreichbare Zustände entfernen.''' Vom Startzustand <math>q_0</math> führen die Zeichen nach <math>q_1</math> und <math>q_4</math>, von dort führen sie nach <math>q_3</math> und <math>q_2</math>. Alle fünf Zustände sind erreichbar, es entfällt keiner.


'''Schritt 2: Endzustand und Nicht-Endzustand markieren.''' Die Endzustände sind q3 und q4. Markiert werden die Paare (q0,q3), (q0,q4), (q1,q3), (q1,q4), (q2,q3) und (q2,q4), weil bei jedem dieser Paare genau ein Partner ein Endzustand ist.
'''Schritt 2: Runde 0.''' Die Endzustände sind <math>q_3</math> und <math>q_4</math>. Markiert werden die Paare <math>(q_0; q_3)</math>, <math>(q_0; q_4)</math>, <math>(q_1; q_3)</math>, <math>(q_1; q_4)</math>, <math>(q_2; q_3)</math> und <math>(q_2; q_4)</math>, weil bei jedem dieser Paare genau ein Partner ein Endzustand ist.


'''Schritt 3: Folgepaare prüfen.''' Noch unmarkiert sind (q0,q1), (q0,q2), (q1,q2) und (q3,q4).
'''Schritt 3: Runde 1.''' Noch unmarkiert sind vier Paare. Für jedes wird geprüft, auf welche Folgepaare die Zeichen führen. Beim Paar <math>(q_0; q_1)</math> zum Beispiel führt <math>K</math> von <math>q_0</math> nach <math>q_1</math> und von <math>q_1</math> nach <math>q_3</math>. Das Folgepaar ist also <math>(q_1; q_3)</math>.
* (q0,q1) wird markiert: Bei K entsteht das Paar (q1,q3), und dieses ist markiert.
* <math>(q_0; q_1)</math> wird markiert: Bei <math>K</math> entsteht das Folgepaar <math>(q_1; q_3)</math>, und dieses ist seit Runde 0 markiert.
* (q0,q2) wird markiert: Bei K entsteht das Paar (q1,q4), und dieses ist markiert.
* <math>(q_0; q_2)</math> wird markiert: Bei <math>K</math> entsteht das Folgepaar <math>(q_1; q_4)</math>, und dieses ist seit Runde 0 markiert.
* (q1,q2) bleibt unmarkiert: Bei K entsteht (q3,q4), bei E entsteht (q4,q3). Das ist dasselbe Paar, und es ist nicht markiert.
* <math>(q_1; q_2)</math> bleibt unmarkiert: Bei <math>K</math> entsteht <math>(q_3; q_4)</math>, bei <math>E</math> entsteht <math>(q_1; q_2)</math>. Keines dieser Folgepaare ist markiert.
* (q3,q4) bleibt unmarkiert: Bei K entsteht (q1,q2), bei E entsteht (q2,q1). Das ist dasselbe Paar, und es ist nicht markiert.
* <math>(q_3; q_4)</math> bleibt unmarkiert: Bei <math>K</math> entsteht <math>(q_1; q_2)</math>, bei <math>E</math> entsteht <math>(q_3; q_4)</math>. Keines dieser Folgepaare ist markiert.


Eine weitere Runde markiert nichts Neues.
Runde 2 markiert kein weiteres Paar, das Verfahren endet. Die Dreieckstabelle fasst das Ergebnis zusammen. Die Zahl nennt die Runde, in der das Paar markiert wurde, ein Strich steht für ein unmarkiertes Paar:


'''Schritt 4: Unmarkierte Paare zusammenlegen.''' Aus (q1,q2) und (q3,q4) entstehen die Zustände {q1,q2} und {q3,q4}. q0 bleibt allein.
{| class="wikitable" style="text-align:center"
!  !! <math>q_0</math> !! <math>q_1</math> !! <math>q_2</math> !! <math>q_3</math>
|-
| <math>q_1</math> || 1 ||  ||  ||
|-
| <math>q_2</math> || 1 || – ||  ||
|-
| <math>q_3</math> || 0 || 0 || 0 ||
|-
| <math>q_4</math> || 0 || 0 || 0 || –
|}
 
'''Schritt 4: Unmarkierte Paare zusammenlegen.''' Aus <math>(q_1; q_2)</math> und <math>(q_3; q_4)</math> entstehen die Zustände <math>\{q_1; q_2\}</math> und <math>\{q_3; q_4\}</math>. <math>q_0</math> bleibt allein. Die Übergänge der neuen Zustände werden an einem Zustand der Gruppe abgelesen: <math>q_1</math> führt mit <math>K</math> nach <math>q_3</math>, und dieser Zustand gehört zur Gruppe <math>\{q_3; q_4\}</math>. Also führt <math>\{q_1; q_2\}</math> mit <math>K</math> nach <math>\{q_3; q_4\}</math>. Mit <math>q_2</math> ergibt sich dasselbe, denn <math>q_2</math> führt mit <math>K</math> nach <math>q_4</math>.


[[Datei:DEA nach der Minimierung.png|mini|DEA nach der Minimierung]]
[[Datei:DEA nach der Minimierung.png|mini|DEA nach der Minimierung]]
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! Zustand !! K !! E
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
|-
|-
| → q0 || {q1,q2} || {q1,q2}
| <math>\rightarrow q_0</math> || <math>\{q_1; q_2\}</math> || <math>\{q_3; q_4\}</math>
|-
|-
| {q1,q2} || {q3,q4} || {q3,q4}
| <math>\{q_1; q_2\}</math> || <math>\{q_3; q_4\}</math> || <math>\{q_1; q_2\}</math>
|-
|-
| * {q3,q4} || {q1,q2} || {q1,q2}
| <math>{}^*\{q_3; q_4\}</math> || <math>\{q_1; q_2\}</math> || <math>\{q_3; q_4\}</math>
|}
|}


Der minimale DEA hat drei Zustände. Nach dem ersten Zeichen steht er in {q1,q2}, danach wechselt er mit jedem Zeichen zwischen {q1,q2} und {q3,q4}. In {q3,q4} ist die Länge gerade und mindestens 2.
Der minimale DEA hat drei Zustände. In <math>\{q_1; q_2\}</math> ist die Anzahl der gelesenen <math>K</math> ungerade, in <math>\{q_3; q_4\}</math> ist sie gerade. Jedes <math>K</math> wechselt zwischen diesen beiden Zuständen, ein <math>E</math> ändert dort nichts mehr: Die Anzahl der <math>E</math> merkt sich der minimale DEA nicht. Der Startzustand <math>q_0</math> bleibt für sich, weil das leere Wort nicht akzeptiert wird.


===Produktautomat bilden===
===Produktautomat bilden===
Gegeben sind zwei DEA über <math>\Sigma = \{K, E\}</math>:
Gegeben sind zwei DEA über <math>\Sigma = \{K; E\}</math>. Ihre Zustände heißen hier <math>a</math> und <math>b</math> sowie <math>c</math> und <math>d</math>, damit sich die Zustände des Produktautomaten kurz schreiben lassen:
* DEA 1 „mindestens ein K“ hat die Zustände a und b. a bedeutet, dass noch kein K gelesen wurde, und ist der Startzustand. b bedeutet, dass ein K gelesen wurde, und ist der Endzustand. Bei K wechselt der Automat von a nach b und bleibt dann in b. E ändert nichts.
* DEA 1 „mindestens ein <math>K</math>“ hat die Zustände <math>a</math> und <math>b</math>. <math>a</math> bedeutet, dass noch kein <math>K</math> gelesen wurde, und ist der Startzustand. <math>b</math> bedeutet, dass mindestens ein <math>K</math> gelesen wurde, und ist der Endzustand. Bei <math>K</math> wechselt der Automat von <math>a</math> nach <math>b</math> und bleibt dann in <math>b</math>. <math>E</math> ändert nichts.
* DEA 2 „gerade Anzahl E“ hat die Zustände c und d. c bedeutet gerade Anzahl, ist Startzustand und Endzustand. d bedeutet ungerade Anzahl. Bei E wechselt der Automat zwischen c und d. K ändert nichts.
* DEA 2 „gerade Anzahl <math>E</math>“ hat die Zustände <math>c</math> und <math>d</math>. <math>c</math> bedeutet gerade Anzahl, ist Startzustand und Endzustand. <math>d</math> bedeutet ungerade Anzahl. Bei <math>E</math> wechselt der Automat zwischen <math>c</math> und <math>d</math>. <math>K</math> ändert nichts.
 
{| class="wikitable" style="text-align:center"
|+ style="white-space:nowrap" | DEA 1: mindestens ein <math>K</math>
! <math>\delta_1</math> !! <math>K</math> !! <math>E</math>
|-
| <math>\rightarrow a</math> || <math>b</math> || <math>a</math>
|-
| <math>{}^*b</math> || <math>b</math> || <math>b</math>
|}


Der Produktautomat soll nur Wörter akzeptieren, die beide Bedingungen erfüllen. Seine Zustände sind die Paare ac, ad, bc und bd, geschrieben ohne Klammern. Der Start ist ac, weil beide Automaten in ihrem Startzustand beginnen. Als Endzustand zählt nur bc, denn nur dort sind beide Komponenten Endzustände: <math>F = F_1 \times F_2 = \{bc\}</math>.
{| class="wikitable" style="text-align:center"
|+ style="white-space:nowrap" | DEA 2: gerade Anzahl <math>E</math>
! <math>\delta_2</math> !! <math>K</math> !! <math>E</math>
|-
| <math>\rightarrow {}^*c</math> || <math>c</math> || <math>d</math>
|-
| <math>d</math> || <math>d</math> || <math>c</math>
|}
 
Der Produktautomat soll nur Wörter akzeptieren, die beide Bedingungen erfüllen. Seine Zustände sind die Paare <math>ac</math>, <math>ad</math>, <math>bc</math> und <math>bd</math>, kurz ohne Klammern und Semikolon geschrieben. Der Start ist <math>ac</math>, weil beide Automaten in ihrem Startzustand beginnen. Als Endzustand zählt nur <math>bc</math>, denn nur dort sind beide Komponenten Endzustände: <math>F = F_1 \times F_2 = \{bc\}</math>.
 
Jeder Übergang wird komponentenweise berechnet: Der erste Buchstabe des Paares folgt DEA 1, der zweite DEA 2. Die Tabelle leitet alle acht Übergänge her:
 
{| class="wikitable" style="text-align:center"
! Zustand !! Zeichen !! DEA 1 !! DEA 2 !! Folgezustand
|-
| <math>ac</math> || <math>K</math> || <math>a \xrightarrow{K} b</math> || <math>c \xrightarrow{K} c</math> || <math>bc</math>
|-
| <math>ac</math> || <math>E</math> || <math>a \xrightarrow{E} a</math> || <math>c \xrightarrow{E} d</math> || <math>ad</math>
|-
| <math>ad</math> || <math>K</math> || <math>a \xrightarrow{K} b</math> || <math>d \xrightarrow{K} d</math> || <math>bd</math>
|-
| <math>ad</math> || <math>E</math> || <math>a \xrightarrow{E} a</math> || <math>d \xrightarrow{E} c</math> || <math>ac</math>
|-
| <math>bc</math> || <math>K</math> || <math>b \xrightarrow{K} b</math> || <math>c \xrightarrow{K} c</math> || <math>bc</math>
|-
| <math>bc</math> || <math>E</math> || <math>b \xrightarrow{E} b</math> || <math>c \xrightarrow{E} d</math> || <math>bd</math>
|-
| <math>bd</math> || <math>K</math> || <math>b \xrightarrow{K} b</math> || <math>d \xrightarrow{K} d</math> || <math>bd</math>
|-
| <math>bd</math> || <math>E</math> || <math>b \xrightarrow{E} b</math> || <math>d \xrightarrow{E} c</math> || <math>bc</math>
|}
 
Daraus entsteht die Übergangstabelle des Produktautomaten:


[[Datei:DEA Produktautomat.png|mini|Produktautomat aus „mindestens ein K“ und „gerade Anzahl E“]]
[[Datei:DEA Produktautomat.png|mini|Produktautomat aus „mindestens ein K“ und „gerade Anzahl E“]]
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! Zustand !! K !! E
! <math>\delta</math> !! <math>K</math> !! <math>E</math>
|-
|-
| → ac || bc || ad
| <math>\rightarrow ac</math> || <math>bc</math> || <math>ad</math>
|-
|-
| ad || bd || ac
| <math>ad</math> || <math>bd</math> || <math>ac</math>
|-
|-
| * bc || bc || bd
| <math>{}^*bc</math> || <math>bc</math> || <math>bd</math>
|-
|-
| bd || bd || bc
| <math>bd</math> || <math>bd</math> || <math>bc</math>
|}
|}


Jeder Übergang wird komponentenweise berechnet. Beispiel: Im Zustand ac führt K nach bc, weil a mit K nach b geht und c mit K in c bleibt. E führt nach ad, weil a bei E in a bleibt und c bei E nach d wechselt.
Der Produktautomat akzeptiert die Wörter, die mindestens ein <math>K</math> enthalten und eine gerade Anzahl <math>E</math> haben. Sollen stattdessen die Wörter akzeptiert werden, die mindestens eine der beiden Bedingungen erfüllen, bleiben Zustände und Übergänge gleich. Nur die Endzustände ändern sich: Endzustand ist dann jedes Paar mit <math>b</math> an erster oder <math>c</math> an zweiter Stelle, also <math>F = \{ac; bc; bd\}</math>.
 
Der Produktautomat akzeptiert die Wörter, die mindestens ein K enthalten und eine gerade Anzahl E haben.


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