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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
159 Aufrufe
Hallo

Wie kommt man in der Tabelle auf die 1-äquivalenz ?

die 0 äquivalenz ist mir klar da wurde doch nur in Menge der Endzustände und nicht endzustände unterteilt ?
in 2014-N-01 von uvlpj uvlpj Lernwillige(r) (510 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo uvlpj,

exakt, bei der 0-Äquivalenz bildet eine Menge die Menge aller Endzustände und die andere Menge ist die Menge aller Nicht-Endzustände.

Bei der 1-Äquivalenz prüfst du für jeden Zustand in der Menge, in welcher Art Zustand du mit den unterschiedlichen Eingaben landest. Schauen wir uns die Menge der Nicht-Endzustände an, also {s0, s1, s7}. Für s0 landest du sowohl für die Eingabe a als auch b in einem Endzustand. Für s1 landest du ebenfalls für die Eingaben a und b in einem Endzustand. Mit s7 landest du für a und b in einem Nicht-Endzustand.
Infolge dessen bilden die Zustände s0 und s1 eine Menge bei der 1-Äquivalenz, der Zustand s7 bildet eine einelementige Menge.
Für die andere Menge verfährst du ebenso.

Ich hoffe, deine Frage hat sich dadurch geklärt, sonst frag noch einmal nach.

Viele Grüße

Hannah (Tutorin)
von uneoo uneoo Eins-Komma-Null-Anwärter(in) (2.4k Punkte)  
0 0
Vielen Dank das macht Sinn
jetzt verstehe ich aber nicht den schritte bei HK 2018 von 1 zu 2-Äquivalenz
Auf die 1-Äquivalenz bin ich gekommen wie du es oben beschrieben hast aber wieso sind jetzt s1 und s5 in einer Menge ?
0 0
Hallo,
ja du hast recht, das ist wirklich komisch. Ich denke, hier ist die Musterlösung falsch und die Zustände s1 und s2 sind vertauscht.
Ich hoffe, jetzt ist es klarer.
Viele Grüße
Hannah
0 0
Okay
kannst du mir vielleicht noch sagen wieso bei der 2 Äquivalenz s0 und s3 in einer Menge sind ohne s1 ?
0 0
Bei der 1-Äquivalenz hast du ja nur die Art des direkt nächsten Zustands für die Eingaben a und b betrachtet. Jetzt schaust du dir die jeweils 2 nächsten Zustände an. Dort gibt es 4 Möglichkeiten: aa, ab, ba, bb. Jetzt "läufst" du diese Wege jeweils von s0, s1 und s3 aus und überprüfst, für welche der Zustände du bei allen 4 Möglichkeiten in derselben Art des "Landezustands" endest. Dies ist in diesem Fall bei s0 und s3 gleich, bei s1 anders.
Es gibt sicher noch eine elegantere oder "offiziellere" Lösung, aber so kannst du es testen.
Viele Grüße
Hannah
0 0
Top vielen vielen Dank
...