Warum ist Nichtdeterminismus (Push-down-Automaten) notwendig?

Ich würde gerne wissen, warum für die Erkennung kontextfreier Sprachen nur nicht deterministische Push-Down-Automaten (DPA = NPDA) funktionieren. Warum erkennen deterministische Push-Down-Automaten (DPDA) solche Sprachen nicht?

Ich bin mir nicht ganz sicher, welchen Geschmack von "Warum" Sie suchen. Ein Grund für die Leistungssteigerung beim Zulassen von Nichtdeterminismus ist im folgenden Beispiel zu sehen:

Sei die Menge der Palindrome über einem Alphabet (mit mindestens zwei Symbolen), wobei die Umkehrung von . Ein NPDA für diese Sprache kann einfach weiterhin Symbole auf seinen Stapel schieben und dann irgendwann vermuten, dass er die Mitte der Eingabe erreicht hat, und den Stapel allmählich leeren. Beachten Sie, dass die Annahmebedingung rein existenziell ist - es reicht aus, dass das zu akzeptierende Wort richtig erraten wird.w ˉ w ˉ w$L$$w\bar{w}$$\bar{w}$$w$

Ein deterministischer PDA müsste die Position, die er als Mitte betrachtet, auf eine Weise auswählen, die nur vom aktuellen Präfix abhängt. Angenommen, ist eine solche DPDA. Für jedes sei ; sei das leere Wort und . Dies ist eine Folge von Palindromen, von denen jedes ein Präfix des nächsten ist, so dass nach dem Lesen von in einem akzeptierenden Zustand , wobei der Stapel leer ist . Nach dem Taubenlochprinzip muss es einige so dass undk ∈ N u k = a b 2 k a v 0 v k + 1 = v k u k v k A q k v k k , l k ≠ l q k = q l k A v k u k v k v l u k v $A$$k\in\mathbb{N}$$u_k=ab^{2k}a$$v_0$$v_{k+1} = v_ku_kv_k$$A$$q_k$$v_k$$k,l$$k\neq l$$q_k=q_l$(Es gibt eine endliche Anzahl von Zuständen, und daher müssen einige "wiederverwendet" werden, da es eine unendliche Anzahl von ) Aber dann kann , das ein Palindrom ist, nicht von , was nicht der ist.$k$$A$$v_ku_kv_k$$v_lu_kv_k$

FA akzeptiert deterministisch oder nicht deterministisch dieselbe Sprache (dh Regular Lang).

Im Fall von PDA werden jedoch einige CFLs (CFLs ohne Präfixeigenschaft (außer RLs)) nicht akzeptiert , wenn wir das deterministische Verhalten einschränken .

Warum so?

Stellen Sie sich ein Beispiel für eine CFL vor, die keine Präfix-Eigenschaft hat (Präfix-Eigenschaft einer Sprache: Keine Zeichenfolge ist ein korrektes Präfix einer anderen Zeichenfolge in der Sprache).

L = wwr

z.B. Zeichenfolgen 00 und 0000 . (00 ist ein richtiges Präfix von 0000, daher hat wwr keine Präferenzeigenschaft).

Bei Auftreten von 00 geht DPDA in den Endzustand über. Nun , da DPDA keine andere Wahl zwischen acceptancy und Kontinuität hat , kann sie nicht akzeptiert 0000 nach der Übernahme 00 . Dies ist der Ort, an dem PDA Nichtdeterminismus erfordert .

Beobachtungen : Bei FA lang (RL) ohne Präferenz. Eigenschaft kann deterministisch akzeptiert werden (z. B. Zeichenfolgen, die mit 0 beginnen). Dies zeigt, dass der Effekt der Präfixeigenschaft von RL und CFL unterschiedlich ist . Der Unterschied zwischen Determinismus und Nichtdeterminismus für PDA führt zu einer neuen Familie von Lang. welches von DPDA akzeptiert wird. Diese Sprache heißt DCFL .