Saya ingin tahu apakah masalah berikut ini dapat ditentukan: Instance: NFA A dengan n state Pertanyaan: Apakah ada beberapa bilangan prima p sehingga A menerima beberapa untaian panjang p. Keyakinan saya adalah bahwa masalah ini tidak dapat diputuskan, tetapi saya tidak dapat membuktikannya....
Diberi alfabet Σ={a,b}Σ={a,b}\Sigma = \{ a,b \} , berapa banyak bahasa reguler yang berbeda yang dapat diterima oleh otomat terbatas non-deterministik nnn -negara? Sebagai contoh, mari kita pertimbangkan n=3n=3n=3 . Kami kemudian memiliki 2182182^{18} konfigurasi transisi yang berbeda dan 23232^3...
Saya tahu bahwa kami dapat meminimalkan DFA dengan menemukan dan menggabungkan status yang setara, tetapi mengapa kami tidak dapat melakukan hal yang sama dengan NFA? Saya tidak mencari bukti atau semacamnya - kecuali bukti lebih mudah dimengerti. Saya hanya ingin memahami secara intuitif mengapa...
Saya baru saja mulai membaca tentang teori perhitungan. Jika kita membandingkan mana yang lebih kuat (dalam menerima string), keduanya sama. Tetapi bagaimana dengan efisiensi? DFA akan lebih cepat dibandingkan dengan NFA, karena hanya memiliki satu tepi keluar & tidak akan ada ambiguitas....
Saya mempelajari bahasa formal dan sistem basis produksi (sistem basis aturan) dan saya sedikit bingung mengapa dua kata "produksi" dan "aturan" ini memiliki arti yang sama dalam banyak konteks dalam Ilmu Komputer. Dalam Bahasa Inggris mereka tampaknya tidak berarti hal yang sama. Saya bukan...
Saya seorang programmer dengan pegangan pada automata, tetapi tidak pada logika. Saya membaca di surat kabar bahwa keduanya berhubungan sangat erat. Deterministic Finite Automata (DFA), Tree Automata dan Visible Pushdown Automata semuanya terkait dengan Monadic Second Order Logic (MSO). Meskipun,...
Besok adalah presentasi saya dan saya ingin menghapus konsep saya ... Saya pernah membaca bahwa di DFA, "Untuk setiap negara, transisi pada semua simbol yang mungkin (alfabet) harus ditentukan." Apakah untuk setiap negara bagian, mendefinisikan transisi pada semua simbol yang mungkin wajib di...
Pada gambar di bawah, saya mencoba mencari tahu apa sebenarnya yang diterima NFA ini. Yang membingungkan saya adalah jump at .q 0ϵϵ\epsilonq0q0q_0 Jika dimasukkan, apakah sistem pindah ke dan (status terima)?q 0 q 1000q0q0q_0 q1q1q_1 Jika dimasukkan, apakah sistem pindah ke dan ?q 1 q...
Saya bertanya-tanya, apa kerumitan waktu menentukan kekosongan untuk DFA 2 arah? Yaitu, automata terbatas yang dapat bergerak mundur pada tape input read-only. Menurut Wikipedia, mereka setara dengan DFA, meskipun DFA yang setara mungkin secara eksponensial lebih besar. Saya telah menemukan...
Jika tidak, lalu apa artinya bila untuk beberapa negara dan beberapa simbol a , δ ( q , a ) tidak ada?qqqaaaδ(q,a)δ(q,a)\delta(q,
Tujuannya adalah membuat DFA dari ekspresi reguler dan menggunakan "Exp reguler> NFA> Konversi DFA" bukan opsi. Bagaimana seharusnya orang melakukan itu? Saya mengajukan pertanyaan ini kepada profesor kami tetapi dia mengatakan kepada kami bahwa kami dapat menggunakan intuisi dan dengan baik...
Ini mungkin pertanyaan konyol. Tampak jelas bahwa FSA, karena terbatas, hanya dapat menghitung jumlah simbol dalam string inputnya hingga sejumlah yang dibatasi oleh jumlah negara bagian. Tapi sekarang anggaplah kita melengkapi FSA dengan kemampuan output (misalnya pencetakan). Maka akan sangat...
Saya mendapat kesan bahwa komputer kita, yang terbatas, pada akhirnya tidak lebih kuat daripada (hingga luar biasa besar) Mesin Negara Hingga. Namun, Mesin Turing Linearly Bounded juga terbatas, tetapi tampaknya Bahasa Reguler benar-benar merupakan bagian yang tidak tepat dari Bahasa...
Di tempat kerja saya ditugaskan untuk menyimpulkan beberapa jenis informasi tentang bahasa yang dinamis. Saya menulis ulang urutan pernyataan menjadi letekspresi bersarang , seperti: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z =>...
Saya memiliki masalah sederhana dalam membuat DFA yang menerima semua input yang dimulai dengan huruf ganda (aa, bb) atau diakhiri dengan huruf ganda (aa, bb), mengingat Σ = { a , b }Σ={Sebuah,b}\Sigma =\{a, b\} adalah set alfabet dari bahasa yang diberikan. Saya mencoba menyelesaikannya secara...
Diberikan dua set A , BSEBUAH,BA,B string lebih dari alfabet ΣΣ\Sigma , dapatkah kita menghitung otomat kondisi-terbatas deterministik terkecil (DFA) M.M.M sehingga A ⊆ L ( M)SEBUAH⊆L.(M.)A \subseteq L(M) dan L ( M) ⊆ Σ∗∖ BL.(M.)⊆Σ∗∖BL(M) \subseteq \Sigma^*\setminus B ? Dengan kata lain, mewakili...
Jadi mengingat dua DFA, apakah masalah menemukan jika mereka menghasilkan bahasa yang sama merupakan masalah yang Layak? Saya sudah tahu bahwa Kesetaraan dua CFL tidak Dapat Dipilih tapi bagaimana dengan Kesetaraan dua DFA? mengingat sebagian besar masalah dengan DFA adalah decidable, apakah ini...
Meminimalkan deterministic finite automata (DFAs) adalah masalah yang telah dipelajari secara menyeluruh dalam literatur, dan beberapa algoritma telah diusulkan untuk menyelesaikan masalah berikut: Dengan DFA , hitung DFA minimal yang sesuai yang menerima bahasa yang sama dengan . Sebagian besar...
Jika saya mengerti dengan benar, NFA memiliki kekuatan ekspresif yang sama dengan ekspresi reguler. Seringkali, membacakan persamaan reguler yang setara dari NFA mudah: Anda menerjemahkan siklus ke bintang, persimpangan sebagai alternatif, dan sebagainya. Tetapi apa yang harus dilakukan dalam kasus...
Atau setidaknya menghasilkan serangkaian string yang diterima oleh satu NFA, jadi saya bisa memasukkannya ke NFA lainnya. Jika saya melakukan pencarian melalui setiap jalur NFA, apakah itu akan berhasil? Meskipun itu akan memakan waktu