Memutuskan apakah bahasa yang peka konteks unary itu teratur

Ini adalah hasil yang terkenal dari pertanyaan itu

Apakah tata bahasa bebas konteks menghasilkan bahasa reguler?

tidak dapat ditentukan. Namun, itu menjadi decidable pada alfabet unary, hanya karena dalam kasus ini, kelas bahasa bebas konteks dan reguler bertepatan.

Pertanyaan saya adalah untuk mengetahui apa yang terjadi pada bahasa yang peka konteks unary .

Apakah dapat memutuskan untuk mengetahui apakah tata bahasa konteks-sensitif yang diberikan pada alfabet unary menghasilkan bahasa reguler.

Jika jawabannya positif, estimasi kerumitan akan diterima.

Sayangnya, masalah Anda tidak dapat diputuskan. Pendekatan yang saya temui (yang mungkin terlalu padat, jadi siapa pun yang memiliki pendekatan yang lebih bijaksana harus melangkah!) Pertama menggunakan argumen diagonal untuk menunjukkan bahwa ada CSL unary $X$yang tidak teratur (berbeda dengan hasil positif untuk CFL unary), dan kemudian mengurangi dari masalah penghentian untuk mesin Turing oleh, diberi TM $M$ , membangun CSG $G$ yang mensimulasikan $M$ pada panjang pita lebih pendek dari string parse $w$ , mengenali $X$ jika $M$ berhenti tanpa melampaui batas-batasnya dan gagal mem-parsing sebaliknya, sehingga $G$ berhasil mem-parsing semua $w \in X$yang cukup lama jika $M$ berhenti (sehingga $L(G)$ berbeda dari $X$ hanya pada banyak string dan karenanya tidak dapat teratur), jika tidak $G$ mengenali bahasa kosong (yang jelas-jelas teratur).

Kunci dari pendekatan ini adalah pengamatan bahwa CSG tidak hanya peduli dengan masalah tata bahasa seperti struktur frasa - memang, derivasi deret CSG dapat melakukan perhitungan ruang-terikat nondeterministik sewenang-wenang (memang ada $\mathbf{PSPACE}$-Lengkap CSLs) sebelum sampai ke bisnis menyelaraskan dengan string parse. Ini paling mudah diamati melalui konversi standar antara CSG dan tata bahasa monoton (yang terus bekerja ketika dibatasi pada huruf unary), dan penggunaan produksi monoton sederhana untuk mensimulasikan transisi mesin Turing pada string derivasi yang mewakili tahapan dalam sejarah perhitungan. Di seluruh jawaban ini saya akan menganggap pembaca dapat melihat sebagian besar detail ketika CSG diperlukan untuk mensimulasikan perhitungan yang diberikan. (Saya menganggap penanya merasa nyaman dengan semua ini, tapi saya akan menyelesaikannya untuk kelengkapan. Namun, jangan ragu untuk meminta klarifikasi dalam komentar.)

Pertama, kami membutuhkan CSG unary reguler kami. ( EDIT: jadi, ini berlebihan - CSL unary yang tidak teratur dapat dengan mudah dipamerkan misalnya melalui pemompaan lemma pada bahasa apa pun yang menunjukkan ketidakteraturan paling mendasar. Lihat komentar sebagai contoh. Di belakang, dengan menggunakan argumen diagonal seperti membawa hulu ledak nuklir ke perkelahian dengan pisau. Teliti konstruksi ini jika Anda penasaran, jika tidak langsung ke pengurangannya.)

Biarkan menjadi enumerasi DFA lebih dari alfabet { 1 } , sehingga jumlah negara dalam D i meningkat di i . Kami menjelaskan CSG G X dalam hal perilakunya sementara mengurai string 1 n ∈ { 1 } ∗ :$D_1, D_2, ...$$\{1\}$$D_i$$i$$G_X$$1^n \in \{1\}^*$

