Top-Themen

Thank you! Your submission has been received!

Oops! Something went wrong while submitting the form.

DEA

Während du dich mit regulären Sprachen auseinandergesetzt hast, hast du sicherlich einmal überprüft, ob ein gegebenes Wort in einer regulären Sprache liegt oder nicht. Deterministische endliche Automaten (kurz DEA) helfen dir dabei, anschaulich zu entscheiden, ob ein Wort zu einer Sprache gehört oder nicht.

Reguläre Ausdrücke können sehr kompliziert werden. Möchtest du anhand ihnen ein Wort hinsichtlich seiner Sprachzugehörigkeit überprüfen, kannst du schnell den Überblick verlieren. Gibt es also einen anschaulichen Standardweg, der die Entscheidungsfindung deutlich vereinfacht? Die Antwort lautet: Ja, und zwar mithilfe von DEAs!

simpleclub zeigt dir, wie du schnell und bildhaft die Sprachzugehörigkeit von Wörtern mithilfe von deterministischen endlichen Automaten (DEA) überprüfen kannst.

DEA einfach erklärt

Der Begriff Automat ist dir sicherlich schon öfter im Alltag begegnet, zum Beispiel in Form von Getränke- oder Geldautomaten. Tatsächlich haben DEAs sehr viel mit ihnen gemeinsam. Sieh dir dazu das folgende Beispiel an.

Stelle dir vor, du kaufst einen Kaffee an einen vereinfachten Automaten. Dazu führst du folgende Schritte aus:

Du wirfst Geld ein.
Du wählst aus, dass du einen Kaffee haben möchtest.
Der Automat bereitet das Getränk zu.
Du entnimmst das Getränk.

Falls du dich nach der Bezahlung doch noch gegen den Kaffee entscheidest, kannst du auch einfach „Abbruch" drücken und der Automat geht wieder zurück in seine Ausgangssituation.

Tippe auf die Münze, um sie einzuwerfen. Klicke anschließend auf eine der beiden Tasten, um dir einen Kaffee zu kaufen oder abzubrechen. Falls du dir einen Kaffee kaufst, kannst du den Becher entnehmen, indem du ihn antippst.

Der Automat ändert nach jeder deiner Eingaben (wie Geldeinwurf oder Drücken der Kaffeetaste), seinen Zustand. Diese Zustandsänderungen heißen Zustandsübergänge. Die Menge aller erlaubten Eingaben wird als das Eingabealphabet des Automaten bezeichnet.

DEA Definition

Ein deterministischer endlicher Automat (kurz DEA) besteht aus Zuständen, Zustandsübergängen und einem Eingabealphabet.

DEAs helfen dir dabei zu entscheiden, ob ein Wort zu einer regulären Sprache gehört oder nicht.

DEA Erklärung

Bestandteile eines DEA

Du hast jetzt bereits alle wesentlichen Elemente eines DEA kennengelernt und es wird Zeit, etwas formaler zu werden.

Um einen DEA zu konstruieren, benötigst du folgende Zutaten:

Zustände Q $Q$ , wobei einzelne Zustände meist mit q $q$ und fortlaufender Nummer bezeichnet werden
Anfangszustand q_0 \in Q $q_0 \in Q$
Endzustände F \subseteq Q $F \subseteq Q$
Eingabealphabet \Sigma $\Sigma$ , welches die Menge aller erlaubten Eingaben (auch Zeichen genannt) ist
Übergangsfunktion \delta: Q \times \Sigma \to Q $\delta: Q \times \Sigma \to Q$ welche die Zustandsübergänge festlegt

Der gesamte Automat wird formal dann als (Q, \Sigma, \delta, q_0, F) $(Q, \Sigma, \delta, q_0, F)$ geschrieben.

Zustände, die weder Anfangs- noch Endzustände sind, werden auch als Zwischenzustände bezeichnet.

Nach den Grundlagen bleibt nun nur noch zu klären, was deterministisch und endlich im Zusammenhang mit Automaten bedeutet.

