Aufgaben: Endliche Automaten: Verhalten, Tabelle und Graph

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$.

1. a) Stellen Sie die Übergangstabelle des Automaten auf.

1. b) Zeichnen Sie den zugehörigen Zustandsgraphen oder beschreiben Sie ihn vollständig (Knoten, Pfeile mit Beschriftung, Start- und Endzustand).

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:

1. a) $0110$

1. b) $1000$

1. c) $11$

1. 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$, $B\xrightarrow{b}B$.

1. a) Geben Sie drei Wörter der Länge 3 an, die akzeptiert werden, und ein Wort, das nicht akzeptiert wird.

1. b) Beschreiben Sie die akzeptierte Sprache in Worten.

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.

1. 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.

1. 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.

1. a) Geben Sie den Graphen und die Übergangstabelle an.

1. b) Ändern Sie den Automaten so, dass er genau die Wörter mit einer ungeraden Anzahl von Einsen akzeptiert. Welche Änderung genügt?

1. c) Begründen Sie, warum der Automat mit zwei Zuständen auskommt.

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$

1. a) Zeichnen Sie den Zustandsgraphen.

1. b) Ermitteln Sie die akzeptierte Sprache und beschreiben Sie sie in Worten.

1. c) Geben Sie das kürzeste akzeptierte Wort an.

Ein Automat soll über $\{0,1\}$ genau die Wörter akzeptieren, die auf $01$ enden.

1. 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.

1. b) Zeigen Sie an den Wörtern $1001$, $0110$ und $01$, dass Ihr Automat korrekt arbeitet.

1. 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.

1. a) Entwickeln Sie einen vollständigen deterministischen Automaten (einschließlich eines Fangzustands).

1. b) Beschreiben Sie die Sprache durch eine Aussage über die Buchstabenfolge.

1. c) Begründen Sie, warum ein Fangzustand nötig ist, wenn der Automat vollständig sein soll.

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).

1. a) Begründen Sie, dass beim Einlesen eines Bits $x$ aus dem Rest $r$ der neue Rest $(2r+x) \bmod 3$ entsteht.

1. b) Stellen Sie die Übergangstabelle auf und zeichnen Sie den Graphen.

1. c) Testen Sie die Wörter $110$, $1001$ und $111$.