Какой самый лучший или самый простой метод для определения эквивалентности между двумя автоматами?
То есть, если даны два конечных автомата A и B, как я могу определить, распознают ли они один и тот же язык?
Они оба детерминированы или оба недетерминированы.
Два недетерминированных конечных автомата (НКА) эквивалентны, если они принимают один и тот же язык.
Чтобы определить, принимают ли они один и тот же язык, мы смотрим на тот факт, что каждый НКА имеет минимальный ДКА, в котором нет двух идентичных состояний. Минимальный DFA также уникален. Таким образом, при наличии двух НКА, если вы обнаружите, что соответствующие им минимальные ДКА эквивалентны, то эти два НКА также должны быть эквивалентны.
Для более глубокого изучения этой темы я настоятельно рекомендую вам прочитать Введение в формальный язык и автоматы.
Другой, более простой подход заключается в дополнении и пересечении автоматов. Автомат A эквивалентен B тогда и только тогда, когда L(A) содержится в L(B) и наоборот, то есть тогда и только тогда, когда пересечение между дополнением L(B) и L(A) пусто, и наоборот.
Вот алгоритм проверки, содержится ли L(A) в L(B):
B, используя конструкцию подмножества. Затем сделайте каждое принимающее состояние отвергающим и каждое отвергающее состояние принимающим. Вы получаете автомат, который распознает дополнение L(B).L(B) и L(A). То есть построить автомат на пересечении автомата из шага 1 и A. Чтобы пересечь два автомата U и V, вы строите автомат с состояниями U x V. Автомат переходит из состояния (u,v) в (u',v') с буквой a тогда и только тогда, когда есть переходы u --a--> u' в U и v --a--> v' в V. Состояния принятия — это состояния (u,v), где u принимает в U, а v принимает в V.Если L(A) содержится в L(B), нам нужно запустить тот же алгоритм, чтобы проверить, содержится ли L(B) в L(A).
Я просто перефразирую ответ @Guy.
Чтобы сравнить языки, принятые обоими, мы должны выяснить, L(A) is equal to L(B) это или нет.
Таким образом, вам нужно выяснить, является ли L(A)-L(B) and L(B)-L(A) нулевым или нет. (Причина 1)
Часть 1:
Чтобы выяснить это, мы строим NFA X из NFA A и NFA B, .
Если X пустой набор, то L(A) = L(B) иначе L(A) != L(B). (Причина 2)
Часть 2:
Теперь нам нужно найти эффективный способ доказать или опровергнуть X is empty set. Когда X станет пустым как DFA или NFA? Ответ: X будет пустым, если нет пути, ведущего из начального состояния в любое из конечных состояний X. Для этого мы можем использовать BFS или DFS.
Reason1: Если оба значения равны нулю, то L(A) = L(B).
Reason2: Мы можем доказать, что множество регулярных языков замкнуто относительно пересечения и объединения. Таким образом, мы сможем эффективно создавать NFA X.
а для наборов:
