Aufgabe zum Pumping-Lemma

[vip*r]

Hi Leute!

Ich hab hier eine Aufgabe zum Pumping-Lemma:

Beweisen oder widerlegen sie:

$L = \{0^j1^k0^l | j=k+l\}$

Ich hab dann so angefangen:

Sei n die Konstante des PL. Es gilt laut PL: $|uv| \leq n$ und $y \neq \epsilon$

$w = 0^j1^k0^l$

Zerlegung: w = \underbrace{0^j}_{=u}\underbrace{1^k}_{=v}\underbrace{0^l}_{=w}

i=1: $w=uv^iw \in L$

Da ja die Anzahl der ersten Nullen von w von der Addition von j und k abhängt, kann ich j oder auch l so oft pumpen wie ich will. Die Anzahl der ersten Nullen von w geht da immer mit und ich flieg niemals aus L raus.

Stimmt das soweit?

[Christoph]

vip@r schrieb:

Beweisen oder widerlegen sie:

$L = \{0^j1^k0^l | j=k+l\}$

Da ist nichts zu beweisen, das ist nur eine Definition.

vip@r schrieb:

Sei n die Konstante des PL. Es gilt laut PL: $|uv| \leq n$ und $y \neq \epsilon$

$w = 0^j1^k0^l$

n ist also "die Konstante des PL", was recht unscharf ist, aber in Ordnung, je nach Kontext. In diesem Kontext ist es nicht in Ordnung, weil du nicht gesagt hast, was du eigentlich vorhast. Möchtest du annehmen, dass das PL gilt, und dann einen Widerspruch ableiten? Wenn ja, dann schreib das doch hin.

Aber viel wichtiger: Was sind denn u, v, y, w, j, k, l für Variablen? Warum tauchen die plötzlich auf ohne jede Erklärung?

Dir muss bei jeder Variablen immer hundert Prozent klar sein, woher sie kommt und welchen Wert sie gerade hat. Definier u, v, y, w, j, k, l, dann wird es klarer.

[knivil]

1.) ich habe mich schon gefragt, wann du dich wieder meldest
2.) Es ist nicht angegeben, was bewiesen werden soll. Ich nehme mal an, L soll kontextfrei sein. Oder aber siehe Punkt 4.
3.) ich haette einen Kellerautomaten angegeben, sofern das Pumping Lemma nicht explizit gefordert wird. Die entsprechende Grammatik ist auch total simpel. Hier mal die Produktionsregeln:

S -> 0S0
S -> 0S1
S -> ε

Bleibt nur noch zu zeigen, dass diese Sprache { 0^j1^k0^l | j = k+l } erkennt. Aber das ist trivial.

4.) Wenn ich so genauer drueber nachdenke, dann sollst du wahrscheinlich zeigen, dass L nicht regulaer ist. Sofern das pumping lemma nicht explizit gefordert wird, haette ich die Sprache L mit 0^*1^* geschnitten. Das Ergebnis 0ⁿ1ⁿ ist offensichtlich nicht regulaer (siehe Beispiel aus der Vorlesung hoffentlich). Da regulaere Sprachen aber abgeschlossen sind gegenueber Schnittmengenbildung kann L nicht regulaer sein.

Stimmt das soweit?

Mein Gefuehl sagt mir bei dir: Nein (ohne das Pumping Lemma nochmals naeher angeschaut zu haben).

[vip*r]

Christoph schrieb:

Da ist nichts zu beweisen, das ist nur eine Definition.

Das ist meine gesamte Aufgabenstellung:

Beweisen oder widerlegen Sie mit dem Pumping-Lemma, dass die folgende Sprache regulär ist:

L_1 = \{ 0^j1^k0^l | j=k+l \text{ für }j,k,l \in \mathbb N \}

So, dann fang ich nochmal an:

Vermutung: L ist regulär!

Sei $n_0$ die Konstante des PL, dann gilt: $n_0 \in \mathbb N$ mit $n_0 \geq 1$:

