Beweise mit dem regulären Pump-Lemma

Ich habe zwei Fragen:

1. Ich betrachte die folgende Sprache

   $$L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}.$$ Mit anderen Worten, $w$ ist kein Palindrom mit gerader Länge. Ich habe bewiesen, dass diese Sprache NICHT regelmäßig ist, indem ich bewiesen habe, dass ihre Ergänzung nicht regelmäßig ist. Meine Frage ist, wie man es mit dem Pump-Lemma beweist, ohne das Komplement zu überschreiten.

2. Lassen Ich habe durch die Verwendung von Äquivalenzklassen bewiesen, dass diese Sprache nicht regelmäßig ist. Wie kann ich es mit dem Pump-Lemma beweisen?

   $$L_2=\{w\in\{0,1\}^* \mid \text{$w$ has same number of 101 substrings and 010 substrings}\}.$$

Vielen Dank für die Bearbeitung :)

Nicht alle nicht regulären Sprachen bestehen den Test des Pump-Lemmas nicht. Wikipedia hat ein ärgerlich komplexes Beispiel für eine nicht reguläre Sprache, die gepumpt werden kann. Selbst wenn eine Sprache nicht regulär ist, können wir diese Tatsache möglicherweise nicht mit dem Pump-Lemma beweisen.

Es stellt sich jedoch heraus, dass wir das Pump-Lemma verwenden können, um zu beweisen, dass Ihre Muttersprache nicht regelmäßig ist. Bei der zweiten bin ich mir nicht sicher.

Behauptung: ist nicht regulär.$L_1$

Beweis: Durch das Pump-Lemma. Sei die Pumplänge. (Ich werde das Alphabet { a , b } anstelle von { 0 , 1 } verwenden .) Wenn p = 1 , nehmen Sie die Zeichenfolge a b b a a , die sich in L 1 befindet, und pumpen Sie sie zu a a b b a a, das nicht in L 1 ist , also wäre L 1 nicht regulär.$p$$\{a,b\}$$\{0,1\}$$p = 1$$abbaa$$L_1$$aabbaa$$L_1$$L_1$

Wenn , dann nehmen Sie die Zeichenfolge ein p b b eine N . (Wir werden herausfinden, was wir wollen $p > 1$$a^pbba^{N}$$N$ später sein.) Prüfen Dann jede Teilung der Saite in , wo x = a p - k , y = ein k und z = b b ein N .$xyz$$x=a^{p-k}$$y=a^k$$z=bba^{N}$

Jetzt lasst uns diesen String mal pumpen . (Wir werden später herausfinden, was ich sein soll.) Wir erhalten die Zeichenfolge x y i$i$$i$$xy^iz$ , das gibt .$a^{p-k}a^{ik}bba^{N} = a^{p-k+ik}bba^{N}$

Jetzt lass uns zurück gehen. Zuerst haben wir . Dann wurde eine Auswahl von k getroffen. Dann haben wir i ausgewählt . Wir wollen herausfinden, welches N zu wählen ist, damit wir für jede Wahl von k ∈ [ 1 , p ] ein i wählen können , das diese Zeichenkette zu einem Palindrom macht, indem wir die Zahl von a s links gleich der Zahl auf der machen Recht. (Es wird immer eine gerade Länge haben.)$N$$k$$i$$N$$k \in [1,p]$$i$$a$

Wir wollen also immer . Wenn wir mit der Mathematik herumspielen, finden wir, dass wir N = p + p wählen sollten ! und wähle i = p ! / k + 1 .$p-k+ik=N$$N=p+p!$$i=p!/k+1$

Um es noch einmal zusammenzufassen, wir haben und wählt die Zeichenfolge ein p b b ein N . Dann wurde eine Auswahl von k getroffen, so dass die Zeichenkette aus a p - k y b b a N bestand, wobei y = a k . Dann haben wir i = p gewählt ! / k + 1 . Wir haben die Saite gepumpt, um ein p - k y i b b $N=p+p!$$a^pbba^N$$k$$a^{p-k}ybba^N$$y=a^k$$i=p!/k + 1$ .$a^{p-k}y^{i}bba^N = a^{p-k}a^{ik}bba^N = a^{p-k+ik}bba^N$

Aber wir wissen, dass . Und$p-k+ik = p-k+(\frac{p!}{k}+1)k = p-k+p!+k=p+p!$. Die Anzahl der a s an beiden Enden ist also gleich, daher ist die Zeichenfolge ein Palindrom mit gerader Länge, also nicht in L 1 , also ist L 1 nicht regulär. $N=p+p!$$a$$L_1$$L_1$$\square$

Für Frage eins die Zeichenfolge ist ein geeignetes Gegenbeispiel. Was auch immer die Länge von y ist, es muss ein Faktor von p sein ! , also pumpen wir es genug und wir bekommen p + p ! Nullen am Anfang.$0^{p}1^{2p}0^{p+p!}$$y$$p!$$p+p!$

Nach langem Nachdenken denke ich, dass ich 2 geantwortet habe.

Wir wählen String (010) ^ N (101) ^ N, wobei N die Pumplänge ist. Egal für welches y wir uns entscheiden, xy ^ 0z hat mehr 101 als 010. Die Idee ist, dass wir nur mehr 101 Unterzeichenfolgen im ersten Teil der Zeichenfolge hinzufügen oder einige 010 Unterzeichenfolgen entfernen können.