Pumping Lemma- alternative Begründung richtig?

Question

Wäre es auch möglich hier bei der Begründung das Pumpwort $w =111$ zu wählen, dieses in

 

$xy = 1^j$, $y = 1^k$, $x = 1^{j-k}$ und $z = 1^{n-j}11$ für $0 < k \leq j \leq n$

 

zu zerlegen und mit $i = 0$ zu pumpen, sodass das Wort $w' = 1^{n-k}11$ entsteht, welches nicht element $L_3$ ist, da w^|w| gelten muss?

 

Danke im Voraus!

Answer 1

Nein, das geht nicht, denn Ihr Wort hat nicht die Länge $|w|\geq n$. (Das ist sehr wichtig und ein häufiger Fehler, bitte beachten Sie das in der Klausur!)

Außerdem dürfen Sie die Zerlegung nicht wählen, sondern müssen über alle möglichen Zerlegungen argumentieren!

Viele Grüße

Lukas König

Comments

und wenn ich das Pumpwort 1^n1^n1^n wähle? und den beweis dann äquivalent wie in den tuts führe mit Pumpvariable i=0 ?

y=1^k x=1^j-k xy=1^j mit 0<k<=j<=n
und daraus z=1^n-j1^n1^n

dann mit i=0 pumpen => w= 1^n-k 1^n1^n und das ist kein Element von L

---

Wie soll das denn gehen, $1^n1^n1^n$ ist doch nicht für alle $n$ in $L$! Gleich für $n=2$ gilt $111111 \notin L$.

---

Bitte schauen Sie sich das Pumping-Lemma nochmal gründlich an.