Binärautomat I

(A1)

Gegeben ist der folgende endliche Automat. Sein Startzustand ist S0

(i) Gib eine Beschreibung des Automaten als Menge M = {Z, E, δ, Q, {P}} an 1) Z: Zustandsmenge, E: Eingabemenge, δ: Übergangsfunktion, Q: Startzustand, {P}: Endzustandsmenge Notiere δ als 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.

Lösungen