4. Hilfe bei Aufgabe über Moore-Automat

Hilfe bei Aufgabe über Moore-Automat

  • A

    Hallo,

    ich bräuchte mal wieder einen Tipp bei einer Hausaufgabe über Moore-Automaten. Mal die Aufgabenstellung so wie ich sie verstanden habe:

    Gegeben ist das Eingabealphabet X={0,1,2,3,4,5}X=\{0,1,2,3,4,5\} und Ausgabealphabet Y={0,1}Y=\{0,1\}. Gefunden werden muss ein Wort (=Dezimahlzahl) ω ∈ X^*, das nicht durch 6 teilbar ist. Weiter ist gegeben, dass die 0 ebenfalls durch 6 teilbar ist. Gefunden werden soll ein Automat mit möglichst wenig Zuständen, der das Wort annimmt.

    Was ich schon herausgefunden habe: Eine Zahl ist durch 6 teilbar wenn sie gerade ist und wenn ihre Quersumme durch 3 teilbar ist. Bei einem einstelligem Wort sind die Zahlen 1-5 nicht durch 6 teilbar, 0 dagegen schon.

    Bei Mehrstelligen Wörtern komme ich jetzt nicht weiter. Das Problem ist ja, dass ein Zustand nicht weiß welches Wort vorliegt, er kennt nur ein Symbol. Ich vermute, dass es möglich ist Zyklen in den Automaten einzubauen, anhand denen man erkennen kann ob eine beliebig große Zahlenfolge korrekt ist oder nicht. Ich hab schon versucht zu prüfen ob sich anhand einer dreistelligen Zahl solch ein Zyklus finden lässt. Da mir das aber doch zu viele Zustände geworden sind und ich auch kein Zyklus gefunden habe, der immer passt hab ich das aber wieder aufgegeben.

    Kann mir jemand sagen ob meine bisherigen Gedanken dazu richtig sind und ich auf der richtigen Fährte bin oder sollte ich in einer anderen Richtung weitersuchen?

    0
  • B

    Du solltest mit den Zuständen die Quersumme modulo 3 nachbilden, also so, dass du am Anfang im Zustand "0" bist und nach jeder gelesenen Zahl der Zustand gleich der bisherigen Quersumme modulo 3 ist. Bau das erstmal für die Teilbarkeit durch 3 und kombiniere es erst dann mit der Teilbarkeit durch 2.

    0
  • L

    Eigentlich hat Bashar ja schon alles gesagt. Noch ein Tipp zur Herangehensweise.

    Antoras schrieb:

    Was ich schon herausgefunden habe: Eine Zahl ist durch 6 teilbar wenn sie gerade ist und wenn ihre Quersumme durch 3 teilbar ist.

    Das ist ja schon sehr gut, du weisst eigentlich schon was du machen musst. Jetzt darfst du aber nicht zwischen einstelligen und mehrstelligen Worten unterscheiden. Es ist besser wenn du einfach mal ein Beispiel durchrechnest, dann kommst du auch drauf wie der Automat aussehen muss:

    Z.B.: Input 1245354910 (ich machs mal für Teilbarkeit durch 3)

    Dann gehst du Schritt für Schritt durch:
    1: Quersumme 1, nicht durch 3 teilbar
    2: Zahl 12, 1+2=3 = 0 (mod 3), durch 3 teilbar
    4: Zahl 124, 3+4=7= 1 (mod 3), nicht durch 3 Teilbar
    5: Zahl 1245, 1+5=6=0 (mod 3), durch 3 teilbar

    Du musst dir überlegen: Wenn eine Ziffer dazukommt, was ändert sich dann. Dann fällt dir hoffentlich auf, dass die Antwort nur von der Quersumme % 3 des letzten Schrittes abhängt. Wenn du das so machst, fällt es dir vielleicht leichter auf die Lösung zu kommen.

    0
  • A

    Vielen Dank euch beiden. Ich hab verstanden was ich machen muss.

    lustig schrieb:

    4: Zahl 124, 3+4=7= 1 (mod 3), nicht durch 3 Teilbar

    Sollt das nicht eher

    4: Zahl 124, 0+4=4= 1 (mod 3), nicht durch 3 Teilbar

    heißen? Also immer nur mit dem modulo weiter rechnen.

    Ich bin bei Teilbarkeit durch 3 auf 4 und bei Teilbarkeit durch 2 auf 3 Zustände gekommen. Bei Teilbarkeit durch 2 und 3 bin ich dann auf 7 Zustände gekommen (jeweils mit den Ziffern 0-5).

    Ich bin die Zustände mit mehreren Beispielen durchgegangen und auf das richtige Ergebnis gekommen, deshalb nehme ich an, dass alles korrekt ist.

    Hier die Zustände, falls jemand mal das gleiche Problem haben sollte oder es einfach mal durchschauen möchte:

    Teilbarkeit durch 2 und 3:

Ausgangszustand->Folgezustand|Übergangswert
Z0->{Z1|0,Z2|4,Z3|2,Z4|3,Z5|1,Z6|5}
Z1->{Z1|0,Z2|4,Z3|2,Z4|3,Z5|1,Z6|5}
Z2->{Z1|2,Z2|0,Z3|4,Z4|5,Z5|3,Z6|1}
Z3->{Z1|4,Z2|2,Z3|0,Z4|1,Z5|5,Z6|3}
Z4->{Z1|0,Z2|4,Z3|2,Z4|3,Z5|1,Z6|5}
Z5->{Z1|2,Z2|0,Z3|4,Z4|5,Z5|3,Z6|1}
Z6->{Z1|4,Z2|2,Z3|0,Z4|1,Z5|5,Z6|3}

Z0: Eingangszustand
Z1: (x mod 2 = 0) and (y mod 3 = 0)
Z2: (x mod 2 = 0) and (y mod 3 = 1)
Z3: (x mod 2 = 0) and (y mod 3 = 2)
Z4: (x mod 2 = 1) and (y mod 3 = 0)
Z5: (x mod 2 = 1) and (y mod 3 = 1)
Z6: (x mod 2 = 1) and (y mod 3 = 2)
x: letzte Ziffer
y: Quersumme

Z1 nimmt die Eingabe an

    Da bei meiner Aufgabenstellung eine Zahl nicht durch 2 und 3 teilbar sein darf wird die Eingabe in den Zuständen Z2-Z5 angenommen. Die 0 zählt zwar als vielfaches von 6, landet aber glücklicherweise in Z1 weshalb sie dann auch nicht angenommen wird.

    0
  • A

    Hm, mir fällt gerade auf, dass die Zustände Z4-Z6 äquivalent zu Z1-Z3 sind. D.h. Z5 und Z6 kann man wegfallen lassen. Z4 dagegen nicht, da Z1 angenommen wird was bei Z4 nicht der Fall ist. Also wäre die minimal mögliche Anzahl an Zuständen 5?

    Dann ergibt sich:

    Z0->{Z1|0,Z2|{4,1},Z3|{2,5},Z4|3,Z5|1,Z6|5}
Z1->{Z1|0,Z2|{4,1},Z3|{2,5},Z4|3,Z5|1,Z6|5}
Z2->{Z1|2,Z2|{0,3},Z3|{4,1},Z4|5,Z5|3,Z6|1}
Z3->{Z1|4,Z2|{2,5},Z3|{0,3},Z4|1,Z5|5,Z6|3}
Z4->{Z1|0,Z2|{4,1},Z3|{2,5},Z4|3,Z5|1,Z6|5}
    0
Anmelden zum Antworten