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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

2 Pluspunkte 0 Minuspunkte
149 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
in MIN-AC von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4.3k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
 
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?

von Dozent (10.1m Punkte)  
ausgewählt von uqdrx uqdrx
0 0
Vielen Dank !:)
...