Pumping-Lemma-Beweis
-
vip@r schrieb:
(wenn du dich jetzt noch daran erinnerst, daß k2>0 gilt, ergibt sich der Rest von selber)
Woher weiß ich das?
Das gehört zu den Bedingungen des Pumping-Lemmas: |v|>0 (un in deinem Fall ist v=0k2.
Zum Rest: Du weißt k1+k2+k3+n == 2n (aus der Definition der Sprache und der Aufteilung von z) und k2>0 (s.o.). Bei Anwendung des Pumping-Lemmas (mit i=2) erhältst du das Wort 0k1(0k2)20k312n0n=0k1+2*k2+k312n0n - liegt dieses Wort jetzt in der Sprache oder nicht?
-
vip@r schrieb:
Nein, ich hab keinen gültigen Automat. Ich hab auch noch nicht versucht einen zu zeichnen. Ich möchte es ja mit dem Lemma versuchen...
!!!
das pumping lemma ist eine NOTWENDIGE bedingung um zu testen ob eine sprache regulär ist, aber keine hinreichende !!!
sprich, eine sprache muss pumpbar sein, damit es regulär ist, aber weil es pumpbar ist, heisst es nicht, dass es auch regulär ist !!!
sagmal, hast du eigentlich ein buch was du parrallel zum studium liest?
ich kann dir die grundlagen der theoretischen informatik von kurt ulrich witt empfehlen... (sehr geiler prof, hab den letztes semester gehabt und der is einfach nur cool, aber flott und fordernd - was ja nicht schlecht ist - und er schreibt sehr gut)
-
Bei Anwendung des Pumping-Lemmas (mit i=2) erhältst du das Wort 0k1(0k2)20k312n0n=0k1+2*k2+k312n0n - liegt dieses Wort jetzt in der Sprache oder nicht?
Das Wort liegt in L.
k1+k2+k3+n == 2n (aus der Definition der Sprache und der Aufteilung von z) und k2>0 (s.o.)
Dass k2>0 sein muss ist mir mittlerweile klar, da ja der "Exponent" von v >= 1 sein muss. Ein Exponent =0 für v ist ja unzulässig, nicht wahr?
Wie ich aber k1+k2+k3+n == 2n aus der Definition der Sprache in Verbindung mit der Zerlegung (die ich ja wiederum selbst erstmal machen muss) erkennen soll. Ist mir noch schleierhaft.
-
sagmal, hast du eigentlich ein buch was du parrallel zum studium liest?
Zu einem Buch hat unser Prof. nicht ermutigt. Er hat ausführliche Foliensätze die mir bis jetzt auch genügt haben, außer beim PL. Das kapier ich einfach beim besten Willen nicht...
-
Skym0sh0 schrieb:
das pumping lemma ist eine NOTWENDIGE bedingung um zu testen ob eine sprache regulär ist, aber keine hinreichende !!!
Also sowohl in EN- und DE-Wikipedia wird nicht betont.
These lemmas can be used to determine if a particular language is not in a given language class. However, they cannot be used to determine if a language is in a given class, since satisfying the pumping lemma is a necessary, but not sufficient, condition for class membership.
-
vip@r schrieb:
Bei Anwendung des Pumping-Lemmas (mit i=2) erhältst du das Wort 0k1(0k2)20k312n0n=0k1+2*k2+k312n0n - liegt dieses Wort jetzt in der Sprache oder nicht?
Das Wort liegt in L.
Sicher? Ganz sicher? Wenn ja, würde ich da gerne deinen Rechenweg sehen.
k1+k2+k3+n == 2n (aus der Definition der Sprache und der Aufteilung von z) und k2>0 (s.o.)
Dass k2>0 sein muss ist mir mittlerweile klar, da ja der "Exponent" von v >= 1 sein muss. Ein Exponent =0 für v ist ja unzulässig, nicht wahr?
Wie ich aber k1+k2+k3+n == 2n aus der Definition der Sprache in Verbindung mit der Zerlegung (die ich ja wiederum selbst erstmal machen muss) erkennen soll. Ist mir noch schleierhaft.
Die Zerlegung hattes du doch schon: u=0k1, v=0k2, w=0k312n0n. Und jetzt schau dir mal die Exponenten an und setz die in die Definition der Sprache von ganz dort oben ein.
-
Und jetzt schau dir mal die Exponenten an und setz die in die Definition der Sprache von ganz dort oben ein.
Gut, ich seh die 5 Exponenten.
Die Definition der Sprache lautet ja: k=j+l.
So wie ich das jetzt verstehe muss ich in k, j, l, jetzt irgendwie die Zerlegung u=0k1, v=0k2, w=0k312n0n einsetzen. Aber welches der drei k soll ich denn da jetzt in das k der Defintion einsetzen?
-
Sicher? Ganz sicher? Wenn ja, würde ich da gerne deinen Rechenweg sehen.
Naja wenn ich das jetzt mathematisch ausformuliere, dann ist der rechte Ausdruck gleich dem linken und umgekehrt...
0k1(0k2)20k312n0n=0k1+2*k2+k312n0n
<=>0k102*k20k312n0n=0k1+2*k2+k312n0n
<=>0k1+2*k2+k312n0n=0k1+2*k2+k312n0nBeide Seiten gleich also in sprache L...
-
vip@r schrieb:
So wie ich das jetzt verstehe muss ich in k, j, l, jetzt irgendwie die Zerlegung u=0k1, v=0k2, w=0k312n0n einsetzen. Aber welches der drei k soll ich denn da jetzt in das k der Defintion einsetzen?
Der 0-Block von z bildet sich ja aus den drei 0-Blöcken von u, v und w (erster Teil) zusammengenommen, also mußt du dort die Summe aller drei k's verwenden.
Und was deine Herleitung angeht: Erstens hast du dort mitten drin aufgehört, bevor du die überhaupt die Sprach-Eigenschaft verwendet hast - und zweitens sollst du nicht beweisen, daß beide Seiten gleich sind, sondern daß das resultierende Wort in L liegt.
-
Der 0-Block von z bildet sich ja aus den drei 0-Blöcken von u, v und w (erster Teil) zusammengenommen, also mußt du dort die Summe aller drei k's verwenden.
Ich hab jetzt dastehen:
wir wählen: z=0n12n0n
Zerlegung: 0k10k20k312n0njetzt folgt dann k1+k2+k3=n
Das meinst du wahrscheinlich mit: "z bildet sich ja aus den drei 0-Blöcken von u, v und w (erster Teil) zusammengenommen, also mußt du dort die Summe aller drei k's verwenden."
Jetzt bleibt mir ja quasi noch er letzte Teil von w über also: 12n0n
Und wie geht's da jetzt weiter?
-
vip@r schrieb:
sagmal, hast du eigentlich ein buch was du parrallel zum studium liest?
Zu einem Buch hat unser Prof. nicht ermutigt. Er hat ausführliche Foliensätze die mir bis jetzt auch genügt haben, außer beim PL. Das kapier ich einfach beim besten Willen nicht...
Ganz ehrlich: Du haast auch mit anderen Dingen deine Schwierigkeiten. Ein erster Schritt wäre es, in der Vorlesung mitzuschreiben. Das hilft mir persönlich sehr viel. Wenn das noch nicht ausreicht, muss wohl ein Buch her.
-
Was wären diese anderen Dinge?
-
Schau dir mal an, welche Threads du in letzter Zeit erstellt hast. Sieben Stück sind auf der ersten Seite in RudP zu finden.
Edit: Auf der zweiten Seite sind nochmal sieben. Auf der dritten sind sechs.