unendlich viele paarware nicht äquivalente Wörter

Neue Frage »

habeeinefrage_ Auf diesen Beitrag antworten »
unendlich viele paarware nicht äquivalente Wörter
Hallo,

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 smile
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.
habeeinefrage_ Auf diesen Beitrag antworten »

Zitat:
Original von kiste
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.

danke schonmal

aber bei der ersten sollte das a^2^n heißen

Wo siehst du denn die 0 Folge?
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?
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 ... )
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?
 
 
habeeinefrage_ Auf diesen Beitrag antworten »

Zitat:
Original von kiste
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?

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
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}.
habeeinefrage_ Auf diesen Beitrag antworten »

Ja,

a, aaaaaaa, aaaaaaaaaaaaaaa

Ich denke das sie nicht in der selben Äquivalenzklasse liegen
kiste Auf diesen Beitrag antworten »

Genau das stimmt, aber warum liegen sie nicht in derselben Äquivalenzklasse?
Hinweis: 2^n ist monoton wachsend
habeeinefrage_ Auf diesen Beitrag antworten »

Zitat:
Original von kiste
Genau das stimmt, aber warum liegen sie nicht in derselben Äquivalenzklasse?
Hinweis: 2^n ist monoton wachsend

Weil sie paarweise nicht äquivalent sind? (den hinweis versteh ich aber nicht)
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
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?
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?)
habeeinefrage Auf diesen Beitrag antworten »

Zitat:
Original von kiste
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?)

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
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
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
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.
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?
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?
habeeinefrage Auf diesen Beitrag antworten »

Zitat:
Original von kiste
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?

hmm kannst du mir erklären, wieso

0^n unendlich viele Klassen gibt, und

(00)^n nicht?
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?
habeeinefrage Auf diesen Beitrag antworten »

Zitat:
Original von habeeinefrage
Zitat:
Original von kiste
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?)

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

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."
kiste Auf diesen Beitrag antworten »

Das war aber für die Sprache {w1^n | w€{0,1}* hat Länge n} traurig
habeeinefrage Auf diesen Beitrag antworten »

Zitat:
Original von kiste
Das war aber für die Sprache {w1^n | w€{0,1}* hat Länge n} traurig

Ja schon, aber ich dachte das gilt allgemein :/
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
habeeinefrage Auf diesen Beitrag antworten »

Zitat:
Original von kiste
Wenn das allgemein gelten würde wäre jede Sprache über dem Alphabet {0} regulär

stimmt, wär irgendwie komisch

kannst du mir nochmal erklären, warum es manchmal gilt und manchmal nicht?
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
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
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.?
habeeinefrage Auf diesen Beitrag antworten »

Ja damit kann ich dann beliebige Wörter mit 0en und 1en machen
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
habeeinefrage Auf diesen Beitrag antworten »

[0]=[00]=[000]=..
[1]=[11]=[111]=..

nur wie komme ich jetzt auf unendlich viele?
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 Augenzwinkern
Was ist den mit [01^n]? Warum sind diese Klassen disjunkt?
habeeinefrage Auf diesen Beitrag antworten »

Zitat:
Original von kiste

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 Augenzwinkern
Was ist den mit [01^n]? Warum sind diese Klassen disjunkt?

Will dich daran nicht hindern Big Laugh

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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »