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

Schöne Ferien!
 

 

Wie füllt man die Tabelle bzgl. der k-äquivalenz aus?

+1 Punkt
141 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!
Gefragt 28, Jan 2017 in 2015-N-01 von uzdzr uzdzr Lernwillige(r) (220 Punkte)  

2 Antworten

0 Punkte
 
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.

Beantwortet 28, Jan 2017 von Lukas König Dozent (10,065,100 Punkte)  
ausgewählt 28, Jan 2017 von Lukas König
+1 Punkt
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)
Beantwortet 28, Jan 2017 von updrq updrq Tutor(in) (103,620 Punkte)  
...