Neben den hier vorgestellten Aufgaben bietet der Exorciser die Möglichkeit sich in der Erstellung von Automaten zu üben.
Neben den hier vorgestellten Aufgaben bietet der Exorciser die Möglichkeit sich in der Erstellung von Automaten zu üben.
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$)
Beispieleingaben | |
1000111110110 | wird akzeptiert |
1011101000111 | wird nicht akzeptiert |
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 |
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 |
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 |
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) |
Definiere zunächst ein entsprechendes Eingabealphabet für diesen Automaten. Prüfe auch welche einstelligen Zahlwörter das Teilbarkeitskriterium erfüllen.
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:
Spielausgänge werden wie folgt modelliert:
u = unentschieden, g = gewonnen, v = verloren
.
Konstruiere je einen DEA für die folgenden Sprachen:
Zweite Teilaufgabe Lösungsvorschlag (FLACI)
Dritte Teilaufgabe Lösungsvorschlag (FLACI)
Überführen Sie diesen Automaten in einen regulären Ausdruck.
$\varepsilon | (\varepsilon | a)(\varepsilon |b)a$
$(bb)^*a^*$
$b^*a^*a$
$((bba)*a*)*$
$(ab)^*(b|a^*)$
$\varepsilon |(aa)^*b^*a$