$w = 0^{n_0}1^k0^l$

Für alle $w \in L$ mit $|w| \geq n_0$ mit $u,v,w \in \Sigma^{\star}_{\text{Bool}}$ und $|uv| \leq 1$ und $v \neq \epsilon$ gilt die Zerlegung:

w = \underbrace{0^m\_1}\_{\text{=u}} \underbrace{0^m\_2}\_{\text{=v}} \underbrace{1^k 0^l}_{\text{=w}} mit $m\_1+m\_2=j$

Betrachte: $uv^iw \in L$ mit i=2: $uv^2w = 0^{m\_1}(0^{m\_2})^21^k0^l = 0^{m\_1}0^{2m\_2}1^k0^l = ...?$

Und ab hier weiß ich dann nicht mehr weiter. Laut der Sprachdefinition von oben hängt die Anzahl der ersten Nulln $0^j$ von der Anzahl der Zeichen $1^k$ und $0^l$ ab. Wenn ich jetzt bspw. k=2 und l=3 wähle, dann berechnet sich ja j=k+l=5. Dann sieht das Wort w ja so aus: 0000011000.

Stimmt das soweit?

knivil schrieb:

Die entsprechende Grammatik ist auch total simpel.

Grammatiken kommen laut Curriculum meiner Vorlesung überhaupt nicht vor!

[Christoph]

vip@r schrieb:

Christoph schrieb:

Da ist nichts zu beweisen, das ist nur eine Definition.

Das ist meine gesamte Aufgabenstellung:

Beweisen oder widerlegen Sie mit dem Pumping-Lemma, dass die folgende Sprache regulär ist:
[...]

Ja, die Aufgabenstellung fragt nach mehr. Nämlich ob diese Sprache regulär ist.

vip@r schrieb:

Für alle $w \in L$ mit $|w| \geq n_0$ mit $u,v,w \in \Sigma^{\star}_{\text{Bool}}$ und $|uv| \leq 1$ und $v \neq \epsilon$ gilt die Zerlegung:

w = \underbrace{0^j}_{\text{=u}} \underbrace{1^k}_{\text{=v}} \underbrace{0^l}_{\text{=w}}

Das ist doch Unfug. Jedes Wort w soll sich schreiben lassen als 000...000111...111000...000? Und was ist, wenn w mit 101 beginnt?

Sorry, aber da möchte ich auch nichts mehr zu schreiben. Lies bitte im Skript, bis du das Skript verstanden hast. Lies *nicht* das Skript, bis du glaubst, die Aufgaben irgendwie lösen zu können. Lies im Skript, bis du das Skript verstanden hast. Wenn du eine Stelle im Skript (nicht in der Aufgabe, sondern im Skript) auch nach mehrmaligem Lesen nicht verstehst, frag einen Tutor, die sind dafür da. Aber das wichtige ist, dass du es verstehst, nicht, dass ein Tutor dir irgendwelche mathematischen Mantras beibringt, die du dann versuchst irgendwie zu verbinden.

Das wird lange dauern, keine Frage. Aber es ist der einzige Weg, wenn du es verstehen willst.

[daki]

wo studierst du wenn ich fragen darf? die Aufgaben kommen mir alle verdächtig bekannt vor..

[otze]

Vermutung: L ist regulär!

falsche Vermutung. Überlege dir Warum. Wenn du weißt warum, dann kannst du auch den Beweis aufschreiben.

[knivil]

Vielleicht ist es ja ein Widerspruchsbeweis.

[Michael E.]

Es muss sogar ein Widerspruchsbeweis sein, weil man mit dem Pumping-Lemma nicht beweisen kann, dass eine Sprache regulär ist.

[vip*r]

Ja, es soll ja auch ein Widerspruchsbeweis werden. Ich nehme eben vor dem PL an, dass die Sprache regulär ist.

