Ambiguitas dalam bahasa reguler dan bebas konteks

Saya memahami klaim berikut ini sebagai benar:

1. Dua derivasi berbeda dari string dalam CFG yang diberikan kadang-kadang dapat menghubungkan pohon parse yang sama dengan string.
2. Ketika ada derivasi dari beberapa string dalam CFG yang diberikan yang menghubungkan pohon parse yang berbeda, CFG bersifat ambigu.
3. Beberapa bahasa bebas konteks yang dihasilkan oleh CFG ambigu juga dihasilkan oleh CFG yang ambigu.
4. Beberapa bahasa sedemikian rupa sehingga satu-satunya CFG yang dapat menghasilkan mereka (dan ada beberapa seperti itu) adalah ambigu.

Q1. Saya memahaminya juga tidak dapat diputuskan apakah CFG yang sewenang-wenang bersifat mendua, dalam pengertian poin 3 di atas. Atau apakah itu lebih diputuskan apakah bahasa bebas konteks itu ambigu, dalam arti poin 4? Atau keduanya tidak dapat diputuskan?

Q2. Manakah dari poin 1-4 yang menjadi salah ketika kita mengganti "bebas konteks" dengan "biasa"? Apakah tata bahasa dan bahasa reguler selalu tidak ambigu?

Tentang Q1: Baik masalah ambiguitas (diberikan CFG, apakah ambigu) maupun masalah ambiguitas yang melekat (diberikan CFG, apakah bahasanya secara inheren ambigu, yaitu apakah CFG yang setara ambigu) tidak dapat diputuskan. Berikut ini adalah referensi asli:

• Ketidakpastian ambiguitas dibuktikan oleh Cantor (1962) , Floyd (1962) , dan Chomsky dan Schützenberger (1963) . Bukti dalam buku teks biasanya berkurang dari Masalah Post Correspondence.
• Ketidakpastian ambiguitas inheren dibuktikan oleh Ginsburg dan Ullian (1966) .

Tentang Q2: Tata bahasa biasa adalah tata bahasa bebas "satu sisi linear" konteks, di mana paling banyak satu nonterminal muncul di bagian kanan aturan apa pun, dan di mana nonterminal itu adalah yang terakhir (dalam tata bahasa linear kanan ) atau pertama (di tata bahasa linear kiri ) posisi. Tata bahasa seperti itu dengan mudah diterjemahkan ke dalam automata keadaan terbatas yang setara (kira-kira dengan mempertimbangkan setiap nonterminal sebagai suatu keadaan), yang tidak ambigu jika tata bahasa regulernya tidak ambigu. Kelas tata bahasa reguler yang tidak ambigu dan automata yang tidak ambigu telah dipelajari secara khusus oleh Stearns dan Hunt (1985) , yang menunjukkan bahwa mereka menikmati algoritma yang dapat dilacak untuk masalah inklusi.

1. $\beta A\gamma\Rightarrow \beta\alpha\gamma$$A\to\alpha$$A$$X_1,\dots,X_m$$A\to X_1\cdots X_m$

   $\gamma A\eta B\theta$$A$$B$$A\to\alpha$$\gamma\alpha\eta B\theta$$B\to\beta$$\gamma A\eta\beta\theta$$\gamma\alpha\eta\beta\theta$(selalu menurunkan nonterminal paling kiri dalam bentuk sentensial apa pun) atau derivasi paling kanan memaksakan urutan tetap untuk mengunjungi pohon derivasi, dan kemudian ada derivasi tunggal untuk pohon derivasi yang diberikan.

   Dalam tata bahasa bebas konteks linear , tidak ada pilihan seperti itu, karena ada paling banyak satu nonterminal dalam bentuk sentensial apa pun, dan ada derivasi tunggal untuk pohon derivasi tertentu, yang paling kiri dan paling kanan.

2. $w$$w$$w$

3. dan 4. Jika Anda mengambil tampilan automata keadaan-terbatas, cukuplah untuk menentukan automaton Anda yang mendua untuk mendapatkan automat yang tidak ambigu untuk bahasa yang sama: akan ada proses tunggal untuk kata tertentu. Otomat deterministik ini setara dengan tata bahasa reguler yang tidak ambigu.$~$

   $S\to A\mid B,\,A\to a,\,B\to a$$a$$S\Rightarrow A\Rightarrow a$$S\Rightarrow B\Rightarrow a$$S\to a$

$O(|G|^2)$$(q,q')$$q\neq q'$

$G$$\Sigma^*$

Saya tidak mengerti tentang bahasa apa yang Anda gunakan untuk berbicara 4. Setiap bahasa CF memiliki tata bahasa yang ambigu.

Q2. Semuanya dapat diputuskan jika Anda memiliki kesepakatan dengan tata bahasa biasa. Anda hanya harus membangun DFA minimal dan menggunakannya Anda dapat membangun tata bahasa yang tidak ambigu. Jika Anda memiliki kesepakatan dengan bahasa reguler yang ditentukan oleh tata bahasa CF, jawabannya adalah tidak - lihat Q1.

Itu tergantung pada apakah Anda mengganti 'bebas konteks' dengan 'biasa' hanya di depan 'bahasa', atau juga di depan 'tata bahasa'.

Semua bahasa reguler dihasilkan oleh tata bahasa reguler , dan khususnya, oleh tata bahasa reguler yang tidak ambigu, misalnya LL (1) tata bahasa reguler-kanan, yang semuanya tidak ambigu.