Pertanyaan tentang automata terbatas deterministik
Saya telah merevisi Teori Komputasi untuk bersenang-senang dan pertanyaan ini telah mengganggu saya untuk sementara waktu (lucu tidak pernah memikirkannya ketika saya belajar Teori Automata di sarjana saya). Jadi "mengapa" tepatnya kita mempelajari automata terbatas deterministik dan...
Setelah mempelajari deterministic finite state automata (DFA) di tingkat sarjana, saya merasa mereka sangat dipahami. Pertanyaan saya adalah apakah ada sesuatu yang masih belum kita mengerti tentang mereka. Maksud saya bukan generalisasi DFA tetapi DFA asli yang tidak dimodifikasi yang kami...
Perpotongan dua (minimal) DFA dengan n status dapat dihitung menggunakan O (n 2 ) waktu dan ruang. Ini optimal secara umum, karena DFA (minimal) yang dihasilkan mungkin memiliki n 2 status. Namun, jika DFA minimal yang dihasilkan memiliki status z, di mana z = O (n), dapatkah ia dihitung dalam...
Diberikan dua string x dan y, saya ingin membangun DFA ukuran minimum yang menerima x dan menolak y. Salah satu cara untuk melakukan ini adalah pencarian brute force. Anda menghitung mulai DFA dengan yang terkecil. Anda mencoba setiap DFA sampai Anda menemukan satu yang menerima x dan menolak...
Untuk alfabet yang terbatas tetap ΣΣ\Sigma , bahasa formal LLL lebih ΣΣ\Sigma adalah biasa jika ada sebuah robot yang terbatas deterministik (DFA) lebih ΣΣ\Sigma yang menerima persis LLL . Saya tertarik pada bahasa yang "hampir" teratur dalam arti bahwa mereka dapat dikenali oleh automata keluarga...
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...
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...
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...
Dua puluh tahun yang lalu, saya membangun paket ekspresi reguler yang mencakup konversi dari ekspresi reguler ke mesin keadaan terbatas (DFA) dan mendukung sejumlah operasi ekspresi reguler tertutup (bintang Kleene, penggabungan, pembalikan, set operasi, dll). Saya tidak yakin tentang kinerja...
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...
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...
Salah satu masalah terbuka yang menarik tentang DFA yang terdaftar di Apakah ada masalah terbuka yang tersisa tentang DFA? adalah ukuran DFA yang diperlukan untuk memisahkan dua string panjang nnn . Saya ingin tahu apakah ada hasil tentang kemampuan DFA acak untuk memisahkan dua string (nonrandom)...
Saya memiliki otomat terbatas non-deterministik yang sangat besar dan saya perlu mengubahnya ke DFA. Secara umum saya maksudkan 40 000+ negara bagian. Sejauh ini saya telah melakukan beberapa percobaan dan memprogram algoritma default yang mencari melalui tabel (seperti dijelaskan di sini ),...
Terinspirasi oleh pertanyaan ini , saya ingin tahu tentang yang berikut: Apa kompleksitas kasus terburuk dari memeriksa apakah DFA yang diberikan menerima bahasa yang sama dengan ekspresi reguler yang diberikan? Apakah ini diketahui? Harapannya adalah bahwa masalah ini ada di P - bahwa ada...
Semua buku teks saya menggunakan algoritma yang sama untuk menghasilkan DFA diberi regex: Pertama, buat NFA yang mengenali bahasa regex, kemudian, dengan menggunakan konstruksi subset (alias "powerset"), ubah NFA menjadi DFA yang setara ( opsional meminimalkan DFA). Saya juga pernah mendengar...
Saya tertarik dengan sedikit generalisasi DFA. Seperti biasa kita memiliki set-negara QQQ , alfabet terbatas ΣΣ\Sigma , sebuah aksi Σ∗Σ∗\Sigma^* didefinisikan pada QQQ oleh δ:Q×Σ→Qδ:Q×Σ→Q\delta : Q\times\Sigma\rightarrow Q , dan kondisi awal q0q0q_0 ; tapi bukannya biasa set terminal, kita...
Transduser yang dipertimbangkan di sini adalah Wikipedia yang disebut transduser keadaan terbatas . Perilaku transduser , yaitu, hubungan yang dihitungnya, ditulis : kata adalah output untuk iff .TTT[ T][T][T]yyyxxxx [ T] yx[T]yx[T]y Pertanyaan: Apakah masalah berikut dapat diputuskan:...
Pembaruan: Tampaknya masalah ini telah dipelajari dan diselesaikan baru-baru ini, lihat artikel wiki ini: http://en.wikipedia.org/wiki/Tree_walking_automaton Dan juga survei ini: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Misalkan alih-alih seperangkat kata yang biasa, {0,1} *,...
Saya tertarik pada algoritma yang efisien untuk persimpangan DFA untuk kasus khusus. Yaitu, ketika DFA untuk memotong mematuhi struktur tertentu dan / atau beroperasi pada alfabet terbatas. Apakah ada sumber di mana saya dapat menemukan algoritma kasus seperti itu? Agar tidak membuat pertanyaan...
Biarkan menjadi alfabet ukuran , dan pertimbangkan DFA minimal yang ukurannya dibatasi paling banyak . Misalkan menunjukkan jumlah DFA minimal yang berbeda.2 m f ( m )ΣΣ\Sigma222mmmf( m )f(m)f(m) Bisakah kita menemukan rumus bentuk tertutup untuk ?f( m )f(m)f(m) Menimbang bahwa untuk fungsi...