Informatiker Board | formale Sprachen | Problem mit Pumping-Lemma

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Der letzte Beitrag

bandchef

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?