Алгоритм: пересечение двух регулярных выражений

Question

Я хотел бы выяснить (во время выполнения), пересекаются ли два регулярных выражения (т.е. если они существуют, существует ли одна или несколько строк, совпадающих с обоими регулярными выражениями).

Алгоритм должен быть довольно быстрым, так как мне нужно пройтись по базе данных и проверить существующие значения.

Нашли какую-то теорию по этому вопросу, но без реализаций?

Answer 1

Вот реализация в Haskell с использованием частных производных регулярных выражений. Комментарий к этому сообщению указывает на проблему с подходом в ответе Криса Додда.

Answer 2

Очевидным решением было бы преобразовать регулярные выражения в DFA, вычислить пересечение DFA (тривиально) и посмотреть, есть ли что-то, что может принять полученный DFA (также тривиально). Единственная сложная часть - преобразование регулярных выражений в DFA, что требует некоторой работы.

Answer 3

Как насчет проверки сначала одного, а затем другого с помощью ввода, который прошел первый?