Deswegen kapiere ich nicht, warum ich nicht schreiben darf: Vermutun: L ist regulär. Und dann Beweis mit PL...

Also, wenn ihr nix dagegen habt, dann hätte zu dieser (offiziellen) Lösung ein paar Fragen:

Aufgabe: L = \{ 0^j 1^k 0^l | j=k+l \text{ für } j,k,l \in \mathbb N\}
--- Die Sprache (an sich) kann man dann doch auch so schreiben: $0^{k+l} 1^k 0^l$ ---
--- Die Sprache verstehe ich so: die Anzahl der 0en an erster Stell ist gleich mit der gemeinsamen Anzahl von 1en an der zweiten stelle und der Anzahl der 0en an der letzten Stelle, stimmt das so? ---
--- Bsp.: k=2, l=3 und j=k+l=5 => 0000011000; das ist natürlich jetzt nich nur das einzige Wort aus der Sprache sondern es gibt unendliche viele Wörter, die genau diesen Aufbau haben, oder? ---

Annahme: L ist regulär.

Sei $n_0$ die Konstante des PL, dann gilt:
$n_0 \in \mathbb N$ und $n_0 \geq 1$
--- bis hierhin is soweit alles klar ---

$z = 0^{n\_0} 1^{n\_0} 0^{0}$
--- Warum wird die letzte 0 hoch 0 genommen? ---

Jede gültige Zerlegung hat die Form:

z = \underbrace{0^{k\_1}}\_{=u} \underbrace{1^{k\_2}}\_{=v} \underbrace{0^{k\_3} 1^{n\_0} 0^0}_{=w}
--- Wie kommt man auf diese Zerlegung? Das ist eigentlich immer das was ich am wenigsten verstehe. Könnt ihr mir das erklären? ---

mit $k\_1 + k\_2 + k\_3 = n\_0$ und $k\_1 + k\_3 \leq n_0$ und $k_2 \geq 1$
sowie $z = uvw$, $|v| \geq 1$ und $|uv| \leq n_0$

Nun betrachten wir i=0, dann ist $uv^iw \notin L$:
--- Warum hier nun i=0 und nicht i=2 oder so?

$uv^0w = 0^{k\_1} (0^{k\_2})^0 0^{k\_3} 1^{n\_0} 0^0 = 0^{k\_1} \epsilon 0^{k\_3} 1^{n\_0} \epsilon = 0^{k\_1 + k\_3} 1^{n\_0} \notin L$, da $k\_1 + k\_3 < n_0$ ist.
--- Die Umformung ist mir dann soweit wieder klar, wenn ich die anderen unklaren Sachen weiß ---

[Gast]

Woher kommt das von dir erwähnte i?

Also wenn ich das gerade richtig in Erinnerung habe, gilt es ja, für jede Wortlänge n >= n0 (naja, nicht ganz exakt, du musst eigentlich zeigen, dass es für ein beliebiges n ein wort der länge n' > n gibt, eventuell gibt es für die speziellen Wörter die du später betrachtest nicht für jede Länge eines, sondern nur für jede fünfte Wortlänge) ein spezielles Wort der Sprache zu finden, das keine Zerlegung hat, welche pumpbar ist. Daher nehmen die Jungs das Wort ohne abschließende Nullen daher, da es in der Sprache liegt aber praktischerweise weniger Zerlegungen besitzt als die restlichen Wörter dieser Länge aus der Sprache. Nun überleg dir mal, welche Zerlegungen uvw vom Wort 0^a1^a (2a=n) es gibt. Vielleicht kommt man dann mit etwas Überlegungen auf den Term, den die da haben, ich habe gerade noch meine Zweifel^^

Aber es läuft auf folgendes hinaus:
v liegt in den 0en -> die gepumpten wörter sind nicht in der sprache
v liegt über der Grenze -> es entstehen Folgen von 01 001100 etc... nicht in der Sprache...
v liegt in den 1en -> symmetrischer Fall zum ersten.