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

Имеется ли два произвольных регулярных выражения, существует ли «эффективный» алгоритм для определения того, соответствуют ли они одному и тому же набору строк?

В более общем смысле, можем ли мы вычислить размер пересечения двух наборов совпадений?

Какие алгоритмы существуют для этого и в каком классе сложности они живут?

Если мы запретим звезду Клини, это вообще изменит картину?

algorithms regular-expressions MathematicalOrchid
источник

Что вы подразумеваете под «размером пересечения»? В большинстве интересных случаев оно будет бесконечно большим; Вы заинтересованы в размерах WRT ?

Σ^{n}

$\Sigma^n$

Рафаэль

@ Рафаэль Насколько я понимаю, устранение звезды Клини заставляет размер множества быть конечным.

Математическая

Зависит. Какие другие операторы разрешены? Если вы допускаете дополнения, то, что вы говорите, не соответствует действительности. Кроме того, вы спрашиваете о ситуации со звездой Клини, поэтому вам все равно нужно прояснить ситуацию.

Рафаэль

См. Также cs.stackexchange.com/q/12624/755

Ответы:

Хендрик Ян дает хороший ответ для класса сложности, но не сам алгоритм.

Самый простой алгоритм, который мне известен, это преобразовать регулярное выражение в DFA. Существуют известные методы преобразования регулярного выражения в NFA и NFA в DFA.

Если у вас есть два DFA, тестирование на эквивалентность является эффективным и решаемым, поскольку минимальная форма DFA уникальна с точностью до изоморфизма.

Однако построение этих DFA из NFA может занять много времени и привести к созданию очень большого DFAS, экспоненциально большого в худшем случае.

jmite
источник

Известно, что эквивалентность регулярных выражений полна PSPACE, что довольно плохо. В статье «Сложность решения задач для простых регулярных выражений» перечислены несколько подклассов регулярных выражений с соответствующими им сложностями. ( ссылка )

Хендрик Ян
источник

это даже EXPSPACE-завершено, если вы разрешаете квадратный оператор (т.е. пишете вместо ). Это становится СЛЕДУЮЩИМ-полным без звезды Клини.

e^{2}

$e^2$

e e

$ee$

Денис

@dkuper Спасибо за дополнительное объяснение. Не стесняйтесь редактировать ответ, чтобы добавить эту или подходящие ссылки. (Или даже начните свой собственный ответ.)

Хендрик Ян

Есть ли ссылка на общие регулярные выражения, чтобы они были полными в PSPACE?

Райан

Ваша ссылка мертва. Можете ли вы предоставить свежую или хотя бы некоторую соответствующую информацию из газеты?

Д. Бен Кнобл

@ D.BenKnoble Ссылка отлично работает для меня.

Хендрик Ян