Pumping Lemma Beweise für reguläre Sprachen

08.02.2021, 23:55	Auf diesen Beitrag antworten »
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 , 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 . 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

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »