Wie füllt man die Tabelle bzgl. der k-äquivalenz aus?

Question

Hallo,

mir ist nicht ganz schlüssig, wie man die Tabelle bzgl der k-äquivalenz bei Aufgabenteil b) ausfüllt. Gibt es hier auch ein Schema nachdem man gehen kann, wie bei der Minimierungstabelle?

Danke im Voraus!

Answer 1

Na, Sie haben ja zuvor schon die Minimierungstabelle ausgefüllt. Dort steht jede Zelle für ein Zustandspaar.

• Wenn die Zelle leer ist, sind die Zustände äquivalent zueinander, das heißt $k$-äquivalent für alle $k$.
• Wenn in der Zelle $\times_i$ steht, dann sind die beiden Zustände nicht $i$-äquivalent, aber $i-1$-äquivalent zueinander.

Das heißt also, Sie fangen mit einer Menge an, die alle Zustände enthält (diese können wir ja mal unformal $-1$-äquivalent nennen, damit die obige Beschreibung auch für den $i=0$-fall passt), und trennen diese immer weiter auf. Zuerst beginnen Sie also mit den Zellen, die $\times_0$ enthalten. Das sind Zustandspaare, die zueinander nicht $0$-äquivalent sind. Die entsprechenden Zustände werden also voneinander getrennt, was zu zwei Mengen führt (in diesem Fall die Menge der Endzustände und die Menge der Nicht-Endzustände, für $i=0$ braucht man die Tabelle also noch gar nicht). So erhalten Sie die erste Zeile der Tabelle Dann nehmen Sie sich genauso die $\times_1$-Zellen vor und trennen die Zustände voneinander, die zwar noch $0$-äquivalent waren, aber nicht mehr $1$-äquivalent sind. Dann die $\times_2$-Zellen usw.

In der letzten Zeile sind die Zellen gerade so aufgeteilt, wie die Zustände äquivalent zueinander sind.

Answer 2

Hallo,
wichtig ist dabei, dass du verstehst, was deine Markierungen in der Minimierungstabelle bedeuten. Alle Paare die z.B mit einem X0 markiert sind, sind NICHT X0-äquivalent. Dementsprechend gehst du die Minimierungstabelle nach den einzelnen Äquivalenzen durch und schaust, welche Paare noch nicht markiert sind und somit z.B X0 äquvalent SIND. Bei den X0 äquvalenten sind ja nur alle Kombinationen mit S4 markiert, das heißt S4 ist mit keinem anderen Zustand X0 äquivalent und so weiter.
Grüße Verena (Tutor)