Einfache Pumping-Eigenschaft

CStoll

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 L2^cυ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 ∩ L2^c = L

(ich merke gerade, daß ich da die Mengen-Operatoren durcheinandergeworfen habe - aber das hat auf den restlichen Beweis keinen Einfluß)

vip*r

Danke für deine Hilfe. Also ist die Aufgabe dann mal soweit gelöst.

vip*r

Der Rest sind Gleichungs-Umformungen (und Grundkenntnisse in der Mengenlehre bzw. booleschen Algebra)

Kannst du das näher erläutern? Insbesondere wie du durch die Gleichungs-Umformung und Grundkenntnisse der Mengenlehre bzw. booleschen Algebra darauf kommst, dass gilt: L2^c∩M = L

CStoll

vip@r schrieb:

Insbesondere wie du durch die Gleichungs-Umformung und Grundkenntnisse der Mengenlehre bzw. booleschen Algebra darauf kommst, dass gilt: L2^c∩M = L

Das geht bei mir größtenteils intuitiv, ist also schwer in Worte zu fassen. Aber ich versuche mal, die nötigen Regeln herauszusuchen:

L [e]upsilon[/e] L2 = M               ursprüngliche Beziehung (kannst du dir anhand der Mengendefinitionen klarmachen)
(L [e]upsilon[/e] L2) - L2 = M - L2   (ich bin mir jetzt nicht sicher, wie diese Regel heißt)
(L-L2) [e]upsilon[/e] (L2-L2) = M-L2  Distributivgesetz 
L [e]upsilon[/e] 0 = M-L2             1) L und L2 sind disjunkt, also ist L-L2=L
                         2) X-X=0
L = M - L2               Neutrales Element der Vereinigung
L = M [e]cap[/e] L2[h]c[/h]              Anwendung der Definitionen der Schnitt- und Komplementärmenge

vip*r

Ich hab mir jetzt deine Erklärung mit meinem Bronstein näher geführt. Die Umformungen verstehe ich soweit.

Mein Problem besteht halt leider immer nur noch darin, dass ich einfach nicht verstehe wie man auf die zwei zusätzlichen Sprachen kommt. Auch wenn die Sprache L eine sehr nahe Verwandtschaft mit der Sprache L2 hat, verstehe ich einfach nicht wie man auf den Gedanken kommt.

Und warum kommt dann auch noch die Sprache M zum Einsatz? Die hat ja jetzt aber auch schon mal gar nix mehr mit der eigentlich zu beweisenden Sprache L2 zu tun. Ich mein der Kleene-Stern hat ja damit nix zu tun, oder? Der kleene Stern macht ja hier aus der 0 und der 1 nix anderes wie jedes mögliche Wort welches aus 0 bzw. 1 entstehen kann. In diesem Fall eben eine unendliche lange anreihung von 0 und 1...

Jester

Die Grundidee ist doch eigentlich, dass uns auffällt, dass {0ⁿ¹m | n!=m} irgendwie ganz viel mit {0ⁿ¹m | n=m} zu tun hat. Das eine ist quasi das komplement des anderen, aber halt nicht komplement bezüglich Σ^*, sondern bezüglich der Sprache {0ⁿ¹m | n,m bel.}; deren kurzer Name lautet aber 0^*1*.

CStoll

vip@r schrieb:

Mein Problem besteht halt leider immer nur noch darin, dass ich einfach nicht verstehe wie man auf die zwei zusätzlichen Sprachen kommt. Auch wenn die Sprache L eine sehr nahe Verwandtschaft mit der Sprache L2 hat, verstehe ich einfach nicht wie man auf den Gedanken kommt.

L hattest du doch selber am Anfang des Threads aufgeworfen. Und M entsteht aus L bzw. L2, indem du die Beschränkungen der Teilwort-Längen weglässt.
Das ist der Teil der Informatik, den man als "Intuition" bezeichnet - man schaut sich das Problem an, vergleicht mit früher gelösten Problemem und entdeckt auf diese Weise gemeinsame Strukturen (hier zum Beispiel, daß es immer um eine Reihe von Nullen gefolgt von einer Reihe von Einsen geht). Wenn du dich ein wenig länger damit beschäftigst, entwickelst du auch einen Blick für diese Details.

herda

Warum kann man nicht gleich sagen, dass L2 = Kompliment L. Und da L nicht regulär ist, so muss L2 auch unregulär sein?
Wozu braucht man den Beweis über M = {0*1*} zu führen ?

CStoll

herda schrieb:

Warum kann man nicht gleich sagen, dass L2 = Kompliment L. Und da L nicht regulär ist, so muss L2 auch unregulär sein?

Weil L2 nicht das Komplement von L ist (Komplement bezieht sich auf die Menge ALLER Wörter, d.h. Σ^*)

herda

Aber wenn man sagt: M = L2 u L = {0* 1*}. Dann ist doch L2 das Kompliment von L. Oder bezieht sich das Komplement IMMER auf die Menge aller Wörter?
L ist ja M - L2 <=> L = M ∩ L2^c

ps. bevor du fragst. Ja, wir sind zu 99% in der selben Gruppe an der FH wie der vipar ^^ Ich weiss aber nicht wer er ist.

CStoll

herda schrieb:

Aber wenn man sagt: M = L2 u L = {0* 1*}. Dann ist doch L2 das Kompliment von L. Oder bezieht sich das Komplement IMMER auf die Menge aller Wörter?
L ist ja M - L2 <=> L = M ∩ L2^c

Komplement bezieht sich auf die betrachtete Grundmenge - bei formalen Sprachen ist das halt die Menge aller Wörter.

ps. bevor du fragst. Ja, wir sind zu 99% in der selben Gruppe an der FH wie der vipar ^^ Ich weiss aber nicht wer er ist.

Da könntet ihr euch ja mal in der FH verabreden zum gemeinsamen Lernen- es dürfte doch nicht so schwer sein, sich gegenseitig zu identifizieren

herda

Jetzt bin ich verwirrt. Stimmt es also, dass wenn L2 regulär ist, dann ist nicht L2 auch regulär und zwar wegen der Abschlusseigenschaft?

Ich vermute "nicht L2" ist das gleiche wie L2^c und = Kompliment von L2.

ps. Ja schon, aber wenn er hier Fragen stellt, dann hat er auch keine Ahnung

CStoll

herda schrieb:

Jetzt bin ich verwirrt. Stimmt es also, dass wenn L2 regulär ist, dann ist nicht L2 auch regulär und zwar wegen der Abschlusseigenschaft?

Ich vermute "nicht L2" ist das gleiche wie L2^c und = Kompliment von L2.

Ja, stimmt beides.

Jester

herda schrieb:

Aber wenn man sagt: M = L2 u L = {0* 1*}. Dann ist doch L2 das Kompliment von L. Oder bezieht sich das Komplement IMMER auf die Menge aller Wörter?

Genau. Hier wollen wir sozusagen nicht das ganze komplement, sondern nur das Komplement bzgl. einer kleineren Sprache, die aber glücklicherweise regulär ist, das erreichen wir durch das schneiden mit dieser Sprache. das komplement einer regulären sprache bezüglich einer beliebigen sprache ist im allgemeinen nicht regulär (betrachte zum beispiel das komplement der leeren sprache bezüglich 0ⁿ¹n).