Общее доказательство эквивалентности двух автоматов за конечное время?

Question

Существует ли общее доказательство эквивалентности двух (детерминированных) конечных автоматов, которое всегда занимает конечное время?То есть, имея два автомата, можете ли вы доказать, что при одних и тех же входных данных они всегда будут выдавать одни и те же выходные данные без фактической необходимости выполнять автоматы (что может быть незавершающим?)Если такое доказательство существует, какова временная сложность?

Answer 1

Доказательство есть, хотя я его не знаю.Поищите учебник Сипсера по этому предмету, я оттуда знаю.

Копаю в памяти:по сути, для данного DFA существует уникальный минимальный DFA, и существует алгоритм минимизации, который всегда завершается.Минимизируйте A и B и посмотрите, имеют ли они одинаковый минимальный DFA.Я не знаю сложности минимизации, хотя она не так уж и плоха (думаю, она полиномиальна).Изоморфизм графа довольно сложно вычислить, но, поскольку существует специальный начальный узел, мы надеемся, что это может быть несколько проще.Честно говоря, вам может даже не потребоваться изоморфизм графов.

Но нет, вам даже не нужно запускать DFA, просто проанализируйте их структуру.

Answer 2

Предположим, у вас есть два автомата с O(н) состояния.Тогда вы можете сделать автомат размера O(н²), который признает только симметричные различия принимаемых ими языков.(Создайте автомат, состояния которого соответствуют паре состояний, по одному от каждого автомата.Затем на каждом этапе одновременно обновляйте каждую часть пары.Состояние в новом автомате является состоянием принятия тогда и только тогда, когда ровно один из пары был состоянием принятия.) Теперь минимизируйте этот автомат и посмотрите, совпадает ли он с тривиальным автоматом с одним состоянием, который отвергает все.Минимизация автомата с помощью м состояний занимает время O(м бревно м), так что в целом вы можете сделать все за время O(н² бревно н).

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