Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

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

+1 Punkt
1,302 Aufrufe
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
Gefragt 10, Feb 2017 in END-AA von upcws upcws Tutor(in) (101,310 Punkte)  
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

2 Antworten

0 Punkte
 
Beste Antwort

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!

Beantwortet 12, Feb 2017 von Lukas König Dozent (10,065,100 Punkte)  
ausgewählt 13, Feb 2017 von upcws upcws
0 Punkte
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)
Beantwortet 12, Feb 2017 von uwdtl uwdtl Tutor(in) (102,530 Punkte)  
...