Übung 13 / 2 - Moore Automat

Benutzeravatar
Iblis
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 19. Mär 2009 00:37
Kontaktdaten:

Übung 13 / 2 - Moore Automat

Beitrag von Iblis »

Hi,

nachdem mir meine beiden, sonst äußerst zuverlässigen Informanten bei dem Thema auch nicht weiterhelfen konnten, muss ich mich leider doch mal hier outen :)

Es geht um Aufgabe Ü13 / 2.

Generell versteh ich garnicht wie man auf die Lösung des gesuchten Graphen kommt. Ich habe schon meine Schwierigkeiten zu verstehen was jeweils mit den Übergängen gemeint ist....steht "00,01" jetzt für "xy, x+y+" oder für "00 oder 01" ?

Und wieso kann im Zustand S2 mit der Sequenz "00,10" der Übergang nicht wieder auf S2 zeigen ? In S3 zeigt der Pfeil mit selbiger Sequenz auch auf sich selbst. Das klärt sich aber wohl mit dem Wissen wie man eben die Lösung bekommt.

Sind also noch einige Wissenslücken vorhanden...kann das evtl jemand kurz erläutern ? Aus dem Skript werde ich leider auch nicht schlau x(

Gruß

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Übung 13 / 2 - Moore Automat

Beitrag von Mspringer »

Bei den Transition steht 00,01 für 00 oder 01.

Auf den Automaten kommt man wie folgt: Grundsätzlich müssen die Sequenzen, wann immer sie in einer Folge auftreten, die gewünschte Operation ausführen.

Man beginnt also mit dem Zustand S0 und wählt für y einen Wert (Hier z.b. die 0). Danach überlegst du dir, was bei der jeweiligen Eingabe jeweils passieren kann. Da sich keine Änderung ergibt, wenn wir eine 00 oder eine 11 lesen, können wir im Zustand bleiben. Wenn jetzt allerdings eine 10 oder eine 01 kommt, müssen wir das irgendwie speichern, da wir den ersten Teil einer Sequenz gelesen haben. Deshalb nehmen wir uns einen neuen Zustand S1, bei dem sich der Wert für y nicht ändert (wir haben hier noch keine vollständige Sequenz gelesen).
Im Zustand S1 überlegen wir uns wieder, wie wir auf die verschiedenen Eingaben reagieren müssen. Wenn wir 00 erhalten, dann ist unsere Sequenz in jedem Fall unterbrochen und wir müssen wieder zurück in S0. Wenn wir 10 oder 01 lesen, dann können wir im Zustand bleiben, weil wir in diesem Zustand sowieso speichern, ob wir zuvor entweder 01 oder 10 gelesen haben. Wenn wir als Eingabe allerdings 11 erhalten, so haben wir in jedem Fall entweder die Sequenz 01,11 oder 10,11 erfüllt. Es muss jetzt also möglich sein, dies zu Speichern. Deshalb nehmen wir uns wieder einen neuen Zustand S2. In S2 muss dann Y=1 gelten. Egal welche Sequenz wir gelesen haben.
Das selbe musst du jetzt wiederum in S2 machen.

Hoffe das hilft ein wenig.
Zuletzt geändert von Mspringer am 31. Mär 2009 17:34, insgesamt 1-mal geändert.

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: Übung 13 / 2 - Moore Automat

Beitrag von robert.n »

Mspringer hat geschrieben:Es steht für 00,01 steht für 00 oder 01.
Damit ist die Aufgabe auch für mich plötzlich viel verständlicher. Mit "Sequenz" habe nämlich zumindest ich einen Wertübergang verbunden, was dem Threadersteller wohl genauso ging...
Danke (an beide^^)! 8)

//edit: Ist ja auch eine Sequenz, aber eben nicht mehr im Zustandsübergangsgrafen... da ist mit AB,CD dann AB oder CD gemeint...

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Übung 13 / 2 - Moore Automat

Beitrag von Mspringer »

Ok, um es noch mal genauer zu sagen: Was in der Mulö an den Transitionen steht, sind keine Sequenzen.

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: Übung 13 / 2 - Moore Automat

Beitrag von ivoch »

