Menge der 0/1/2 äquivalenten Zustände bestimmen

Question

Kann mir jm bitte erklären wie man nach der Minimierung eines endlichen Automaten die Menge der 0/1/2 äquivalenten Zustände bestimmen kann? Bin da leider komplett lost.

Answer 1

Hallo uqgap,

0-äquivalent sind zwei Mengen, einmal alle Nicht-Endzustände (N.EZ) und einmal alle Endzustände (EZ). Die sind 0-äquivalent, da wenn das Wort enden würde, würde es einmal akzeptiert werden und das andere mal nicht.

1-äquivalent sind alle Zustände (miteinander), die nach einem Zeichen in der gleichen Menge (N.EZ bzw. EZ) sind.

2-äquivalent, wenn die Zustände nach 2 Zeichen noch in der gleichen Menge landen (Z.b. es gibt 0en und 1en wie hier, dann müssen alle Kombinationen  (00, 01, 10, 11) von jeweils zwei Zuständen entweder beide im N.EZ oder im EZ landen, kann auch gemischt sein, aber bei der gleichen Kombi muss es die gleiche Menge sein).

3-äquivalent ...

Man kann das mit der Tabelle machen, man schreibt zuerst z.b. bei k-äquivalent s0 auf und geht dann die Spalte/Zeile durch und schaut,  welcher Zustand ist zu s0 >x_k. Den schreibt man in die Menge. Die nächste Menge beginnt dann mit einem nicht zu s0 k-äquivalenten Zustand.

Ein paar Sachen noch dazu:
- Die einzelnen Mengen werden niemals größer (man braucht also entweder gleich viele Mengenklammern oder mehr)
- Die ganz äquivalenten Zustände sind immer zusammen in einer Mengenklammer