Beantwortet: Erstellung Minimierungstabelle

Sun, 16 Nov 2014 16:41:26 +0000

Ich verstehe dein Verfahren nicht ganz. Was meinst du mit "einen Zustand (S4) markieren"?

In der Dreieckstabelle kann man eigentlich nur eine "Kombination" von 2 Zuständen markieren, z. B. (S1, S4). Das macht auch Sinn, da Äquivalenz bzw. Nicht-Äquivalenz keine Eigenschaft eines einzeln Zustandes ist, sondern immer das Verhältnes von 2 Zuständen beinhaltet.

Das korrekte Verfahren ist (analog zur Vorlesung):

1. Alle Kombinationen von 2 Zuständen mit X0 markieren, von denen GENAU EINER ein Endzustand ist. (2 Endzustände sind 0-äquivalent zu einandern!)

2. alle bisher unmarkierten Kombinationen von 2 Zuständen mit X1 markieren, bei die Eingabe des selben Zeichens in beiden Zuständen zu einer in einer vorherigen Iteration bereits markierten Kombination von Zuständen führt. Beispiel: betrachte die Kombination (S0,S5): gibt man eine 0 ein, so kommt man von S0 zu S6 und von S5 zu S4. (S4,S6) ist bereits mit X0 markiert --> (S0, S5) markieren. (S0, S1) wird nicht mit X1 markiert, da weder (S5,S6) [Eingabe von 0] noch (S0,S3) [Eingabe von 1] mit X0 markiert ist.

3. Schritt 2 solange wiederholen, bis in einer Iteration keine Kombination mehr markiert wurde. Die Zahl hinter dem X bei neu zu markiertenden Zuständen bei jeder Iteration um eins erhöhen.

Zwei Zuständen sind dann äquivalent, wenn ihre Kombination nach Ende des Algorithmuses nicht markiert ist (=leeres Kästchen).

Tobias (Tutor)

Beantwortet: Frage zu Minimierungstabelle und Zustandspaaren

Sun, 16 Nov 2014 16:39:17 +0000

Hallo,

ich bin mir nicht ganz sicher, ob ich deine Frage richtig verstehe, aber wenn du für k=2 das Paar (s0,s1) anguckst, dann landest du bei einer 0 in (s6,s5) und dieses Feld ist leer. Bei einer 1 landest du in (s3,s0) und auch dieses Feld ist zum Zeitpunkt k=2 leer. Du kannst also nichts in das Feld (s1,s2) reinschreiben. Bei (s1,s3) landest du aber bei einer 0 in (s5,s1), welches schon mit X1 markiert ist, daher kannst X2 in (s1,s3) reinschreiben.

Im nächsten Schritt (k=3) guckst du dann nochmal (s0,s1) an und stellst fest, dass du bei einer 1 in (s3,s0) landest. Dieses Feld wurde aber vorher mit X2 markiert. Also kannst du jetzt (s0,s1) mit X3 markieren.

Viele Grüße,

Vivian (Tutor)

Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in MIN-AD

Beantwortet: Erstellung Minimierungstabelle

Beantwortet: Frage zu Minimierungstabelle und Zustandspaaren