Algoritma untuk menentukan apakah dua regex setara

11

Diberikan dua ekspresi reguler yang berubah-ubah, apakah ada algoritma "efisien" untuk menentukan apakah mereka cocok dengan rangkaian string yang sama?

Secara lebih umum, dapatkah kita menghitung ukuran persimpangan dari dua set pertandingan?

Algoritma apa yang ada untuk melakukan ini, dan kelas kompleksitas apa yang mereka tinggali?

Jika kita melarang bintang Kleene, apakah itu mengubah gambar sama sekali?

algorithms regular-expressions Matematika Matematika
sumber
Apa yang Anda maksud dengan "ukuran persimpangan"? Dalam kebanyakan kasus yang menarik, ukurannya akan sangat besar; apakah Anda tertarik dengan ukuran wrt ? Σn
Raphael
@ Raphael Pemahaman saya adalah bahwa menghilangkan bintang Kleene memaksa ukuran set menjadi terbatas.
MathematicalOrchid
Tergantung. Operator apa yang diizinkan? Jika Anda mengizinkan pelengkap, apa yang Anda katakan tidak benar. Juga, Anda meminta situasi dengan bintang Kleene juga, jadi Anda perlu mengklarifikasi pula.
Raphael
Lihat juga cs.stackexchange.com/q/12624/755
DW

Jawaban:

12

Hendrik Jan memberikan jawaban yang bagus untuk kelas kompleksitas, tetapi bukan algoritma itu sendiri.

Algoritma paling sederhana untuk melakukan ini yang saya tahu adalah untuk mengubah ekspresi reguler menjadi DFA. Ada teknik yang dikenal untuk mengubah ekspresi reguler menjadi NFA, dan NFA menjadi DFA.

Setelah Anda memiliki dua DFA, pengujian untuk kesetaraan adalah efisien dan dapat ditentukan, karena bentuk minimal DFA unik hingga isomorfisma.

Namun, membangun DFA ini dari NFA bisa memakan banyak waktu, dan menghasilkan DFAS yang sangat besar, secara eksponensial besar dalam kasus terburuk.

Ya ampun
sumber
10

Kesetaraan ekspresi reguler dikenal sebagai PSPACE-complete, yang agak buruk. Makalah "Kompleksitas Masalah Keputusan untuk Ekspresi Reguler Sederhana" daftar beberapa subclass dari ekspresi reguler dengan kompleksitas masing-masing. ( tautan )

Hendrik Jan
sumber
1
bahkan EXPSPACE-complete jika Anda mengizinkan operator kuadrat (yaitu menulis bukannya e e ). Ini menjadi NEXPTIME-lengkap tanpa bintang Kleene. e2ee
Denis
@dkuper Terima kasih atas penjelasan tambahannya. Jangan ragu untuk mengedit jawaban untuk menambahkan ini atau referensi yang sesuai. (Atau bahkan mulai jawaban Anda sendiri.)
Hendrik
Apakah ada referensi untuk ekspresi reguler umum agar PSPACE-complete?
Ryan
Tautan Anda mati. Bisakah Anda memberikan yang baru atau setidaknya beberapa info yang relevan dari koran?
D. Ben Knoble
@ D.BenKnoble Link berfungsi dengan baik untuk saya.
Hendrik Jan