Mengapa non-determinisme (Push-down automata) diperlukan?

Saya ingin tahu mengapa untuk pengenalan bahasa bebas konteks, hanya automata push-down (DPA = NPDA) non-deterministik yang berfungsi. Mengapa deterministic push-down automata (DPDA) tidak mengenali bahasa seperti itu?

Saya tidak yakin rasa "mengapa" yang Anda cari. Salah satu alasan peningkatan daya ketika memungkinkan nondeterminisme dapat dilihat pada contoh berikut:

$L$$w\bar{w}$$\bar{w}$$w$

$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$$k$$A$$v_ku_kv_k$$v_lu_kv_k$

FA secara deterministik atau non-deterministik menerima bahasa yang sama (mis. Reguler Lang).

Tetapi dalam kasus PDA , jika kita membatasi untuk berperilaku deterministik, ia tidak akan menerima beberapa CFL (CFL tanpa properti awalan (kecuali RL)).

Kenapa begitu?

Pertimbangkan contoh CFL yang tidak memiliki properti awalan (Properti awalan dari lang: tidak ada string adalah awalan yang tepat dari string lain di lang).

L = wwr

misalnya. string 00 dan 0000 . (00 adalah awalan yang tepat dari 0000 sehingga wwr tidak memiliki properti pref).

Pada kejadian 00 DPDA akan masuk ke negara final. Sekarang karena DPDA tidak memiliki pilihan antara penerimaan dan kontinuitas , DPDA tidak dapat menerima 0000 setelah menerima 00 . Ini adalah tempat di mana PDA membutuhkan non-determinisme .

Pengamatan : Dalam kasus FA, lang (RL) tanpa pref. properti dapat diterima secara deterministik (mis. string dimulai dengan 0). Ini menunjukkan bahwa efek properti awalan RL dan CFL berbeda . Perbedaan antara determinisme dan non-determinisme untuk PDA menimbulkan keluarga bahasa baru. yang diterima oleh DPDA. Bahasa ini disebut DCFL .