Dies ist eine alte Version des Dokuments!
Binärautomat I
(A1)
Gegeben ist der folgende endliche Automat. Sein Startzustand ist S_0
(i) Gib eine Beschreibung des Automaten als Menge M = {Z, E, δ, Q, {P}} an 1)
(ii) Notiere die Zustandsübergangstabelle.
(iii) Welche der folgenden Worte werden akzeptiert? Begründe, indem du zu jedem Wort die Reihenfolge der durchlaufenen Zustände notierst.
- 1001001
- 0110110
- 10111
- 11110
(iv) Beschreibe allgemein, welche Worte der Automat akzeptiert und erläutere deine Beschreibung anhand des Automatendiagramms.
(v) Der Automat soll nun nur die Worte akzeptieren, die zusätzlich zu den bisherigen Bedingungen eine gerade Anzahl von Nullen (0) enthalten.
- Akzeptiert würde demnach: 1001, 10101, 10001000001
- Nicht akzeptiert würde 101, 10001, 100, 1001010.
Erweitere den obigen Automaten entsprechend – zwei zusätzliche Zustände sollten ausreichen.
1)
Z: Zustandsmenge, E: Eingabemenge, δ: Übergangsfunktion, Q: Startzustand, {P}: Endzustandsmenge