Проверьте, соответствует ли 2 минимальных DFA

Question

У меня есть 2 минимизированных DFA, и мне нужно проверить, эквивалентны ли они.

Если они эквивалентны, проблема заключается в том, чтобы найти эффективное сравнение состояния независимо от разных меток. В моем случае DFA - это таблица, тогда мне нужно найти перестановку, которая соответствует строкам первого DFA с строками второго DFA.

Я думал, что у меня есть поиск в Dread вначале Breadth и создание минимальной строки доступа к состоянию, а затем сравнение первого списка со вторым списком (это должно быть независимо от конкретного ввода, например: 001 и 110 могут быть взаимозаменяемыми).

Мне интересен прямой и неэффективный алгоритм и более сложный алгоритм.

Answer 1

Я нашел эти алгоритмы:

- Symmetric difference 
- Table-filling algorithm 
- Faster Table-Filling algorithm O(n^2) 
- Hopcroft algorithm 
- Nearly Linear algorithm by Hopcroft and Karp 

Полный справочник является:

• Algorithms for testing equivalence of finite automata, with a grading tool for Jflap - Нортон, 2009

Я принял это мое сообщение, потому что один из @abbaasi слишком неполный. Я приму любой другой ответ со значительным вкладом.

Answer 2

Правильный подход заключается в создании другого DFA с: L3 = (L1-L2) U (L2-L1) И проверить, является ли L3 пустым или нет. Если L3 пусто, то L1 = L2, в противном случае L1 <> L2