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
668 Aufrufe

Hallo,

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

Vielen Dank!

 

in AU-1-4 von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
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 Pluspunkte 0 Minuspunkte
 
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)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
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 Pluspunkte 0 Minuspunkte

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!

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...