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

Question

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

Answer 1

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

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

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

Answer 2

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

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