Informatiker Board | formale Sprachen | Problem mit Pumping-Lemma

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Problem mit Pumping-Lemma

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Problem mit Pumping-Lemma

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

bandchef
Mitglied

Dabei seit: 06.10.2009
Beiträge: 28

Problem mit Pumping-Lemma

Zitatantwort auf diesen Beitrag erstellen

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?

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von bandchef: 05.06.2012 18:00.

05.06.2012 17:52

Nehmen Sie bandchef in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Problem mit Pumping-Lemma