Hallo,
Zu euren Fragen:
Der Algorithmus funktioniert im Grunde so
0. Erstelle eine Matrix. schreibe links als Zeilen s0 bis s7 und unten ebenfalls s0 bis s7. Da aber die Paare (si, si) sowieso äquivalent sind, kann man die Diagonale wegstreichen. Den rechten oberen Teil, als die rechte obere Dreiecksmatrix können wir auch wegstreichen, da das Paar (s4, s5) äquivalent ist zu (s5, s4). Wieso ist das so? Nun, weil ich aus den einzelnen Feldern letztendlich nur rauslesen will, ob si und sj äquivalent sind. Ob ich nun (si, sj) oder (sj, si) betrachte ist egal, daher kann ich die obere Dreiecksmatrix weglassen und nur die unteren Dreiecksmatrix betrachten.
1. Wir schauen uns in unserer Zustandstabelle an, welche Zustände alles Endzustände sind. Daraus können wir schlussfolgern, welche Zustände denn alle NICHT miteinander 0-äquivalent sind: Alle Nichtendzustände und Endzustände sind zueinander NICHT 0-äquivalent, also schreiben wir X0 rein.
Konkret: s4 ist Endzustand. s0 aber nicht. Deswegen kommt in das Feld (s4,s0) ein X0 rein.
Und so kriegst du quasi überall wo in der Zeile/Spalte s4 steht, ein X0, da nur s4 Endzustand ist.
2. Nun schauen wir uns in unserer Zustandstabelle an, welche Zustände zum Endzustand führen.
Konkret: Das sind gerade s5, s7
Wir wissen also: Wenn wir einen Schritt von s5 oder s7 aus gehen, landen wir im Endzustand s4. Wenn wir einen Schritt von allen anderen Zuständen aus gehen, dann landen wir in einem Nichtendzustand. Beispiel: s0 landet entweder in s1 oder s3, während s5 in s4 landet. Wenn wir nun in unserer Tabelle gucken, dann stellen wir fest, dass (s1,s4) und (s3,s4) bereits mit X0 gekennzeichnet sind. Das heißt, s0 und s5 sind zueinander NICHT 1-äquivalent, also kommt ein X1 in das Feld (s0,s5) rein.
3. Und so lässt sich das Verfahren immer weiter fortsetzen, bis wir feststellen, dass sich die Tabelle nicht mehr verändert. Die leeren Paare sind gerade die zueinander äquivalenten Paare.
Viele Grüße,
Vivian (Tutor)