beweisen, dass kein DPDA die Sprache von Palindromen mit gerader Länge akzeptiert

7

Wie beweisen Sie, dass die Sprache der gleichlangen Palindrome, dh L={wwRw{0,1}}, kann von einem bestimmten Push-Down-Automaten nicht akzeptiert werden?

Gibt es eine allgemeine Möglichkeit zu beweisen, dass eine kontextfreie Sprache von einem deterministischen PDA nicht akzeptiert werden kann? Ich meine vielleicht so etwas wie Lemma pumpen?

Ohne Titel
quelle
5
Die Antworten auf diese Frage können hilfreich sein.
Luke Mathieson

Antworten:

4

Wie Luke bemerkt, gibt es ein Pumping Lemma für deterministische CFL . Wenn es zwei Zeichenfolgen gibt zz1 und zz2 in der Sprache mit gemeinsamem Präfix z, dann für deterministische Geräte die Berechnung in beiden Teilzeichenfolgen zmuss das Selbe sein. Die Idee hinter diesem Lemma ist, dass jetzt auch das Pumpen für beide Saiten gleich sein muss. In kontextfreien Sprachen hat das Pumpen die Formuvwxy. Das Lemma besagt , dass entweder vx sind drinnen zfür beide zz1 und zz2 oder v ist drinnen z und da sind x1 und x2 Innerhalb z1 und z2 so können wir beide Wörter auf diese Weise pumpen.

Ausführliche Informationen finden Sie im Lemma.

Nun überlegen Sie K=L(abbaabbabba)={anbbann0}{anbba2mbbanm,n0}. WennL ist DCFL dann so ist K. Können wir pumpen?z1=a2nbba2n und z2=a2nbba2nbba2nauf die gleiche Weise? Neinv,x Teile sind beim Pumpen anders angeordnet z1,z2 was dem DCFL-Pumpen widerspricht.

Auch hier muss man etwas genauer sein und die richtigen Teile des Lemmas zitieren.

Hendrik Jan.
quelle