Geschrieben von jw.powerplay am 27.02.2013 um 12:55:
Äquivalenzklassen von Nerode Verständnisproblem
Hallo,
ich habe ein Problem beim Verständnis der Nerode Äquivalenzklassen.
Ich wäre Euch sehr dankbar, wenn Ihr mir folgendes Beispiel erläutern/ erklären könntet.
Aufgabe inkl. Lösung gibt es direkt hier. Aufgabe 13.1 a
Zum Verständnis habe ich hier noch die Def.
- Zwei Wörter sind bezüglich der Nerode-Relation äquivalent gdw. sie beide durch exakt die selben Suffixe zu Wörtern der Sprache L ergänzt werden können. (Für mich heißt dass, es gibt verschiedene Wörter. Diese sind dann äquivalent bzgl. der Nerode Äquivalenz, wenn sie durch die selben "Endungen", also durch das Anhängen von dem selbem Wort, so sind, dass sie in L vorkommen. Kann man das so sagen?)
- Die Äquivalenzklasse [x] btgz der Nerode-Relation ist definiert als die Menge aller Wörter y die bzgl der Nerode-Relation äquivalent zu x sind. (???)
Zur Aufgabe:
Meine Denkweise: Da alle Wörter, die als vorletztes Zeichen ein a haben in L2 liegen, können mögliche Äquivalenzklassen [ab] und [aa] sein.
Bitte helft mir