Äquivalenzklasse zu Minimalautomaten

Question

Aufgabenstellung:

Gegeben sei der DFA \( M=\left(\{0,1\},\left\{z_{0}, \ldots, z_{4}\right\}, z_{0}, \delta,\left\{z_{0}, z_{4}\right\}\right) \) mit \( \delta \) wie folgt:

Bereits bearbeitet:

(a) Bestimmen Sie mit dem Algorithmus der Vorlesung den Minimalautomaten \( M^{\prime} \) zu M.

Aufgabe/Problem:
(b) Bestimmen Sie die Äquivalenzklassen der Myhill-Nerode-Relation zu \( M^{\prime} \). Sie müssen nicht die Teilsprachen der Klassen formal charakterisieren, es reicht aus, einen Repräsentanten anzugeben.

Ich verstehe, glaube ich zumindest, was diese Äquivalenzklassen sein sollen, bin mir jedoch nicht sicher und habe keine Ahnung wie ich das aufschreiben soll.

Answer 1

Sie müssen nicht die Teilsprachen der Klassen formal charakterisieren, es reicht aus, einen Repräsentanten anzugeben.

Gib für jeden Zustand ein Wort an, mit dem man vom Startzustand aus diesen Zustand erreicht.

Comments

Also schreibe ich als beispiel

z' = 11

z1 = 11

z2 = 10

z3 = 00

Aber müsste ich dann bei z2 irgendwie wieder in den endzustand z' kommen, so wie ich es bei z1 = 11 und z3 = 00 gemacht habe?

---

z' = 11

Nein. z' ist ein Zusand, 11 ist ein Wort aus ∑*. Deshalb gehört da kein Gleichheitszeichen hin.

Aber müsste ich dann bei z2 irgendwie wieder in den endzustand z' kommen

Nein. Wie kommst du darauf?

---

Alles klar, demnach wäre also nur "1" auch als Wort ausreichend für z1 und nur "0" für z3?

---

Nein, es ist nicht nur "1" als Wort ausreichend für z₁. Auch jedes der Wörter "111", "001" und "11001" ist ausreichend für z₁. Und noch viele weitere.

---

Eine kurze Frage dazu:

Wir haben ja die Äquivalenzklassen

[0]

[1]

[01]

[10]

Wenn wir nun ein Wort x = 110 bekämen, dann wäre dieses doch in der Äquivalenzklasse [1], da alles nach der Zahl 1 der Suffix ist, oder?