Endliche Automaten: Verhalten, Tabelle und Graph
Am Eingang eines Fahrradparkhauses in Münster wirfst du Münzen ein, und irgendwann geht die Schranke auf. Das Gerät „merkt“ sich nur, wie viel Geld schon drin ist, nicht die ganze Geschichte der Münzen. Genau das leistet ein endlicher Automat: Er hat endlich viele Zustände und weiß zu jedem Zeitpunkt nur, in welchem Zustand er sich befindet. Wie du so einen Automaten beschreibst, liest und selbst entwirfst, lernst du hier.
Bausteine eines Automaten
Ein deterministischer endlicher Automat (DEA) liest ein Eingabewort von links nach rechts. Bei jedem Zeichen springt er in genau einen Folgezustand. Am Ende des Wortes entscheidet der erreichte Zustand: Endzustand ⇒ Wort wird akzeptiert, sonst verworfen.
Das leere Wort $\varepsilon$ hat die Länge 0. Es wird genau dann akzeptiert, wenn der Startzustand ein Endzustand ist.
Der Zustandsgraph zeichnet das Ganze: Zustände sind Kreise, Übergänge beschriftete Pfeile, der Startzustand hat einen Pfeil „von außen“, Endzustände sind doppelt umrandet.
Dieselbe Information steht in der Übergangstabelle: Zeilen = Zustände, Spalten = Zeichen, Einträge = Folgezustände.
| $\delta$ | a | b |
|---|---|---|
| $\rightarrow q_0$ | $q_1$ | $q_0$ |
| $q_1$ | $q_1$ | $q_2$ |
| $*q_2$ | $q_2$ | $q_2$ |
(Pfeil $\rightarrow$ = Startzustand, Stern $*$ = Endzustand.)
Ein endlicher Automat hat die Zustände $q_0$, $q_1$, $q_2$, das Eingabealphabet $\{a, b\}$, den Startzustand $q_0$ und den einzigen Endzustand $q_2$. Die Übergänge…
Ein endlicher Automat hat die Zustände $q_0$, $q_1$, $q_2$, das Eingabealphabet $\{a, b\}$, den Startzustand $q_0$ und den einzigen Endzustand $q_2$. Die Übergänge lauten:
$\delta(q_0,a)=q_1$, $\delta(q_0,b)=q_0$, $\delta(q_1,a)=q_1$, $\delta(q_1,b)=q_2$, $\delta(q_2,a)=q_2$, $\delta(q_2,b)=q_2$.
- a) Stellen Sie die Übergangstabelle des Automaten auf.
- b) Zeichnen Sie den zugehörigen Zustandsgraphen oder beschreiben Sie ihn vollständig (Knoten, Pfeile mit Beschriftung, Start- und Endzustand).
Verhalten: Wörter verarbeiten
Um zu prüfen, ob ein Wort akzeptiert wird, folgst du den Pfeilen Zeichen für Zeichen und notierst die Zustandsfolge.
Aus den Beispielen kannst du die Sprache ablesen: Der Automat oben erreicht $q_2$ genau dann, wenn irgendwo im Wort ein $a$ gefolgt von einem $b$ direkt nacheinander steht (also das Teilwort $ab$). Danach bleibt er in $q_2$ „hängen“. Die Sprache ist $L=\{w \in \{a,b\}^* \mid w \text{ enthält } ab\}$.
Gegeben ist ein Automat mit den Zuständen $s_0$ (Start), $s_1$ (Endzustand) und dem Alphabet $\{0,1\}$. Es gilt: $\delta(s_0,0)=s_0$, $\delta(s_0,1)=s_1$,…
Gegeben ist ein Automat mit den Zuständen $s_0$ (Start), $s_1$ (Endzustand) und dem Alphabet $\{0,1\}$. Es gilt: $\delta(s_0,0)=s_0$, $\delta(s_0,1)=s_1$, $\delta(s_1,0)=s_1$, $\delta(s_1,1)=s_0$.
Entscheiden Sie jeweils, ob der Automat das Wort akzeptiert, und geben Sie die durchlaufene Zustandsfolge an:
- a) $0110$
- b) $1000$
- c) $11$
- d) $\varepsilon$ (das leere Wort)
Ein Automat für das Alphabet $\{a,b\}$ hat den Startzustand $A$, den Endzustand $B$ und die Übergänge $A\xrightarrow{a}B$, $A\xrightarrow{b}A$, $B\xrightarrow{a}B$,…
Ein Automat für das Alphabet $\{a,b\}$ hat den Startzustand $A$, den Endzustand $B$ und die Übergänge $A\xrightarrow{a}B$, $A\xrightarrow{b}A$, $B\xrightarrow{a}B$, $B\xrightarrow{b}B$.
- a) Geben Sie drei Wörter der Länge 3 an, die akzeptiert werden, und ein Wort, das nicht akzeptiert wird.
- b) Beschreiben Sie die akzeptierte Sprache in Worten.
Die Sprache eines Automaten ermitteln
Gegeben ist eine Tabelle oder ein Graph, gesucht ist die Sprache. Vorgehen:
-
Zeichne den Graphen.
-
Frage bei jedem Zustand: Was hat der Automat bis hier „gemerkt“?
-
Formuliere die Sprache als Aussage über die Buchstabenfolge.
-
Probe: Teste kurze Wörter, vor allem das kürzeste akzeptierte.
Gegeben ist die Übergangstabelle (Start: $z_0$, Endzustand: $z_3$): | | a | b | |---|---|---| | $z_0$ | $z_1$ | $z_0$ | | $z_1$ | $z_1$ | $z_2$ | | $z_2$ | $z_1$ | $z_3$…
Gegeben ist die Übergangstabelle (Start: $z_0$, Endzustand: $z_3$):
| a | b | |
|---|---|---|
| $z_0$ | $z_1$ | $z_0$ |
| $z_1$ | $z_1$ | $z_2$ |
| $z_2$ | $z_1$ | $z_3$ |
| $z_3$ | $z_3$ | $z_3$ |
- a) Zeichnen Sie den Zustandsgraphen.
- b) Ermitteln Sie die akzeptierte Sprache und beschreiben Sie sie in Worten.
- c) Geben Sie das kürzeste akzeptierte Wort an.
Automaten entwickeln
Jetzt rückwärts: Die Sprache ist gegeben, du baust den Automaten. Überlege, was sich der Automat merken muss, und mache daraus die Zustände.
Ein bequemes Prinzip: Endzustände tauschen. Alle Endzustände werden zu Nicht-Endzuständen und umgekehrt. Dann akzeptiert der (vollständige) Automat genau das Gegenteil der Sprache.
Endungen und Teilwörter
Für „Wort endet auf $01$“ merkt sich der Automat den längsten Anfang von $01$, der gerade am Wortende steht: nichts ($s$), „$0$“ ($z_0$) oder „$01$“ ($z_{01}$). Das sind drei Zustände. Bei jedem Zeichen fragst du: Welcher Anfang von $01$ steht jetzt am Ende?
Lies ab: Von $s$ führt $0$ nach $z_0$, $1$ bleibt in $s$ (Schleife). Von $z_0$ führt $0$ in $z_0$ selbst (Schleife, die neue Null ist wieder ein möglicher Anfang) und $1$ nach $z_{01}$. Von $z_{01}$ führt $0$ zurück nach $z_0$ (neue Null am Ende), $1$ zurück nach $s$ (nichts Brauchbares am Ende). Das ist der Kern von Aufgabe DIFICIL-01.
Einen Automaten modifizieren
Soll ein vorhandener Automat eine leicht veränderte Sprache akzeptieren, baust du ihn nicht neu, sondern änderst gezielt etwas: Endzustände tauschen (Komplement), einen Zustand zum Endzustand machen oder einen Zustand ergänzen.
Vollständigkeit und Fangzustand
Ein vollständiger DEA braucht für jedes Zeichen in jedem Zustand einen Pfeil. Wird ein Wort „verdorben“ (z. B. enthält schon das verbotene Teilwort $aa$), geht der Automat in einen Fangzustand (Papierkorb): Er hat keinen Ausweg mehr, alle Pfeile führen zu ihm zurück, und er ist kein Endzustand. So bleibt jedes weitere Zeichen definiert, und das Wort wird nie mehr akzeptiert.
Der Eingang eines Fahrradparkhauses in Münster wird von einem Automaten gesteuert. Es werden nur Münzen zu 1 € (Zeichen $e$) und 2 € (Zeichen $z$) eingeworfen. Das…
Der Eingang eines Fahrradparkhauses in Münster wird von einem Automaten gesteuert. Es werden nur Münzen zu 1 € (Zeichen $e$) und 2 € (Zeichen $z$) eingeworfen. Das Parkhaus öffnet, sobald mindestens 3 € eingeworfen wurden (Endzustand). Weitere Münzen ändern daran nichts.
- a) Entwickeln Sie einen endlichen Automaten (Zustände nach eingeworfenem Betrag: 0 €, 1 €, 2 €, „≥ 3 €“) und geben Sie ihn als Graphen und als Tabelle an.
- b) Prüfen Sie die Wörter $ez$, $ee$, $zz$ und $eee$ mit Ihrem Automaten.
Entwerfen Sie einen deterministischen endlichen Automaten über dem Alphabet $\{0,1\}$, der genau die Wörter akzeptiert, die eine gerade Anzahl von Einsen enthalten. a)…
Entwerfen Sie einen deterministischen endlichen Automaten über dem Alphabet $\{0,1\}$, der genau die Wörter akzeptiert, die eine gerade Anzahl von Einsen enthalten.
- a) Geben Sie den Graphen und die Übergangstabelle an.
- b) Ändern Sie den Automaten so, dass er genau die Wörter mit einer ungeraden Anzahl von Einsen akzeptiert. Welche Änderung genügt?
- c) Begründen Sie, warum der Automat mit zwei Zuständen auskommt.
Ein Automat soll über $\{0,1\}$ genau die Wörter akzeptieren, die auf $01$ enden. a) Entwickeln Sie einen deterministischen Automaten mit möglichst wenigen Zuständen.…
Ein Automat soll über $\{0,1\}$ genau die Wörter akzeptieren, die auf $01$ enden.
- a) Entwickeln Sie einen deterministischen Automaten mit möglichst wenigen Zuständen. Geben Sie Graph und Tabelle an und erläutern Sie die Bedeutung jedes Zustands.
- b) Zeigen Sie an den Wörtern $1001$, $0110$ und $01$, dass Ihr Automat korrekt arbeitet.
- c) Modifizieren Sie den Automaten so, dass er Wörter akzeptiert, die auf $01$ enden oder das leere Wort sind. Begründen Sie Ihre Änderung.
Ein Automat über $\{a,b\}$ soll die Wörter akzeptieren, die weder das Teilwort $aa$ noch das Teilwort $bb$ enthalten. a) Entwickeln Sie einen vollständigen…
Ein Automat über $\{a,b\}$ soll die Wörter akzeptieren, die weder das Teilwort $aa$ noch das Teilwort $bb$ enthalten.
- a) Entwickeln Sie einen vollständigen deterministischen Automaten (einschließlich eines Fangzustands).
- b) Beschreiben Sie die Sprache durch eine Aussage über die Buchstabenfolge.
- c) Begründen Sie, warum ein Fangzustand nötig ist, wenn der Automat vollständig sein soll.
Rechnen im Automaten: Reste
Zustände können auch Zahlenreste sein. Liest man eine Binärzahl mit dem höchstwertigen Bit zuerst, so ergibt das Anhängen eines Bits $x$ aus dem bisherigen Wert $w$ den neuen Wert $2w+x$. Das ist wie beim Dezimalsystem: Aus $12$ wird mit angehängter $5$ die Zahl $125 = 10\cdot 12+5$.
Interessiert nur der Rest $r$ von $w$ bei Division durch $3$, genügt $r$: Es gilt $(2w+x) \bmod 3 = (2r+x)\bmod 3$. Deshalb reichen drei Zustände $0,1,2$.
Ein Automat verarbeitet Binärzahlen, die Bit für Bit mit dem höchstwertigen Bit zuerst eingelesen werden. Er soll genau die Wörter akzeptieren, deren Zahlenwert durch 3…
Ein Automat verarbeitet Binärzahlen, die Bit für Bit mit dem höchstwertigen Bit zuerst eingelesen werden. Er soll genau die Wörter akzeptieren, deren Zahlenwert durch 3 teilbar ist. Die Zustände entsprechen dem Rest bei Division durch 3 (0, 1, 2).
- a) Begründen Sie, dass beim Einlesen eines Bits $x$ aus dem Rest $r$ der neue Rest $(2r+x) \bmod 3$ entsteht.
- b) Stellen Sie die Übergangstabelle auf und zeichnen Sie den Graphen.
- c) Testen Sie die Wörter $110$, $1001$ und $111$.
Auf einen Blick
Zurück zum Anfang: Die Schranke in Münster kennt als Zustände nur den eingeworfenen Betrag (0 €, 1 €, 2 €, ≥ 3 €). Mehr muss sie sich nicht merken, und genau das macht sie zu einem endlichen Automaten.