3. Pumping-Lemma-Beweis

Pumping-Lemma-Beweis

  • C

    Bei einer regulären Sprache kann jedes Wort über der Mindestlänge gepumpt werden können (das meinte ich mit Pumping-Eigenschaft). Wenn wir wie hier beweisen wollen, daß die Sprache nicht regulär ist*, müssen wir nur ein Wort der Sprache finden, das nicht gepumpt werden kann. Das Wort z dort oben ist Element deiner Sprache, also können wir jetzt versuchen, es zu pumpen.

    * daß sie nicht regulär ist, erkennt man zur Not durch "scharfes Hinsehen" 😃

    0
  • Z

    @CStoll
    Dann pump mal *gg* - Könnte ich mir nicht verkneifen 😛

    0
  • C

    Zeus schrieb:

    @CStoll
    Dann pump mal *gg* - Könnte ich mir nicht verkneifen 😛

    Also alles will ich viper nun nicht abnehmen, schließlich will er ja etwas lernen :p

    0
  • V

    Also alles will ich viper nun nicht abnehmen, schließlich will er ja etwas lernen :p

    Natürlich will ICH etwas lernen; oder meint ihr ich poste hier in diesem Forum um mein Leben? 😃

    müssen wir nur ein Wort der Sprache finden

    Soweit bin ich noch dabei.

    Das Wort z dort oben ist Element deiner Sprache, also können wir jetzt versuchen, es zu pumpen.

    Mit dem Wort z meinst du wohl z=uvw, oder? Oder meinst du z=0n12n0n0?

    0
  • C

    Mit z meinte ich (z.B.) das Wort aus meiner ersten Antwort - und das darfst du jetzt selber in die Teile uvw zerteilen und dir dann überlegen, wie das (nach dem Pumpen entstandene) uv2w aussehen würde.

    0
  • V

    kann man nun das so zerteilen:

    0k10k20k312n0n

    Die erste Null ist u die zweite Null ist v und die drei letzten Teile bilden w. Stimmt das so?

    Warum muss ich da jetzt dann uv2w ausprobieren?

    0
  • C

    vip@r schrieb:

    Warum muss ich da jetzt dann uv2w ausprobieren?

    Wenn die Sprache regulär wäre, wären alle uviw in der Sprache, also kannst du jetzt alle Werte von i durchgehen und prüfen, bis du entweder ein Wort außerhalb der Sprache hast oder sicher bist, daß es keins geben kann. (wenn du dich jetzt noch daran erinnerst, daß k2>0 gilt, ergibt sich der Rest von selber)

    0
  • V

    (wenn du dich jetzt noch daran erinnerst, daß k2>0 gilt, ergibt sich der Rest von selber)

    Woher weiß ich das?

    k1+2k2+k3+n0>n0+n0 -> Genau das hab ich in der Lösung stehen. Ich versteh aber da die Aufteilung nicht. Warum es aber 2k2 heißt, ist mir dank deinem letzten Beitrag klar geworden. Weil, falls regulär, jedes Wort (ausgedrückt durch ^i) in der Sprache liegen müsste. Ich versteh's einfach nicht.

    Kannst du mir mal genau sagen, was jedes einzelne Zeichen in der obigen "Formel" bedeutet?

    0
  • V

    Oder kommt dieser Ungleichungsausdruck k1+2k2+k3+n0>n0+n0 von der Eigenschaft der Sprache, dass eben k=j+l sein soll?

    Was mir auch noch aufgefallen ist, dass das k3+n0 auf der linken Seite und das n0+n0 auf der rechten Seite ja irgendwie (nur etwas zerteilt) das bei der Zerlegung angegebene "w" widerspiegeln, oder?

    Ich rate leider noch immer im dunkeln...

    0
  • C

    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?

    0
  • S

    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)

    0
  • V

    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.

    0
  • V

    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...

    0
  • Z

    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.

    0
  • C

    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.

    0
  • V

    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?

    0
  • V

    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+k312n0n

    Beide Seiten gleich also in sprache L...

    0
  • C

    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.

    0
  • V

    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: 0k10k20k312n0n

    jetzt 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?

    0
  • M

    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.

    0
Anmelden zum Antworten