0 Daumen
474 Aufrufe

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:

Unbenannt.JPG

Bereits bearbeitet:

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

M'.png

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.

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort
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.

Avatar von 5,6 k

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 z1. Auch jedes der Wörter "111", "001" und "11001" ist ausreichend für z1. 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?

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Antworten
1 Antwort
1 Antwort
Gefragt 11 Mai 2018 von Gast

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community