Mengapa memutuskan keteraturan bahasa bebas konteks tidak dapat diputuskan?

Seperti yang telah saya pelajari, memutuskan keteraturan bahasa bebas konteks tidak dapat diputuskan.

Namun, kita dapat menguji keteraturan menggunakan teorema Myhill – Nerode yang menyediakan kondisi yang diperlukan dan memadai. Jadi masalahnya harus diperhitungkan.

Di mana kesalahan saya?

formal-languages computability regular-languages undecidability Jiya
sumber

Bagaimana Anda mengusulkan untuk mengatakan apakah relasi Myhill-Nerode memiliki sejumlah kelas kesetaraan yang terbatas? Menurut Anda, properti apa dari bahasa bebas konteks yang memungkinkan Anda melakukan itu?

David Richerby

Silakan periksa definisi komputabilitas: Anda perlu memberikan mesin Turing (atau, lebih umum, sebuah algoritma) yang memecahkan masalah (selalu). Myhill-Nerode, per se, bukan algoritma, hanya karakterisasi. Apakah properti yang disediakan dapat diputuskan? Sudahkah Anda mencoba mengubah teorema menjadi suatu algoritma?

Raphael

@Jiya Apa yang Anda maksud dengan "putuskan keteraturan"? Pada awalnya, tampak jelas apa artinya itu tetapi sebenarnya lebih halus. Prosedur pengambilan keputusan (algoritma) harus mengambil input yang terbatas, jadi bagaimana Anda akan memberikan bahasa tak terbatas sebagai input? Mungkin Anda ingin menggunakan ekspresi seperti

{a^{n} b^{n} ∣ n \geq 0}

$\{a^nb^n\mid n\ge 0\}$ . OK, tapi ekspresi apa yang akan Anda izinkan?

{a^{n} b^{m} ∣ the m th Turing machine halts on input m}

$\{a^nb^m\mid \text{the }m\text{th Turing machine halts on input }m\}$ ?

{a^{n} b^{k n} ∣ k is one of David Richerby's favourite numbers}

$\{a^nb^{kn}\mid k\text{ is one of David Richerby's favourite numbers}\}$ ?

David Richerby

@Jiya Tentu saja, ya. Tetapi Anda harus memilih rangkaian ekspresi apa yang ingin Anda terima dan menulis spesifikasi formal ekspresi itu. Kemudian, mesin Turing Anda harus mengurai ekspresi dan memutuskan apakah itu sesuai dengan bahasa biasa atau tidak.

David Richerby

@Jiya Jika satu-satunya bahasa yang Anda pertimbangkan adalah bahasa yang ada dalam formulir

{a^{k x} b^{ℓ x} c^{m x} | x \geq 0}

$\{a^{kx}b^{\ell x}c^{mx}|x\ge 0\}$ dimana

k

$k$ ,

ℓ

$\ell$ dan

m

$m$ adalah konstanta, maka bahasa yang dihasilkan adalah reguler jika, dan hanya jika, dua atau tiga

k

$k$ ,

ℓ

$\ell$ dan

m

$m$ adalah nol. Jadi, untuk bahasa didefinisikan dengan cara itu, masalah menentukan apakah bahasa yang dihasilkan biasa adalah decidable. Tapi, jika Anda mengizinkan hubungan yang lebih kompleks antara angka

a

$a$ s,

b

$b$ dan

c

$c$ s, dapat diputuskan apakah suatu bahasa biasa atau tidak. Inilah sebabnya mengapa sangat penting bagaimana bahasa ditentukan.

David Richerby

Jawaban:

Myhill – Nerode memang memberikan karakterisasi bahasa biasa tapi itu tidak cukup untuk menunjukkan bahwa masalahnya dapat diputuskan. "Decidable" berarti ada algoritma (lebih formal, mesin Turing) yang berakhir untuk setiap input dan, tentu saja, selalu memberikan jawaban yang benar. Jadi, dalam hal ini, Anda perlu memberikan algoritma yang, diberi bahasa sebagai input, menentukan apakah relasi Myhill-Nerode memiliki jumlah kelas ekivalensi yang terbatas. Ternyata ini tidak dapat dilakukan untuk bahasa bebas konteks; rincian dalam buku teks bahasa formal favorit Anda.

Jika Anda ingin memutuskan apakah suatu bahasa umum itu teratur, yang lebih halus adalah Anda harus berhati-hati tentang apa yang menjadi input untuk algoritma Anda. Input harus berupa string hingga - jika tidak, bahkan hanya membaca input akan menjadi algoritma non-terminating. Dalam hal bahasa bebas konteks, Anda bisa menggunakan tata bahasa sebagai representasi terbatas dari bahasa tak terbatas. Untuk bahasa yang lebih umum, Anda perlu ... yah, sesuatu yang lebih umum. Namun, pada akhirnya, jika Anda ingin berurusan dengan semua bahasa, Anda akan dikutuk. Di atas setiap alfabet terbatas, ada banyak bahasa yang tak terhitung banyaknya tetapi hanya banyak string terbatas. Itu berarti Anda tidak dapat menjelaskan semua bahasa menggunakan string hingga. ¹Oleh karena itu, mencoba menulis suatu algoritma untuk menentukan apakah bahasa arbitrer yang diberikan sebagai input adalah benar-benar gagal sebelum dimulai. Bukan hanya karena Anda tidak dapat menulis algoritme: Anda bahkan tidak dapat menulis input!

Perhatikan bahwa ini tidak berarti bahwa Anda, manusia, tidak dapat menggunakan Myhill – Nerode untuk menentukan apakah bahasa itu teratur. Itu hanya berarti bahwa Anda tidak dapat menuliskan satu set instruksi yang tepat untuk memberi tahu saya bagaimana melakukannya. Pada titik tertentu, seperangkat instruksi semacam itu harus mengatakan sesuatu seperti, "Dan kemudian bermain dengannya untuk melihat apa yang berhasil," atau "Dari sana, Anda harus mencari tahu sendiri."

Secara khusus, ini berarti bahwa beberapa bahasa harus diputuskan, karena ada lebih banyak bahasa daripada algoritma.

David Richerby
sumber

Kita dapat menghindari masalah dengan pengkodean input dengan membatasi diri kita pada semua bahasa yang berulang secara berulang, atau dapat dipisahkan, atau bahkan bebas konteks. Kemudian, kita memiliki pengkodean input "alami" (tata bahasa, mesin Turing, ...) tetapi masih belum dapat memutuskan keteraturan. Jadi, jelas, ada banyak hal halus yang sedang terjadi.

Raphael

Terima kasih Raphael. Saya telah mengedit untuk memperjelas bahwa bagian "malapetaka" yang dimaksud tidak dapat menerima semua bahasa sebagai masukan.

David Richerby