warum wird Zelle (s0, s1) mit X2 markiert?

Question

Könnte mir noch jemand erklären, warum die Zelle (s0, s1) mit X2 markiert wird?

s0 führt ja auf (s1,s2), was mit X1 markiert ist und s1 führt ebenfalls auf ein mit X1 markiertes Zustandspaar.

Ich dachte man würde ein Kästchen nur mit X2 markieren, wenn eine Komponente auf ein mit X1-markiertes Kästchen zeigt, das andere aber nicht...

Danke schonmal :)

Grüße

 

Answer 1

Hallo,

es scheint, als hättest du das Prinzip nicht ganz richtig verstanden oder vermittelt bekommen. Ganz kurz die Idee:

Sind zwei Zustände k-äquivalent, so sind sie auch (k-1)-äquivalent. Umgekehrt gilt also:

Sind zwei Zustände nicht k- äquivalent, so sind sie auch nicht (k+1)-äquivalent.

Wir überprüfen dies also iterativ. Wir betrachte also Schritt für Schritt, ob zwei Zustände bei der selben Eingabe auf ein bis dahin äquivalentes Zustandspaar führen.

Was ist also zu tun:

Zunächst alle Paare von Endzuständen mit Nicht-Endzuständen markieren (Definition von 0-äquivalenz).

Im nächsten Schritt muss für alle Zustandspaare vergleichen, ob ich bei Eingabe von 0 oder 1 auf ein bereits markiertes Feld komme (Betrachte ich zwei Zustände, haben beide einen Übergang für 0, die beiden erreichten Zustände muss ich vergleichen, also das entsprechende Kästchen suchen! Dasselbe gilt für die Eingabe von 1).

Wenn eines der beiden Felder markiert ist, kann keine Äquivalenz vorliegen und die Zustände sind nicht 1-äquivalent. Andernfalls lassen wir das Feld leer. Sind alle Felder verglichen, beginnt die nächste Runde, usw.

Das aber nur kurz die Forumversion, für eine ausführliche Erklärung schau nochmal ins Skript oder frage deinen Tutor.

Gruß,

Adam (Tutor)

 

Comments

Super, Danke! :)

Dann hätte ich nur noch 2 kurze Fragen:

1. Muss ich beispielsweise die Zelle (s1,s1) betrachten, dann weiß ich, dass die Zelle nicht markiert ist, da die Zustände äquivalent zueinander sind, oder?

2. Du schreibst ja " Wenn eines der beiden Felder markiert ist, kann keine Äquivalenz vorlieren"

Was passiert wenn BEIDE Fehler markiert sind? Dann liegt auch keien Äquivalenz vor, oder?

Danke nochmal!!! :)

Grüße

---

Hallo,

zu 1): Ich hab die Frage leider nicht ganz verstanden.

Allgemein: Ein Zustand ist immer zu sich selbst äquivalent, zeigen also zwei Zustände mit derselben Eingabe auf den selben Zustand, ist dieser natürlich äquivalent und es kann selbstverständlich kein Kreuz dastehen. Man kann dann überlegen, dass zwei Zustände äquivalent sind, wenn sie mit der gleichen Eingabe auf denselben Zustand zeigen.

zu 2): Genau, ich hätte sagen müssen "...mindestens eines der beiden Felder markiert..."

Gruß,

Adam (Tutor)