Deterministische Endliche Automaten – Ein definitive Guide
Was ist ein Deterministischer Endlicher Automat?
Ein Deterministischer Endlicher Automat (DFA) ist ein Modell, welches einfache Berechnungsvorgänge durchführen kann. Dabei kann man sich einen DFA wie eine Maschine vorstellen, die bestimmte Eingaben akzeptiert und diese in einen bestimmten Ausgabestatus überführt. Ein DFA hat dabei immer einen bestimmten Startzustand und einen oder mehrere Endzustände. Wenn der Automat in einem Endzustand ankommt, hat er die Berechnung erfolgreich abgeschlossen. Man kann sich einen DFA auch als eine Art Finite State Machine (FSM) vorstellen.
Wie funktioniert ein Deterministischer Endlicher Automat?
Ein DFA besteht aus einer Menge an Zuständen (States), einer Menge an Eingabesymbolen (Input Symbols) und einer Übergangsfunktion (Transition Function), die einem Zustand ein bestimmtes Eingabesymbol zuordnet. Wenn der Automat ein bestimmtes Eingabesymbol erhält, wird er in den Zustand versetzt, der der Übergangsfunktion zugeordnet ist. Zusätzlich hat der Automat immer einen Startzustand (Start State) und einen oder mehrere Endzustände (Final States). Wenn der Automat in einem Endzustand ankommt, ist die Berechnung erfolgreich abgeschlossen. Ansonsten ist die Berechnung fehlgeschlagen.
Beispiel eines Deterministischen Endlichen Automaten
Betrachten wir folgendes einfaches Beispiel eines DFA, der die Eingabe 0 oder 1 akzeptiert und die Eingabe 2 ablehnt. Der Automat hat drei Zustände: q0, q1 und q2. q0 ist der Startzustand und q2 ist der Endzustand. Wenn der Automat eine 0 oder 1 erhält, bleibt er in seinem aktuellen Zustand, aber wenn er eine 2 erhält, wechselt er in den Zustand q2. Wenn der Automat in den Zustand q2 gelangt, ist die Berechnung erfolgreich abgeschlossen.
Überführungsfunktion (Transition Function)
Die Übergangsfunktion (Transition Function) ist eine Funktion, die jedem Zustand ein bestimmtes Eingabesymbol zuordnet. In unserem obigen Beispiel sieht die Übergangsfunktion wie folgt aus:
Überführungsdiagramm (Transition Diagram)
Ein Übergangsdiagramm ist ein Graph, der die Zustände und Übergänge zwischen diesen Zuständen darstellt. In unserem obigen Beispiel sieht das Übergangsdiagramm wie folgt aus:
5 Aufgaben zum Deterministischen Endlichen Automaten
Bestimmen Sie die Zustände, Eingabesymbole und die Übergangsfunktion für folgenden DFA:
Bestimmen Sie die Zustände, Eingabesymbole und die Übergangsfunktion für folgenden DFA:
Bestimmen Sie die Zustände, Eingabesymbole und die Übergangsfunktion für folgenden DFA:
Bestimmen Sie die Zustände, Eingabesymbole und die Übergangsfunktion für folgenden DFA:
Bestimmen Sie die Zustände, Eingabesymbole und die Übergangsfunktion für folgenden DFA:
Lösungen
Aufgabe 1
Zustände: q0, q1, q2, q3 Eingabesymbole: a, b Übergangsfunktion:
