Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Verständnisprobleme A27 c)

+2 Punkte
89 Aufrufe
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
Gefragt 5, Feb 2016 in MIN-AC von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4,290 Punkte)  

Eine Antwort

+1 Punkt
 
Beste Antwort

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?

Beantwortet 5, Feb 2016 von Lukas König Dozent (10,065,100 Punkte)  
ausgewählt 5, Feb 2016 von uqdrx uqdrx
Vielen Dank !:)
...