Легкого пути нет.
Пока ваши регулярные выражения используют только стандартные функции (я думаю, что Perl позволяет вам встраивать произвольный код в соответствие), вы можете производить из каждого недетерминированный конечный автомат (NFA) , который компактно кодирует все строки, которые соответствуют RE.
Учитывая любую пару NFA, можно решить, является ли их пересечение пустым. Если пересечение не пустое, то некоторая строка соответствует обоим RE в паре (и наоборот).
Стандартное доказательство разрешимости состоит в том, чтобы сначала определить их в DFA с, а затем построить новый DFA, состояния которого являются парами двух состояний DFA, а конечные состояния - это именно те, в которых оба состояния в паре являются окончательными в их оригинальном DFA. В качестве альтернативы, если вы уже показали, как вычислить дополнение NFA, то вы можете (стиль закона Деморгана) получить пересечение по complement(union(complement(A),complement(B))).
К сожалению, NFA-> DFA включает в себя взрыв экспоненциального размера (потому что состояния в DFA являются подмножествами состояний в NFA). От Википедия :
Некоторые классы обычных языков могут
быть описанным только детерминированным
конечные автоматы, размер которых растет
экспоненциально в размере
кратчайший эквивалентный регулярный
выражения. Стандартный пример
здесь языки L_k, состоящие из
все строки в алфавите {a, b}
чья k-я последняя буква равна a.
Кстати, вы обязательно должны использовать OpenFST . Вы можете создавать автоматы в виде текстовых файлов и играть с такими операциями, как минимизация, пересечение и т. Д., Чтобы увидеть, насколько они эффективны для вашей задачи. Уже существуют открытые компиляторы regexp-> nfa-> dfa (я помню модуль Perl); измените один для вывода файлов автоматов OpenFST и поиграйтесь.
К счастью, можно избежать взрыва подмножества состояний и напрямую пересечь два NFA, используя ту же конструкцию, что и для DFA:
, если A ->a B (в одном NFA вы можете перейти из состояния A в B с выводом буквы 'a')
и X ->a Y (в других NFA)
затем (A,X) ->a (B,Y) на перекрестке
(C,Z) является окончательным, если C является окончательным в одном NFA и Z является окончательным в другом.
Чтобы начать процесс, вы начинаете в паре начальных состояний для двух NFA, например, (A,X) - это начальное состояние перекрестка-NFA. Каждый раз, когда вы впервые посещаете состояние, генерируйте дугу по указанному выше правилу для каждой пары дуг, выходящих из двух состояний, а затем посещайте все (новые) состояния, которых достигают эти дуги. Вы бы сохранили тот факт, что вы расширили дуги состояния (например, в хеш-таблице) и в конечном итоге изучили все состояния, доступные с самого начала.
Если вы разрешаете эпсилон-переходы (которые не выводят буквы), это нормально:
если A ->epsilon B в первом NFA, то для каждого достигнутого вами состояния (A,Y) добавьте дугу (A,Y) ->epsilon (B,Y) и аналогично для эпсилонов в NFA второго положения.
Эпсилон-переходы полезны (но не обязательны) для объединения двух NFA при преобразовании регулярного выражения в NFA; всякий раз, когда у вас есть чередование regexp1|regexp2|regexp3, вы берете объединение: NFA, начальное состояние которого имеет эпсилон-переход к каждому из NFA, представляющих регулярные выражения в чередовании.
Решить пустоту для NFA легко: если вы когда-либо достигаете конечного состояния при выполнении поиска в глубину из начального состояния, оно не пустое.
Это пересечение NFA аналогично конечному составу преобразователя состояния (преобразователь - это NFA, который выводит пары символов, которые попарно объединяются для согласования входной и выходной строк или для преобразования заданного ввода в выход).