Попытка найти алгоритм, который берет 2 регулярных выражения и говорит, эквивалентны ли они

Question

Я пытаюсь выяснить, каким был бы алгоритм, дав два языка L1 и L2, чтобы определить, эквивалентны ли они (L1 = L2).

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

Кроме того, я знаю, что если L1 - L2 и L2 - L1 пусты, то L1 = L2.

Кто-нибудь хорошо с теорией здесь?

Answer 1

Вот концептуально простой ответ (при условии, что L1 и L2 регулярны).

1) Найдите DFA D1 и D2 для L1 и L2 соответственно.

2) Постройте D'1 и D'2 из D1 и D2 путем замены принимающих / не принимающих состояний (обратите внимание, что D'1 принимает в точности ~ L1, а D'2 принимает ~ L2, где ~ означает «дополнение»)

3) Используйте стандартКонструкция продукта три раза для создания DFA, который принимает точно (L1 пересекаются ~ L2) объединение (L2 пересекаются ~ L1)

4) Проверьте, принимает ли DFA из части 3 какие-либо строки, проверяя каждое состояние принятия длядостижимость из начального состояния.

5) Если DFA из части 3 принимает какие-либо строки, то L1 <> L2.В противном случае, L1 = L2

Существует огромное количество эвристик, которые можно использовать для ускорения, но концептуально это, вероятно, самый простой алгоритм.Хорошей ссылкой на конструкцию продукта в части 3 является «Автоматизация и вычислимость» Декстера Козена.

Answer 2

Вы можете найти описание достаточно эффективного алгоритма для тестирования, т. Е. равенство здесь:

http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf

Просмотрите ссылки в статье, чтобы найти другие решения, которые могут быть менее эффективными, но более простыми в реализации.