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

Question

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

Answer 1

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

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

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

Answer 2

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

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