0-Äquivalenz und k-Äquivalenz: Verständnisproblem

Question

Hallo,

habe ich das jetzt richtig verstanden:

jeder Nichtendzustand ist immer 0-äquivalent zu jedem Endzustand?

Und zwei Endzustände sind immer k-äquivalent zueinander?

Oder müsste ich die Endzustände auch nochmal untereinander auf Äquivalenz untersuchen wie alle anderen Paare auch mit X0, X1 ...etc ?

 

Answer 1

Das stimmt so nicht wie du das schreibst. Für 0-Äquivalenz gilt, dass alle Nichtendzustände äquivalent sind und alle Endzustände sind äquivalent, deswegen gibt es auch bei 0-Äquivalenz immer 2 Mengen: {alle Endzustände}, {alle Nichtendzustände}.

Zwei Endzustände sind auch nicht k-äquivalent, k-äquivalent sind nur alle Zustandspaare, bei denen man nach Eingabe aller möglichen Wörter mit einer Länge <= k wieder in 2 Endzuständen oder 2 Nichtendzuständen landet.

Wenn du schon die Minimierungstabelle aufgestellt hast, gibt es eine Art Algorithmus wie man 1-,2-,3-,... äquivalente Zustände findet. 1-äquivalent sind alle Zustandspaare, bei denen in der Tabelle X2, X3 oder höher steht (oder natürlich auch gar nichts wenn sie ganz äquivalent sind). 2-äquivalent wären dann alle Zustandspaare, bei denen in der Tabelle X3, X4 oder höher steht und so weiter.

Ich hoffe, dass ich dir damit helfen konnte.

Viele Grüße

Patrick (Tutor)