Aufgabe 1
Entwerfen Sie jeweils einen Akzeptor mit dem Eingabealphabet X= {a,b}, der jeweils die Worte der gegebenen Sprache L(A) erkennt.
- L(A) = \{ \} … leere Menge
- L(A) = \{ \epsilon \} … die Menge, die nur das leere Wort enthält
- L(A) = \{ abba \} … die Menge, die genau das Wort abba enthält
- L(A) = \{ a^{n} \mid n \in \mathbb{N} \} … die Menge, die alle nur aus a bestehenden Worte enthält
- L(A) = \{ w \mid w \in X^{*}, \text{w enthält eine gerade Anzahl von a} \}
- L(A) = \{ X^{*} \setminus \{abba\} \} … die Menge, die alle möglichen Worte außer dem Wort abba enthält
- L(A) = \{ a^{n}b^{2} \mid n > 0 \} und L(A) = \{ a^{n}b^{2} \mid n \ge 0 \}
- L(A) = \{ (ab)^{n} \mid n > 0 \}
Aufgabe 2
Gesucht ist ein Automat, der Dualzahlen erkennt, die
- eine ungerade Anzahl von Einsen enthalten,
- der nur die Folgen 0001, 00010001, 000100010001, … erkennt,
- mindestens zwei aufeinander folgende Einsen oder zwei aufeinander folgende Nullen enthalten,
- durch 2 (4, 8, …) teilbar sind,
- an vorletzter Stelle eine Null haben.
Aufgabe 3
Geben Sie den Übergangsgraphen eines Automaten an, der die folgende Pascal-ähnliche Deklaration für ein Feld erkennt.
Aufgabe 4
Gegenstand dieser Aufgabe soll das Spielzeug aus einer schon bekannten Aufgabe sein.
Gesucht ist ein Akzeptor, der über dem Eingabealphabet X = \{a, b\} genau die Worte (Eingabesequenzen) akzeptiert, bei denen die zuletzt eingeworfene Kugel bei D herausfällt. Der dargestellte Zustand gilt als Anfangszustand für den Automaten.
