Automat für Teilbarkeit durch 3

Hallo,

habe hier einen Automaten für die Teilbarkeit von Dualzahlen durch 3 gefunden.
Die Zustände geben ja den Rest der Teilung an. Aber was sind die Übergänge? Also wie kommt man darauf, dass sie gerade so sein müssen? Gibt es dazu eine Formel oder sowas?
Ich würde mich über eine Erklärung freuen...

Mit freundlichen Grüßen

Du hast am Anfang das leere Wort.
Das hat den Rest 0 mod 3 und man befindet sich im Zustand t_0.

Jetzt wird eine 0 oder 1 angehängt.
Das bedeutet, dass das bisherige Wort mit 2 multipliziert wird. (Linksshift)
Der Rest wird also auch mit 2 multipliziert. 0*2=0.
Dazu kommt dann noch die neue Ziffer. Das bedeutet, es wird einfach 0 oder 1 addiert.
Mit 0 bleibt man im Zustand t_0, mit 1 kommt man zu t_1

In den Zuständen t_1 und t_2 passiert genau das Gleiche:

Zustand t_1, (alter Rest=1):
Neue Ziffer = 0: Rest=alter Rest*2+0 = 2+0 = 2 => neuer Zustand t_2
Neue Ziffer = 1: Rest=alter Rest*2+1 = 2+1 = 3 => neuer Zustand t_0

Zustand t_2, (alter Rest=2):
Neue Ziffer = 0: Rest=alter Rest*2+0 = 2*2+0 = 4 = 1 mod 3 => neuer Zustand t_1
Neue Ziffer = 1: Rest=alter Rest*2+1 = 2*2+1 = 5 = 2 mod 3 => neuer Zustand t_2


Statt 2 mod 3 kann man natürlich auch -1 mod 3 schreiben, dann ist es noch etwas einfacher.

Ok. Danke für Deine Erklärung.