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 turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant 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 huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 0 Minuspunkte
32 Aufrufe

Kann mir jm bitte erklären wie man nach der Minimierung eines endlichen Automaten die Menge der 0/1/2 äquivalenten Zustände bestimmen kann? Bin da leider komplett lost.

in MIN-AA von uqgap uqgap Lernwillige(r) (120 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo uqgap,

0-äquivalent sind zwei Mengen, einmal alle Nicht-Endzustände (N.EZ) und einmal alle Endzustände (EZ). Die sind 0-äquivalent, da wenn das Wort enden würde, würde es einmal akzeptiert werden und das andere mal nicht.

1-äquivalent sind alle Zustände (miteinander), die nach einem Zeichen in der gleichen Menge (N.EZ bzw. EZ) sind.

2-äquivalent, wenn die Zustände nach 2 Zeichen noch in der gleichen Menge landen (Z.b. es gibt 0en und 1en wie hier, dann müssen alle Kombinationen  (00, 01, 10, 11) von jeweils zwei Zuständen entweder beide im N.EZ oder im EZ landen, kann auch gemischt sein, aber bei der gleichen Kombi muss es die gleiche Menge sein).

3-äquivalent ...

Man kann das mit der Tabelle machen, man schreibt zuerst z.b. bei k-äquivalent s0 auf und geht dann die Spalte/Zeile durch und schaut,  welcher Zustand ist zu s0 >x_k. Den schreibt man in die Menge. Die nächste Menge beginnt dann mit einem nicht zu s0 k-äquivalenten Zustand.

Ein paar Sachen noch dazu:
- Die einzelnen Mengen werden niemals größer (man braucht also entweder gleich viele Mengenklammern oder mehr)
- Die ganz äquivalenten Zustände sind immer zusammen in einer Mengenklammer
von uvlwv uvlwv Info-Genie (9.4k Punkte)  
...