Guten Morgen,

vielleicht kann mir ja einer eine kurze Frage beantworten: Muss In den bei 7.3 beschriebenen Zuständen ersichtlich werden wie der Automat überprüft, ob die eingegebene Binäre-Zahl durch 3 teilbar ist?

Die Antwort auf deine Frage steht doch in der Aufgabenstellung. Siehe 2. Absatz.

Kann mir jemand nen Tipp geben, wie man das mit dem DFA realisieren soll? Habe mir etliche Tabellen gebastelt mit Zahlen die akzeptiert werden und welche mit Zahlen, die nicht akzeptiert werden. Hab ewig gegrübelt, aber ich hab einfach keine Idee, weil der DFA sich ja nicht das gesamte Leseband ansehen und merken kann.

Wird die Zahl von den höherwertigen zu den niederwertigen Bits hin gelesen oder umgekehrt?

Du kennst doch den Trick mit der Quersumme für Teilbarkeit durch 3 und 9 im Dezimalsystem, oder? Wenn die Quersumme durch 3 teilbar ist, dann ist auch die Zahl selbst durch 3 teilbar, dto. für die 9. Warum funktioniert das für die 3 und die 9? Weil sie die 10 mit Rest 1 teilen (3*3 + 1 bzw. 1*9 + 1).

Für welche Zahlensysteme funktioniert der Trick mit der 3 dann außer im Dezimalsystem? Sicher mit dem Vierersystem, weil 1*3 + 1 = 4 ist. Das Vierersystem ist eng mit dem Binärsystem verwandt, weil zwei Binärziffern immer eine Viererziffer bilden.

Du brauchst also im Prinzip erstmal drei Zustände für die aktuelle Quersumme. Diese musst Du dann verdoppeln, um Dir zu merken, ob Du gerade bei der niederwertigen Binärstelle des Vierersystems bist oder bei der höherwertigen Stelle.

Mit jedem Einlesen eines Zeichens musst Du zwischen diesen beiden Zustandsmengen hin- und herspringen. Eine eingelesene 0 ändert nicht die Quersumme, dann musst Du zur entsprechenden "Parallel"-Quersumme springen. Eine eingelesene 1 ist entweder 1 oder 2 wert, je nachdem, in welcher Zustandsmenge Du gerade bist.

Hm, dann solltest Du mit 6 Zuständen und 12 Übergängen auskommen. Wenn man nach dem kompletten Einlesen bei einem der beiden 0-Zustände ist, dann ist die Zahl durch drei teilbar. So stelle ich mir das ungefähr vor.

Ach so, das ganze funktioniert natürlich nur, wenn man schon beim Einlesen weiß, ob man gerade eine gerade oder ungerade Stelle einliest. Man muss also von rechts einlesen (dann beginnt man immer bei einer geraden bzw. niederwertigen Ziffer) oder wissen, aus wievielen Ziffern die Zahl besteht und dann im entsprechenden Null-Zustand anfangen.

Kann mir jemand nen Tipp geben, wie man das mit dem DFA realisieren soll? Habe mir etliche Tabellen gebastelt mit Zahlen die akzeptiert werden und welche mit Zahlen, die nicht akzeptiert werden. Hab ewig gegrübelt, aber ich hab einfach keine Idee, weil der DFA sich ja nicht das gesamte Leseband ansehen und merken kann.

Ich würd's wie folgt versuchen: Angenommen, du hast eine Zahl, die durch 3 teilbar bzw. nicht durch 3 teilbar ist, und hängst noch eine 0 hinten dran. Was bleibt gleich und was ändert sich? Was passiert, wenn's eine 1 ist? (Stichwort: Restklassen)

Nachtrag: Freds Ansatz klingt aber auch ganz erfolgversprechend. Schön zu sehen, dass es da Spielraum für kreativität gibt. :)

Wird die Zahl von den höherwertigen zu den niederwertigen Bits hin gelesen oder umgekehrt?

