Apakah kesetaraan dua DFA merupakan masalah yang dapat diperhitungkan?

11

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 decidable juga?

computability automata finite-automata decision-problem Richard Jones
sumber
1
Ya, itu dapat ditentukan dalam waktu linier drona.csa.iisc.ernet.in/~deepakd/atc-common/…
abc
1
Selamat Datang di Ilmu Komputer! Apa yang sudah kamu coba? Di mana Anda terjebak? Kami tidak ingin hanya memberikan Anda solusinya; kami ingin Anda mendapatkan pemahaman. Namun, karena kami tidak tahu apa masalah mendasar Anda, jadi kami tidak dapat mulai membantu. Lihat di sini untuk kiat mengajukan pertanyaan tentang masalah olahraga. Jika Anda tidak yakin bagaimana meningkatkan pertanyaan Anda, mengapa tidak bertanya-tanya dalam Obrolan Ilmu Komputer ?
Raphael

Jawaban:

22

Untuk memutuskan apakah bahasa yang dihasilkan oleh dua DFA dengan yang sama, buat DFA untuk perbedaan simetris , dan periksa apakah .A1,A2AΔL(A1)ΔL(A2):=(L(A1)∖L(A2))∪(L(A2)∖L(A1))L(AΔ)=∅

Berikut ini beberapa detail lainnya. Anda dapat membuat menggunakan konstruksi produk : membuat automaton produk, dan menggunakan sebagai rangkaian negara penerima. ( F 1 × ¯ F 2 ) ∪ ( ¯ F 1 × F 2 )AΔ(F1×F2¯)∪(F1¯×F2)

Untuk memeriksa apakah kosong atau tidak, cukup untuk memeriksa apakah beberapa negara penerima dapat dijangkau dari keadaan awal, dan ini dapat dilakukan dengan menggunakan BFS / DFS.L(AΔ)

Yuval Filmus
sumber
3

D 2 D 1 D 2 D 1D1D2D1D2D1D2

D1D2

fade2black
sumber
1
Saya yakin Anda menyamakan "kesetaraan" DFA dan persamaannya.
einpoklum
@einpoklum ya, saya menggunakan istilah "kesetaraan" sebagai sinonim dari "kesetaraan" karena OP menggunakan istilah "Kesetaraan".
fade2black
2
Keduanya tidak sama. Bahkan setelah minimalisasi, automata tidak sama . Kita tahu mereka adalah isomorfik, yang tentu saja dapat diperhitungkan (jika berpotensi lebih sulit daripada kesetaraan).
Raphael