1. Secara nondeterministis menghasilkan string "kosong" non-terminal, yang kita anggap sebagai "pita". Salah satu terminal non-kosong harus non-terminal "kosong + baca-tulis + keadaan awal" yang terpisah. Jika string parse bukan 1 n maka derivasi ini akan berakhir gagal. Kami menggambarkan sisa proses dalam hal perhitungan deterministik yang disimulasikan oleh satu-satunya derivasi yang mungkin.$n$$1^n$
2. Cetak pada rekaman itu suatu pengkodean diikuti oleh angka i dalam biner, di mana i = n - c dan c dipilih sehingga kami selalu memiliki cukup ruang pada pita kami untuk melakukan apa yang kami butuhkan. (Ini dimungkinkan karena ruang yang diperlukan untuk menyandikan D i dan i tumbuh secara logaritma di i .)$D_i$$i$$i = n - c$$c$$D_i$$i$$i$
3. Evaluasi pada input 1 i . Ini tidak memerlukan rekaman D i yang mewakili - Anda hanya dapat menyimpan satu negara, yang Anda ubah sesuai dengan transisi D i saat Anda mengurangi i .$D_i$$1^i$$D_i$$D_i$$i$
4. Jika menolak 1 i , timpa seluruh pita dengan non-terminal yang menghasilkan 1 . Kalau tidak gagal.$D_i$ $1^i$$1$

Kami mengambil . Jelas X ≠ L ( D i ) untuk semua i , karena 1 i + c ∈ X ⇔ 1 i + c ∉ L ( D i ) .$X = L(G_X)$$X \ne L(D_i)$$i$$1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$

Langkah selanjutnya adalah merancang pengurangan dari masalah penghentian ke masalah penanya. (Jika Anda melewatkan bagian di atas, misalkan adalah CSL unary non-reguler sewenang-wenang yang dihasilkan oleh CSG G X. )$X$$G_X$

Biarkan menjadi TM yang sewenang-wenang. Kami mengonversi M menjadi CSG G yang berperilaku sebagai berikut pada parse string 1 n :$M$$M$$G$$1^n$

1. Hasilkan kosong non-terminal, yang paling kiri menjadi kosong kosong + read-write head non-terminal, dan juga menghasilkan "batas" non-terminal di setiap sisi. Sekali lagi, jika kita menghasilkan jumlah non-terminal yang salah maka kita gagal.$n-2$
2. Mensimulasikan di ruang antara batas non-terminal. Jika M pernah bergeser ke salah satu negara batas, kami mengakhiri simulasi dan menganggap bahwa M tidak pernah berhenti.$M$$M$$M$
3. Jika perhentian, berperilaku seperti G X . Jika kami harus menghentikan simulasi, maka gagal.$M$$G_X$

Perhatikan bahwa jika berhasil berjalan selamanya dalam batas maka tidak pernah dapat menghasilkan string parse dan karenanya akan gagal. Jika berhenti, maka ada sejumlah ruang yang cukup untuk memuat seluruh perhitungan , maka mem-parsing setiap kali dan , dan karenanya X adalah gabungan dari L ( G ) dan bahasa yang terbatas, di mana L ( G ) tidak teratur. Di sisi lain, jika M tidak pernah berhenti, maka L (G M n M G 1 m m ≥ n + 2 1 m ∈ $M$$G$$M$$n$$M$$G$$1^m$$m \ge n+2$$1^m \in X$$X$$L(G)$$L(G)$$M$ jelas teratur.$L(G) = \varnothing$

Algoritma untuk memutuskan apakah teratur atau tidak akan menentukan apakah M berhenti pada pita kosong, yang tidak dapat diputuskan. Oleh karena itu masalah si penanya tidak dapat ditentukan.$L(G)$$M$

Ini pada dasarnya adalah jawaban yang sama seperti di atas, tetapi karena jawaban "lebih bijaksana" dicari, saya menyebutkan ini: (Juga, ini adalah posting pertama saya di sini, jadi maafkan saya jika saya memposting hal-hal sepele!)

Amati bahwa kekosongan tidak dapat diputuskan untuk bahasa yang peka konteks unary. Perbaiki bahasa yang peka konteks, tetapi tidak teratur . Dengan diberi LBA untuk L ⊆ a ∗ , orang dapat dengan mudah membuat LBA untuk L ′ = { a n ∣ a n ∈ N  dan  ∃ m ≤ n : a m ∈ L } . Maka jelas L ′ adalah biasa jika dan hanya jika L kosong.$N\subseteq a^*$$L\subseteq a^*$$L'=\{ a^n \mid \text{$a^n\in N$ and $\exists m\le n\colon a^m \in L$}\}$$L'$$L$

Pembaruan: Tentu saja, argumen yang sama menunjukkan bahwa ketidakpastian sudah berlaku untuk ruang logaritmik deterministik.