Apakah ada cara untuk menguji apakah dua NFA menerima bahasa yang sama?

10

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 lama.

algorithms regular-languages finite-automata Duncan
sumber
Tidak (setidaknya setahu kami). Kesetaraan NFA adalah PSPACE-complete. Lihat diskusi ini .
Shaull
@ Samull: OP tidak melakukan cara yang efisien .
frafl
@frafl: Anda benar. Saya berasumsi oleh "akan memakan waktu lama" bahwa OP menginginkan solusi yang efisien. Tetap saja, komentar saya menyebutkan bahwa itu ada di PSPACE, jadi itu bisa ditentukan.
Shaull

Jawaban:

10

Masalah keputusannya adalah PSPACE-complete seperti yang dicatat oleh Shaull.

Namun, ternyata dalam praktiknya sering dimungkinkan untuk memutuskan kesetaraan NFA dengan cukup cepat. Mayr dan Clemente (berdasarkan bukti eksperimental) mengklaim bahwa kompleksitas kasus rata-rata berskala kuadratik . Teknik mereka mengandalkan pemangkasan sistem transisi berlabel yang mendasari melalui perkiraan lokal inklusi jejak.

Sama seperti SAT yang NP-lengkap dalam analisis kasus terburuk, namun sering kali ternyata dapat ditelusuri secara mengejutkan untuk contoh-contoh dunia nyata, karena itu nampaknya kesetaraan NFA dapat diputuskan secara efisien untuk banyak contoh di dunia nyata.

András Salamon
sumber