Ein Automat heißt endlich, wenn er nur endlich viele Zustände besitzt.

Er ist außerdem deterministisch, wenn die Zustandsübergänge eindeutig sind. Das heißt, wenn er durch eine Eingabe von einem Zustand in genau einen anderen Zustand wechseln kann.

Der Kaffeeautomat wäre zum Beispiel nicht deterministisch, wenn er nach dem Drücken der Getränketaste manchmal dein Getränk zubereitet, aber auch manchmal wieder zurück in seine Anfangsposition kehren würde.

Darstellung als Diagramm

Die obige Definition ist sehr mathematisch, jedoch gibt es die Möglichkeit, einen DEA als anschauliches Übergangsdiagramm darzustellen. Die jeweiligen Elemente werden folgendermaßen verbildlicht:

Zustände werden als Kreise gekennzeichnet.
Der Anfangszustand wird mit einem Pfeil und der Beschriftung "Start" markiert.
Der Endzustand wird mit einem Doppelkreis gekennzeichnet.
Zustandsübergänge werden durch Pfeile repräsentiert, die mit dem passenden Zeichen aus dem Eingabealphabet beschriftet werden.

Ein DEA mit vier Zuständen wird als Übergangsdiagramm dargestellt. Der Anfangs- und Endzustand, sowie die Zwischenzustände und Zustandsübergänge sind mit Pfeilen, die auf sie deuten, hervorgehoben und mit ihren Bezeichnungen beschriftet. — Übergangsdiagramm für einen DEA mit erlaubten Zeichen a und b.

Einen deterministischen Automaten erkennst du daran, dass alle Übergangspfeile, die von einem Zustand zu unterschiedlichen Folgezuständen führen, mit unterschiedlichen Zeichen aus dem Eingabealphabet gekennzeichnet werden. Die folgende Situation darf also nicht vorliegen.

Ein nichtdeterministischer Automat mit den erlaubten Zeichen a und b wird als Übergangsdiagramm dargestellt. Vom Startzustand aus sind zwei Zustandsübergänge eingezeichnet, welche beide mit dem Zeichen a versehen sind. — Übergangsdiagramm für einen nichtdeterministischen Automaten.

Die Darstellung eines DEAs als Übergangdiagramm ist die häufigste Darstellungsform.

Karteikarten zu diesem Thema?

Mit der Karteikartenfunktion kannst du deine Vokabeln, Definitionen oder andere Themen, die du auswendig lernen musst, einfach einscannen.

Karteikarten zu diesem Thema erstellen?

Darstellung als Tabelle

DEAs können alternativ auch als Tabellen dargestellt werden. In die Spalten schreibst du die Zeichen des Eingabealphabets, in die Zeilen hingegen die Zustände. Der Anfangszustand wird zusätzlich mit einem kleinen Pfeil gekennzeichnet, die Endzustände mit einem zusätzlichen Sternchen. In die Einträge der Tabelle fügst du nun den Zustand ein, in den der Automat wechselt, wenn er sich in dem Zustand der Zeile befindet und das Zeichen der Spalte einliest.

Die folgende Tabelle zeigt denselben DEA, den du weiter oben als beschriftetes Übergangsdiagramm findest.

\downarrow $\downarrow$ Zustände / Zeichen \to $\to$	a	b
\to q_0 $\to q_0$	q_1 $q_1$	q_0 $q_0$
q_1 $q_1$	q_1 $q_1$	q_2 $q_2$
q_2 $q_2$	q_3 $q_3$	q_0 $q_0$
q_3* $q_3*$	q_1 $q_1$	q_2 $q_2$

Auch hier kannst du schnell erkennen, ob ein Automat deterministisch ist oder nicht. In der Tabelle eines deterministischen Automaten trägst du nur einen Folgezustand ein.

DEA Beispiele

Sprachzugehörigkeit von Wörtern prüfen

