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

Wie kommt man vom Zustandsübergangsdiagramm des Automaten auf die Tabelle?

0 Punkte
622 Aufrufe

Hallo,

könnte jemand freundlicherweise erklären, wie man vom Zustandsübergangsdiagramm des Automaten auf die Tabelle kommt?

Vielen Dank!

 

Gefragt 22, Sep 2015 in AU-1-4 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Nein, meine Frage war wie ich von der Tabelle auf die andere Tabelle mit x1, xo usw komme.
Also von der Zustandsüberführungstabelle auf die Minimierungstabelle

Danke!

2 Antworten

0 Punkte
 
Beste Antwort

Hallo,

Zu euren Fragen:

Der Algorithmus funktioniert im Grunde so

0. Erstelle eine Matrix. schreibe links als Zeilen s0 bis s7 und unten ebenfalls s0 bis s7. Da aber die Paare (si, si) sowieso äquivalent sind, kann man die Diagonale wegstreichen. Den rechten oberen Teil, als die rechte obere Dreiecksmatrix können wir auch wegstreichen, da das Paar (s4, s5) äquivalent ist zu (s5, s4). Wieso ist das so? Nun, weil ich aus den einzelnen Feldern letztendlich nur rauslesen will, ob si und sj äquivalent sind. Ob ich nun (si, sj) oder (sj, si) betrachte ist egal, daher kann ich die obere Dreiecksmatrix weglassen und nur die unteren Dreiecksmatrix betrachten.

1. Wir schauen uns in unserer Zustandstabelle an, welche Zustände alles Endzustände sind. Daraus können wir schlussfolgern, welche Zustände denn alle NICHT miteinander 0-äquivalent sind: Alle Nichtendzustände und Endzustände sind zueinander NICHT 0-äquivalent, also schreiben wir X0 rein.

Konkret: s4 ist Endzustand. s0 aber nicht. Deswegen kommt in das Feld (s4,s0) ein X0 rein.

Und so kriegst du quasi überall wo in der Zeile/Spalte s4 steht, ein X0, da nur s4 Endzustand ist.

2. Nun schauen wir uns in unserer Zustandstabelle an, welche Zustände zum Endzustand führen.

Konkret: Das sind gerade s5, s7

Wir wissen also: Wenn wir einen Schritt von s5 oder s7 aus gehen, landen wir im Endzustand s4. Wenn wir einen Schritt von allen anderen Zuständen aus gehen, dann landen wir in einem Nichtendzustand. Beispiel: s0 landet entweder in s1 oder s3, während s5 in s4 landet. Wenn wir nun in unserer Tabelle gucken, dann stellen wir fest, dass (s1,s4) und (s3,s4) bereits mit X0 gekennzeichnet sind. Das heißt, s0 und s5 sind zueinander NICHT 1-äquivalent, also kommt ein X1 in das Feld (s0,s5) rein.

3. Und so lässt sich das Verfahren immer weiter fortsetzen, bis wir feststellen, dass sich die Tabelle nicht mehr verändert. Die leeren Paare sind gerade die zueinander äquivalenten Paare.

Viele Grüße,

Vivian (Tutor)

 

Beantwortet 22, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Noch 2 kleine Ergänzungem:

- Im nächsten Schritt würde man gucken, welche Zustände alle zu s5, s7 führen und diese Zustände dann wiederum mit den anderen vergleichen.

- Es genügt im Übrigen, sobald man mit EINER Eingabe (0 bzw. 1) in einem nichtäquivalenten Zustandspaar landet. Dann ist das betrachtete Zustandspaar bereits nicht mehr äquivalent.
0 Punkte

hallo,

du musst einfach nur schauen, für welche eingabe( 0 oder 1) du in welchen neuen zustand kommst und das dann einfach in das entsprechende feld eintragen? war das deine frage?:) bin mir nicht sicher.

ich würde allerdings gerne wissen, wie man von der tabelle auf die matriv kommt. beim zustand s2s5 lande ich ja im feld s5s4, was ja außerhalb der matrix ist. wird das dann wie ein bereits markiertes feld behandelt? sonst kann ich mir das x1 nicht erklären...

danke!

 

Beantwortet 22, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...