Biaya Kueri Kesetaraan untuk DFA

12

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 algoritma polinomial dalam ukuran keduanya.

automata-theory lg.learning regular-expressions dfa Lev Reyzin
sumber

Jawaban:

16

Menurut Garey dan Johnson (p. 174), EKSPRESI REGULER NON-UNIVERSALITY adalah PSPACE-complete. Ini adalah masalah memutuskan apakah ekspresi reguler lebih tidak tidak menghasilkan semua string. Jadi masalah Anda juga lengkap dengan PSPACE.{0,1}

Berikut adalah salah satu cara untuk melihat bahwa masalah OP ada di PSPACE. Diberi DFA dan ekspresi reguler , buat NFA untuk , dan gunakan konstruksi rangkaian daya untuk membuat konstruksi DFA setara dengan ; kami tidak akan menyimpan dalam memori, tetapi kami memiliki akses oracle ke hanya menggunakan ruang polinomial. Sekarang secara virtual membuat DFA untuk perbedaan simetris dan menggunakan konstruksi produk. DFA ini tidak menerima string (danArBrCBCCDACL(A)=L(r)) jika tidak ada jalur dari status awal ke status penerima. Karena reachability dalam NL dan memiliki ukuran , kita dapat memeriksa apakah di , persamaan terakhir karena teorema Savitch.D2poly(n)L(D)=∅NSPACE(poly(n))=NPSPACE=PSPACE

Yuval Filmus
sumber
Apakah Anda yakin itu ada di PSPACE (jika tidak hanya PSPACE-HARD)? Atau mungkin itu cukup untuk memeriksa semua string dengan panjang polinomial untuk melihat apakah regexp dan DFA setuju pada mereka semua? Apakah itu jelas? :-)
Neal Young
4
Ingat jangkauan berada di NL, jadi meskipun DFA yang sesuai dengan ekspresi reguler adalah eksponensial, karena akses oracle ke itu murah, kita dapat mengetahui apakah perbedaan simetris kosong atau tidak di NPSPACE = PSPACE.
Yuval Filmus
Saya tidak melihat hasil kekerasannya. Artinya, bagaimana Anda mengurangi masalah di atas menjadi universalitas ekspresi reguler?
Markus
2
Pilih DFA yang menerima segalanya. Untuk menunjukkan kekerasan, Anda mengurangi EKSPRESI REGULER NON-UNIVERSALITY ke masalah yang dimaksud.
Yuval Filmus
1
@YuvalFilmus Terima kasih untuk referensi! Anda mungkin harus menambahkan komentar pertama Anda ke jawaban Anda untuk kelengkapan, dalam kedua arti kata :)
Lev Reyzin