Wann ist Binärzahl mod m = 0 - Darstellung EA

Question

Hallo,

 

Ist gefragt, wann n mod 2 = 0, so ist klar wie hier der Automat erstellt werden muss. Ist jedoch n mod 7 = 0 oder ähnliches gefragt, so ist mir dies noch nicht ganz klar. Ich weiß, dass eine Binärzahl durch 3 teilbar ist, wenn ihre alternierende Quersumme durch 3 teilbar ist. Wie realisiere ich das am besten in einem EA? W

Danke im Voraus

Comments

Hallo, auf welche Aufgabe bezieht sich deine Frage?
Du hast in der Kategorie END-AA geschrieben und da geht es um einen Mealy Automaten zur bitseriellen Subtraktion.

Viele Grüße

Answer 1

Für allgemeine $m$ und $n$ in Dualdarstellung ist das durch endliche Automaten gar nicht lösbar. Dafür müsste man ja die eine Zahl durch die andere teilen, wofür man mehr Rechenleistung benötigt als endliche Automaten bieten.

Für einige spezielle $m$ wie $2$ oder $3$ ist es natürlich lösbar, da würde wir aber im Zweifel in der Klausur angeben, wie Sie vorgehen müssen. Das mit der alternierenden Quersumme können Sie ja mal versuchen.

Auch wenn $n$ in Unärdarstellung vorliegt, wenn es also nur um die Länge der Eingabe geht, kann für jedes feste $m$ ein endlicher Automat angegeben werden, der genau dann akzeptiert, wenn die Länge der Eingabe $n=|w|$ durch $m$ teilbar ist. Versuchen Sie sich mal zu überlegen, wie das geht, das ist eine gute Übung!

Answer 2

Hallo upcws!

Das ist schon eine sehr spezielle Frage. Wenn es irgendwo eine ähnliche Aufgabe gibt könnte ich dir vielleicht besser helfen, aber zwischen durch 2 teilbar und durch 3 teilbar liegen ja noch einige Schwierigkeitsstufen.

Ich habe mich damit auseinander gesetzt und keine direkte Lösung gefunden. Hier kannst du dich da drüber informieren, falls es dich sehr interessiert:

http://www.math.uni-bremen.de/didaktik/ma/ralbers/Publikationen/Dissertation/K7_EndlAutomat.pdf

Grüße, Felix (Tutor)