Hero Wunders
2004-08-19 23:00:11 UTC
Hallo!
Ich bin in der 13. Klasse und wir haben heute im Informatikunterricht
mit Endlichen Automaten angefangen.
Als Hausaufgabe:
Konstruiere einen Automaten, der anhand einer Zahl im Binärsystem
entscheidet, ob diese ohne Rest durch 3 teilbar ist.
Vom Lehrer haben wir noch den Tip bekommen, dass wir mindestens drei
Zustände einplanen müssen.
So, nun dachte ich mir, dass ich versuche Muster von allen durch 3
teilbaren Zahlen im Binärsystem zu finden und diese dann irgendwie in
einem Automaten umzusetzen.
Leider habe ich nur "2-stellige" Muster gefunden (obwohl der Automat Bit
für Bit bearbeitet).
Die Muster waren:
Wenn ich die letzten zwei Bits als eigene Zahl betrachte, wird diese
immer weiter runtergezählt (00, 11, 10, 01, 00, 11 ...).
Bei nächsten 2er Gruppe (von rechts) wird's schon hakeliger.
Hier wiederholt sich die Zahl einmal, dann wird zweimal 1 hochgezählt,
dann wiiederholt sich die Zahl wieder einmal.
Die nächste Gruppe hat wieder ein komplett anderes Muster (ich konnte
also die Muster der einzelnen Gruppen nicht noch weiter abstrahieren, so
dass ich vorraussagen könnte, was für ein Muster z.B. in Gruppe 4
auftaucht).
Hmm. Dann ist mir noch was aufgefallen:
Die Quersumme der einzelnen 2er Gruppen (wieder als einzelne Zahlen
gesehen) ergibt auch immer wieder eine durch 3 teilbare Zahl (im
Binärsystem notiert).
Daher muss (Gruppen durch ' getrennt) 01'01'01 oder 10'11'11'01 durch 3
teilbar sein.
Leider konnte ich das nicht so recht in einem Automaten "verwurschteln".
Man kann es auch so sehen: Es lassen sich immer 2er Gruppen so addieren
(entweder 01+01+01, 10+01 oder 01+10, an irgendeiner geraden Stelle der
Zahl), dass am Ende nur noch 11er und/oder 00er Gruppen da stehen.
Hmm, auch da bin ich nicht weitergekommen.
Ok...
Dann habe ich einfach mal angefangen weiterzudenken:
Beliebig viele Nullen am Anfang dürfen nichts ausmachen.
=> Z1 wechselt nicht bei 0
=> Z1 wechselt bei 1 zu Z2
Nun habe ich einfach ein Beispiel genommen, die 3 also 11
Wenn Z1 bei 1 wechselt und 11 schon zum Endpunkt führen, muss der mir
dann angibt, ob es sich um eine durch drei teilbare Zahl handelt (und
ich mir einfach ausgesucht habe, dass dieser Punkt wieder Z1 ist), muss
also Z2 bei 1 als Eingabe wieder zu Z1 gehen.
Also schonmal so:
0
,.
|| 1
+--+ ---> +--+
|Z1| |Z2|
+--+ <--- +--+
1
Nun könnte Z2 bei 0 nicht wechseln, was aber nicht mit dem Tip vom
Lehrer übereinstimmt, da dann hier Ende wäre.
Also muss bei 0 zu Z3 gewechselt werden.
0
,.
|| 1 0
+--+ ---> +--+ ---> +--+
|Z1| |Z2| |Z3|
+--+ <--- +--+ +--+
1
Jetzt kommt noch das Verhalten von Z3 ins Spiel.
Wenn ich annehme, dass wir zu Z3 durch die Eingabe 1,0 gekommen sind,
dann können meiner Theorie nach nun folgende Möglichkeiten eintreten:
1. Es gibt eine beliebig große Anzahl von 00er Gruppen, danach eine 01.
2. Es gibt eine beliebig große Anzahl von 11er Gruppen, danach eine 01.
Die einzige Möglichkeit 1 zu lösen und dabei wieder aus der Schleife
durch ein 01 herauszukommen besteht wohl darin, diese zwischen Z2 und Z3
laufen zu lassen.
Daraus folgt dann automatisch, dass Z3 bei 1 nichts tut.
Also:
0 1
,. ,.
|| 1 0 ||
+--+ ---> +--+ ---> +--+
|Z1| |Z2| |Z3|
+--+ <--- +--+ <--- +--+
1 0
Fertig.
Ist diese Argumentation dicht?
Ich schätze nicht, da ich nicht mit Sicherheit sagen kann, dass noch
andere Zahlen die genannten Eigenschaften haben.
Daher frage ich euch:
1. Wie geht man richtig systematisch so ein Problem an?
2. Woher weiß man wieviele Zustände eine solche Maschine mindestens und
höchstens haben muss (das ist wahrscheinlich ein besonders schwieriges
Gebiet)?
Ich bedanke mich schonmal bei euch für eure Hilfe!
Hero Wunders
Ich bin in der 13. Klasse und wir haben heute im Informatikunterricht
mit Endlichen Automaten angefangen.
Als Hausaufgabe:
Konstruiere einen Automaten, der anhand einer Zahl im Binärsystem
entscheidet, ob diese ohne Rest durch 3 teilbar ist.
Vom Lehrer haben wir noch den Tip bekommen, dass wir mindestens drei
Zustände einplanen müssen.
So, nun dachte ich mir, dass ich versuche Muster von allen durch 3
teilbaren Zahlen im Binärsystem zu finden und diese dann irgendwie in
einem Automaten umzusetzen.
Leider habe ich nur "2-stellige" Muster gefunden (obwohl der Automat Bit
für Bit bearbeitet).
Die Muster waren:
Wenn ich die letzten zwei Bits als eigene Zahl betrachte, wird diese
immer weiter runtergezählt (00, 11, 10, 01, 00, 11 ...).
Bei nächsten 2er Gruppe (von rechts) wird's schon hakeliger.
Hier wiederholt sich die Zahl einmal, dann wird zweimal 1 hochgezählt,
dann wiiederholt sich die Zahl wieder einmal.
Die nächste Gruppe hat wieder ein komplett anderes Muster (ich konnte
also die Muster der einzelnen Gruppen nicht noch weiter abstrahieren, so
dass ich vorraussagen könnte, was für ein Muster z.B. in Gruppe 4
auftaucht).
Hmm. Dann ist mir noch was aufgefallen:
Die Quersumme der einzelnen 2er Gruppen (wieder als einzelne Zahlen
gesehen) ergibt auch immer wieder eine durch 3 teilbare Zahl (im
Binärsystem notiert).
Daher muss (Gruppen durch ' getrennt) 01'01'01 oder 10'11'11'01 durch 3
teilbar sein.
Leider konnte ich das nicht so recht in einem Automaten "verwurschteln".
Man kann es auch so sehen: Es lassen sich immer 2er Gruppen so addieren
(entweder 01+01+01, 10+01 oder 01+10, an irgendeiner geraden Stelle der
Zahl), dass am Ende nur noch 11er und/oder 00er Gruppen da stehen.
Hmm, auch da bin ich nicht weitergekommen.
Ok...
Dann habe ich einfach mal angefangen weiterzudenken:
Beliebig viele Nullen am Anfang dürfen nichts ausmachen.
=> Z1 wechselt nicht bei 0
=> Z1 wechselt bei 1 zu Z2
Nun habe ich einfach ein Beispiel genommen, die 3 also 11
Wenn Z1 bei 1 wechselt und 11 schon zum Endpunkt führen, muss der mir
dann angibt, ob es sich um eine durch drei teilbare Zahl handelt (und
ich mir einfach ausgesucht habe, dass dieser Punkt wieder Z1 ist), muss
also Z2 bei 1 als Eingabe wieder zu Z1 gehen.
Also schonmal so:
0
,.
|| 1
+--+ ---> +--+
|Z1| |Z2|
+--+ <--- +--+
1
Nun könnte Z2 bei 0 nicht wechseln, was aber nicht mit dem Tip vom
Lehrer übereinstimmt, da dann hier Ende wäre.
Also muss bei 0 zu Z3 gewechselt werden.
0
,.
|| 1 0
+--+ ---> +--+ ---> +--+
|Z1| |Z2| |Z3|
+--+ <--- +--+ +--+
1
Jetzt kommt noch das Verhalten von Z3 ins Spiel.
Wenn ich annehme, dass wir zu Z3 durch die Eingabe 1,0 gekommen sind,
dann können meiner Theorie nach nun folgende Möglichkeiten eintreten:
1. Es gibt eine beliebig große Anzahl von 00er Gruppen, danach eine 01.
2. Es gibt eine beliebig große Anzahl von 11er Gruppen, danach eine 01.
Die einzige Möglichkeit 1 zu lösen und dabei wieder aus der Schleife
durch ein 01 herauszukommen besteht wohl darin, diese zwischen Z2 und Z3
laufen zu lassen.
Daraus folgt dann automatisch, dass Z3 bei 1 nichts tut.
Also:
0 1
,. ,.
|| 1 0 ||
+--+ ---> +--+ ---> +--+
|Z1| |Z2| |Z3|
+--+ <--- +--+ <--- +--+
1 0
Fertig.
Ist diese Argumentation dicht?
Ich schätze nicht, da ich nicht mit Sicherheit sagen kann, dass noch
andere Zahlen die genannten Eigenschaften haben.
Daher frage ich euch:
1. Wie geht man richtig systematisch so ein Problem an?
2. Woher weiß man wieviele Zustände eine solche Maschine mindestens und
höchstens haben muss (das ist wahrscheinlich ein besonders schwieriges
Gebiet)?
Ich bedanke mich schonmal bei euch für eure Hilfe!
Hero Wunders