Ich hab's von hoch- zu niederwertig bearbeitet, also so wie die Zahl auf dem Papier steht.

Angenommen, du […] hängst noch eine 0 hinten dran. Was bleibt gleich und was ändert sich?

Ah, interessant. Bei einer 0 verdoppelt sich der Rest (modulo 3), und bei einer 1 kommt zusätzlich noch 1 auf den Rest drauf (modulo 3). Das ist ja viel einfacher als mein Ansatz. Dann sollten wohl auch drei Zustände reichen.

Edit: LOL, der DFA sieht bei mir aus wie ein $-Zeichen [28]

keine ahnung wie ihr das macht, aber da wäre ich nie drauf gekommen und das mit der quersumme höre ich heute zum ersten mal. wieso klappt das denn wenn mod 1 im dezimalsystem rauskommt?

wieso klappt das denn wenn mod 1 im dezimalsystem rauskommt?

Mach Dir den Zusammenhang zwischen "Zahl" und "Repräsentation einer Zahl" klar. Die Repräsentation einer Zahl ist im Allgemeinen eine Aneinanderreihung von gewichteten Ziffern. Die gewichtete Summierung dieser Ziffern ergibt den Betrag der Zahl. (Eine Ausnahme bilden hier z.B. die römischen Zahlen). Die Menge der verfügbaren Ziffern wird durch das Zahlensystem vorgegeben.

Im Dezimalsystem wird z.B. die Anzahl der Tage pro Jahr als Aneinanderreihung der Ziffern 3, 6 und 5 repräsentiert: 365. Wir sagen auch "Dreihundertfünfundsechzig" zu dieser Zahl. Die 3 hat also das Gewicht 100 ("Dreihundert"), die 6 das Gewicht 10 ("sechzig"), die 5 das Gewicht 1 ("fünf"). (An dieser Stelle merkt man, dass die Reihenfolge in der deutschen Sprechweise unlogisch ist!). 365 = 300 + 60 + 5. Jede Stelle ist 10 Mal so viel Wert wie ihr rechter Nachbar - 10, weil die Basis 10 ist.

Bei der Division durch 3 kann man sich die Frage stellen, wieviel eine Ziffer auf einer bestimmten Stelle zum Divisionrest beiträgt. Bei der ganz rechten Stelle ist dies offenbar der Betrag der Ziffer selbst, modulo 3:
0%3 = 0, 1%3 = 1, 2%3 = 2
3%3 = 0, 4%3 = 1, 5%3 = 2
6%3 = 0, 7%3 = 1, 8%3 = 2
9%3 = 0

Wenn wir den Beitrag einer Stelle zum Divisionsrest kennen, wie sieht dann der Beitrag des linken Nachbars aus?
(10x)%3
= ((9+1)x)%3 wegen 10 = 9+1
= ((9x)%3 + (1x)%3)%3 wegen ((a+b)m)%n = ((am)%n + (bm)%n)%n
= ((3*3x)%3 + x%3)%3 wegen 9 = 3*3 und 1m = m
= (0 + x%3)%3 wegen (nm)%n = 0
= (x%3)%3 wegen 0+m = m
= x%3 wegen (m%n)%n = m%n

Das Ergebnis unserer Rechnung nochmal zusammengefasst: (10x)%3 = x%3. Vollständige Induktion zeigt: der Beitrag zum Divisionrest ist also unabhängig von der Stelle! Dieses Phänomen tritt immer dann auf, wenn der Divisor die Basis des Zahlensystems mit Rest 1 schneidet, weil man die Basis dann als m*Divisor + 1 darstellen kann und durch die Rechengesetze in endlichen Körpern nur die 1 übrig bleibt.

Zwei bekannte Beispiele für dieses Phänomen sind die Divisionreste beim Teilen durch 3 und 9 im Dezimalsystem. Im Hexadezimalsystem mit 16 Ziffern funktioniert dies für 3, 5 und 15 (wegen 16%3 = 1, 16%5 = 1 und 16%15 = 1).