Verständnis zur k-Äquivalenz

Question

Hallo,

irgendwie komme ich bei der k-Äquivalenz immer durcheinander, deshalb möchte ich mal fragen, ob ich die Definition richtig verstanden habe:

Als Ausgangspunkt habe ich einen EA A mit den Zuständen S und den dazugehörigen reduzierten Automaten A' mit den Zuständen S'.
Ein beliebiger Zustand a aus S und ein beliebiger Zustand b aus S' heißen k-äquivalent, wenn ich von beiden Zuständen a,b durch die Eingabe eines Wortes w (\( |w| \leq k\) ) sowohl bei A als auch bei A' in einen Endzustand gelange?

Wenn A und A' mehrere Endzustände haben, muss man dann in beiden Automaten in den gleichen Endzustand gelangen, damit die Zustände k-äquivalent sind oder reicht es aus, dass man überhaupt in einen Endzustand gelangt (sprich in bin in A in einem anderen Endzustand als in A')

Habe gerade auf Folie 2-34 gesehen, dass man die Definition der k-Äquivalen auch auf zwei verschiedene Zustände von ein- und demselben Automaten anwendbar ist.
Auch hier ist meine Frage, ob man bei mehreren Endzuständen durch das Wort in den gleichen Endzustand gelangen muss oder ob es egal ist in welchen Endzustand man gelangt, damit die beiden Zustän k-äquivalent sind

Danke und Gruß

 

Answer 1

Hallo,

zunächst geht es eigentlich nur um einen Automaten. Der reduzierte Automat A' fasst dann lediglich die im Automaten A äquivalenten (also k = unendlich) Zustände zusammen.

Das Ganze funktioniert immer rekursiv. Das heißt, du startest bei k = 0. Hier geht es darum, dass zwei Zustände 0-äquivalent sind, wenn sie entweder beide Endzustände sind, oder wenn sie beide Nicht-Endzustände sind.

Alles weitere lässt sich hierauf zurückführen.

Bsp: Von Zustand 1 gelange ich durch Eingabe 0 auf Zustand 1a und durch Eingabe 1 auf Zustand 1b.

Von Zustand 2 gelange ich durch Eingabe 0 auf Zustand 2a und durch Eingabe 1 auf Zustand 2b.

Die Eingabe hat die Länge eins. Wenn jetzt sowohl 1a und 2a 0-äquivalent sind, als auch 1b und 2b (es muss aber nicht "über kreuz" funktionieren), dann sind Zustand 1 und 2 1-äquivalent (du konntest, ausgehend von Zustand 1 und 2 einen Schritt gehen, ohne die 0-äquivalenz zu verlieren).

In dieser Weise erweiterst du dein Wort. Wenn sich an der k-äquivalenz nichts mehr ändert, dann weißt du von allen, die auf der höchsten Stufe sind, dass sie eben auch äquivalent sind.

Also kommst du mit diesen Zuständen, unabhängig von der Eingabe, auf das gleiche Ergebnis - sie sind somit redundant und können ausgelassen werden.

Ich hoffe, ich konnte dir ein wenig weiterhelfen.

Viele Grüße

Philippe (Tutor)