"00,01" bei einem Übergäng von A nach B (zum Beispiel) bedeutet "Wenn der Automat sich gerade im Zustand A befindet und die Eingänge so gesetzt werden: x1 = 0; x2 = 0 ODER x1 = 0; x2 = 1, dann geht/schaltet der Automat in den Zustand B". Mit anderen Worten, die ersten zwei Ziffern bezeichnen einen Übergang, der genau dann auftritt, wenn die Eingangsvariablen genau so gesetzt werden (in diesem Fall - 0,0). Die zweite Gruppe von zwei Ziffern bezeichnen einen "anderen" Übergang, der genau dann auftritt, wenn die Variablen auf diese andere Weise gesetzt werden (in diesem Fall - 0,1). In Wirklichkeit sind diese zwei Übergänge aber ein und derselbe, da sie dieselbe zwei Zustände verbinden.

Vielleicht verstehst du es auch besser, wenn ich dir die Vorgehensweise zeige:

Erstmal hoffe ich, dass die Aufgabenstellung klar ist - wenn eine andere Sequenz auftritt als die drei gegebenen, z.B. x0x1 = 01, 01 oder x0x1 = 11, 11 usw, dann bleibt der Ausgang konstant. ACHTUNG: "Ausgang konstant" bedeutet nicht unbedingt "derselbe Zustand im Graphen" - es kann ja sein, aus welchen Gründen auch immer, dass zwei verschiedene Zustände denselben Ausgangswert haben - in diesem Fall könntest du bei der Sequenz 01, 01 von dem einen dieser Zustände zum anderen übergehen, ohne die Bedingung/Aufgabenstellung zu verletzen.

So, dann fangen wir mal an:

1. Zeichnen wir erstmal den Ursprungszustand des Automaten. In diesem Fall ist keiner gegeben, also wählen wir einen Zufällig und nennen ihn "S0". Im Zustand S0 ist der Ausgangswert 0.

