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

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Pumping Lemma Beweise für reguläre Sprachen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

pumpkin lemma
unregistriert

Pumping Lemma Beweise für reguläre Sprachen

Zitatantwort auf diesen Beitrag erstellen

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

08.02.2021 23:55

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Pumping Lemma Beweise für reguläre Sprachen