Deterministische endliche Automaten

DEA ist die deutsche Abkürzung für Deterministischer Endlicher Automat. Im Englische lautet die Abkürzung DFA fürDeterministic Final Automaton. Auch in deutschsprachiger Fachliteratur wird oft das Akronym DFA genutzt.

Ein DEA ist ein 5-Tupel DEA = { Q, Σ, δ, E, s} er besteht also aus den folgenden 5 Teilen:

• Q Menge aller Zustände (oft auch Z oder S (engl. state))
• Σ Alphabet / Menge der Alphabetzeichen (Sigma)
• δ Übergangsfunktion (Delta)
• E Menge der akzeptierenden Endzustände,
• s Startzustand.

Den Übergang von einem Zustand zum nächsten bezeichnet man auch als Transition oder Zustandsübergang.

Ein DEA wir häufig durch seinen Übergangsgraphen dargestellt. Gelegentlich wird auch der Begriff Zustandsübergangsdiagramm verwendet.

Im Übergangsgraphen sind viele Informationen enthalten:

• Q={q0,q1,q2,q3}
• Σ={a,b}
• δ wird dargestellt durch die Pfeile, die von einem Zustand zum nächsten führen.
• E={q3}
• s=q0

Die Übergangsfunktion δ kann auch als Übergangsmatrix oder Übergangstabelle dargestellt werden. Dabei werden in der ersten Spalte alle Zustände eingetragen und in der ersten Zeile alle Zeichen des Eingabealphabets Σ eingetragen.

In den Tabellenzellen wird vermerkt, zu welchem Zustand der Automat wechselt, wenn er zuvor im Zustand der ersten Spalte war und dann die Eingabe der ersten Zeile erfolgt. Die Übergangstabelle für das obige Beispiel sieht also so aus:

Das bedeutet im Beispiel: Wenn der Automat sich im Zustand q1 befindet, und es erfolgt die Eingabe a, wechselt er zum Zustand q3.

Nun fällt auf, dass die Tabelle unvollständig ist: Wenn der Automat sich im Zustand q1 befindet, und die Eingabe b erfolgt, ist kein Ziel angegeben, denn der Automat akzeptiert an dieser Stelle die Eingabe b überhaupt nicht. Das liegt daran, dass im Übergangsdiagramm der Fehlerzustand der Übersichtlichkeit halber weggelassen wurde. Das vollständige Diagramm sieht so aus:

Die vollständige Übergangsmatrix sieht also so aus:

Gegeben ist der folgende DEA: M = ({z0,z1,z2,z3}, {apfel,birne}, δ, {z0}, z3). δ ist in Form einer Übergangstabelle gegeben:

• Welches sind die Zustände des DEA, was der Start, was gültige Endzustände?
• Welche Eingaben akzeptiert der Automat?
• Erstelle ein Zustandsübergangsdiagramm für den DEA

Entwickle einen DEA, der als Eingabemenge Σ={0,1} hat, und alle Eingaben akzeptiert, die auf 10 enden.

• Gib einen Übergangsgraphen an
• Gib eine Darstellung als Übergangsmatrix an

1000111110110 wird akzeptiert
1011101000111 wird nicht akzeptiert

Hilfestellung

Es soll ein Automat entworfen werden, der alle Worte der Form aⁿ (also a, aa, aaa, aaaa, u.s.w.) besteht, wobei n durch 3 oder durch 4 (oder durch beide) teilbar ist.

• Gib einen Übergangsgraphen an
• Gib eine Darstellung als Übergangsmatrix an

aaa      wird akzeptiert
aaaa     wird akzeptiert
aaaaa    wird nicht akzeptiert
aaaaaa   wird akzeptiert

Hilfestellung 1

Hilfestellung 2 - Antwort auf die Frage aus Hilfestellung 1

Hilfestellung 3

Lösung