Wie beweisen Sie, dass die Sprache der gleichlangen Palindrome, dh , 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?
context-free
pushdown-automata
Ohne Titel
quelle
quelle
Antworten:
Wie Luke bemerkt, gibt es ein Pumping Lemma für deterministische CFL . Wenn es zwei Zeichenfolgen gibtzz1 und zz2 in der Sprache mit gemeinsamem Präfix z , dann für deterministische Geräte die Berechnung in beiden Teilzeichenfolgen z muss 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 z fü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 SieK=L∩(a∗bba∗∪a∗bba∗bba∗)={anbban∣n≥0}∪{anbba2mbban∣m,n≥0} . WennL ist DCFL dann so ist K . Können wir pumpen?z1=a2nbba2n und z2=a2nbba2nbba2n auf 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.
quelle