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

1 Pluspunkt 1 Minuspunkt
99 Aufrufe

Könnte mir noch jemand erklären, warum die Zelle (s0, s1) mit X2 markiert wird?

s0 führt ja auf (s1,s2), was mit X1 markiert ist und s1 führt ebenfalls auf ein mit X1 markiertes Zustandspaar.

Ich dachte man würde ein Kästchen nur mit X2 markieren, wenn eine Komponente auf ein mit X1-markiertes Kästchen zeigt, das andere aber nicht...

Danke schonmal :)

Grüße

 

in MIN-AB von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
 
Beste Antwort

Hallo,

es scheint, als hättest du das Prinzip nicht ganz richtig verstanden oder vermittelt bekommen. Ganz kurz die Idee:

Sind zwei Zustände k-äquivalent, so sind sie auch (k-1)-äquivalent. Umgekehrt gilt also:

Sind zwei Zustände nicht k- äquivalent, so sind sie auch nicht (k+1)-äquivalent.

Wir überprüfen dies also iterativ. Wir betrachte also Schritt für Schritt, ob zwei Zustände bei der selben Eingabe auf ein bis dahin äquivalentes Zustandspaar führen.

Was ist also zu tun:

Zunächst alle Paare von Endzuständen mit Nicht-Endzuständen markieren (Definition von 0-äquivalenz).

Im nächsten Schritt muss für alle Zustandspaare vergleichen, ob ich bei Eingabe von 0 oder 1 auf ein bereits markiertes Feld komme (Betrachte ich zwei Zustände, haben beide einen Übergang für 0, die beiden erreichten Zustände muss ich vergleichen, also das entsprechende Kästchen suchen! Dasselbe gilt für die Eingabe von 1).

Wenn eines der beiden Felder markiert ist, kann keine Äquivalenz vorliegen und die Zustände sind nicht 1-äquivalent. Andernfalls lassen wir das Feld leer. Sind alle Felder verglichen, beginnt die nächste Runde, usw.

Das aber nur kurz die Forumversion, für eine ausführliche Erklärung schau nochmal ins Skript oder frage deinen Tutor.

Gruß,

Adam (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Super, Danke! :)

Dann hätte ich nur noch 2 kurze Fragen:

1. Muss ich beispielsweise die Zelle (s1,s1) betrachten, dann weiß ich, dass die Zelle nicht markiert ist, da die Zustände äquivalent zueinander sind, oder?

2. Du schreibst ja " Wenn eines der beiden Felder markiert ist, kann keine Äquivalenz vorlieren"

Was passiert wenn BEIDE Fehler markiert sind? Dann liegt auch keien Äquivalenz vor, oder?

Danke nochmal!!! :)

Grüße
0 0
Hallo,

zu 1): Ich hab die Frage leider nicht ganz verstanden.

Allgemein: Ein Zustand ist immer zu sich selbst äquivalent, zeigen also zwei Zustände mit derselben Eingabe auf den selben Zustand, ist dieser natürlich äquivalent und es kann selbstverständlich kein Kreuz dastehen. Man kann dann überlegen, dass zwei Zustände äquivalent sind, wenn sie mit der gleichen Eingabe auf denselben Zustand zeigen.

zu 2): Genau, ich hätte sagen müssen "...mindestens eines der beiden Felder markiert..."

Gruß,

Adam (Tutor)
...