b): Verständnisproblem bzgl. Betrachtung der Partitionen

Question

Hallo,
In der Musterlösung heißt es "Betrachte eine beliebige Partition".
Ich dachte wir müssen für das Pumping-Lemma alle möglichen Partitionen betrachten und widerlegen, daher nehmen wir ja auch die Variablen Exponenten und zeigen es für alle möglichen k, l, m etc.

Nun gibt es aber für das Palindrom noch eine weitere Partition, die nicht so abgedeckt wird:

\( x = 0^{n-k} y = 0^k * 1 * 0^k  z=0^{n-k}\) mit \(k \in [0, n] \)

Das k deckt somit alle Partitionen ab, die die ersten beiden Bedingungen erfüllen.
Pumpt man nun für i=2 erhält man wieder ein Palindrom, lediglich i=0 führt zu einem Widerspruch, da: \( xy^0z = 0^{n-k} * 0^{n-k} = 0^{2n - 2k} \notin w \)

Müsste man das nicht alles noch zeigen, oder habe ich das mit dem \( \neg \exists Zerlegung = \forall Zerlegung \) bei dem Widerspuch falsch verstanden?

Unklar bin ich mir leider auch noch über die Bedeutung des "n", wir haben ja einmal ein n als Exponent in unserer Zerlegung, welcher aber nichts mit dem "\( |w| \leq n\)" zu tun hat, oder?
Also ist n einfach eine beliebige Variable? Denn falls nicht: \(|0^n*1*0^n| = 2n + 1 > n\) und niemals \(\leq n \).
Andersrum wäre meine obere Zerlegung hinfällig, weil dann |xy| > n für jedes k wäre?
Sprich: Ist n einfach eine Variable und wir müssen dafür sorgen, dass das Wort mindestens so lang wird aber gleichzeitig xy nur genauso lang ist wie das n?

Sorry für die Verwirrung, vermutlich gibt es eine einfache Lösung

Answer 1

Hallo,

was Marc und Paul schreiben ist so nicht ganz korrekt. Im Pumpinglemma heißt es "es gibt eine Partition", nicht "für alle beliebigen Partitionen". Daher muss man im Umkehrschluss, wie Sie richtig geschrieben haben(!), alle möglichen Partitionen betrachten. Wenn wir in der Musterlösung schreiben "Betrachte eine beliebige Partition", dann ist genau das gemeint. Wenn wir eine beliebige Partition betrachten, heißt das, dass wir keine Einschränkungen für x, y, z vornehmen, also untersuchen wir alle Möglichkeiten.

Viele Grüße

Lukas König

 

Comments

Hallo,
solangsam verstehe ich es :)

Was ich oben meinte ist, dass wir mit zB \(x = 0^{n-k} y = 0^k\) und \(z = 1*0^n \) zwar durch die Wahl von k eine große Menge an Partitionen abdecken, aber mich wunderte, warum wir zB nicht 010 als y (Pumpvariable) nehmen, was ja auch eine Partition wäre.

Liegt das daran, dass damit die Bedingung \(|xy| \leq n\) verletzen würde für alle anderen Partitionen? Sprich: Das die 1 frühestens in z kommen darf, da \(|0^n*1| = n+1 \)?

Was aber, wenn ich zB \(xy = 0^{n-5} * 1\) also \(xyz = 0^{n-5}*1*0^{n-5}\) betrachte? Dort ist xy kürzer als n und das Wort ist sowohl Element der Sprache als auch das selbe Wort, nur mit n = n - 5.
Das wäre doch auch eine Partition, die es zu überprüfen gilt, die sogar aufgepumpt Palindrome ergeben würde?


Ich hoffe ich habe mich klar ausgedrückt, mir ist aufgefallen, dass wir eigentlich immer nur das erste "Zeichen" (zB a, bei \( a^nb^n\)) betrachten, nur ist mir nicht klar warum.

Oh und noch eine Kleinigkeit: \( (010)^3 = (010) * (010) * (010)\neq (0^3 1^3 0^3) \)

Sprich: Wenn ich 010 pumpe, verletzt das dann die Form 010 indem es zu 010010 wird, oder wird es zu 001100?

Gruß,
Marc

---

Hallo,

wenn Sie \( (010)^3 \) haben, dann wird das zu \( 010010010 \). Sie können sich das ganz gut überlegen, dass, wenn Sie das PPL für reguläre Sprachen betrachten, es ja um die Existenz von Schleifen geht, das heißt Sie können eine Schleife, die \( 010 \) generiert, einfach mehrmals ablaufen.

Viele Grüße

Friederike Pfeiffer-Bohnen

Answer 2

Also es reicht wenn du eine Zerlegung findest, sodass die Sprache nicht erkannt werden kann.

Zweite Frage: n ist beliebig aber fest, d.h. du nimmst dir einen "Wortteil", der eine gewisse Länge nicht überschreiten darf

 

Answer 3

Hallo Marc,

Das Pumpinglemma sagt aus, dass man dieses Wort beliebig zerlegen und pumpen kann und es nach dem "pumpen" immer noch Teil der Wortklasse ist.

Als Umkehrschluss bedeutet das, dass es ausreicht wenn du eine Variante findest, in der dies nicht gegeben ist, und somit das Pumping Lemma widerlegt, heißt die Sprache ist eben nicht Teil der angenommenen Sprachklasse.

Zu deiner 2. Frage: das "n" im Exponent und das n in der Rechnung sind die selben. Es stimmt dass wir hier, da wir ausschließlich ganzzahlige n's haben, auch > schreiben könnten, da wenn n=0 immernoch gilt 1>0, nur der mathematischen korrektheit schreiben wir hier \( \leq \), ich hoffe ich konnte dir weiterhelfen.

Viele Grüße,

Marc (Tutor)