andere Zerlegung des Worts möglich ?

Question

Hallo, 

kann man denn eigentlich das Wort auch so zerlegen, dass man das Pumping Lemma dann bei \(1^n 0^n 1^n\) anwendet? Dann koennte man ja direkt beim Pumpen sehen, dass das Wort nicht Element der Sprache ist.. Oder muessen immer vorher die gleichen Teile des Wortes zusammengefasst werden? 

Danke im Voraus! 

Gruesse 

Niklas Boehn

 

Answer 1

Hallo Herr Boehn,

ich bin mir nicht ganz sicher, ob ich Ihre Frage richtig verstanden habb: Also Sie wollen das Wort \( 0^n 1^n 0^n 1^n \) (so wie in der Lösung der Teilaufgabe b) wählen? Dann können Sie das PPL nur bei 0^n durchführen, da ja \( xy \leq n \) ist.

Habe ich Ihre Frage so richtig verstanden?

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Comments

Also wenn ich das Pumping Lemma dann bei \( 0^n\) anwende, dann weiß ich doch aber eigentlich gleich, dass mein y nur 0 sein kann und muss dann doch eigentlich die relativ umständliche Zerlegung in der  Loesung nicht durchführen oder? Wenn ich dann zum Beispiel mit i=2 pumpe weiß man doch gleich, dass das Wort nicht zur Sprache gehört oder?

Grüße

Niklas Boehn

---

Hallo,

bei diesem Wort ermöglicht dir aber erst die umständliche Zerlegung (denn diese Zerlegung erfüllt ja gerade die Voraussetzungen (1) und (2)) das Punpen innerhalb der ersten n Nuller (in anderen Worten: erst die Zerlegung, dann das Pumpen). Der Rest wird dann dadurch wie du schon sagtest, relativ einfach (Pumpen mit i ungleich 1 führt zu einem Widerspruch zu (3)).

Oder hast du deine Frage vielleicht anders gemeint?

Viele Grüße,

Vivian (Tutor)

---

Ich bin mir auch nicht sicher, dass ich dich richtig verstehe.

Du wendest das Pumping-Lemma auf \(0^n\) an, wie oben durch die Übungsleiter beschrieben wurde. Du musst jedoch dann zeigen, dass damit das gesamte Wort nicht mehr Element der Sprache sein kann. Deshalb musst du die gesamte Zerlegung auf jeden Fall durchführen, um nach dem Zusammensetzen und dem Wählen der Pumpvariable feststellen zu können, dass das gesamte Wort nicht mehr Teil der Sprache sein kann.

Das sollte formal korrekt aufgeschrieben werden, auch wenn einem vielleicht schon früher klar ist, dass das Wort nicht zur Sprache gehören kann.

Viele Grüße,

Melanie (Tutorin)

---

Ach so ok danke, das mit dem gesamten Wort macht Sinn.. Mich hat im Vergleich dazu nur die Aufgabe 3b von der ersten Saalübung verwirrt, wo es ja gereicht hat zu argumentieren dass vwx bspw. nur a's enthält und dass durch das Pumpen das Wort dann nicht mehr in der Sprache enthalten ist. Im Gegensatz zu Aufgabe 1-3 würde das ja hier reichen oder?

---

Es reicht generell nicht, nur für eine Zerlegung zu zeigen, dass das Wort für eine Pumpvariable nicht in der Sprache enthalten ist. Hierfür verweise ich auf einen Eintrag weiter oben:

(...) Generell besagt die Umkehrung des Pumpinglemmas (mit der wir den Widerspruch zeigen wollen), dass ein Wort nicht erkannt wird, wenn es überhaupt keine gültige Zerlegung mit den 3 Bedingungen gibt, dass also für jede Zerlegung das Aufpumpen verletzt ist. Irgendeine Zerlegung zu finden, die das Pumpinglemma verletzt, reicht also nicht aus. (...)

Viele Grüße,

Melanie (Tutorin)

---

Das stimmt so nicht ganz.

Bei der Aufgabe 3b der Saalübung wurde für jede Zerlegung gezeigt, dass w nicht in L liegt (genau so, wie Melanie das bereits beschrieben hat).

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König