Übungen Automaten

Atocc und FLACI

Die hier verwendeten Aufgaben sind teilweise der Aufgabensammlung AtoCC entnommen, welche von M.Hielscher und Chr. Wagenknecht 2007 verfasst wurden. Die Aufgaben können mit dem Onlinetool FLACI bearbeitet werden. Dieses erlaubt ohne Anmeldung die Erstellung verschiedener Automaten und ist in der Bedienung sehr übersichtlich.

Exorciser

Neben den hier vorgestellten Aufgaben bietet der Exorciser die Möglichkeit sich in der Erstellung von Automaten zu üben.

Deterministische endliche Automaten

Definition endlicher Deterministischer Automat (DFA/DEA)

Ein DFA ist ein Quintupel: $M = (Q,\Sigma,\delta,q0,E)$, mit

$Q$ … endliche Menge von Zuständen,

$\Sigma$ … Eingabealphabet,

$\delta$ … Überführungsfunktion, $Q \times \Sigma \rightarrow Q$,

$q_0$ … Anfangszustand ($q_0 \in Q$),

$E$ … endliche Menge von Endzuständen ($E \in Q$)

Aufgabe 1 - Einfach

Entwickelt einen deterministischen endlichen Automaten, der die Sprache aller Wörter über $\{0,1\}^*$ beschreibt, welche mit dem Teilwort „10“ enden.

Beispieleingaben
1000111110110	wird akzeptiert
1011101000111	wird nicht akzeptiert

Hinweis

Betrachtet zunächst besondere Wörter wie etwa „0“ oder „“ (leeres Wort) und entscheidet, ob diese Wörter zur beschriebenen Sprache gehören oder nicht.

Lösungsvorschlag

Lösungsvorschlag (FLACI)¹⁾

Aufgabe 2 - leicht

Erstelle einen DFA über dem Alphabet $\{a, b\}$ der die Sprache $L$ erkennt. $L = \{ w | w \text{ beinhaltet höchstens vier 'b's }\}$

Beispieleingaben
baaababbaaaa	wird akzeptiert
bbbbb	wird nicht akzeptiert

Lösungsvorschlag

Lösungsvorschlag (FLACI)

Aufgabe 3 - mittel

Gegeben sei die Sprache $S$, die aus allen Wörtern der Form $a^n$ besteht, wobei $n$ durch $3$ oder durch $4$ (oder durch beide) teilbar ist. Gib einen zugehörigen DEA an.

$\Sigma = {a}$

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

Lösungsvorschlag

Lösungsvorschlag (FLACI)

Aufgabe 4 - mittel

Erstelle einen DFA über dem Alphabet $\{a, b\}$ der die Sprache $L$ erkennt. $L = \{ w | w$ beinhaltet eine ungerade Anzahl 'b's oder $w$ beinhaltet das Teilwort "baa"$\}$

Beispieleingaben
b	wird akzeptiert
ba	wird akzeptiert
baaaa	wird akzeptiert
baabababa	wird akzeptiert
babababa	wird nicht akzeptiert

Lösungsvorschlag

Lösungsvorschlag (FLACI)

Aufgabe 5 - anspruchsvoll

Entwickle einen DFA, der alle Wörter akzeptiert, die eine durch 4 teilbare natürliche Zahl repräsentieren. Dabei gilt, dass alle mehrstelligen Zahlen durch 4 teilbar sind, wenn die durch die letzten beiden Stellen gebildete Zahl durch 4 teilbar ist.

Beispieleingaben
8	wird akzeptiert (8 durch 4 teilbar)
1342340	wird akzeptiert (40 durch 4 teilbar)
234523173	wird nicht akzeptiert (73 nicht durch 4 teilbar)

Hinweis

Definiere zunächst ein entsprechendes Eingabealphabet für diesen Automaten. Prüfe auch welche einstelligen Zahlwörter das Teilbarkeitskriterium erfüllen.

Lösungsvorschlag

Lösungsvorschlag 1 (FLACI)

Lösungsvorschlag 2 (FLACI)

Aufgabe 6 - Das Coaching-System²⁾

Der Vorstand eines Gaming-Teams möchte jeglichen Diskussionen über eine mögliche Entlassung des Coaches nach verlorenen Spielen entgegenwirken. Er hat daher ein Regelwerk aufgestellt, aus dem eindeutig hervorgeht, unter welchen Bedingungen ein Coach entlassen wird. Man ist sich einig, dass jeder der beiden folgenden Umstände zu einer Entlassung des Coaches führt:

Das Team hat dreimal hintereinander verloren.
Das Team hat viermal hintereinander nicht gewonnen.

Spielausgänge werden wie folgt modelliert: u = unentschieden, g = gewonnen, v = verloren.

Gib zu jedem der beiden Fälle eine Ergebnisfolge $x \in \{u, g, v\}^*$ an, die zu einer Trainerentlassung nach 6 Spielen führt.
Entwirf einen DEA über dem Alphabet $\{u, g, v\}$, der genau die Folgen von Spielausgängen akzeptiert, die zu einer Coach-Entlassung nach dem obigen Regelwerk führen.

Lösungsvorschlag