Formale Beschreibung eines DEA/DFA

[Ninjafighter]

Sehr geehrte Community,

freut mich, dass es eine Hausaufgaben-Ecke nun gibt, die wird uns bestimmt sehr viel helfen

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 Z 1065 oder 1066?
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.

Daher gibt es einen Trick zur Lösung?

 

[JCODA]

Also der Automat sollte 1024 Zustände haben. Z0 bis Z1023.
Als einziger Zustand akzeptiert Z42. Startzustand ist eben Z0.
Die Überführungsfunktion ist gegeben durch delta(Zk,b) = Z((k+1)mod1024),
d.h. delta(Zk,b) = Z(k+1) falls 0<=k<1023 und delta(Z1023,b) = Z0 und das bedeutet anschaulich, dass der "Graph" ein Kreis ist.
(eine kleine Anmerkung noch, es heißt nicht n elementar N, sondern n element N, in prosa würde man vermutlich schreiben: n in N)