Pertanyaan Menentukan apakah suatu regex adalah bagian dari yang lain


Saya memiliki banyak koleksi ekspresi reguler yang ketika dicocokkan panggilan handler http tertentu. Beberapa dari regex lama tidak dapat dijangkau (mis. a.c* ⊃ abc*) dan saya ingin memangkasnya.

Apakah ada perpustakaan yang diberikan dua regex akan memberi tahu saya jika yang kedua adalah subkumpulan pertama?

Saya tidak yakin ini dapat diatasi pada awalnya (baunya seperti masalah terputus-putus dengan nama yang berbeda). Tapi ternyata itu bisa diputuskan.


32
2017-09-10 21:27


asal


Jawaban:


Mencoba untuk menemukan kompleksitas masalah ini menuntun saya ke makalah ini.

Definisi formal masalah dapat ditemukan dalam: ini umumnya disebut masalah inklusi

Masalah inklusi untuk R, adalah untuk menguji dua ekspresi yang diberikan r, r ′ ∈ R,   apakah r ⊆ r ′.

Makalah itu memiliki beberapa informasi hebat (ringkasan: semua kecuali ekspresi yang paling sederhana cukup rumit), namun mencari informasi tentang masalah inklusi mengarahkan seseorang langsung kembali ke StackOverflow. Jawaban itu sudah memiliki tautan ke makalah yang menjelaskan algoritma waktu polinomial yang dapat dilewati yang harus mencakup banyak kasus umum.


12
2017-09-18 05:31



Jika ekspresi reguler menggunakan "fitur lanjutan" dari penjudi prosedural khusus (seperti yang ada di Perl, Java, Python, Ruby, dll.) Yang memungkinkan menerima bahasa yang tidak biasa, maka Anda kurang beruntung. Masalahnya secara umum tidak dapat diputuskan. Misalnya. masalah apakah satu otomat pushdown mengenali bahasa konteks bebas (CF) yang sama dengan yang lain tidak dapat diputuskan. Ekspresi reguler yang diperluas dapat menggambarkan bahasa CF.

Di sisi lain, jika ekspresi reguler adalah "benar" dalam arti teoritis, hanya terdiri dari gabungan, alternasi, dan Kleene membintangi string dengan alfabet berhingga, ditambah gula sintaksis biasa pada ini (kelas karakter, +,?, dll), maka ada algoritma waktu polinomial sederhana.

Saya tidak bisa memberi Anda pustaka, tetapi ini:

For each pair of regexes r and s for languages L(r) and L(s)
  Find the corresponding Deterministic Finite Automata M(r) and M(s)
    Compute the cross-product machine M(r x s) and assign accepting states
       so that it computes L(r) - L(s)
    Use a DFS or BFS of the the M(r x s) transition table to see if any
       accepting state can be reached from the start state
    If no, you can eliminate s because L(s) is a subset of L(r).
    Reassign accepting states so that M(r x s) computes L(s) - L(r)
    Repeat the steps above to see if it's possible to eliminate r

Mengonversi regex menjadi DFA umumnya menggunakan konstruksi Thompson untuk mendapatkan robot yang tidak deterministik. Ini diubah menjadi DFA menggunakan Konstruksi Subset. Mesin cross-product adalah algoritma standar lainnya.

Ini semua berhasil pada tahun 1960-an dan sekarang menjadi bagian dari kursus teori ilmu komputer yang terbaik. Standar emas untuk topik ini Hopcroft dan Ullman, Teori Automata.


5
2017-09-22 01:51



Ada jawaban di bagian matematika: https://math.stackexchange.com/questions/283838/is-one-regular-language-subset-of-another.

Ide dasar:

  • Hitung minimal DFA untuk kedua bahasa.
  • Hitung produk silang dari mengotomatiskan M1 dan M2, yang berarti bahwa setiap negara terdiri dari sepasang [m1, m2] di mana m1 adalah dari M1 dan m2 dari M2 untuk semua kombinasi yang mungkin.
  • Transisi baru F12 adalah: F12 ([m1, m2], x) => [F1 (m1, x), F2 (m2, x)]. Ini berarti jika ada transisi di M1 dari negara m1 ke m1 'saat membaca x dan M2 dari keadaan m2 ke m2' sambil membaca x maka ada satu transisi di M12 dari [m1, m2] ke [m1 ', m2' ] saat membaca x.
  • Pada akhirnya Anda melihat ke negara-negara yang terjangkau:
    • Jika ada pasangan [menerima, menolak] maka M2 bukan bagian dari M1
    • Jika ada pasangan [menolak, accapting] maka M1 bukan bagian dari M2

Akan bermanfaat jika Anda hanya menghitung transisi baru dan status yang dihasilkan, mengabaikan semua negara yang tidak terjangkau dari awal.


4
2017-09-17 21:41



Saya menemukan pustaka regex python yang menyediakan operasi set.

http://github.com/ferno/greenery

Buktinya mengatakan Sub ⊆ Sup ⇔ Sub ∩ ¬Sup is {}. Saya dapat menerapkan ini dengan pustaka python:

import sys
from greenery.lego import parse

subregex = parse(sys.argv[1])
supregex = parse(sys.argv[2])

s = subregex&(supregex.everythingbut())
if s.empty():
  print("%s is a subset of %s"%(subregex,supregex))
else:
  print("%s is not a subset of %s, it also matches %s"%(subregex,supregex,s)

contoh:

subset.py abcd.* ab.*
abcd.* is a subset of ab.*

subset.py a[bcd]f* a[cde]f*
a[bcd]f* is not a subset of a[cde]f*, it also matches abf*

Perpustakaan mungkin tidak kuat karena seperti yang disebutkan dalam jawaban lainnya, Anda perlu menggunakan DFA minimal agar ini berfungsi. Aku tidak yakin ferno's perpustakaan membuat (atau dapat membuat) jaminan itu.

Sebagai samping: bermain dengan perpustakaan untuk menghitung inverse atau menyederhanakan regex adalah sangat menyenangkan.
a(b|.).* menyederhanakan ke a.+. Yang sangat minim.
Kebalikan dari abf* aku s ([^a]|a([^b]|bf*[^f])).*|a?. Cobalah untuk memikirkannya sendiri!


3
2017-09-25 19:12