Beweisführung bei PPL

Question

Hallo,

1. Frage: Ist das Wort $(111 111)^6$ Teil der Sprache $L$? Ich vermute nein.

2. Frage: Welches konkrete Wort $w \in L$, $|w| \geq n$ wurde in der Lösung gewählt, um zu beweisen, dass die Sprache nicht regulär ist? Ich vermute: $w= |xy^2z| mit$ $i=2$.

3. Frage: Habe ich das richtig verstanden, dass das Wort w hier in x=0, y=w, z=0 zerlegt wurde, da $|xy| \leq n$ und $|y| \geq 1$?  Und anschließend würde das Wort $111$ (kleinstes Wort als Bsp.) aufgepumpt $111 111$, nochmal aufgepumpt $111 111 111 111$, usw. (eben immer um die doppelte Länge) lauten. Dieses kann niemals mit der Sprache $111$, $111 111 111$, .... (mit Faktor 3) übereinstimmen.  Könnte man hier dann nicht $i = beliebig$ außer 0,1 und 3 wählen und man fällt immer aus der Sprache?

Vielen Dank!

Answer 1

1. wenn du mit (111111)⁶ das Wort mit 46 Einsen meinst, dann nicht. Es sind nämlich nur die Wörter mit 3, 9, 81, 6561 … Einsen teil der Sprache. Die Anzahl der Einsen des vorherigen Wortes quadriert ergibt nämlich die Anzahl der Einsen des nächsten Wortes.

2. So wie ich die Lösung verstehe wurde in diesem Beispiel kein bestimmtes Wort gewählt, da dies für alle Wörter der Sprach gezeigt werden kann (wir machen ja eine Abschätzung und sagen es gillt bereits für das 2. Wort nicht mehr wenn vom ersten ausgehen, damit kann es für alle anderen auch nicht gehen). Bei den Beispielen im Tutorium war es wichtig eine „bestimmte Art von Wörtern“ der Sprach zu verwenden. Je nach dem welches Wort wir dort gewählt haben konnte es sein, dass wir durch Pumpen keinen Widerspruch zeigen konnten.

3. ja, es wurde gezeigt, dass mindestens das 3-Fache benötigt wird um ein neues Wort zu generieren, das gilt aber nur um auf das 2. Wort zu kommen. Danach wird bereits das 9-Fache benötigt, dann dass 81-Fache etc. Das 2-Fache kann daher auf keinen Fall ausreichend sein, genau so wie z.B. das 0-Fache. Beim Pumping Lemma kann meist für verschiedene i gezeigt werden, dass das Wort nach dem Pumpen nicht mehr Teil der Sprache ist. Da wir einen Widerspruchsbeweis führen reicht jedoch ein einziges Gegenbeispiel.

 

Viele Grüße,

Sören (Tutor)