Wie kommt man auf die Mengen der 1-Äquivalenz ?

Question

Hallo,

ich hab das immer noch nicht ganz verstanden.
Mir ist klar, wie man auf die zwei Mengen bei der 0-Äquivalenz kommt. Aber was muss ich dann machen um auf die Mengen der 1-Äquivalenz zu kommen. Was genau muss ich miteinander vergleichen (oder kann man es vielleicht einfach aus dem Zustandsdiagramm/Minimierungstabelle ablesen)?

Danke und Gruß

 

Answer 1

Sobald du die 0-äquivalenten Zustände in die Minimierungstabelle eingefügt hast, musst du nun überprüfen, ob du mit einem Paar, das noch unmarkiert in der Tabelle ist (nicht-0-äquivalent) auf ein markiertes Paar kommst.

Hier ein Beispiel, anhand dessen du dir das generelle Vorgehen hoffentlich verdeutlichen kannst (Tabelle aus der Aufgabe, nicht-0-äquivalente Paare bereits eingetragen):

Betrachte das Paar s0-s3. Es ist 0-äquivalent (da noch nicht markiert). Dieses Paar führt mit der Eingabe von 0 auf das Paar s1-s5 und mit der Eingabe von 1 auf das Paar s2-s5. Nun sind beide Paare bereits in der Tabelle Markiert (es würde auch nur eines von beiden genügen) und somit ist das Paar s0-s3 nicht-1-äquivalent.

Ich hoffe, das hilft dir weiter.

Gruß,

Philip (Tutor)

 

Comments

Hallo Philip,

danke für deine Antwort. Aber wir leider ein bisschen aneinander vorbeigeredet oder ich hab undeutlich ausgedrückt.
Wie man die Minimierungstabelle ausfüllt habe ich verstanden und kriege ich auch immer hin.
Mein Problem is hier der nächste Schritt, das Aufzählen der k-äquivalenten Mengen:
- Mengen 0-äquivalenter Zustände: {s0, s1, s2, s3}; {s4 , s5}
- Mengen 1-äquivalenter Zustände: {s0, s1}; {s2}; {s3}; {s4, s5}
- usw.

Wie gesagt, wie man die Menge der 0-äquivalenten Zustände angibt ist mir klar (Nicht Endzustände und Endzustände). Aber wie geht man vor um die Mengen weiter aufzuspalten für 1,2,3-Äquivalenz? Gibt es da einen Algorithmus oder kann man das aus der Minimierungstabelle ablesen?

Danke und Gruß

---

Hallo,

zunächst möchte ich dich darauf hinweisen, dass wir nicht-k-äquivalente Zustände bestimmen (das nicht ist wichtig). Nun zu deiner Frage:

Ja, du kannst diese Nicht-k-Äquivalenz aus der Minimierungstabelle ablesen, und zwar kommt es darauf an, in welcher Iteration das Kreuzchen gesetzt wurde. Daher steht auch immer ein X0, X1, X2, .. dort, was bedeutet, dass die Zustände nicht 0, 1, 2, .. äquivalent sind. Es ist also direkt aus der Tabelle ablesbar. Ein (nach Ende des Algorithmus) leeres Kästchen bedeutet die Äquivalenz dieser zwei Zustände.

Vielleicht noch ein kleiner Zusatz:

Das Komplement zu den nicht-k-äquivalenten Mengen sind also die k-äquivalenten Mengen. Beispiel:

s4, s5 sind nicht-0-äquivalent zu s0, s1, s2, s3 (X0 in der Tabelle). Damit sind {s4,s5} und {s0,s1,s2,s3} äquivalent.

Und nochmal von der einer Anderen Betrachtung aus:

Vor der 3. Runde (X1 gesetzt, X2 noch nicht) siehst du, dass die Paare s0-s1 und s4-s5 noch nicht markiert sind. Daraus folgt, dass diese Mengen (jeweils) noch 2-äquivalent sind. Ob sie zusammengehören kannst du leider nicht schlussfolgern, wie die folgende Logik zeigt. Jedoch ist dies durch den Verlauf des Algorithmus klar. Die Logik sieht wie folgt aus:

Aus einem markierten Kästchen folgt die nicht-k-Äquivalenz (a=>b). Damit folgt (Kontraposition):

Aus einer k-Äquivalenz folgt die nicht-Markierung des Kästchens.

Nun muss noch überprüft werden, ob die nicht-Markierten Paare zu einer Menge zusammengehören (was hier offensichtlich nicht der Falls ist).

Ich hoffe, das hilft weiter, Gruß,

Philip (Tutor)