Beweise mit dem regulären Pump-Lemma

8

Ich habe zwei Fragen:

  1. Ich betrachte die folgende Sprache

    L1={w{0,1}u{0,1}:w=uuR}.
    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?

    L2={w{0,1}w has same number of 101 substrings and 010 substrings}.

Vielen Dank für die Bearbeitung :)

Farseer
quelle
Hinweis. Mein Browser zeigt das Zeichen "nicht vorhanden" in der Beschreibung von . Keine Sorge: Es befindet sich in der Quelle, und das Wechseln des Browsers hat geholfen. L1
Hendrik

Antworten:

7

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.L1

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=1abbaaL1aabbaaL1L1

Wenn , dann nehmen Sie die Zeichenfolge ein p b b eine N . (Wir werden herausfinden, was wir wollen N.p>1apbbaNN 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 .xyzx=einp- -ky=einkz=bbeinN.

Jetzt lasst uns diesen String mal pumpen . (Wir werden später herausfinden, was ich sein soll.) Wir erhalten die Zeichenfolge x y i zichichxyichz , das gibt .einp- -keinichkbbeinN.=einp- -k+ichkbbeinN.

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.kichN.k[1,p]]ichein

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 .pk+ik=NN=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 a zu erhaltenN=p+p!apbbaNkapkybbaNy=aki=p!/k+1 .apkyibbaN=apkaikbbaN=apk+ikbbaN

Aber wir wissen, dass . Undpk+ik=pk+(p!k+1)k=pk+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!aL1L1

usul
quelle
Perfekte Antwort!
Farseer
Vielen Dank für die Hilfe. Die Idee möchte die Saite mit Bedacht auswählen.
Farseer
Ich hätte Ihnen gerne eine Antwort auf beide Sprachen gegeben, aber die zweite sieht schmerzhaft aus! Der Ansatz, der auf die Antwort auf dem ersten führte ich versucht zu beweisen , dass tatsächlich ist pumpbar - wenn ich zum letzten Fall bekam und konnte es nicht beweisen, konnte ich beginnen , zu sehen , wie die obige Zeichenfolge zu konstruieren. L1
Usul
@usul wie bist du dazu gekommen: , i = p ! / k + 1 i = p ! / k + 1 ? N=p+p!i=p!/k+1i=p!/k+1
Dima Knivets
3

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.0p12p0p+p!yp!p+p!

Luke Mathieson
quelle
1

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.

Farseer
quelle
Leider scheint es nicht zu funktionieren :( String 010010101101 (N = 2) hat jeweils drei (!) Vorkommen. Wenn wir den dritten Buchstaben löschen, erhalten wir 01010101101, das noch drei Vorkommen von 010 hat. Beachten Sie die Überlappung. Ich bin immer noch verwirrt ...
Hendrik Jan
Ja! Aber wir haben 4 Vorkommen von 101! Und so Menge von 101 Unterstrings! = Menge von 010
Farseer
Hoppla. Es tut uns leid. Ich hätte lesen sollen, was Sie genau gesagt haben: "Fügen Sie weitere 101 Teilzeichenfolgen hinzu". +1 (Fall geschlossen)
Hendrik Jan