Äquivalenzen

Ich habe ein kleines Problem bei dem aktuellen Zettel.

> Wenn zwei Zustände bei der gleichen Eingabe gleiche Ausgaben erzeugen und den
gleichen Folgezustand annehmen, so sind sie äquivalent.

> Wenn zwei Zustände bei der gleichen Eingabe gleiche Ausgaben erzeugen und äquiva-
lente Folgezustände annehmen, so sind sie äquivalent.

Bei der ersten Aufgabe bin ich auf die Zustände g b und d gestoßen. (Ist zwar ein Teil der Lösung, aber es geht leider nicht anders).

Wenn ich in g eine 1 bekommen, schreibe ich eine 1 und gehe nach b. Wenn ich in in b eine 1 lese, bleibe ich dort. Beide Zustände gehen bei einer Null in d über und schreiben eine 1.
Da b und g für die 1 nicht den gleichen Folgezustand annehmen, folgt aus dem ersten Kriterium nicht die Äquivalenz.

Damit ist auch das zweite Kriterium nicht benutzbar, da die Zustände in die b und g für die 1 übergehen, nicht äquivalent sind.

Somit sind b und g nicht äquivalent.
Dieses Ergebniss wundert mich stark, da es für Eingaben, die nicht nur aus 1en bestehen, egal ist, ob man in b oder in g begonnen hat.

Könnte mir da jemand auf die Sprünge helfen?

Nikolas

Nikolas schrieb:
-------------------------------------------------------
> Bei der ersten Aufgabe bin ich auf die Zustände g
> b und d gestoßen. (Ist zwar ein Teil der Lösung,
> aber es geht leider nicht anders).

Soviel sei verraten: Nicht alle Zustände der Menge {g,b,d} sind paarweise äquivalent.

> Wenn ich in g eine 1 bekommen, schreibe ich eine 1
> und gehe nach b. Wenn ich in in b eine 1 lese,
> bleibe ich dort. Beide Zustände gehen bei einer
> Null in d über und schreiben eine 1.
> Da b und g für die 1 nicht den gleichen
> Folgezustand annehmen, folgt aus dem ersten
> Kriterium nicht die Äquivalenz.

Lies nochmal ganz genau durch, was Du geschrieben hast.
In welchen Zustand kommt man unter welcher Ausgabe bei Eingabewert 0 ausgehend von g bzw. b?
In welchen Zustand kommt man unter welcher Ausgabe bei Eingabewert 1 ausgehend von g bzw. b?
Was gilt also?

Grüße
Tobias Nopper

P.S.: Noch ein Tipp: Es steht ja nirgends, dass der Nachfolgerzustand eines Zustandes nicht auch der Zustand selbst wieder sein darf.

Grüße
Tobias Nopper
Lehrstuhl für Betriebssysteme



2 mal bearbeitet. Zuletzt am 06.02.2008 11:55 von nopper.

> Soviel sei verraten: Nicht alle Zustände der Menge {g,b,d} sind paarweise äquivalent.
Das hab ich auch so nicht gemeint. Ich wollte nur alle relevanten Knoten aufzählen.

> In welchen Zustand kommt man unter welcher Ausgabe bei Eingabewert 0 ausgehend von g bzw. b?
Naja, das sind natürlich .. und ...
> In welchen Zustand kommt man unter welcher Ausgabe bei Eingabewert 1 ausgehend von g bzw. b?
und ... bzw. ..., oha, komisch.

Ich habs mir noch mal aufgemalt und plötzlich sahs ganz anders aus. 8 Zustände ist schon etwas voll :)

Danke für die schnelle Hilfe : )