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 | 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 | 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> | * <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. | ||
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 | <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 | * 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 | 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 | 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>. | ||
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== | ||
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. | |||
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 | 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 | Ä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. | ||
# | # 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. | 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 | :<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: | 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 | Der DEA <math>A = (Q; \Sigma; \delta; q_0; F)</math> hat diese Bestandteile: | ||
* <math>Q = \{ | * <math>Q = \{q_0; q_1; q_2; q_3; q_4; q_F\}</math> | ||
* <math>\Sigma = \{K | * <math>\Sigma = \{K; E\}</math> | ||
* <math>\delta</math> laut Übergangstabelle | * <math>\delta</math> laut Übergangstabelle | ||
* Startzustand | * Startzustand <math>q_0</math> | ||
* <math>F = \{ | * <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" | ||
! | ! <math>\delta</math> !! <math>K</math> !! <math>E</math> | ||
|- | |- | ||
| | | <math>\rightarrow q_0</math> || <math>q_1</math> || <math>q_2</math> | ||
|- | |- | ||
| | | <math>q_1</math> || <math>q_2</math> || <math>q_3</math> | ||
|- | |- | ||
| | | <math>q_2</math> || <math>q_3</math> || <math>q_4</math> | ||
|- | |- | ||
| | | <math>q_3</math> || <math>q_4</math> || <math>q_F</math> | ||
|- | |- | ||
| * | | <math>{}^*q_4</math> || <math>q_F</math> || <math>q_F</math> | ||
|- | |- | ||
| | | <math>q_F</math> || <math>q_F</math> || <math>q_F</math> | ||
|} | |} | ||
Beispiel für das Lesen der Tabelle: Im Zustand | 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 | 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> || – || – | |||
|} | |||
Zur Kontrolle: Die Tabelle hat zehn Zellen. Sieben sind gefüllt, so viele Pfeile hat der Graph. Drei enthalten einen Strich. | |||
Der | ===Unvollständigen DEA vervollständigen=== | ||
Der Entwurf aus dem vorigen Beispiel zeigt den Kaffeeautomaten ohne Fehlerzustand. In seiner Übergangstabelle enthalten drei Zellen einen Strich. | |||
''' | '''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 | '''Schritt 2: Fehlerzustand ergänzen.''' Der neue Zustand <math>q_F</math> kommt hinzu. Er ist kein Endzustand. | ||
''' | '''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 | '''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 | 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. | ||
* | * <math>q_0</math>: Es ist noch kein Anfang von <math>KE</math> gelesen. | ||
* | * <math>q_1</math>: Das letzte Zeichen war <math>K</math>. Kommt jetzt ein <math>E</math>, ist <math>KE</math> gefunden. | ||
* | * <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 | * 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 | * 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 | * 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> | |||
|- | |- | ||
| | | <math>\rightarrow {}^*q_0</math> || <math>q_1</math> || <math>q_2</math> | ||
|- | |- | ||
| | | <math>q_1</math> || <math>q_2</math> || <math>q_0</math> | ||
|- | |- | ||
| | | <math>q_2</math> || <math>q_0</math> || <math>q_1</math> | ||
|} | |} | ||
'''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 | 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" | ||
! | ! <math>\delta</math> !! <math>K</math> !! <math>E</math> | ||
|- | |- | ||
| | | <math>\rightarrow q_0</math> || <math>q_1</math> || <math>q_4</math> | ||
|- | |- | ||
| | | <math>q_1</math> || <math>q_3</math> || <math>q_2</math> | ||
|- | |- | ||
| | | <math>q_2</math> || <math>q_4</math> || <math>q_1</math> | ||
|- | |- | ||
| * | | <math>{}^*q_3</math> || <math>q_1</math> || <math>q_4</math> | ||
|- | |- | ||
| * | | <math>{}^*q_4</math> || <math>q_2</math> || <math>q_3</math> | ||
|} | |} | ||
'''Schritt 1: Nicht erreichbare Zustände entfernen.''' | '''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: | '''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: | '''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>. | ||
* ( | * <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. | ||
* ( | * <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. | ||
* ( | * <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. | ||
* ( | * <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. | ||
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 ( | {| 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" | ||
! | ! <math>\delta</math> !! <math>K</math> !! <math>E</math> | ||
|- | |- | ||
| | | <math>\rightarrow q_0</math> || <math>\{q_1; q_2\}</math> || <math>\{q_3; q_4\}</math> | ||
|- | |- | ||
| { | | <math>\{q_1; q_2\}</math> || <math>\{q_3; q_4\}</math> || <math>\{q_1; q_2\}</math> | ||
|- | |- | ||
| * { | | <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. | 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 | 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 | * 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 | * 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, | {| 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" | ||
! | ! <math>\delta</math> !! <math>K</math> !! <math>E</math> | ||
|- | |- | ||
| | | <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> | ||
|} | |} | ||
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]] | ||