[Folie 6-9] Zustandsübergangsgraf

[Krümelmonster]

Kann jemand mal erklären, wie man aus den Tabellen
auf diesen Grafen kommt?
Vor allem die Bedeutung der Kanten und Knoten.

[AlexB]

Nicht alles immer für bare Münze nehmen, was man liest. Das im Skript gemeinte ist kein Adeliger sondern ein Graph - aber das nur am Rande.

Jetzt zur eigentlichen Frage:
Was man einsieht: Egal, was anfangs in meinem Register steht, wenn ich einmal shifte, steht danach nur noch entweder die Werte 0, 1, 2 oder 3.
Der Zustand A des Graphen ist durch einen Kringel als Startzustand markiert, gehen wir also mal von ihm aus. Nun gibt es folgende Möglichkeiten:
- Steht in meinem Register eine 7 (111) oder eine 6 (110) und wird diese Zahl nach rechts geshiftet (Zustandsübergang von A nach B), so erhält man eine 3 (011). Das soll Zustand B verdeutlichen
- Steht im Register eine 5 (101) oder 4 (100), erhält man eine 2 (010). Das entspricht dem Zustand C
- Steht im Register eine 3 (011) oder 2 (010), erhält man eine 1 (001). Das entspricht Zustand D
- Steht im Register eine 1 (001) oder 0 (000), erhält man eine 0 (000). Das entspricht wieder Zustand A

Und jetzt kommt der Clou: Den Rest habe ich auch nicht verstanden. Weder die Übgergänge aus den Zuständen B bis D, noch die Farbzuordnung.
So wie ich den Graphen verstanden habe, kann im Zustand B nicht mehr # = 4 oder 5 sein. Hm.

[AlexB]

Nachtrag: Da ich den Graphen wie gesagt selbst noch nicht ganz durchschaut habe, möchte ich mich davor hüten zu behaupten, er sei falsch.
Aber alternativ dazu habe ich kurz einen Zustandsgraphen gemalt, wie ich ihn erwartet hätte. Farben spielen keine Rolle, sie dienen nur zur Hervorhebung. Keine Gewähr auf Richtigkeit, es darf gerne darüber diskutiert werden.

[Krümelmonster]

Danke erstmal für die Antwort.

In einer späteren neuen Rechtschreibung wird bestimmt auch Graph mit v erlaubt sein.

Die Farben verwirren mich auch weiterhin, aber das ist eine andere Sache.
Was mir noch nicht klar ist: Wie kommt man von einem Knoten auf die Kanten,
die den Knoten verlassen.

Warum verlässt z.B. die Kante mit # = 4 oder 5 den Knoten B und nicht ein anderer?

[AlexB]

Warum verlässt z.B. die Kante mit # = 4 oder 5 den Knoten B und nicht ein anderer?

Weshalb von B im Graphen des Skripts # = 4 oder 5 abgeht, habe ich auch nicht verstanden.
Die Zustände entsprechen - so wie ich es mir zusammengereimt habe - grob dem, was im Register steht.
A: Im Register steht irgendwas von 000 bis 111
B: Im Register steht 011
C: Im Register steht 010
D: Im Register steht 001

[Krümelmonster]

So würde ich es mir auch erklären.

Allerdings bleibt dann noch die Frage der folgenden Transitionen.

[AlexB]

In meinem Graph gibt es beispielsweise für den Zustand B, der bedeutet, dass im Register nun eine 3 (011) steht, nur noch den Übergang # = 3, was bedeutet, dass eben diese 3 nach rechts geshiftet wird und zu einer 1 (001) wird, folglich landet die Transition im Zustand D.
Anderes Beispiel: Wenn man zu Beginn eine 5 im Register hatte und sie shiftet, landet man im Zustand C, d.h. im Register steht der Wert 010. Von diesem Zustand aus kann es nur die Transition # = 2 geben. Das ergibt eine 1 (001), man landet folglich wie von B ausgehend bei D.

Was im Skript gemeint ist, kann ich leider noch immer nicht sagen. Tut mir leid. Ich hoffe, dass hier noch andere Meinungen auftauchen. Falls nicht, darfst Du ruhig einmal Prof. Huss vor, während oder nach der Vorlesung fragen, wie der Graph zu interpretieren ist. Nett wäre es, wenn Du dann das Ergebnis hier kurz reinstellst, ich bin da ebenso gespannt wie Du

[Krümelmonster]

Ich hätte den Graph auch so dargestellt wie du.

Auf dieser offenen Frage werde ich bestimmt nicht sitzen bleiben.

[bashFish]

Ob sich des Rätzels Lösung noch vor der Klausur finden lässt?

Wie wärs mal mit nem Kommentar vom Tutor ? Ich würde im Übrigen auch für Alex's Bildchen stimmen...

[AlexB]

Na viel kommentieren kann ich nicht, weiß ja nicht, ob mein Graph stimmt. Hatte jedenfalls beim Veranstalter auf das Problem hingewiesen. Den Hinweis an Euch, doch einfach mal nach einer Vorlesung Prof. Huss zu fragen, hat anscheinend jedoch niemand umgesetzt.