unendlich viele paarware nicht äquivalente Wörter |
08.07.2007, 14:46 | habeeinefrage_ | Auf diesen Beitrag antworten » | ||||
unendlich viele paarware nicht äquivalente Wörter gehört zwar eigentlich zur Theoretischen Informatik, hat aber vllt. doch ein bisschen mit Mathe zu tun. Kann mir jemand sagen, wie ich für eine Sprache zeige, das die jeweilige Relation unendlich viele Äquivalenzklassen hat? z.B für {a^2n | n>=0 } oder {w1^n | w€{0,1}* hat Länge n} Danke schonmal im Voraus |
||||||
08.07.2007, 15:16 | kiste | Auf diesen Beitrag antworten » | ||||
Zuerst solltest du einmal sagen wie die Relation definiert ist. Da ich denke das es um den Satz von Myhill-Nerode geht ist sie folgendermassen definiert?: Naja die erste Sprache ist ja regulär hat in dem Fall nur 2 Äquivalenzklassen. Bei der zweiten kann man leicht unendlich viele angeben wenn man die folge der 0en anschaut. [0],[0^2],[0^3],.. sind unendlich viele. |
||||||
08.07.2007, 21:12 | habeeinefrage_ | Auf diesen Beitrag antworten » | ||||
danke schonmal aber bei der ersten sollte das a^2^n heißen Wo siehst du denn die 0 Folge? |
||||||
08.07.2007, 21:32 | kiste | Auf diesen Beitrag antworten » | ||||
Naja die Nullen beim Zweiten hab ich als Id genommen. Im Grunde genommen sind in diesen Äquivalenzklassen genau die Teilworte die nicht mit 1 enden und die gleiche Länge haben. Bspw. ist . Beim ersten ist es genauso einfach. Stell dir doch einmal vor was die Äquivalenzklassen aussagen. Du hast ein einelementiges Alphabet und brauchst immer mehr a's damit es in die Form a^2^n kommt, z.B. a und aaa brauchen beide ein a um auf die Form zu kommen aber wenn du 3 a's hinzufügst ist zwar a^4 in der Sprache a^6 aber nicht. Welche Äquivalenzklassen gibt es also? PS: Geht es nicht genauso einfach, wenn nicht einfacher, mit dem Pumping-Lemma? |
||||||
08.07.2007, 21:41 | habeeinefrage_ | Auf diesen Beitrag antworten » | ||||
Gut möglich, in der Aufgabe sollen wir es aber so machen, und ich versteh das noch nicht so wirklich :/ a^2^1 = aa a^2^2 = aaaa a^2^3 = aaaaaaaa a^2^4 = aaaaaaaaaaaaaaaa ... wäre das so richtig? falls ja wie geb ich das jetzt allgemein an (ohne ... ) |
||||||
08.07.2007, 21:45 | kiste | Auf diesen Beitrag antworten » | ||||
Und in welcher dieser Äquivalenzklassen ist jetzt das Wort aaa? Aber naja es reicht ja eine Teilmenge aller Äquivalenzklassen um zu zeigen das es unendlich viele sind von daher ist deine Lösung ja richtig und du hättest mit [a^2^n] unendlich viele Äquivalenzklassen. Warum sind diese Klassen jetzt disjunkt? |
||||||
Anzeige | ||||||
|
||||||
08.07.2007, 21:54 | habeeinefrage_ | Auf diesen Beitrag antworten » | ||||
Ich dachte aaa ist nicht möglich und daher in keiner Klasse ? Ich denke die sind disjunkt, da keiner eine Teilmenge einer anderen ist. Ich hab da nochmal zwei solche Aufgaben, und zwar w € {0,1}* | w=x0y und |x|=|y|} wären diese Klassen richtig? 0 01010 10010 ... nur wie finde ich da jetzt eine allgemeine Klasse für alle Wörter? und {ww | w € {0,1}* } 00 11 0101 1111 ... hier habe ich genau das gleiche Problem Wär super wenn du mir da auch noch helfen kannst |
||||||
08.07.2007, 22:01 | kiste | Auf diesen Beitrag antworten » | ||||
Bevor wir uns den 2 neuen Sprachen zuwenden versteh erst mal die ersten beiden dann schaffst du die neuen vllt. alleine. aaa ist zwar kein Wort der Sprache aber das muss es auch nicht. Es muss nur die Nerode-Relation erfüllt sein. Das heißt alle Wörter in der Äquivalenzklasse [aaa] müssen mit einem beliebigen Wort konkateniert entweder in der Sprache sein oder auch nicht. So ist aaa konkateniert mit a in der Sprache. Gibt es noch ein anderes Wort das konkateniert mit a in der Sprache liegt? Liegen die beiden in der selben Äquivalenzklasse? Die Begründung das sie disjunkt sind ist falsch aber vllt. erkennst du die Begründung ja an dem Beispiel mit aaa. PS: 2 Mengen können nicht Teilmenge einer anderen sein und trotzdem nicht disjunkt sein. Beispiel {a,b} und {b,c}. |
||||||
08.07.2007, 22:08 | habeeinefrage_ | Auf diesen Beitrag antworten » | ||||
Ja, a, aaaaaaa, aaaaaaaaaaaaaaa Ich denke das sie nicht in der selben Äquivalenzklasse liegen |
||||||
08.07.2007, 22:10 | kiste | Auf diesen Beitrag antworten » | ||||
Genau das stimmt, aber warum liegen sie nicht in derselben Äquivalenzklasse? Hinweis: 2^n ist monoton wachsend |
||||||
08.07.2007, 22:12 | habeeinefrage_ | Auf diesen Beitrag antworten » | ||||
Weil sie paarweise nicht äquivalent sind? (den hinweis versteh ich aber nicht) |
||||||
08.07.2007, 22:18 | kiste | Auf diesen Beitrag antworten » | ||||
Naja sie sind ja nicht äquivalent da man immer mehr a's brauchen wird da 2^n monoton steigend ist. D.h. 2 Wörter können gar nicht äquivalent sein. Daraus folgt das jede Folge von a's eine eigene Äquivalenzklasse ist. Verstanden? Dann versuch einmal für deine neuen Sprachen Äquivalenzklassen anzugeben und zu begründen warum du diese genommen hast |
||||||
08.07.2007, 22:29 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
ok, also w € {0,1}* | w=x0y und |x|=|y|} 0 01010 10010 ... Da ist auch jedes (mögliche) Wort eine eigene Klasse, da das ja auch immer mehr werden und sie so nicht äquivalent sein können. Nur wie finde ich da jetzt eine allgemeine Klasse bzw. 2 Wörter die jeweils alle Wörter ausdrücken die nicht äquivalent sind? |
||||||
08.07.2007, 22:35 | kiste | Auf diesen Beitrag antworten » | ||||
Nein jedes Wort ist nicht eine eigene Klasse, so sind z.B. 01 und 11 in derselben Klasse oder meintest du nur die Worte in der Sprache? Aber du kannst z.B. unendlich viele Klasse angeben wenn du nur die Folge der Einsen betrachtest. Du musst ja nur unendlich viele finden nicht alle Äquivalenzklassen also reicht es die Äquivalenzklassen [1^n] zu nehmen die ja disjunkt sind(Warum?) |
||||||
08.07.2007, 22:40 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
sie sind disjunkt, da es immer eine 1 mehr wird, und somit nicht zwei in der selben Klasse sind, richtig? Kann ich die selben Klassen ( [1^n] ) dann auch als Antwort für {ww | w € {0,1}* } nehmen? da steckt ja auch 1^n drinn |
||||||
08.07.2007, 22:45 | kiste | Auf diesen Beitrag antworten » | ||||
Nein sie sind disjunkt den wenn man eine 0 anfügt braucht man auch genauso viele Zeichen nach der 0, sie können also nicht äquivalent sein. [1^n] kannst du dort nicht benutzen da das hier nur die Klassen disjunkten Klassen [1] und [11] ergibt. Den entweder ist es eine ungerade Anzahl oder eine gerade Anzahl von 1sen. Je nach dem braucht man eine ungerade bzw. gerade Anzahl damit es in der Sprache liegt. 1 und 111 sind also z.b. äquivalent |
||||||
08.07.2007, 22:53 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
und wie mache ich das da dann? ich sehe bei den Wörtern irgendwie (außer der 0 in der Mitte) keine großen Gemeinsamkeiten |
||||||
08.07.2007, 23:02 | kiste | Auf diesen Beitrag antworten » | ||||
Bei der mit der 0 in der Mitte ist [1^n] ja auch richtig nur bei eben nicht. Versuch das letzte einmal selbst bringt dir ja nicht viel wenn ich dir alles angebe. Denk dir einfach ein paar Wörter aus und zeige das sie eben äquivalent oder nicht äquivalent sind vllt. findest du dann Regelmässigkeiten und unendlich viele Äquivalenzklassen. |
||||||
08.07.2007, 23:21 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
Sorry mein Fehler :/ Hatte an die eine Aufgabe gedacht, aber über die andere geschrieben... Einige Wörter wären: 00 0000 000000 11 1111 111111 also (00)^n (oder auch (11)^n ) wären jeweils disjunkt, da es immer mehr werden richtig? |
||||||
08.07.2007, 23:30 | kiste | Auf diesen Beitrag antworten » | ||||
Denke eher an gemischte Wörter nicht die mit nur einem Buchstaben. 00 und 0000 sind äquivalent genauso wie (00)^n bzw. (11)^n jeweils nur eine Äquivalenzklasse sind, warum sollten sie den disjunkt sein? |
||||||
08.07.2007, 23:32 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
hmm kannst du mir erklären, wieso 0^n unendlich viele Klassen gibt, und (00)^n nicht? |
||||||
08.07.2007, 23:39 | kiste | Auf diesen Beitrag antworten » | ||||
Nein den 0^n gibt nur 2 Äquivalenzklasse, die mit gerader Anzahl und die mit ungerader Anzahl an nullen äquivalent zur Begründung oben warum 1^n nicht unendlich viele Äquivalenzklassen ergibt. Warum denkst du den das es unendlich Klassen gibt? |
||||||
08.07.2007, 23:46 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
Ich dachte das, weil du geschrieben hast "Bei der zweiten kann man leicht unendlich viele angeben wenn man die folge der 0en anschaut. [0],[0^2],[0^3],.. sind unendlich viele." |
||||||
08.07.2007, 23:47 | kiste | Auf diesen Beitrag antworten » | ||||
Das war aber für die Sprache {w1^n | w€{0,1}* hat Länge n} |
||||||
08.07.2007, 23:49 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
Ja schon, aber ich dachte das gilt allgemein :/ |
||||||
08.07.2007, 23:52 | kiste | Auf diesen Beitrag antworten » | ||||
Wenn das allgemein gelten würde wäre jede Sprache über dem Alphabet {0} _nicht_ regulär edit: ein wichtiges nicht vergessen |
||||||
08.07.2007, 23:56 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
stimmt, wär irgendwie komisch kannst du mir nochmal erklären, warum es manchmal gilt und manchmal nicht? |
||||||
09.07.2007, 00:00 | kiste | Auf diesen Beitrag antworten » | ||||
Das liegt an der Definition der Relation L ist hier deine Sprache. Da die Äquivalenzklasse genau die Wörter enthält die äquivalent sind und die Äquivalenz der Wörter von der Sprache abhängt kann man keine allgemeinen Aussagen machen |
||||||
09.07.2007, 00:06 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
kannst du mir dann bei dieser Sprache nochmal weiterhelfen, weil ich kann da viele Wörter aufzählen, komm da aber trotzdem nicht weiter 0101 1010 010010 wären z.B einige Wörter wo nicht nur die selben Zahlen beinhalten |
||||||
09.07.2007, 00:09 | kiste | Auf diesen Beitrag antworten » | ||||
Mit Wörter meinte ich nicht Wörter der Sprache sondern von , also Elemente der Äquivalenzklassen. Was ist z.B. mit 0,01, 10, 011, usw.? |
||||||
09.07.2007, 00:12 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
Ja damit kann ich dann beliebige Wörter mit 0en und 1en machen |
||||||
09.07.2007, 00:17 | kiste | Auf diesen Beitrag antworten » | ||||
Ja aber es geht doch nicht um wieviele Wörter es gibt sondern wieviele Äquivalenzklassen. Versuche ein paar Wörter Klassen zuzuordnen die disjunkt sind!, und versuche dann damit unendlich viele Äquivalenzklassen zu finden. Das ganze ist im Grunde nicht schwer ich glaube bloß du hast zentrale Begriffe wie Relation und Äquivalenzklasse noch nicht verstanden |
||||||
09.07.2007, 00:24 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
[0]=[00]=[000]=.. [1]=[11]=[111]=.. nur wie komme ich jetzt auf unendlich viele? |
||||||
09.07.2007, 00:27 | kiste | Auf diesen Beitrag antworten » | ||||
00 liegt doch in der Sprache und 0 nicht, also können die beiden nicht äquivalent sein, ergo sind auch die beiden Äquivalenzklassen nicht gleich. Ich geb dir jetzt einfach mal die Äquivalenzklassen an die ich mir gedacht hab weil ich bald schlafen will Was ist den mit [01^n]? Warum sind diese Klassen disjunkt? |
||||||
09.07.2007, 00:53 | habeeinefrage | Auf diesen Beitrag antworten » | ||||
Will dich daran nicht hindern Ich danke dir auf jeden Fall für deine (sehr lange) Hilfe, ich werd mir das jetzt nochmal durchschauen, vllt. wirds mir dann auch noch klarer. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |