Pumping Lemma Korrekt?

Wissenschaft Mathematik
#1

Hallo Leute,

da ich mir mit dem Pumping-Lemma noch unsicher bin, möchte ich gerne wissen, ob der Folgende Widerspruchsbeweis korrekt ist oder ein Fehler enthalten ist.

Zeigen Sie mit Hilfe des Pumping-Lemmas, dass L={a^k b^2k I k elememt d. natürlichen Zahlen} nicht regulär ist.

Die Behauptung ist zu zeigen durch die Kontraposition des Pumping-Lemmas.

Sei n beliebig. Dann ist w=a^n b^2n ein Element von L geschnitten mit Epsilon^≥n.

Sei nun w=xyz eine beliebige Zerlegung mit IyI ≥ 1 und IxyI ≤ n

Dann gilt, dass y= a^p für ein p ≥ 1.

Für i=2 gilt dann, dass xy^iz = a^p+n b^2n

Da p+n ≠ n ist xy^iz kein element von L

Wenn jemand sich die Zeit nehmen könnte, wäre ich sehr dankbar.

Liebe Grüße
Matze

#2

Sorry; schon zu lange raus aus diesem Thema!

#3

Im Prinzip stimmt der Beweis schon, aber an ein paar Stellen ist er vielleicht nicht ganz klar formuliert, ich versuche mal die einzelnen Schritte zu kommentieren.

Zeigen Sie mit Hilfe des Pumping-Lemmas, dass L={a^k b^2k I k
elememt d. natürlichen Zahlen} nicht regulär ist.

Die Behauptung ist zu zeigen durch die Kontraposition des
Pumping-Lemmas.

Sei n beliebig. Dann ist w=a^n b^2n ein Element von L
geschnitten mit Epsilon^≥n.

  1. Was ist Epsilon^≥n?
  2. n beliebig? Laut Pumping-Lemma haben die Wörter ab einer bestimmten Länge n0 diese besondere Eigenschaft, dass sie so zerlegbar sind, dass sich das Mittelstück beliebig aufpumpen lässt. Also sei n≥n0, oder besser n≥1/3*n0.

Sei nun w=xyz eine beliebige Zerlegung mit IyI ≥ 1 und IxyI ≤
n

Dann gilt, dass y= a^p für ein p ≥ 1.

Das gilt nun wegen dem 1/3 oben, dass wir im ersten Drittel des Wortes sind, d.h. der aufzupumpende Teil ist komplett in den a’s. Hier sollte man nun sagen, dass laut Pumping-Lemma eben auch xy^iz ein Wort aus L sein muss…

Für i=2 gilt dann, dass xy^iz = a^p+n b^2n

Da p+n ≠ n ist xy^iz kein element von L

… was eben in Widerspruch zum letztgenannten steht.

Alles in allem kann man dem Beweis nur folgen, wenn man schon weiss, was du ausdrücken willst. Bin hier per Mail nicht ganz sicher, ob das einfach die verkürzte Schreibweise im Schreibmaschinentext ist oder ob dir da noch ein bisschen die Klarheit fehlt.

gruss, mofte

#4

Hallo, vielen Dank, dass du dir die Zeit genommen hast.

Hat mir sehr geholfen!

#5

Die Anwendung des Pumping Lemmas ist so genau richtig.
Durch Pumpen Deines a^p erhältst Du als Wort

a^[(n-p)+(p*i)]b^2n, und das ist nur für i=1 in L.