Äquivalenzklassen

[fake]

iwi steh ich bei dem thema volkommen auf dem schlacuh, kann mir das jemand irgendwie in "einfachen" worten erklären
z.B. die erste aufgabe auf dem zweiten zusätzlichen übungsblatt (fasching), wie geh ich da genau ran, oder die beispielaufgabe auf dem script (seite 143 unten) werden ja die 3 klassen gezeigt, aber ich verstehe einfach nicht wie man drauf kommt >.<
Hoffe jemand ist so nett und kann mir helfen, danke

[Cauchy]

So, da ich hier auch noch ein paar Probleme habe, möchte ich mal eine selbst konstruierte reguläre Sprache posten:


mit anderen Worten:


So, ich hab dann einfach wild mit Beispielen angefangen:

Das Wort liegt zum Beispiel nicht in L, offentlichsich dann auch für alle ,
also ist meine erste Äquivalenzklasse: = <b(a|b)*>[/latex]

So, weiter im Text:
Hab ich ein Wort , dann liegt das offensichtlich nicht in L, so auch dann für alle ,
also ist meine zweite Äquivalenzklasse:

Weiter:
Das Wort ist auch Nerode Äquivalent zu allen Wörtern in <ab(a|b)*>, den egal welches Wort ich dran hänge befindet sich das Wort in L oder eben nicht in L.
Also ist meine dritte Äquivalenzklsse:

So ich hab dann noch die Äquivalentzklasse:


Kann da mal jemand der Ahnung hat drüber gucken?

[fredpape]

[...]
Weiter:
Das Wort ist auch Nerode Äquivalent, den egal welches Wort ich dran hänge befindet sich das Wort in L oder eben nicht in L.
Also ist meine dritte Äquivalenzklsse:
[...]

Vielleicht lese ich das ja nur falsch und ich habe was übersehen, aber was meinst du mit "Das wort ... ist Nerode Äquivalent"?
Die Nerode Äquivalenzrelation ist ja eine binäre Relation mit . Also können immer nur 2 Wörter und nerode-äuivalent sein, nämlich wenn

Sind zwei Wörter nerode äquivalent, so gehören sie ja in die gleiche Klasse. Also würde ich so vorgehen, dass du versuchst ein paar Wörter hinzuschreiben und jeweils zu überprüfen welche davon zueinander nerode äquivalent sind, diese packst du dann in eine Äquivalenzklasse.

[Cauchy]

Ja, Danke!

Da hast du recht! Ich habs oben bereits verbessert. Wäre halt nicht schlecht, wenn da mal jemand das auch probeweiser testen könnte, ob er auf die gleichen Klassen kommt.

[Patric]

Weiter:
Das Wort ist auch Nerode Äquivalent zu allen Wörtern in <ab(a|b)*>, den egal welches Wort ich dran hänge befindet sich das Wort in L oder eben nicht in L.
Also ist meine dritte Äquivalenzklsse:

So ich hab dann noch die Äquivalentzklasse:


Kann da mal jemand der Ahnung hat drüber gucken?

Meiner Meinung nach ist [a] = [ab], du kannst an beide b*a* dran hängen dann sind sie noch in L und wenn du irgendwas mit ab dran hängst sind sie beide nicht mehr in L.
Und es gibt die Klasse [e], da kann man nämlich ab*a* dran hängen und es ist noch im Wort geht sonst mit keiner Klasse.

EDIT: und [aa] = <ab*aa*> nicht wie bei dir da [aa] != [aab]
und = [aab] = <(aab|b)(a|b)*>
und um meine vorheirge Aussage zu unterstüzen: [a] = [ab] = <ab*>

Also habe ich folgende 4 Klassen:
[aa] = <ab*aa*>
= <(aab|b)(a|b)*>
[a] = <ab*>
[e] = <e> (bzw. wie man auf dem übungsblatt sieht <o*>

[Cauchy]

Könnte man nicht [e] und zusammenpacken?
Also dann?
= <(aab|b|e)(a|b)*>

[Thomas]

nein da egal was man an b dranhängt das wort nie in L ist aba wenn man an e einfach a anhängt als beispiel wär das wort in L.

[salami]

Hallo, ich habe auch noch eine Frage zum Thema:

Wieso ist im Beispiel vom Skript [ba] = <a*bb*a(a|b)*> und nicht [ba] = <a*bb*a> ?

[Patric]

weil [ba] alle wörter sind die nie mehr irgendwie in L kommen können weil ein b vor einem a kommt und deswegen muss a|b noch hinten dran weil ja baaaababababababaaabbba auch in der Klasse ist.

[salami]

weil [ba] alle wörter sind die nie mehr irgendwie in L kommen können weil ein b vor einem a kommt und deswegen muss a|b noch hinten dran weil ja baaaababababababaaabbba auch in der Klasse ist.

Hm, ich verstehe nicht ganz..
[a] = <a*>
Wenn man an w € L und an a* etwas anhängt, ist es immer entweder beides aus L oder beides nicht.
z.B. an aaa und aaaaa folgendes anhängen: ab -> aaaab und aaaaaab sind in L
z.B. an aaa und aaaaa folgendes anhängen: ba -> aaaba und aaaaaba sind nicht in L

= <a*bb*>
Hier kann man auch anhängen was man will, es ist immer beides drin oder nicht.
z.B. an aaabb und ab das anhängen: bbb -> aaabbbbb und abbbb sind in L
z.B. an aaabb und ab das anhängen: a -> aaabba und aba sind nicht in L

[ba] = <a*bb*a> bzw. <a*bb*a(a|b)>
Hier kann man anhängen was man will, man kriegt es nie in L rein.
z.B. an aaba und ba das anhängen: aaababababababaaabbba -> aabaaaababababababaaabbba und baaaababababababaaabbba sind beide nicht in L

Wo ist dann der unterschied, ob man das eine oder andere benutzt? Oder mache ich das allgemein falsch?