Informatiker Board | formale Sprachen | Pumping Lemma Beweise für reguläre Sprachen

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Pumping Lemma Beweise für reguläre Sprachen » 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

[quote][i]Original von pumpkin lemma[/i]
Guten Abend,

ich tue mich mit dem Pumping Lemma schwer. Glücklicherweise kommt in der Klausur nächste Woche nur das PL für reguläre Sprachen dran.

Ich versuche zur Zeit Altklausuren zu lösen, bisher habe ich es jedoch noch nicht einmal geschafft, dass mein Lösungsweg der Musterlösung entspricht.
Ich weiß, dass das nicht unbedingt bedeutet, dass mein Weg falsch ist, aber da ich mir mit dem Thema schwer tue und nicht immer sagen kann, ob das, was ich tue, ebenfalls richtig ist, würde ich euch bitten, meine Lösungswege anzuschauen und ggf. zu korrigieren.

Ich würde gleich mal mit einer Aufgabe loslegen:

Wir betrachten über einem Alphabet [latex]\Sigma[/latex] = {0, 1} die Sprache
L := {w | die Länge von w ist gerade und die linke Hälfte von w enthält eine Eins}

[I]Als Hinweis wurde noch gegeben, dass man mit der Form [latex]0^{n} 1 0^{n+1} [/latex] argumentieren soll.[/I]

Meine Lösung:
Angenommen, L wäre regulär. Dann würde das PL gelten und es gäbe eine PLZ n.

Das Wort [latex]0^{n} 1 0^{n+1} [/latex] ist dann in L enthalten und hat die Länge [latex]n+1+n+1 = 2n + 2 > n[/latex] , d.h. es gibt eine Zerlegung [latex]0^{n} 1 0^{n+1} = uvw[/latex] mit [latex]|v| \geq 1[/latex] und  [latex] |uv| \leq n[/latex] , sodass [latex]u v^{i} w[/latex] für alle [latex]i \in N_{0} [/latex] in L liegt.

Wähle [latex]i = 2[/latex] . Dann ist [latex]u v^{2} w = uvvw[/latex] und müsste in L enthalten sein.

Da [latex]|v| \geq 1[/latex] und [latex]|uv| \leq n[/latex] und v zwei Mal aufgepumpt wird, und uv im ersten Nullerbereich liegt, werden links 2 weitere Nullen hinzugefügt, sodass jetzt die 1 in der rechten Hälfte liegt.

Damit liegt uvvw aber nicht mehr in L und das PL gilt nicht mehr. Daher kann L nicht regulär sein.

Wäre toll, wenn ihr mir hierfür Feedback geben könntet!

Dankeschön  :)[/quote]

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

pumpkin lemma

Pumping Lemma Beweise für reguläre Sprachen

Guten Abend,

ich tue mich mit dem Pumping Lemma schwer. Glücklicherweise kommt in der Klausur nächste Woche nur das PL für reguläre Sprachen dran.

Ich versuche zur Zeit Altklausuren zu lösen, bisher habe ich es jedoch noch nicht einmal geschafft, dass mein Lösungsweg der Musterlösung entspricht.
Ich weiß, dass das nicht unbedingt bedeutet, dass mein Weg falsch ist, aber da ich mir mit dem Thema schwer tue und nicht immer sagen kann, ob das, was ich tue, ebenfalls richtig ist, würde ich euch bitten, meine Lösungswege anzuschauen und ggf. zu korrigieren.

Ich würde gleich mal mit einer Aufgabe loslegen:

Wir betrachten über einem Alphabet $[latex]\Sigma[/latex]$ = {0, 1} die Sprache
L := {w | die Länge von w ist gerade und die linke Hälfte von w enthält eine Eins}

Als Hinweis wurde noch gegeben, dass man mit der Form $[latex]0^{n} 1 0^{n+1} [/latex]$ argumentieren soll.

Meine Lösung:
Angenommen, L wäre regulär. Dann würde das PL gelten und es gäbe eine PLZ n.

Das Wort $[latex]0^{n} 1 0^{n+1} [/latex]$ ist dann in L enthalten und hat die Länge [latex]n+1+n+1 = 2n + 2 > n[/latex]

, d.h. es gibt eine Zerlegung $[latex]0^{n} 1 0^{n+1} = uvw[/latex]$ mit $[latex]|v| \geq 1[/latex]$ und $[latex] |uv| \leq n[/latex]$ , sodass $[latex]u v^{i} w[/latex]$ für alle $[latex]i \in N_{0} [/latex]$ in L liegt.

Wähle [latex]i = 2[/latex]

. Dann ist $[latex]u v^{2} w = uvvw[/latex]$ und müsste in L enthalten sein.

Da $[latex]|v| \geq 1[/latex]$ und $[latex]|uv| \leq n[/latex]$ und v zwei Mal aufgepumpt wird, und uv im ersten Nullerbereich liegt, werden links 2 weitere Nullen hinzugefügt, sodass jetzt die 1 in der rechten Hälfte liegt.

Damit liegt uvvw aber nicht mehr in L und das PL gilt nicht mehr. Daher kann L nicht regulär sein.

Wäre toll, wenn ihr mir hierfür Feedback geben könntet!

Dankeschön smile