Pertanyaan yang diberi tag fl.formal-languages

Apakah mungkin untuk menguji secara algoritmik apakah bilangan yang dihitung rasional atau bilangan bulat? Dengan kata lain, apakah mungkin bagi perpustakaan yang mengimplementasikan angka yang dapat dihitung untuk menyediakan fungsi isIntegeratau isRational? Saya menduga itu tidak mungkin, dan...

Saya mencoba untuk memecahkan masalah tertentu, dan saya pikir saya mungkin bisa menyelesaikannya dengan menggunakan teori automata. Saya bertanya-tanya, model automata apa yang memiliki penahanan yang dapat ditentukan dalam waktu polinomial? yaitu jika Anda memiliki mesin Anda dapat menguji apakah...

Bertahun-tahun yang lalu saya mendengar bahwa menghitung NFA minimal (otomat hingga nondeterministik) dari DFA (deterministik) adalah pertanyaan terbuka, berlawanan dengan arah sebaliknya yang telah dikenal selama beberapa dekade dan diteliti dengan baik dengan efisien algoritma. Adakah yang datang...

Kata disebut primitif , jika tidak ada kata dan sehingga . Himpunan Q dari semua kata primitif di atas alfabet \ Sigma adalah bahasa yang terkenal. WLOG kita dapat memilih \ Sigma = \ {a, b \} .wwwv vvk > 1 k>1k > 1w = v kw=vkw = v^k Q QQΣ Σ\SigmaΣ = { a , b }Σ={a,b}\Sigma = \{ a,b \} Bahasa...

2dca (dua arah deterministik one-counter automata) (Petersen, 1994) dapat mengenali bahasa unary berikut: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} Apakah ada bahasa unary nontrivial lain yang dikenali oleh...

Untuk bahasa L ⊆ Σ ^ * , tentukan kongruensi sintaksis ≡ dari L sebagai kongruensi terkecil pada on ^ * yang menjenuhkan L , yaitu: u ≡ v ⇔ (∀ x, y) [xuy ∈ L ↔ xvy ∈ L]. Sekarang tentukan kesetaraan Nerode sebagai kongruensi kanan berikut: u ∼ v ⇔ (∀ x) [ux ∈ L ↔ vx ∈ L]. Biarkan [u] menjadi...

Finite Automatons (UFA) yang tidak ambigu adalah tipe khusus dari finite automatons (NFA) non-deterministik. NFA disebut tidak ambigu jika setiap kata memiliki paling banyak satu jalur penerimaan.w ∈ Σ∗w∈Σ∗w\in \Sigma^* Ini berarti .D FA ⊂ UFA ⊂ NFSEBUAHDFSEBUAH⊂UFSEBUAH⊂NFSEBUAHDFA\subset...

Saya tertarik pada dua pertanyaan tentang bahasa konteks-sensitif (CSL) dan kelengkapan: Apakah ada gagasan tentang kelengkapan untuk CSL, dan bahasa apa yang lengkap? Apakah ada CSL alami yang lengkap dengan NP? Untuk 2., saya pasti bisa memikirkan bahasa NP-lengkap alami yang CSL (karena...

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...

Dengan hasil klasik Kuroda, kelas kompleksitas NSPACE [ ]nnn (juga dikenal sebagai NLIN-SPACE) adalah kelas CSL dari bahasa yang peka konteks . Masalah kepuasan SAT ada di NSPACE [ ], karena perkiraan ukuran linier untuk solusi dapat diperiksa dengan paling banyak jumlah linier overhead untuk...

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 bibliografi yang baik tentang upaya untuk menyelidiki dugaan Collatz sebagai tata bahasa formal? (atau upaya lain apa pun dalam komunitas CS untuk menangani kelas fenomena generatif ini & sifat "tersendat"

Kami mengatakan bahwa NFA adalah Konstanta Ambigu jika ada sehingga setiap kata diterima oleh atau (persis) jalur .MMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Jika automaton secara konstan ambigu untuk , maka disebut Unambiguous FA (UFA).MMMk=1k=1k=1MMM Biarkan menjadi bahasa...

Ada bukti teoretis bahwa konstruksi produk-kartesian naif untuk persimpangan DFA adalah "yang terbaik yang bisa kita lakukan". Bagaimana dengan gabungan dua DFA? Konstruksi sepele melibatkan konversi setiap DFA menjadi NFA, menambahkan transisi epsilon dan menentukan NFA yang dihasilkan. Bisakah...

Latar Belakang: Diberi dua automata terbatas deterministik A dan B, kami membentuk produk C dengan membiarkan negara bagian dalam C menjadi produk kartesian negara bagian di negara A dan negara bagian B. Kemudian, kami memilih transisi, keadaan awal, dan keadaan akhir sehingga bahasa diterima oleh...

Diketahui bahwa meminimalkan ukuran ekspresi reguler adalah PSPACE-complete bahkan jika kita memiliki DFA sebagai spesifikasi bahasa . Apa hasil jika bahasanya terbatas? Satu dapat mempertimbangkan masalah ini dalam dua model: Input adalah semua string dalam bahasa, dan kami mengukur ukuran...

Ini belum tentu merupakan pertanyaan penelitian. Hanya sebuah pertanyaan karena penasaran: Saya mencoba memahami jika seseorang dapat mendefinisikan bahasa yang "tidak dapat direduksi". Sebagai tebakan pertama saya menyebut bahasa L "dapat direduksi" jika dapat ditulis sebagai dengan dan | A |, |...

Ketinggian bintang (yang digeneralisasikan) dari suatu bahasa adalah bersarang minimum dari bintang-bintang Kleene yang diperlukan untuk mewakili bahasa dengan suatu ekspresi reguler yang diperluas. Ingatlah bahwa ekspresi reguler yang diperluas menggunakan alfabet terbatas memenuhi yang...

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 } :...

Menurut Kompleksitas Kebun Binatang , Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1} dan kita tahu bahwa RegReg\mathsf{Reg} tidak dapat dihitung sehingga TC0⊈RegTC0⊈Reg\mathsf{TC^0} \not\subseteq \mathsf{Reg} . Namun tidak disebutkan apakah Reg⊆TC0Reg⊆TC0\mathsf{Reg} \subseteq \mathsf{TC^0}...