Informatiker Board | Druckvorschau: Problem mit Pumping-Lemma

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Problem mit Pumping-Lemma (http://www.informatikerboard.de/board/thread.php?threadid=1227)

Geschrieben von bandchef am 05.06.2012 um 17:52:

Problem mit Pumping-Lemma

Hi Leute!

Ich hab hier ein paar Übungsaufgaben mit dem Pumping-Lemma. Ich hab damit aber schwere Probleme, dass Lemma zu verstehen. Wir machen hier übrigens die verschärfte Version davon.

$[latex]L =\{ 0^j 1^k 0^l | j=k+l \text{ für }j,k,l \in \mathbb N \}[/latex]$

Annahme: L ist regulär.

Sei [latex]n_0[/latex]

die Konstante des PL, dann gilt: $[latex] n_0 \geq 1 [/latex]$ und $[latex]n_o \in \mathbb N [/latex]$

$[latex]z = 0^{2n_0} 1^{n_0} 0^{n_0} [/latex]$ mit $[latex]|z| \geq n_0 [/latex]$ und $[latex] z \in \mathbb N [/latex]$

Sei z=uvw eine Zerlegung von z mit: $[latex]|uv| \leq n_0 [/latex]$ und $[latex]|v| \geq 1 [/latex]$

$[latex]z = uvw = 0^{2n_0} 1^{n_0} 0^{n_0} \Rightarrow u = 0^{2n_0}, v = 1^{n_0} u = 0^{n_0} [/latex]$

Mein Problem ist nun, dass ich immer nicht weiß wie ich hier eine korrekte Zerlegung angebe. Diese hier oben sollte auch falsch sein, denke ich.

Könnt ihr mir helfen?