Formale Beschreibung eines DEA/DFA

Question

Sehr geehrte Community,

Meine Aufgabe ist dies Erstellung einer Beschreibung eines DEA.

M = ( Z, Σ, δ, Z0, E ).

Z = Die Zustände
Σ = Das Alphabet
δ = Überfuhrungsfunktion δ: Z x Σ -> Z, d.h. z.B. (z0, a ) = z2.
Z0 = Startzustand, hier Z0
E = Endzustand, da, wo der Automat endet, terminiert

Nun soll ich die Formale Beschreibung an folgendem Automaten anwenden

T(M) = { b^n | n elementar N, N kongruent 42 mod 1024 }

Σ ist klar, Σ = { b } und der Startzustand sollte Z0 sein, wenn ich mich nicht irre.
Der Endzustand ist bei Z1066 sein?
Bei b ^1066 akzeptiert der Automat dieses Wort, da 1066 / 1024 einen Rest von 42 ergibt.

Wenn ich mich nicht irre. Mein Problem ist, dass ich das Ganze nicht formal beschreiben kann, überhaupt Zeichnen würde recht lange dauern. Das Problem ist die Länge? der Bedingung :)

Daher gibt es einen Trick zur Lösung?

Answer 1

Der Endzustand ist bei Z1066 sein?

Nein. Wie soll sonst das Wort \(b^{42}\) akzeptiert werden? Ich würde \(z_{42}\) als Endzustand setzen und danach in einer Schleife durch \(1023\) weitere Zustände führen. Der letzte Zustand \(z_{(42+1023)}=z_{(1065)}\) führt dann wieder zu \(z_{42}\) der ein akzeptierender Zustand ist. Daraus folgt folgende formale Beschreibung:

\(M:=\left(Z:=\left\{z_0,z_1,z_2,...,z_{42},...,z_{1065}\right\},\Sigma:=\{b\},\delta:(z_i,b)=z_{(i+1\text{ mod }1024)},Z_0:=z_0,E:=\left\{z_{42}\right\}\right)\)

überhaupt Zeichnen würde recht lange dauern.

Du sollst den Automaten nicht zeichnen, sondern formal beschreiben. Du könntest aber mit Punkten eine Zeichnung verkürzen.

Beachte außerdem, dass \(E\) eine Endzustandsmenge ist. Deine Formulierung

E = Endzustand, da, wo der Automat endet, terminiert

ist demnach nicht korrekt.

Comments

Vielen Dank, ich sehe schon, wo ich meinen Fehler hatte.

---

Vielen Dank, ich sehe schon, wo ich meinen Fehler hatte.

Perfekt :-)