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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 1 Minuspunkt
108 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
in HU-1-4 von uafjv uafjv Tutor(in) (168k Punkte)  

3 Antworten

0 Pluspunkte 0 Minuspunkte
 
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

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
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
0 0
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 Pluspunkte 0 Minuspunkte

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

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 Pluspunkte 0 Minuspunkte

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)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...