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 schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
178 Aufrufe
Hallo,

mir ist nicht ganz schlüssig, wie man die Tabelle bzgl der k-äquivalenz bei Aufgabenteil b) ausfüllt. Gibt es hier auch ein Schema nachdem man gehen kann, wie bei der Minimierungstabelle?

Danke im Voraus!
in 2015-N-01 von uzdzr uzdzr Lernwillige(r) (220 Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte
 
Beste Antwort

Na, Sie haben ja zuvor schon die Minimierungstabelle ausgefüllt. Dort steht jede Zelle für ein Zustandspaar.

  • Wenn die Zelle leer ist, sind die Zustände äquivalent zueinander, das heißt $k$-äquivalent für alle $k$.
  • Wenn in der Zelle $\times_i$ steht, dann sind die beiden Zustände nicht $i$-äquivalent, aber $i-1$-äquivalent zueinander.

Das heißt also, Sie fangen mit einer Menge an, die alle Zustände enthält (diese können wir ja mal unformal $-1$-äquivalent nennen, damit die obige Beschreibung auch für den $i=0$-fall passt), und trennen diese immer weiter auf. Zuerst beginnen Sie also mit den Zellen, die $\times_0$ enthalten. Das sind Zustandspaare, die zueinander nicht $0$-äquivalent sind. Die entsprechenden Zustände werden also voneinander getrennt, was zu zwei Mengen führt (in diesem Fall die Menge der Endzustände und die Menge der Nicht-Endzustände, für $i=0$ braucht man die Tabelle also noch gar nicht). So erhalten Sie die erste Zeile der Tabelle Dann nehmen Sie sich genauso die $\times_1$-Zellen vor und trennen die Zustände voneinander, die zwar noch $0$-äquivalent waren, aber nicht mehr $1$-äquivalent sind. Dann die $\times_2$-Zellen usw.

In der letzten Zeile sind die Zellen gerade so aufgeteilt, wie die Zustände äquivalent zueinander sind.

von Dozent (10.1m Punkte)  
ausgewählt von
1 Pluspunkt 0 Minuspunkte
Hallo,
wichtig ist dabei, dass du verstehst, was deine Markierungen in der Minimierungstabelle bedeuten. Alle Paare die z.B mit einem X0 markiert sind, sind NICHT X0-äquivalent. Dementsprechend gehst du die Minimierungstabelle nach den einzelnen Äquivalenzen durch und schaust, welche Paare noch nicht markiert sind und somit z.B X0 äquvalent SIND. Bei den X0 äquvalenten sind ja nur alle Kombinationen mit S4 markiert, das heißt S4 ist mit keinem anderen Zustand X0 äquivalent und so weiter.
Grüße Verena (Tutor)
von updrq updrq Tutor(in) (104k Punkte)  
...