Verständnisprobleme A27 c)

Question

Hallo zsm,

 

leider verstehe ich so gar nicht, wie man bei den Mengen äquivalenter Zustände vorgehen muss, obwohl ich mir schon unzählige Forumsbeiträge hier durchgelesen habe...

 

Wäre jemand so nett und könnte das nochmal Schritt für Schritt erklären, wieso man am Anfang die zueinander äquivalenten Zustände in eine Menge schreibt und die restlichen in eine andere und diese dann weiter aufgeteilt werden ?

Eine MArkierung X0 in einem Feld heisst ja gerade, dass diese 2  Zustände NICHT X0 äquivalent zueinander sind oder ?

 

Mfg

Answer 1

Bei der Zustands-Äquivalenz geht es ja darum, den Automaten zu minimieren. Dabei will man alle Zustände zusammenfassen, die zueinander äquivalent sind, also für dieselben Eingaben in denselben Akzeptanzzustand führen (akzeptiert vs. nicht akzeptiert). Wenn wir den Minimierungsalgorithmus durchführen, dann bertrachten wir erst End- und Nichtendzustände, weil diese jeweils zueinander offenbar nicht äquivalent sein können (sie haben ja schon für die Wortlänge 0 ein unterschiedliches Akzeptanzverhalten). Das ist daher immer die erste (0-äquivalente) Aufteilung. Danach betrachten wir, welche Zustände bei Eingabe von Wörtern der Länge 1, 2 usw. nicht zueinander äquivalent sind (das sind die 1, 2 usw. -Äquivalenzen). Bei jedem dieser Schritte spalten wir die Zustände auseinander, die in diesem Schritt nicht mehr k-äquivalent sind.

Betrachten wir als Beispiel diesen Automaten: 

Im ersten Schritt unterscheiden wir End- und Nichtendzustände, das sind genau die Paare, die in der Minimierungstabelle mit $X_0$ gekennzeichnet sind:

0: $\{s_0\}, \{s_1, \ldots, s_4\}$.

Im zweiten Schritt betrachten wir die mit $X_1$ markierten Paare, diese sind für Wörter der Länge höchstens 1 nicht äquivalent (die schon aufgespaltenen bleiben natürlich aufgespalten):

1: $\{s_0\}, \{s_1\}, \{s_2, \ldots, s_4\}$.

Im nächsten Schritt betrachten wir die Wortlänge 2, also die mit $X_2$ markierten Paare:

2: $\{s_0\}, \{s_1\}, \{s_3\}, \{s_2, s_4\}$.

Da in der Tabelle kein Index höher als 2 ist müssen wir längere Wörter nicht betrachten und sind fertig. Die Aussage des Algorithmus ist nun, dass die Zustände $s_2$ und $s_4$ zueinander äquivalent sind, weil sie für Wörter beliebiger Länge zum selben Akzeptanzverhalten führen. Sie können also zusammengefasst werden.

Wird es dadurch klarer?

Comments

Vielen Dank !:)