Jetzt wird es Zeit zu klären, wie ein DEA dir dabei helfen kann, zu entscheiden, ob ein Wort zu einer gegebenen regulären Sprache gehört oder nicht.

Dazu wird für eine reguläre Sprache, die zum Beispiel durch einen regulären Audruck gegeben ist, ein DEA konstruiert, der genau alle Wörter der Sprache akzeptiert. Dies bedeutet, dass sich der Automat nach Eingabe eines Wortes der Sprache in einem Endzustand befindet. Endet der Automat in einem anderen Zustand, so liegt das Wort nicht in der Sprache.

Um ein Wort zu überprüfen, wird es zeichenweise von links nach rechts eingelesen. Pro Zeichen wechselt der Automat entsprechend der Übergangsfunktion in einen anderen Zustand. Gestartet wird im Anfangszustand. Sieh dir dazu das Beispiel des folgenden DEA an, welcher die Wöter der regulären Sprache (a | b)^*aba $(a | b)^*aba$ akzeptiert.

Lies das Wort „baaba" zeichenweise ein.

Verschiebe den Regler.

Versuche es jetzt selbst! Lese das Wort „bbabab" ein, indem du die Zustände in der Reihenfolge antippst, in der sie der Automat durchlaufen würde. Hast du ein Zeichen korrekt eingelesen, wird es grün markiert und du kannst dich dem nächsten Zeichen widmen.

Tippe die Zustände in der korrekten Reihenfolge an.

Mehrere Endzustände

Es ist möglich, dass Automaten mehrere Endzustände haben, zum Beispiel weil ihr Übergangsdiagramm damit einfacher zu zeichnen ist. Unterschiedliche Endzustände sind jedoch gleichwertig, das heißt, dass ein Wort vom Automaten akzeptiert wird, egal in welchem Endzustand sich der Automat nach dem Einlesen befindet.

Fangzustände

Fangzustände sind Zustände, aus denen es kein Entkommen mehr gibt. Du kannst sie dir wie Sackgassen vorstellen, die der Automat nicht mehr verlassen kann, egal welches Zeichen er einliest.

Ein DEA mit vier Zuständen und erlaubten Eingabezeichen a und b wird als Übergangsdiagramm dargestellt. Einer der Zustände ist mit "Trap" beschriftet. Befindet sich der Automat in diesem Zustand und liest sowohl a als auch b ein, bleibt er in diesem Zustand. — Der Zustand Trap ist ein Fangzustand, aus dem nicht mehr entkommen werden kann.

DEA Zusammenfassung

Ein deterministischr endlicher Automat (kurz DEA) hilft dir dabei zu entscheiden, ob ein Wort in einer regulären Sprache liegt oder nicht. Zu einem DEA gehören folgende Elemente:

Zustände
Genau ein Anfangszustand
Möglichweise mehrere Endzustände
Eingabealphabet
Zustandsübergänge

Ein Automat wird als endlich bezeichnet, wenn die Anzahl seiner Zustände endlich ist und als deterministisch, wenn alle Zustandsübergänge eindeutig sind.

Es wird zu einer gegebenen regulären Sprache ein passender DEA konstruiert, welcher genau die Wörter der Sprache akzeptiert. Das heißt, dass der DEA nach dem zeichenweise Einlesen der Wörter und gleichzeitigem Zustandswechsel in einem Endzustand endet. Möchetst du ein Wort überprüfen, welches nicht Teil der Sprache ist, endet der Automat nach dem vollständigen Einlesen in einem anderen Zustand als einem Endzustand.

Du kannst DEAs auf zwei Arten anschaulicher darstellen:

Als Übergangsdiagramm (häufigste Darstellungsform)
Als Tabelle

No items found.

simpleclub ist am besten in der App.

Mit unserer App hast du immer und überall Zugriff auf: Lernvideos, Erklärungen mit interaktiven Animationen, Übungsaufgaben, Karteikarten, individuelle Lernpläne uvm.

Web-Version

Top-Themen

Get the best learning hacks!

DEA