Eigentlich ist das Ziel bei dem Algorithmus alle Paare zu markieren, die nicht äquivalent sind.
Die Diagonale darf hier also nicht markiert werden, da jeder Zustand immer äquivalent zu sich selbst ist.
Die Vorangehensweise geht eigentlich so:
1. Starte mit einer Leeren Tabelle.
2. Markiere jedes paar, wo ein Zustand akzeptierend ist und der andere nicht. (Denn diese Zustände können nicht äquivalent sein)
3. Iteriere nun durch jedes nicht markierte Paar. Schaue dann, auf welche Paare dieses Paar abgebildet werden können. Wenn mindestens eines dieser Paare markiert ist, wird das betrachtete Paar markiert (denn das Paar kann nicht äquivalent sein)
4. Wiederhole schritt 3 (eine Wiederholung = alle unmarkierten Paare betrachten), bis kein neues Paar markiert wird)
Die nicht markierten Paare sind dann äquivalent.
Zur einfachheit reicht es aus, wenn du nur die Einträge unterhalb der Diagonale betrachtest. Denn:
1. Die Diagonale ist immer nicht markiert
2. Äquivalenz ist eine symmetrische Relation, weswegen die Relationsmatrix am Ende symmetrisch sein wird.
Es ist aber einfach nur falsch, die Einträge auf der Diagonalen und über der Diagonalen zu markieren.