Deterministischer endlicher Automat
Was genau ist nun ein deterministischer endlicher Automat? Genau das erklären wir dir anhand des Prinzips in diesem Beitrag. Mit Hilfe von Aufgaben mit Lösungen zeigen wir dir, wie du mittels Zustandsübergangsdiagramm und Übergangstabelle, die Übergangsfunktion einfach darstellen kannst.
Inhaltsübersicht
Definition – DEA (Informatik)
Deterministische endliche Automaten – kurz DEA (Informatik) oder DFA (Englisch: deterministic finite state machine)– sind endlichen Automaten . Gibt man nun eine Eingabe, wobei nur Zeichen enthalten sein können, die im Eingabealphabet stehen, in den Automaten ein, dann passiert für jede Eingabe ein Zustandsübergang. Hierbei gilt, dass ein determinisitischer endlicher Automat immer eindeutig ist, bei welcher Eingabe welcher Zustandsübergang ausgeführt wird.
Deterministische endliche Automaten – Prinzip
Ein DEA besteht in der Informatik grundlegend aus Zuständen und Zustandsübergängen. Besondere Zustände sind hierbei Start- und Endzustände. Eine ausführlichere Erklärung zu Bauteilen eines Automaten inklusive eines einfachen Beispiels findest du in unserem Video zu endlichen Automaten.
Wichtig hierbei ist, dass bei DEAs die Übergangsrelation eine Funktion ist und somit immer einen eindeutigen Folgezustand liefert. Außerdem hat ein deterministischer endlicher Automat immer nur einen eindeutigen Startzustand.
Die Arbeitsweise eines DEA ist hierbei so simpel wie genial: Nehmen wir an, es liegt ein Eingabewort vor, das nur aus Zeichen des Eingabealphabets besteht. Der Automat startet nun in seinem Startzustand, den wir hier z0 nennen. Nun liest der Automat das erste Zeichen des Wortes ein, wodurch sich der Zustand des Automaten ändert. Dafür brauchen wir die Übergangsfunktion: Der Automat betrachtet den aktuellen Zustand z0 und das eingelesene Zeichen. Er erfährt durch die Übergangsfunktion den neuen Zustand, beziehungsweise den Folgezustand. Dies geschieht so lange, bis das Wort vollständig eingelesen ist. Befindet sich der Automat nun in einem Endzustand, dann wird das Eingabewort akzeptiert. Ist der Automat jedoch in einem normalen Zustand, wird das Wort verworfen.
Deterministischer endlicher Automat – Aufgaben mit Lösungen
Damit du das Alles besser nachvollziehen kannst, zeigen wir dir das Prinzip deterministischer endlicher Automaten anhand von Aufgaben mit Lösungen. Zum Einstieg beginnen wir mit einem einfachen Beispiel aus dem Alltag– dem Snackautomat. Im Anschluss gibt es noch eine weitere Aufgabe mit ausführlicher Erklärung.
Beispiel
Du möchstest dir am Snackautomaten in der Mensa eine Schokoriegel kaufen.
Der Snackautomat kann dabei die Zustände z0 für „Snackautomat bereit für Münzeinwurf“, z1 für „Snackautomat wartet auf Snackauswahl“ und z2 für „Ausgabe Snack“ besitzen.
Die Übergänge können durch
- den Münzeinwurf: δ = (z0, Münze, z1)
- den Kaufabbruch: δ = (z1, Abbruch, z0)
- die Snackauswahl: δ = (z1, Snack, z2)
- und die Snackausgabe: δ = (z2, Ausgabe, z0)
beschrieben werden.
Der Snackautomat lässt sich dann in einem Zustandsübergangsdiagramm graphisch wie folgt darstellen:
Die Übergänge beschreiben also nur die einzelnen Schritte, die der Snackautomat während deines Schokoriegelkaufs durchlaufen muss bis er in seinen Endzustand gelangt, bevor er für den nächsten Einkauf bereit ist und somit im Startzustand auf den nächsten Münzeinwurf warten kann.
Jetzt sollte dir die Grundidee eines DEAs in der Informatik keine Schwierigkeiten mehr bereiten.
Aufgabe mit Lösung – Deterministische endliche Automaten
Doch wie wende ich das nun in einer Prüfungsaufgabe an? Hierfür schauen wir uns ein weiteres Beispiel an, welches den Aufgabenstellungen aus deiner Vorlesung näher kommt.
Deshalb stellen wir uns einen DEA mit den Zuständen Z vor. Das Eingabealphabet E, also die Zeichen, die wir in den Automaten eingeben dürfen, besteht nur aus den Buchstaben „a“ und „b“. Der Startzustand ist mit z0 und der einzige Endzustand mit z2 festgelegt. Außerdem haben wir die Übergangsfunktion δ gegeben. Diese sieht so aus:
δ = {(z0, a, z0), (z0, b, z1), (z1, a, z0), (z1, b, z2), (z2, a, z0), (z2, b, z2)}
Jedes einzelne Element enthält zuerst den Zustand, dann die Eingabe und zum Schluss den Folgezustand, der auf diese Kombination aus Zustand und Eingabe folgt. Schauen wir uns dies am dritten Element der Übergangsfunktion an: Wenn sich der Automat aktuell in Zustand z1 befindet und als Eingabe kommt ein „a“, dann geht der Automat von Zustand z1 in z0 über.
Versuchen wir das doch einfach an einem Anwendungsbeispiel zu verstehen: Wir testen nun, ob unser Automat das Wort „ab“ akzeptiert. Zu Beginn befinden wir uns im Startzustand z0. Das Wort beginnt mit einem „a“ also schauen wir in der Übergangsfunktion was passieren muss, wenn wir uns im Zustand z0 befinden und die Eingabe „a“ eintritt. Wir finden den folgenden Eintrag: z0, a, z0.
Da der Folgezustand mit dem aktuellen Zustand übereinstimmt, müssen wir nichts ändern. Als nächstes folgt ein „b“. Wir suchen hierzu erneut den passenden Eintrag und finden diesen hier: z0, b z1.
Also wechseln wir von z0 zu z1. Eigentlich ganz einfach, oder? Da das Wort hier endet, schauen wir jetzt nur noch, ob das Wort akzeptiert wird. Wir befinden uns in Zustand z1 welcher kein Endzustand ist. Das Wort wird also verworfen.
Zustandsübergangsdiagramm
Ein deterministischer endlicher Automat kann in nur wenigen Schritten als Zustandsübergangsdiagramm dargestellt werden.
Als erstes stellen wir dazu jeden Zustand der Zustandsmenge Z dar. Bereits definiert sind der Start- und der Endzustand, also markieren wir diese. Jetzt müssen wir nur noch die Übergangsfunktion Element für Element einzeichnen: Zuerst kommen alle Übergänge bei Eingabe „a“ hinzu. Jetzt fehlen nur noch die Übergänge bei Eingabe „b“ und wir sind fertig. So einfach kann es gehen!
Übergangstabelle
Eine Übergangstabelle stellt die Übergangsfunktion deutlich übersichtlicher dar. Hierbei steht in der Spalte die jeweilige Eingabe und in der Zeile der aktuelle Zustand. Das daraus resultierende Element ist der Folgezustand. Für unser aktuelles Beispiel sieht das Ganze dann so aus:
Stell dir vor, der Automat ist gerade dabei eine Eingabe zu verwerten und befindet sich aktuell im Zustand z2. Als nächstes Eingabezeichen wird ein „a“ gelesen. Wenn wir jetzt den Folgezustand für z2 finden wollen, müssen wir lediglich in unserer Tabelle die Zeile, in der ganz links unser Zustand z2 steht betrachten. Für die Eingabe „a“ schauen wir in die zweite Spalte und lesen als Folgezustand z0.
Alternativ können wir auch einen Blick auf die Übergangsfunktion von vorhin werfen:
δ = {(z0, a, z0), (z0, b, z1), (z1, a, z0), (z1, b, z2), (z2, a, z0), (z2, b, z2)}
Wir suchen ein Element, das uns für den aktuellen Zustand z2 mit Eingabe „a“ einen Folgezustand liefert. Super, die Übergangsfunktion liefert das gleiche Ergebnis wie die Tabelle.
Sehr gut! Damit hast du alle wichtigen Informationen, die du zu deterministische endliche Automaten wissen musst. Wenn du alle im Video genannten Schemen drauf hast, solltest du keine Probleme mehr mit diesen Automaten bekommen.
Solltest du jedoch noch wissen wollen, wie man einen DEA minimieren kann, also einen Minimalautomat erstellt, schau dir gerne unser Video dazu an.