Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2012-H-01

Beantwortet: Ausdruck geschweifte Klammer

Sun, 02 Feb 2020 11:22:31 +0000

Hallo,

bei der 1-Äquivalenz hast du innerhalb der {} immer die Zustände die nach dem Vergleichen der "2. Ebene von hinten" noch gleich sein können.

Mengen 1-äquivalenter Zustände: {s0, s3, s4}, {s1}, {s2}, {s5}

Hier bedeutet es dass s0,s3,s4 bei dem rekursiven betrachten von 2 Zuständen ausgehend vom Endzustand immer noch keinen Unterschied aufgezeigt haben, wohingegen s1 zu allen anderen Unterschiedlich ist (s2 und s5 sind auch zu allen anderen unterschiedlich). Vom Prinzip her schaust du immer wo noch keine Einträge sind und schreibst die beiden Zustände die noch keinen X? drin stehen haben in eine Klammer. Sind es mehrere die in einer Zeile/Spalte kein X? drin stehen haben schreibst du diese in eine {}.

Constantin (Tutor)

Beantwortet: Aufgabe 1 a)

Wed, 27 Jan 2016 07:46:33 +0000

Hallo,

soweit wie ich das verstehe, glaube ich dass dir ein kleine Denkfehler unterlaufen ist.

Die Minimierungstabelle zeigt die nicht-äquivaventen Zustände an, bedeutet wenn bei s2 in jedem Kästchen ein x0 steht, dann ist s2 nicht-0-äquivalent zu den anderen Zuständen und damit einzeln in eine {} zu schreiben.

Gleiches gilt für s1 und s5, bei denen überall maximal ein s1 drin steht, bedeutet sie sind nicht-1-äquivalent, also einzeln in die Klammern zu fassen.

( Zitat Tutorium 1 S.20: "Ein Algorithmus kennzeichnet zunächst alle Zustandspaare, die nicht 0-äquivalent, dann nicht 1-äquivalent usw. sind, wobei die Zahl 0, 1, … für die minimale Wortlänge steht, für die die Zustände sich unterscheiden.")

Vieel Grüße,

Marc (Tutor)

Beantwortet: Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

Fri, 25 Sep 2015 10:22:31 +0000

ist alpha = (11)*0(11)*00*(10*1)*

korrekt?

Das Testwort 1101100 was bei der ganz ähnlichen Lösung nicht darstellbar ist würde hier zumindest funktionieren...

Beantwortet: wieso bilden für k=1 s1 und s5 nicht eine eigene Menge?

Fri, 25 Sep 2015 10:19:50 +0000

Hallo,

weil in dem Minimierungstableau das Kästchen "s1/s5" mit einem X1 markiert ist, also nicht 1-äquivalent ist.

Viele Grüße

Christiane (Tutorin)

Beantwortet: b): Wieso ist hier F= s0,s1,s3,s4,s5 ?

Fri, 25 Sep 2015 10:18:44 +0000

Aus dem Verfahren zur Minimierung endlicher Automaten weiß man, dass in einem Feld genau dann X0 steht, wenn genau einer der beiden Zustände ein Endzustand ist. Wenn ein Feld also leer ist oder Xi mit i>0 darin steht, dann weiß man dadurch, dass entweder beide Zustände Endzustand oder keiner der beiden Endzustand ist. Damit kommt man dann auf alternativen Endzustände.

Hinweis: die Sprache, die der EA akzeptiert, wird im Allgemeinen natürlich von den Endzuständen abhängen, aber um die akzeptierte Sprache geht es in diesem Aufgabenteil nicht...

Tobias (Tutor)

Beantwortet: Erklärung zu Mengen der k-äquivalenten zustände?

Fri, 25 Sep 2015 10:17:30 +0000

Hallo,

schau dir einmal die in der Aufgabe gegebene Minimierungstabelle an. Die Einträge in dieser Tabelle bedeuten jeweils, dass zwei Zustände nicht k-Äquivalent sind, wenn in dem entsprechenden Kästchen x_k eingetragen ist. Also sind beispielsweise zwei Zustände, bei denen in der Tabelle x_0 vermerkt ist nicht 0-Äquivalent.

Wie du siehst, ist S2 nicht 0-Äquivalent zu allen anderen Zuständen. Deshalb muss es bei der Angabe aller 0-Äquivalenten Zustände in einer eigenen Mengenklammer erfasst werden. Alle anderen Zustände sind 0-Äquivalent und stehen deshalb in der gleichen Mengenklammer.

Im nächsten Schritt betrachtest du nun die 1-Äquivalenz. Da S2 schon nicht 0-Äquivalent zu allen anderen Zuständen war, ist es auch auf keinen Fall 1-Äquivalent zu den anderen Zuständen und muss daher wieder in eine eigene Menge genommen werden. Weiterhin sind S1 und S5 nicht 1-Äquivalent zu den übrigen Zuständen und müssen deshalb auch jeweils eine eigene Mengen bilden... usw...

Viele Grüße

Lukas (Tutor)