Äquivalenzklassen gemäß Myhill-Nerode genau drei Stück?
1 Reihe, die Wörter sind alle Elemente der Sprache, man würde als Präfix epsi dranhängen. Klar soweit
2 Reihe hier fehlt jeweils ein b, damit die Wörter Elemente der Sprache sind
3 Reihe: alle anderen Wörter. Dies verstehe ich nicht:
{a } hier fehlt ein einzelnes b. Oder ist dieses {a} eigentl. schon in der 2 Reihe dabei?
{ epsi} hier fehlt ab , dies müsste die 3 Reihe darstellen, auch wenn hier steht alle anderen Wörter
Warum gibt es hier "genau" drei Äquivalenzklassen?
Es geht hier um den Satz von Myhill-Nerode
2 Antworten
{a } hier fehlt ein einzelnes b. Oder ist dieses {a} eigentl. schon in der 2 Reihe dabei?
a ist in der zweiten klasse
Die dritte Klasse stellt alle wörter x da, für die es unmöglich ist, ein Suffix y zu finden, sodass xy in der Sprache ist. Zum Beispiel das Wort aa, da du nichts dranhängen kannst, sodass es akzeptiert wird.
Das Beispiel ist aber sowieso fehlerhaft, denn es gibt noch eine 4. Klasse: {Epsilon}
da Epsilon nicht akzeptiert wird, kann es nicht in der ersten Klasse sein.
Wenn du an Epsilon b anhängst (oder bab, babab usw) wird es auch nicht akzeptiert, also kann es nicht in der zweiten Klasse sein.
Wenn du ab anhängst, wird es akzeptiert, also kann es nicht in der dritten Klasse sein. Es muss also eine eigene Klasse bilden.
Wir haben somit 4 Klassen.
Bringt mir nicht wirklich was da ich das Buch nicht besitze. Außerdem können Bücher Fehler enthalten.
Danke für deine Antwort, wenn mich gemäß der Neurode Relation nur die Klassen interessieren, wo man einen Präfix (z. B. z ) an ein Wort x oder y anhängt, so dass xz sowie yz Teil meiner Sprache L sind, somit stehen beide in einer Relation. Dann gibt es wie in diesem Bsp. auch angegeben ist nur genau "drei" Äquivalenzklassen für diese Sprache L.
[ab] mit Präfix epsi
[a oder aba] mit Präfix b
[epsi] mit Präfix ab
Bei der Neurode Relation gibt es eine Äquivalenzklasse derart nicht, dass gilt:
"Alle wörter x da, für die es unmöglich ist, ein Suffix y zu finden, sodass xy in der Sprache ist."
Wenn du eine Menge in Äquivalenzklassen aufteilen willst, brauchst du ALLE Klassen. Auch die, die nicht akzeptiert werden können.
Im Studium haben wir immer nur die Klassen bzgl. Neurode-Relation aufgeführt, die diese erfüllen, dies waren unsere Äquivalenzklassen. Mehr hat der Prof nicht erzählt und auch nicht aufgeführt. Wenn mich nur die interessieren, die die Myhill-Neurode erfüllen, dann sind es drei Äquivalenzklassen. In Wirklichkeit wären es aber vier. Werds mir so merken!
3 Reihe: alle anderen Wörter. Dies verstehe ich nicht:
Vielleicht ist die Menge leer, steht ja nicts weiteres dazu da.
{a } hier fehlt ein einzelnes b. Oder ist dieses {a} eigentl. schon in der 2 Reihe dabei?
Gehört in die zweite Reihe, ja.
Epsilon wäre dann in der dritten Reihe, ja. Dann ist die Menge auch nicht leer.
Warum gibt es hier "genau" nur drei Äquivalenzklassen?
Na weil es nicht mehr gibt. Wo soll denn noch eine herkommen?
Vielleicht ist die Menge leer, steht ja nicts weiteres dazu da.
Äquivalenzklassen können nicht leer sein, da sie immer mindestens einen Repräsentanten haben.
Na weil es nicht mehr gibt. Wo soll denn noch eine herkommen?
Gibt es schon, Epsilon bildet eine eigene Klasse, die nur Epsilon einhält. Es muss somit 4 Klassen geben.
Epsilon ist in der dritten Klasse. Was wäre dann deine vierte Klasse?
EDIT: Achso, du hast noch eine Klasse für den Rest. Ja, das kann sein.
Nein, Epsilon ist in der 4. Klasse.
In der dritten Klasse sind alle präfixe x, für die es kein Suffix y gibt, sodass xy in der Sprache ist.
Also z.b b
Das Bsp. ist aus dem Buch von Dirk W. Hoffmann Theoretische Informatik S. 175, 176 5 Auflage