Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

b): Verständnisproblem bzgl. Betrachtung der Partitionen

0 Punkte
80 Aufrufe
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
Gefragt 17, Sep 2015 in HU-1-4 von uafjv uafjv Tutor(in) (167,840 Punkte)  

3 Antworten

0 Punkte
 
Beste Antwort

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

 

Beantwortet 17, Sep 2015 von uafjv uafjv Tutor(in) (167,840 Punkte)  
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
0 Punkte

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

 

Beantwortet 17, Sep 2015 von uafjv uafjv Tutor(in) (167,840 Punkte)  
0 Punkte

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)

 

Beantwortet 17, Sep 2015 von uafjv uafjv Tutor(in) (167,840 Punkte)  
...