Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
MyhillNerode I-5 aus 2003/04/1
gegeben ist eine sprache L aller doppelwoerter,
wenn w ε Σ*, dann ww ε L.
der satz von myhill nerode verlangt ja nur, dass es unendlich viele aequivalenzklassen gibt, welche das genau sind ist egal.
z.b. sind [ab^ia] fuer i aus N unendlich viele Aequivalenzklassen.
[aba], (die klasse, deren woerter mit anhaengen eines b’s zur sprache L gehoeren)
[abba], (dito mit zwei b’s)
[abbba], (dito mit drei b’s)
.
.
.
folgt also, dass der index dieser relation unendlich ist, und weiter, dass L nicht regulaer ist
der automat braeuchte dann unendlich viele zustaende. siehe schoenig s.44
S → aT
T → bU
U → bU | a
also irgendwas kann da nicht stimmen…
ahem, auf was willst du hinaus?
die sprache (ab+a) hat mit L soweit ich das beurteilen kann relativ wenig zu tun …
Deine Grammatik erzeugt abbba das ist kein Doppelwort, zudem umfasst sie
nicht alle Doppelwörter, sondern nur eine kleine Teilmenge davon.
Ich hatte das so verstanden, dass ab^ia nicht regulär sein sollte. Was das allerdings mit den Doppelwörtern zu tun hat, weiss ich auch nicht 
ach ho LOL :^)
Die bloße existenz von Äquivalenzrelationen rechtfertigt nicht, dass diese auch elementfremd sind.
zu zeigen ist also noch:
([ab^i a] ≠ [ab^j a]) ∀(i ≠ j):
a b^i a a b^i a ∈ L := {ww| w∈Σ*}
a b^j a a b^i a !∈ L (nicht Elem) , falls i≠j
=> Es existieren ∞ viele verschiedene Äquivrel.
Das oben müssen aber nicht alle sein!
? wie die existenz von aequivalenzrelationen rechtfertigt nicht, dass sie elementfremd ist ?
die im satz benutzte aequivalenzrelation ist genau definiert, und ja, aequivalenzrelationen erzeugen disjunkte partitionen. 
somit auch Rl
nimm z.b. mal [aba] und [abba]. aba und abba sind die repraesentanten zweier aequivalenzklassen, die mich an sich ueberhaupt nicht interessieren. was ich definitiv weiss ist dass sie disjunkt sind und dass es davon unendlich viele gibt.
[aba] ist die menge aller woerter, denen genau ein b zur mitgliedschaft in L fehlt.
[abba] ist die menge aller woerter, denen genau zwei b zur mitgliedschaft in L fehlen.
du kannst a und b auch vertauschen, erst mal in die waschmaschine und dann eventuell in den trockner stecken der punkt ist nur, dass es davon beliebig viele gibt. ich will ja gar nicht alle wissen (es sei denn, ich sollte zeigen, dass die untersuchte sprache regulaer ist…)
Kommt jetzt drauf an, was Du meinst:
a) unendlich viele Ä-Klassen
b) unendlich viele Elemente in den Ä-Klassen
a - man muss beweisen, dass es unendlich viele Ä-Klassen gibt,
Du hast erst zwei bewiesen - formal sieht das dann wie Antipythagoras aus.
b - bringt nix.
w ε [ab^ia] gdw wb^i ε L, i ε N – formal genug?
ich haett ja scho lust, die beweis-spezialwoerter anzubringen („offensichtlich“, „trivial“, „oBdA“, …)
ich kapier das irgendwie net:
das letzte wort muesste doch aequivalenzklassen heissen?
Äquivalenzklassen gehört da hin.
wenn Dein i ungerade ist isses falsch
Ups, ja, muss Aquiklassen heissen.
des mit dem ungerade musst du bitte erklären
In der Klasse [aba] liegt das Wort „aba“ und das Wort „abbab“, die man beide durch Anfügen eines b’s zu Doppelwörtern machen kann.
Aber:
Durch Anhängen von „aba“ lässt sich das Wort „aba“ wiederum zu einem Doppelwort machen, („aba“+„aba“ = „abaaba“) jedoch nicht „abbab“ („abbab“+„aba“ = „abbababa“).
Daher sind sie nicht beide in der Ä-Klasse [aba].
Somit ist „die klasse, deren woerter mit anhaengen eines b’s zur sprache L gehoeren“ keine Äquivalenzklasse und man kann den Satz von Myhill-Nerode nicht anwenden.
Beim Aussuchen der Äquivalenzklassen kann man ziemlich viele Fehler machen, deswegen würde ich eher Pumpen empfehlen.
Naja, aber wie oben gezeigt, Existieren (mindestens) unendlich viele Äquiklassen.
(Ich hab ja gezeigt, dass [ab^ia] paarweise verschieden sind,
also gibt es so viele (dieser Form) wie es Zahlen in N gibt)
Dies sind möglicherweise nicht alle Äk aber genug (“≥∞”) um zu zeigen, dass es nicht regulär ist → Satz von Myhill Nerode
wenn man diesen weg für die ÄKs sofort sieht, ist der Beweis mit Satz von M-N hier kürzer.
Wo wir gerade bei “Myhill-Nerode nicht anwenbar” sind…
Ich behaupte:
Man kann jede nicht reguläre Sprache mit Myhill-Nerode entlarven.
Satz von Myhill, Nerode:
Eine Sprache L ist genau dann regulär, wenn der Index von R_L
endlich ist.
Ob es umständlich oder einfach ist, steht auf einem ganz anderen
Blatt.
Das Pumping Lemma hingegen, erwischt nicht jede Sprache,
die nicht-regulär ist.
sehr cool jetzt bin ich verwirrt … :-p
ist doch schwieriger als ich zunaechst dachte … yo thx an alle.
@heyhan: das musst du nicht behaupten des is so
lob@elzo! du bist wohl der einzige, der das richtig gerafft hat und dank dir ich jetzt auch! thx!
Kommt schon Leute, diskutiert weiter ueber die Aequivalenzklassen
Wir könnten auch mit Eloquenzklassen weitermachen :o)
Also ich würde sagen nur wenige Leute sind in meiner - ob ich allerdings am Ende einer Reihe in einer artinschen oder noetherschen Ordnung stehe…