Pertanyaan tentang bahasa formal yang dapat dijelaskan dengan ekspresi reguler (dalam arti Kleene), atau, yang setara, bahasa yang dapat diterima oleh automata terbatas.
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...
Mengapa bahasa reguler (dan dari ekspresi reguler itu) disebut "reguler"? Ada banyak keteraturan juga dalam bahasa bebas konteks dari jenis bahasa lainnya. Saya menduga bahwa, pada awalnya, kata sifat "biasa" telah digunakan untuk membedakan jenis bahasa itu dari bahasa "non-reguler" atau entah...
Kami mendefinisikan bahasa pohon biasa seperti dalam buku TATA : Ini adalah kumpulan pohon yang diterima oleh otomat pohon terbatas non-deterministik (Bab 1) atau, setara, serangkaian pohon yang dihasilkan oleh tata bahasa pohon biasa (Bab 2). Kedua formalisme memiliki kemiripan yang erat dengan...
Diberi bahasa reguler (NFA, DFA, grammar, atau regex), bagaimana cara menghitung jumlah kata yang menerima dalam bahasa tertentu? Keduanya "dengan tepat n huruf" dan "dengan paling banyak n huruf" menarik. Margareta Ackerman memiliki dua makalah tentang masalah terkait penghitungan kata-kata yang...
Aku memperbaiki bahasa reguler LLL pada alfabet ΣΣ\Sigma , dan saya menganggap masalah berikut yang saya sebut penjadwalan surat untuk LLL . Informal, input memberi saya nnn huruf dan interval untuk setiap huruf (yaitu, posisi minimal dan maksimal), dan tujuan saya adalah menempatkan setiap huruf...
Misalkan menjadi dua bahasa reguler yang diberikan oleh NFA sebagai input.M 1 , M 2L1,L2L1,L2L_1,L_2M1,M2M1,M2M_1,M_2 Asumsikan kami ingin memeriksa apakah . Ini jelas dapat dilakukan oleh algoritma kuadratik yang menghitung otomat produk , tetapi saya bertanya-tanya apakah ada yang lebih efisien...
Saya perhatikan bahwa bahasa reguler di atas alfabet secara alami dapat dianggap sebagai masalah, dan memang sebuah kisi. Selain itu, rangkaian bersama dengan bahasa kosong mendefinisikan struktur monoid yang ketat pada kategori ini yang bersifat distributif atas gabungan (saya tidak yakin tentang...
Tentukan kelas bahasa "sirkular" berikut di atas alfabet alfabet hingga. Sebenarnya, nama itu sudah ada untuk menunjukkan hal yang berbeda tampaknya, digunakan di bidang komputasi DNA. AFAICT, itu kelas bahasa yang berbeda. Bahasa L adalah bundaran iff untuk semua kata www di Σ∗Σ∗\Sigma^* , kami...
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
Biarkan menjadi kelas dari semua bahasa reguler.REGREG\mathsf{REG} Diketahui dan \ mathsf {REG} \ tidak \ subset \ mathsf {AC} ^ 0 . Tetapi apakah ada karakterisasi untuk bahasa di \ mathsf {AC} ^ 0 \ cap \ mathsf {REG} ?AC0⊄REGAC0⊄REG\mathsf{AC}^0 \not\subset
Pertanyaannya sederhana dan langsung: Untuk tetap , berapa banyak (berbeda) bahasa diterima oleh DFA ukuran n (yaitu n negara)? Saya akan secara resmi menyatakan ini:nnnnnnnnn Tentukan DFA sebagai , di mana semuanya seperti biasa dan δ : Q × Σ → Q adalah fungsi (mungkin sebagian). Kita perlu...
Saya bertanya-tanya apakah spesifikasi JSON mendefinisikan bahasa biasa. Tampaknya cukup sederhana, tetapi saya tidak yakin bagaimana membuktikannya sendiri. Alasan saya bertanya, adalah karena saya bertanya-tanya apakah seseorang dapat menggunakan ekspresi reguler untuk mengurai JSON secara...
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...
Pertimbangkan bahasa Lk−distinctLk−distinctL_{k-distinct} yang terdiri dari semua kkk -surat string lebih ΣΣ\Sigma sehingga tidak ada dua huruf yang sama: Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi}Lk−distinct:={w=σ1σ2...σk∣∀i∈[k]:σi∈Σ and ∀j≠i:σj≠σi} L_{k-distinct} :=\{w =...
Konteks: hubungan antara logika dan automata Teorema Büchi menyatakan bahwa logika Orde Kedua atas string (MSO) Monadic menangkap kelas bahasa biasa. Buktinya benar-benar menunjukkan bahwa MSO eksistensial ( exist atau EMSO ) lebih dari string sudah cukup untuk menangkap bahasa biasa. Ini mungkin...
Dalam teori automata (automata terbatas, automata pushdown, ...) dan dalam kompleksitas, ada gagasan "ambiguitas". Otomat bersifat ambigu jika ada kata www dengan setidaknya dua proses penerimaan yang berbeda. Sebuah mesin kkk ambigu jika untuk setiap kata www diterima oleh mesin paling tidak ada...
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...
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...
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...
Saya membaca " Rangkaian Bahasa Reguler dan Kompleksitas Deskripsional " oleh Galina Jiraskova, 2009 tentang kompleksitas negara yang dihasilkan dari penggabungan dua bahasa reguler (oleh Galina Jiraskova), tetapi saya tidak dapat memahami apa implikasi praktis kompleksitas negara nantinya ....