2. Nehmen wir die Sequenz 00,11. Laut Aufgabenstellung muss bei dieser der Automat seinen Wert auf 0 wechseln (oder in unserem Fall auf 0 bleiben, da wir ja in Zustand S0 schon den Wert 0 haben. Also mit anderen Worten müssen wir bei dieser Sequenz in Zustand S0 bleiben. Also, zeichnen wir einen Übergang, der wie ein Loop von S0 startet und in S0 endet. Dieser Übergang ist das erste Teil der Sequenz, tritt also auf, wenn x0 und x1 jeweils auf 0 gesetzt sind. Dann wollen wir einen zweiten Übergang zeichnen, der auch eine Schleife ist, der das zweite Teil der Sequenz darstellt - also findet dann statt, wenn x0 und x1 jeweils den Wert 1 haben. Da wir aber schon eine Schleife von S0 zu S0 haben, können wir diese auch für den zweiten Übergang benutzen, also beschriften wir sie mit "00,11". DIES BEDEUTET, dass wenn x0 und x1 den Wert 0 haben, findet dieser Übergang statt. Und wenn DANACH x0 und x1 auf 1 wechseln, dann findet dieser Übergang NOCHMAL statt, also zum zweiten Mal. (damit haben wir sogar einige andere Sequenzen abgedeckt, nämlich 11,11 und 11,00 und 00,00, bei denen laut Aufgabenstellung der Ausgang konstant bleiben soll - also soweit alles OK).

3. Da wir zwei Eingänge haben, haben wir VIER Möglichkeiten, eine Sequenz anzustossen - 2^n = 2^2 = 4. Bis jetzt haben wir zwei davon - nämlich 00,xx und 11,xx - wobei das jeweils zweite Teil der Sequenzen noch nicht alle Möglichkeiten abgedeckt hat - wir haben bis jetzt z.B. keine Sequent 00,01. Das kommt aber noch, muss auch nicht explizit von uns überprüft werden, da wenn wir den Automat richtig gezeichnet haben, werden alle Möglichkeiten automatisch abgedeckt. Wir müssen nur sicherstellen, dass das erste Teil aller Sequenzen komplett abgedeckt ist (FÜR ALLE ZUSTÄNDE!). Für S0 brauchen wir also noch 01,xx und 10,xx.

4. Schauen uns mal 01,11 an - laut Aufgabenstellung muss diese Sequenz den Automat auf einen Zustand bringen, bei dem der Ausgang y = 1 ist. Eine Idee wäre, den ersten Übergang (01) auch auf dieselbe Schleife abbilden, die wir schon haben - diese würde dann mit "00,11,01" beschriftet. Das ist aber falsch, denn bei der Sequenz 01,11 würden wir immer noch im Zustand S0 sein. Wir können auch nicht einfach noch einen Übergang zum einen neuen Zustand S1 zeichnen und ihn mit 11 beschriften, denn in diesem Fall würde der Automat nicht entscheiden können, welcher der beiden "11" Übergänge er durchgehen soll. Also zeichnen wir einen neuen Zustand S1 und führen den Übergang "01" zu diesem. Dieser Zustand kann aber nicht den Ausgangswert 1 haben, denn dies würde die Bedingung verletzen, dass alle nicht aufgelisteten Sequenzen den Wert konstant halten sollen - insbesondere also auch die Sequenz "00,01" -bei dieser würde unser Automat erstmal die "Schleife" durchgehen (für das "00" Teil) und dann den neuen Übergang zu S1 (für das "01" Teil). Da bei dieser Sequenz der Ausgang immer noch konstant bleiben muss (also 0, da wir von 0 ausgehen), muss beim Zustand S1 auch der Ausgang 0 sein. Wir wollen aber doch die Sequenz "01,11" abbilden, bei der y = 1 wird. Also zeichnen wir einen dritten Zustand, S2, und führen einen Übergang von S1 zu S2, der genau dann ausgeführt wird, wenn x0 und x1 jeweils 1 werden (also mit "11" beschriften). Beim Zustand S2 ist dann der Ausgangswert schon 1.

5. (Wir betrachten immer noch S0, da wir bei diesem immer noch nicht alle Möglichkeiten ausgeschöpft haben) - Analog machen wir das für die letzte Möglichkeit, eine Sequenz anzustossen, nämlich 10,xx. Nehmen wir die 10,11 - laut Aufgabenstellung muss hier einen Ausgangswechsel erfolgen. Da wir bei S0 sind, also y = 0, muss nach der Sequenz y = 1 sein. Wir haben aber schon das zweite Teil, das von S1 zu S2 führt ("11"). Also benutzen wir denselben Übergang, den wir für die Sequenz 01,11 benutzt haben, also derjenige, der von S0 zu S1 führt. Damit müssen wir ihn mit 01,10 beschriften. JETZT IST S0 FERTIG (wir haben die Übergänge 00 und 01 und 10 und 11)

6. Fangen wir mit S1 an - dieser hat schon einen der vier Möglichen Übergänge, nämlich "11" - der führt ja zu S2. Nehmen wir dann "00" - wenn wir für diesen Übergang eine Schleife machen, die von S1 zu S1 führt (also genau wie die eine beim S0), dann werden zwei der Bedingungen der Aufgabenstellung verletzt - nämlich Bedingung 1: Sequenz 00,11 bewirkt y = 0. Bei uns würde diese Schleife y = 1 bewirken, denn nachdem wir den Übergang 00 durchgegangen sind (und uns immer noch im S1 befinden), werden wir den Übergang 11 durchgehen müssen und somit auf S2 landen, also y = 1. Also können wir keine Schleife machen. Wir können aber einen Übergang von S1 zu S0 machen und dieser mit 00 beschriften - dann werden alle Bedingungen erfüllt.

7. Die Sequenz 01,11 bewirkt y = 1, also müssen wir bei dem Übergang "01" im S1 bleiben, damit wir dann mit "11" zu S2 übergehen können - also, "Loop" zeichnen und mit "01" beschriften.

8. Die Sequenz 10,11 bewirkt y = 'y, also in unserem Fall y = 1 (da in S1 y = 0 ist). Also genau wie bei Punkt 7 - "Loop" zeichnen, also denselben benutzen, den wir schon haben und mit "01,10" beschriften.

9. Somit sind alle vier Möglichkeiten auch bei S1 erschöpft (00 führt zu S0, 01 und 10 führen zu S1 und 11 führt zu S2)

10. Weiter machen mit S2 und dann mit S3 (denn wir unter anderem wegen der Sequenz 00,11 zeichnen müssen).

.......

Wenn bei allen Zuständen alle vier Möglichkeiten erschöpft sind und keine neuen Zustände gezeichnet werden müssen, ist unser Automat fertig.




[EDIT] Markus hats in "etwas" weniger Zeilen erklärt :lol:, aber ich lasse meinen Beitrag so wie er ist - vielleicht hilft er doch jemandem beim Verstehen.

Benutzeravatar
Iblis
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 19. Mär 2009 00:37
Kontaktdaten:

Re: Übung 13 / 2 - Moore Automat

Beitrag von Iblis »

Danke für die hilfreichen Beiträge...das sollte mir weiterhelfen (:

Antworten

Zurück zu „TGdI 1“