Einfache Pumping-Eigenschaft
-
vip@r schrieb:
Ich möchte zeigen, dass die Sprache regulär ist.
Dabei hilft Dir aber das PL nicht.
-
Ich möchte nun für die Sprache L={0n1n |n != m} regularität widerlegen oder beweisen. Das Pumping-Lemma soll aber nicht verwendet werden. Aus welcher Menge n bzw. m stammt ist nicht angegeben. Also gehe ich mal davon aus, dass n,m aus N stammt. Muss ich dafür jetzt einen Automaten bauen? Das sollte aber schwierig werden, da man da mit dem zeichnen nicht mehr fertig wird. Wie soll man dann die evtl. regularität dann widerlegen? Denn ich denke nicht, dass es für diese Sprachen einen Automaten gibt, der die Sprache akzeptiert...
-
Tippfehler in der Sprachdefinition? Das einzelne m sieht strange aus.
-
Oh Sorry! Ja, da is ein Tippfehler. So sieht's aus: L={0n1m |n != m}
-
Was für eine Funktion hat denn das m in dieser Sprachdefinition?Ansonsten kannst du eventuell davon ausgehen, daß 0n1n nicht regulär ist und die regulären Sprachen über Vereinigung und Komplement abgeschlossen sind.(oder du versuchst tatsächlich einen Automaten zu bauen, der die Sprache akzeptiert)
-
Das m gibt doch an wie viele 1 in der Sprache sind und n ist eben ungleich diesem m, wobei das nicht darüber aussagt, ob m kleiner oder größer dem n ist.
-
die regulären Sprachen über Vereinigung und Komplement abgeschlossen sind.
Meinst du damit die Abschlusseigenschaften von regulären Sprachen? Wenn ja, dann sollte mir hier aber die Vereinigung nich so allzuviel bringen weil ich ja keine 2. Sprache hab mit der ich vereinigen könnte. Also bleibt mir nur noch das Komplement.
Also quasi (L)^c.
-
Das mit dem m hat sich inzwischen geklärt, da wart ihr mal wieder zu schnell für mich.
Ansonsten: 0*1* - L = { 0n1n | n aus N }
Edit:
Meinst du damit die Abschlusseigenschaften von regulären Sprachen? Wenn ja, dann sollte mir hier aber die Vereinigung nich so allzuviel bringen weil ich ja keine 2. Sprache hab mit der ich vereinigen könnte.
Was sollte ich sonst meinen, wenn ich "abgeschlossen" sage
Und die Mengendifferenz dort oben kann auf Vereinigung und Komplement zurückgeführt werden.
-
Doch, das geht schon. Das Argument geht so:
Angenommen, L wäre regulär. Dann wäre auch L vereinigt M regulär - und wir wissen, dass L vereinigt M nicht regulär ist. Also kann L nicht regulär sein.
Jetzt musst Du nur eine reguläre Menge M finden, dass das funktioniert.
edit: Jetzt warst Du mal zu schnell
-
Was ist M?
edit: Hier schaut doch die ganz falsche Sprache an, oder?
-
vip@r schrieb:
Was ist M?
In meinem Beispiel wäre das 0*1*
edit: Hier schaut doch die ganz falsche Sprache an, oder?
Wieso? L ist dein 0n1m, daß 0n1n nicht regulär ist, haben wir schon per PL bewiesen.
-
Kannst du vielleicht was ihr da oben geschrieben habt, nochmal genauer für mich formulieren?
-
Ah, ich denke jetzt verstehe ich einigermaßen was ihr mit 0*1* - L = { 0n1n | n aus N } meint. Was ich noch nicht verstehe ist, woher das 0*1* kommt.
-
Wir haben die Sprachen M=0*1* (davon können wir beweisen, daß sie regulär ist), L1={ 0n1n } (da haben wir per PL bewiesen, daß sie nicht regulär ist) und L2={ 0n1m | n!=m }, die wir untersuchen wollen.
Jetzt nehmen wir an, daß L2 regulär ist. Nach den Abschlußeigenschaften ist damit auch L2c und M υ L2c regulär - allerdings ist letzteres gleich L1 und nicht regulär -> Wiederspruch.
-
Danke, deine letzte Antwort hat schon mal einiges Licht ins dunkle gebracht. Jetzt verstehe ich nur noch nicht, warum ihr gerade und vor allem wieso überhaupt auf die Sprache M=0*1* kommt...
-
Nach den Abschlußeigenschaften ist damit auch L2c und M υ L2c regulär
Ist das dann quasi immer so, wenn ich eine Sprache L hab die regulär ist und ich davon das Komplement nehmen, dass dann auch das Komplement regulär ist?
Woher weiß man, dass hier M ∪ L2c regulär ist? Stimmt das so: Wir wissen, besser gesagt wir können beweisen (wdoruch auch immer...) das M regulär ist. Wenn ich nun das reguläre M mit L2c, was wiederum regulär ist, vereinige dann bleibt alles regulär.
-
vip@r schrieb:
Danke, deine letzte Antwort hat schon mal einiges Licht ins dunkle gebracht. Jetzt verstehe ich nur noch nicht, warum ihr gerade und vor allem wieso überhaupt auf die Sprache M=0*1* kommt...
Weil es so schön in die Struktur der anderen beteiligten Sprachen reinpasst
Für diese Details muß man einen Blick entwickeln.vip@r schrieb:
Nach den Abschlußeigenschaften ist damit auch L2c und M υ L2c regulär
Ist das dann quasi immer so, wenn ich eine Sprache L hab die regulär ist und ich davon das Komplement nehmen, dass dann auch das Komplement regulär ist?
Woher weiß man, dass hier M ∪ L2c regulär ist? Stimmt das so: Wir wissen, besser gesagt wir können beweisen (wdoruch auch immer...) das M regulär ist. Wenn ich nun das reguläre M mit L2c, was wiederum regulär ist, vereinige dann bleibt alles regulär.
Wie gesagt, das sind die Abschlußeigenschaften der Klasse "reguläre Sprache": Wenn X und Y regulär sind, sind auch Xc und XυY regulär. (diese Eigenschaften kann man beweisen durch Umformungen der zu den Sprachen gehörenden Automaten)
Der Beweis, daß M regulär ist, ist nun wirklich trivial - du mußt nur einen endlichen Automaten oder einen regulären Ausdruck für die Sprache angeben können - und da ich M durch den zugehörigen regulären Ausdruck beschrieben habe...
-
Ich hab das alles jetzt mal so aufgeschrieben:
L2 = {0n1n | n!= m}
M = {0*1}
L = {0n1n | n aus N} -> durch PL bewiesen, dass unregulärWir nehmen nun an, dass L2 regulär ist. Nach den Abschlusseigenschaften gilt, dass L2c sowie L2cυM ebenfalls regulär ist. Da aber auch L2cυM = L gilt folgt Widerspruch, da L durch PL bewiesen, dass L nicht regulär ist.
Kann man das so als Aufgabenlösung präsentieren? Das PL für die Sprache L haben wir schon desöfteren bewiesen, wodurch ich mir sagen traue, dass ich das hier nicht nocheinmal machen müssen... Was mich aber nach wie vor an der Lösung hier stört, ist, dass es in der Aufgabenstellung heißt, man darf kein PL verwenden. Theoretisch aber muss man aber das PL zum Beweis der Unregularität der Sprache L benutzen!
Ich hab daran jetzt nur 2 Sachen noch nicht verstanden. Warum kommt man auf die Sprache M (gut, hier habt gesagt, dass sind Erfahrungswerte, aber unser Prof. kann 'noch' nicht auf Erfahrungswerte bauen...) und warum ergibt L2cυM = L?
-
vip@r schrieb:
Kann man das so als Aufgabenlösung präsentieren? Das PL für die Sprache L haben wir schon desöfteren bewiesen, wodurch ich mir sagen traue, dass ich das hier nicht nocheinmal machen müssen... Was mich aber nach wie vor an der Lösung hier stört, ist, dass es in der Aufgabenstellung heißt, man darf kein PL verwenden. Theoretisch aber muss man aber das PL zum Beweis der Unregularität der Sprache L benutzen!
Mathematiker machen es sich gerne einfach
Wir haben bewiesen, daß L nicht regulär ist, also können wir für weitere Beweise darauf aufbauen.Ich hab daran jetzt nur 2 Sachen noch nicht verstanden. Warum kommt man auf die Sprache M (gut, hier habt gesagt, dass sind Erfahrungswerte, aber unser Prof. kann 'noch' nicht auf Erfahrungswerte bauen...) und warum ergibt L2cυM = L?
Das hat beides miteinander zu tun. Die Sprache L ist ja nicht umsonst vorher ins Gespräch gekommen, die Ähnlichkeit zwischen L und L2 sollte selbst einem Blinden mit Krückstock auffallen. Und dann ist es nur ein kleiner Schritt zu erkennen, daß LυL2=M ist. Der Rest sind Gleichungs-Umformungen (und Grundkenntnisse in der Mengenlehre bzw. booleschen Algebra):
L υ L2 = M
M - L2 = L
M ∩ L2c = L(ich merke gerade, daß ich da die Mengen-Operatoren durcheinandergeworfen habe - aber das hat auf den restlichen Beweis keinen Einfluß)
-
Danke für deine Hilfe. Also ist die Aufgabe dann mal soweit gelöst.