Apakah ada bahasa bebas konteks yang ambigu dan deterministik?

36

Mari kita sebut bahasa bebas konteks deterministik jika dan hanya jika itu dapat diterima oleh otomat push-down deterministik, dan sebaliknya tidak deterministik.

Mari kita sebut bahasa bebas konteks secara inheren ambigu jika dan hanya jika semua tata bahasa bebas konteks yang menghasilkan bahasa ambigu, dan tidak ambigu sebaliknya.

Contoh bahasa deterministik dan tidak ambigu adalah bahasa: Contoh bahasa yang tidak pasti, tidak ambigu adalah bahasa:

{{Sebuah}^{n} b^{n} \in {Sebuah, b}^{*} | n \geq 0}

$\{a^{n}b^{n} \in \{a, b\}^{*} | n \ge 0\}$

{w \in {Sebuah, b}^{*} | w = w^{R}}

$\{w \in \{a, b\}^{*} | w = w^{R}\}$

Dari Wikipedia , contoh bahasa bebas konteks yang ambigu secara inheren adalah penyatuan bahasa bebas konteks berikut, yang juga harus bebas konteks:

L. = {{Sebuah}^{n} b^{m} c^{m} d^{n} \in {Sebuah, b, c, d}^{*} | n, m \geq 0} \cup {{Sebuah}^{n} b^{n} c^{m} d^{m} \in {Sebuah, b, c, d}^{*} | n, m \geq 0}

$L = \{a^{n}b^{m}c^{m}d^{n} \in \{a, b, c, d\}^{*} | n, m \ge 0\} \cup \{a^{n}b^{n}c^{m}d^{m} \in \{a, b, c, d\}^{*} | n, m \ge 0\}$

Sekarang untuk pertanyaan:

Apakah diketahui apakah ada bahasa bebas konteks yang deterministik, inheren ambigu? Jika demikian, adakah contoh (mudah)?
Apakah diketahui apakah ada bahasa bebas konteks yang tidak bersifat deterministik, inheren ambigu? Jika demikian, adakah contoh (mudah)?

Jelas, karena bahasa bebas konteks yang ambigu secara inheren ada ( adalah contoh), jawaban untuk salah satu dari pertanyaan ini mudah, jika diketahui apakah deterministik atau nondeterministik. Saya juga berasumsi bahwa memang benar bahwa jika ada yang deterministik, pasti ada juga yang tidak deterministik ... tapi saya pernah terkejut sebelumnya. Referensi dihargai, dan permintaan maaf sebelumnya jika ini adalah hasil yang terkenal dan terkenal (dalam hal ini, saya benar-benar tidak menyadarinya). $L$ $L$

formal-languages automata formal-grammars pushdown-automata Patrick87
sumber

30

$L$ $L$

Suatu bahasa dapat dijelaskan oleh beberapa tata bahasa bebas konteks jika dan hanya jika itu dapat dikenali oleh beberapa otomat non-deterministik. Sebagai kasus khusus ini, tata bahasa bebas konteks yang ambigu secara inheren dapat diuraikan oleh beberapa otomat non-deterministik.

Pada catatan terakhir, otomat push-down deterministik apa pun juga tidak deterministik (ini adalah kasus untuk apa saja yang dapat non deterministik, untuk definisi nondeterminisme yang masuk akal).

Alex ten Brink
sumber

+1 untuk referensi untuk fakta bahwa semua CFL deterministik secara inheren tidak ambigu. Bahkan, itu menjawab pertanyaan lain juga: karena ada bahasa yang secara inheren ambigu, dan itu tidak deterministik, itu harus nondeterministic (perhatikan bahwa definisi saya tentang CFL nondeterministic tidak standar, karena tidak termasuk CFL deterministik; itu kesalahan saya untuk penyalahgunaan istilah). Dalam hal apa pun, Anda telah memberikan contoh untuk pertanyaan (2), dan menunjukkan bahwa pertanyaan (1) tidak mungkin dilakukan. Saya akan menunggu dan melihat apakah seseorang menguraikan lebih banyak, tetapi sebaliknya akan menerima ini sebagai benar. Terima kasih!

Patrick87

0

membaca wikipedia & jawabannya & komentar Anda di atasnya, kembali (Q2) untuk menyatakan secara langsung, semua CFL yang inheren ambigu harus nondeterministik di bawah std defn (termasuk contoh Anda sendiri!). berlari melintasi ref ini

Beberapa bahasa bebas konteks yang bersifat mendua yang ambigu / Shamir & kemungkinan yang lain dipelajari dalam literatur.

vzn
sumber

Apakah ada bahasa bebas konteks yang ambigu dan deterministik?

Jawaban: