1.2 Deterministischer EA (DEA)
Endliche Automaten bieten sich nicht nur zur Modellierung von Zugnetzen an. Beispielsweise können wir auch Lichtschalter oder Getränkeautomaten damit modellieren. Wir führen hier deterministische endliche Automaten ein. Wie wir in weiteren Abschnitten sehen werden, gibt es noch weitere endliche Automaten.
Beispiel Lichtschalter
Bauen wir den endlichen Automaten eines einfachen Lichtschalters gemeinsam auf.
Welche Zustände kann der Automat annehmen?
“Licht an” und “Licht aus”. Stellen wir diese in Kreisen dar.
Mit welchem Zustand soll der Automat starten?
“Licht an”. Markieren wir diesen Zustand mit einem Eingangspfeil.
Welchen Zustand soll der Automat erreichen?
“Licht aus”. Umranden wir den Zielzustand doppelt.
Wie kommuniziere ich mit dem Automaten? Welche Impulse gebe ich ihm? Wie reagiert er darauf?
Einen Impuls geben wir, indem wir auf den Knopf drücken. Zeichnen wir die Übergangspfeile ein und beschriften wir sie entsprechend.
Beobachtungen
Wir können der letzten Grafik entnehmen, dass das Licht aus ist, wenn ich eine ungerade Anzahl mal drücke, ansonsten ist es an. Der endliche Automat merkt sich nicht, wie oft bereits gedrückt wurde oder welchen Zustand er als letztes hatte. Er merkt sich nur seinen aktuellen Zustand und reagiert auf den nächsten Impuls.
Beispiel Getränkeautomat
Widmen wir uns einem etwas komplizierteren Automaten, einem Getränketautomaten. Dieser verkauft nur Wasserflaschen zu einem Preis von je CHF 2.-. Der Automat hat also zu entscheiden, ob bereits genügend Geld für ein Wasser eingeworfen wurde oder nicht. Ich welcher Reihenfolge die Münzen eingeworfen werden, oder dass es möglichst wenig Münzen sind, spielt keine Rolle. Der Automat akzeptiert die Münzen (Eingaben) CHF 0.50, CHF 1.- und CHF 2.- . Die unterschiedlichen Eingaben sorgen für unterschiedliche Impulse. Die Menge von allen möglichen Eingaben heisst Eingabealphabet. Die Impulse werden also vom Eingabealphabet beschrieben. Beim Bedienen eines Getränkeautomaten gibt es mehrere Möglichkeiten, die Münzen einzuwerfen. Eine Möglichkeit ist zuerst 0.50, dann, 1.- und zum Schluss nochmals 0.50 einzuwerfen. Diese Folge von Eingaben wird als “Wort” bezeichnet. Ein Wort besteht also aus Elementen vom Eingabealphabet. Später erfahren wir, weshalb diese Bezeichnungen sinnvoll sind. Die Modellierung des beschriebenen Getränkeautomaten kann folgendermassen aussehen. Es gibt mehrere Varianten.
Nach der Eingabe (des Wortes) 0.50, 1.-, 0.50 landen wir zuerst im Kreis mit 0.50, dann im Kreis mit 1.50 und zuletzt im gewünschten doppelt umrandeten Kreis mit ≥2.- und der Automat entscheidet, dass wir genügend Geld eingeworfen haben.
Wenn wir nur zwei 0.50 CHF eingeben, landen wir nach dem Kreis mit 0.50 im Kreis mit 1.- und landen nie im doppelten Kreis. So wird der Automat entscheiden, dass noch zu wenig Geld vorhanden ist und uns kein Wasser geben.
Das Modell und die grafische Darstellung der endlichen Automaten
Ein endlicher Automat besteht aus Zuständen, einem Eingabealphabet und einer Übergangsfunktion. Die (für Menschen) übersichtlichste Darstellung ist die grafische Darstellung.
Beispiel Getränkeautomat
Die grafische Darstellung des Getränkeautomaten enthält …
- … mehrere Zustände (inklusive einem Startzustand und mindestens einem akzeptierenden Zustand): 0.- (Startzustand) , 0.50, 1.-, 1.50, ≥2.- (akzeptierender Zustand)
- … ein Eingabealphabet (Menge von Impulsen): 0.50, 1.-, 2.-
- … und Übergangsfunktionen. Sie gibt für jeden Zustand an, was bei welchem Impuls zu tun ist.
Z. B. machen das in der Grafik die Pfeile:
Die (abstrahierte) grafische Darstellung des Getränkeautomaten sieht wie folgt aus:
Definition: endlicher Automat (EA)
Nun kommen wir zur mathematischen Seite. Ein (deterministischer) endlicher Automat (EA) ist ein 5-Tupel \(M = (Q, Σ, \delta, q_0, F)\) mit
- der endlichen Menge von Zuständen \(Q = \{q_0, q_1, . . . , q_n\} (\) für ein \( n ∈ ℕ_0)\)
- dem endlichen Eingabealphabet \( Σ = \{a_1, a_2, . . . , a_m\} (\) für ein \( m ∈ ℕ_0) \)
- der Übergangsfunktion \(\delta : Q×Σ → Q\)
- dem Startzustand \(q_0 \in Q\)
- der Menge der akzeptierenden Zustände \( F \subseteq Q \)
Die Übergangsfunktion \(δ : Q×Σ → Q\)
Die Übergangsfunktion kann auf verschiedene Weise dargestellt werden: grafisch mittels Pfeilen, als aufzählende Darstellung oder als Übergangstabelle. Die grafische Variante haben wir bereits gesehen. Die aufzählende Dartstellung sieht für den Getränkeautomaten folgendermassen aus, wobei \(δ(q, a) = p\) bedeutet, dass der EA zu \(p\) wechselt, falls im Zustand \(q\) die Eingabe \(a\) gelesen wird.
\(δ(q_0, a_1) = q_1\),\(δ(q_0, a_2) = q_2\),
\(δ(q_0, a_3) = q_4\),
\(δ(q_1, a_1) = q_2\),
\(δ(q_1, a_2) = q_3\),
\(δ(q_1, a_3) = q_4\),
\(δ(q_2, a_1) = q_3\),
usw.
Da die vollständige aufzählende Darstellung etwas aufwendig zu schreiben und unübersichtlich zu lesen ist, ist die Übergangstabelle eine beliebte Alternative. In der linken Spalte steht der aktuelle Zustand und rechts davon steht in der jeweiligen Zeile der Folgezustand für jede mögliche Eingabe. Überprüfen Sie selbst!
Bedeutung von “deterministisch”
Ein EA ist ein deterministischer endlicher Automat (DEA) wenn die Übergangsfunktion für jeden Zustand und jede Eingabe genau einen Zustand als Folgezustand angibt. In diesem Falle schreibt man für die Übergangsfunktion \(δ : Q×Σ → Q\). Grafisch bedeutet dies, dass von jedem Zustand aus keine zwei unterschiedlichen Pfeile mit dem selben Eingabesymbol existieren. Folgendes kann also nicht Teil eines DEA’s sein.
Ist ein Übergang nicht eindeutig, heisst der EA nichtdeterministischer endlicher Automat (NEA). Die obige Grafik kann Teil eines NEA’s sein. Die Übergangsfunktion eines NEA wird als \(δ : Q×Σ → P(Q)\) beschrieben. Dies bedeutet, dass sie einem Zustand und einer Eingabe nicht nur einen einzelnen Zustand sondern eine Teilmenge aller Zustände zuteilen kann. \(P(Q)\) bezeichnet die Potenzmenge von \(Q\), sprich Menge aller Teilmengen von \(Q\). Mehr dazu sehen wir im nächsten Abschnitt, wo wir alles über NEA’s lernen. Auch erlauben NEAs, dass es keinen Folgezustand geben kann. Wir behandeln zuerst die DEAs, die NEAs betrachten wir später genauer.
Damit Sie sehen und hören können, wie eine Berechnung (das lesen/abarbeiten eines Wortes) funktioniert, schauen Sie den verlinkten Abschnitt in diesem Video. Achtung: In der Literatur ist es üblich, «akzeptierende Zustände» als «Endzustände» zu bezeichnen. Sie können die Begriffe synonym verstehen und verwenden.
Hier haben Sie die Option Ihre Notizen zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung z.B. 1_2_DEA_Notizen.