ab^k wieviele Äquivalenz nach Myhill Neurode?
Ich bin ehrlich gesagt, noch etwas verwirrt, wie das mit Myhill Neurode und diesen Äquivalenzklassen funktioniert.
Eine Sprache L besteht aus ab^k k ist element der Natürlichen Zahlen, von 0 bis n
Wie viele Äquivalenzklassen nach Myhill Neurode gibt es jetzt hier? Die Implizite Fehler Äquivalenzklasse lassen wir weg.
Wie geht man vor:
Erstmal, was sind gültige Wörter der Sprache
a, ab, abb, abbb, abbbb....
In{ } stehen die Wörter, dahinter die Präfixe
{a, ab, abb, abbb, abbbb...} Präfix b
Das selbe wäre möglich für
{a, ab, abb, abbb, abbbb..} Präfix epsilon
{a, ab, abb, abbb, abbbb..} Präfix bb
Wie man sieht stehen in jedem Klammerpaar {....} die selben Wörter.
=> Gibt es jetzt nur "eine" Äquivalenzklasse?
=> Was ist wieder mit epsilon? Bildet dies eine eigene Äquivalenzklasse?
{ epsi} als Präfix a
{epsi} als Präfix ab
{espi} als Präfix abb
...
Gibt es jetzt hier für ab^k eine eigene epsilon Äquivalenzklasse oder gibt es sie nicht?
Ich bin hier ehrlich gesagt ziemlich verwirrt, da ich keine klare Struktur erkenne, wann ich eine eigene epsilon Äquivalenzklasse brauche und wann nicht.
1 Antwort
Also ich sehe bei dir noch ein grundsätzliches Verständnisproblem, was dir womöglich im Weg steht.
Du betrachtest zum Ermitteln der Äquivalenzklassen nicht einzelne Suffixe (das meintest du wohl, nicht Präfixe), sondern du fasst die Wörter zusammen, welche sich durch die selben Suffixe zu Wörtern der Sprache zusammensetzen.
Um bei deinem Muster zu bleiben:
{a, ab, abb, ...} Suffixe {epsilon, b, bb, bbb, ...}.
Schau dir dazu nochmal die formale Definition der Nerode-Relation an.
Betrachten wir mal die Suffixe des Epsilons: {a, ab, abb, ...}. So, du siehst, dass die Suffixmenge anders ist als bei der oberen Äquivalenzklasse. Epsilon ist also in einer anderen.
Die "Fehler-Klasse" hat die Suffixe {}, also keine. Das Epsilon ist also auch nicht in dieser Klasse, sondern bildet eine eigene.
Merke: Zu jeder neuen Suffixmenge, welche man findet, gibt es eine eigene Äquivalenzklasse. Diese Klasse enthält dann die Präfixe (Präfix und Suffix zusammen sind dann in der Sprache)
Ok. Danke! D. h. in dem Bsp. ab^k mit k Element der natürlichen Zahlen gibt es, wenn man es genau nimmt, 3 Äquivalenzklassen:
{a, ab, abb, ...} Suffixe {epsilon, b, bb, bbb, ...}
Suffixe des Epsilons: {a, ab, abb, ...}.
"Fehler-Klasse" hat die Suffixe {}, also keine.
Wenn man es nicht so genau mit der Fehlerklasse nimmt, wie bei uns, gibt es 2 Äquivalenzklassen!