Dalam kata pengantar untuk bukunya yang sangat berpengaruh Automata, Bahasa dan Mesin (Volume A, B), Samuel Eilenberg menggoda Volume C dan D yang berurusan dengan "suatu hierarki (disebut hirarki rasional) dari fenomena non-rasional ... menggunakan hubungan rasional sebagai alat untuk...
Dalam banyak makalah yang melibatkan tata bahasa bebas konteks (CFG), contoh-contoh tata bahasa yang disajikan di sana sering mengakui karakterisasi yang mudah dari bahasa yang mereka hasilkan. Sebagai contoh: S→aaSbS→aaSbS \to a a S b S→S→S \to menghasilkan {a2ibi|i≥0}{a2ibi|i≥0}\{ a^{2i}...
Secara praktis, untuk bahasa yang pada akhirnya dapat dikompilasi / diubah menjadi instruksi tingkat sistem, apakah perlu bahwa itu adalah tata bahasa bebas konteks? mis: Apakah semua bahasa pemrograman / scripting konteks tata bahasa gratis? Java didasarkan pada CFG, tetapi apakah sebenarnya...
Ketika bermain-main dengan parsing LR noncanonical, saya memikirkan metode parsing (dengan tabel berukuran tak terbatas, yang membuatnya agak tidak taktis ) yang mampu mengurai persis tata bahasa yang tidak ambigu dalam waktu , dan saya bertanya-tanya apakah mungkin untuk melakukan yang lebih baik...
Saya mencari bahasa yang "mungkin bukan Bebas Konteks" tetapi kami tidak dapat (buktikan) menggunakan teknik standar yang dikenal. Apakah ada survei terbaru pada subjek atau bagian masalah terbuka dari konferensi baru-baru ini? Mungkin tidak banyak bahasa yang tidak dikenal sebagai CF, jadi...
Dilambangkan dengan wnwnw_n jumlah kata-kata panjang nnn dalam (mungkin ambigu) bahasa bebas konteks. Apa yang diketahui tentang wnwnw_n ? Saya yakin ini sudah banyak dipelajari, tetapi saya tidak dapat menemukan apa pun di
Diberikan reguler , apakah ada batasan non-sepele pada ukuran tata bahasa bebas konteks terkecil untuk ?R 1 ∩ ⋯ ∩ R nR1,…,RnR1,…,RnR_1, \dots, R_nR1∩⋯∩RnR1∩⋯∩RnR_1 \cap \cdots \cap
Sudah diketahui bahwa masalah kesetaraan tidak dapat diputuskan untuk bahasa bebas konteks umum. Namun, semua bukti dari fakta ini yang saya sadari tampaknya melibatkan beberapa tata bahasa bebas konteks yang ambigu. Untuk alasan ini, saya ingin bertanya apakah diketahui apakah masalahnya tetap...
Saya pernah membaca di suatu tempat bahwa mesin Turing tidak dapat menghitung ini dan karena itu tidak dapat diputuskan tetapi mengapa? Mengapa secara komputasi mustahil bagi mesin untuk menghasilkan pohon parse dan membuat keputusan? Mungkin saya salah dan itu bisa
Ada banyak algoritma yang dapat menguraikan tata bahasa bebas konteks dalam waktu . Dengan menggunakan perkalian matriks, seseorang bahkan bisa berjalan lebih cepat tanpa gejala dari itu.O ( n3)O(n3)O(n^3) Namun, semua algoritma untuk parsing CFG sewenang-wenang yang saya tahu memiliki penggunaan...
Dalam buku Sakarovitch tentang teori automata, ada tertulis di bagian pengantar tentang rasionalitas dalam kelompok bebas bahwa materi yang disajikan di dalamnya meletakkan "landasan teori matematika yang benar-benar bahasa bebas konteks". Namun demikian, ini tidak dibuat eksplisit, karena bahasa...
Ungkapan permutasi adalah ekstensi ke definisi tata bahasa bebas konteks standar (E) BNF: frase permutasi berisi produksi (atau setara, nonterminals) hingga . Pada posisi kalimat permutasi, kami ingin melihat setiap produksi ini tepat satu kali, tetapi kami tidak tertarik dengan pemesanan...
Saya bertanya-tanya, apakah ada makalah atau penelitian yang berhubungan dengan automata yang terlihat jelas, tetapi membiarkan kata-kata, daripada huruf tunggal, untuk didorong ke tumpukan. Bergantian, konstruksi yang memungkinkan untuk simbol harus didorong pada -transitions bisa mencapai tujuan...
Dalam deskripsi formal Deterministic Pushdown Automata, mereka memungkinkan bergerak, di mana mesin dapat memunculkan atau mendorong simbol ke stack tanpa membaca simbol dari input. Jika ϵ gerakan ini tidak diizinkan, dan tumpukan hanya dapat dimodifikasi satu kali setelah setiap simbol dibaca,...
Ini adalah bukti standar dalam kursus automata bahwa untuk dan bahwa bukan bahasa bebas konteks.L=Σ⋆L=Σ⋆L = \Sigma^\star|Σ|≥2|Σ|≥2|\Sigma| \ge 2S(L)={ww:w∈L}S(L)={ww:w∈L}S(L) = \{ww : w \in L\} Juga benar bahwa untuk setiap terbatas , adalah terbatas (dan karena itu CFL). Saya menduga bahwa yang...
Akan menyenangkan untuk mengumpulkan daftar kondisi yang menyiratkan bahwa bahasa bebas konteks-L adalah reguler, yaitu syarat-syarat bentuk: "jika CFG / PDA yang diberikan memiliki properti P, maka bahasanya adalah reguler" Properti P tidak harus mengkarakterisasi CFG yang menghasilkan bahasa...
Pertimbangkan pertanyaan alami berikut: Dengan bahasa terbatas , apa yang menghasilkan tata bahasa L terkecil yang bebas konteks ?L.L.LL.L.L Kita bisa membuat pertanyaan yang lebih menarik dengan menentukan urutan bahasa , misalnya L n adalah himpunan semua permutasi dari { 1 , ... , n } :...
Setelah membaca pertanyaan terakhir "Apakah komplemen bebas konteks?" {www∣...}{www∣...}\{ www \mid ...\}; Saya ingat masalah yang sama yang tidak bisa saya tolak: Apakah konteks gratis?L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L = \{ ww' \mid...
Bahasa Dyck didefinisikan oleh tata bahasa S → S S berikutD y c k (k)Dyck(k)\mathsf{Dyck}(k) atas himpunan simbol { ( 1 , ... , ( k , ) 1 , ... , ) k } . Bahasa secara intuitif Dyck adalah bahasa kurung seimbang dari k yang berbeda. Sebagai contoh, (S→ SS|(1S)1|...|(kS)k|ϵS→SS|(1S)1|…|(kS)k|ϵ S...
Saya sedang mempertimbangkan bahasa dari semua formula logika proposisional yang memuaskan, SAT (untuk memastikan bahwa ini memiliki alfabet terbatas, kami akan menyandikan huruf proposisional dengan cara yang sesuai [edit: balasan menunjukkan bahwa jawaban untuk pertanyaan mungkin tidak kuat di...