Проверка на равенство детерминированных конечных автоматов

[Tik-tak]

Подскажите пожалуйста алгоритм проверки на равенство двух детерминированых конечных автоматов.

[Хорхе]

Что такое "равенство" в данном случае?
Если это " равенство", а не "эквивалентность", собственно берем и проверяем
Если это "эквивалентность", думаю, такого конечного алгоритма не существует и не может существовать (я могу ошибаться).

[Tik-tak]

Да описался. Эквивалентными называем два автомата, если множества слов которые они воспринимают совпадают. Автомат воспринимает слово, если читая по символу из слова(слева направо) ) и делая переходы согласно функции переходов, прочитав последний символ мы попадём в конечную вершину(при этом раньше в конечную мы не попадали). Рассматривается конечные, детерминированый автомат

[Профессор Снэйп]

Tik-tak писал(а):

Подскажите пожалуйста алгоритм проверки на равенство двух детерминированых конечных автоматов.

Вероятно, имелась в виду эквивалентность автоматов, а не "равенство". Два автомата называются эквивалентными, если они распознают один и тот же язык.

Алгоритм проверки эквивалентности простой. Минимизируем оба автомата и сравниваем минимальные автоматы. Если они совпадают, то исходные автоматы эквивалентны, если нет, то нет.

Алгоритм минимизации автоматов описан, например, здесь, стр. 18~--~22.

[Tik-tak]

Спасиба профессор.
Я сам хотел разбивать вершины на классы еквивалентности, а потом говорить, что автоматы совпадают, если в одном класе нет конечных и не конечных вершин. Но оказался не прав.

[Профессор Снэйп]

Tik-tak писал(а):

Спасиба профессор.
Я сам хотел разбивать вершины на классы еквивалентности, а потом говорить, что автоматы совпадают, если в одном класе нет конечных и не конечных вершин. Но оказался не прав.

А как Вы определяли эту Вашу эквивалентность?

[Tik-tak]

Начальные состояния эквивалентны. Дальше два состояния N и M с разных автоматов эквивалентны, если существует буква А с алфавита, и эквивалентные состояния T и P с соответствующих автоматов, такие что f(T,A)=N; f(P,A)=M. Где f функция переходов.

[Профессор Снэйп]

Tik-tak писал(а):

Начальные состояния эквивалентны. Дальше два состояния N и M с разных автоматов эквивалентны, если существует буква А с алфавита, и эквивалентные состояния T и P с соответствующих автоматов, такие что f(T,A)=N; f(P,A)=M. Где f функция переходов.

Ну, Вам тут надо выражаться точнее. Вы даёте индуктивное определение. Насколько я понял, там у Вас возникает цепочка "эквивалентностей", а та "эквивалентность", о которой Вы ведёте речь, является объединением этой цепочки.

В конце-концов (если я правильно понял), состояния "эквивалентны", если существует слово, переводящее оба автомата в эти состояния.

Мне надо ещё подумать, но, по первому впечатлению, алгоритм правильный. Зря Вы так поспешно в нём усомнились.

[Tik-tak]

Да. Два состояния "эквивалентны", если существует слово, переводящее оба автомата в эти состояния.
Просто мне нада запрограммировать алгоритм, и первое определиние поудобней.

[Профессор Снэйп]

Tik-tak писал(а):

Просто мне нада запрограммировать алгоритм, и первое определиние поудобней.

Если Вам надо это программировать, то лучше программируйте тот алгоритм, который предложил я. Это гораздо проще!

Кстати, он довольно быстрый, этот алгоритм. Если я не ошибаюсь, то время его работы будет порядка $O(k^2)$, где $k$ --- максимальное число состояний этих двух автоматов.

[Профессор Снэйп]

Добавлю ещё, что термин "эквивалентность" применительно к вашему алгоритму явно неудачен. "Эквивалентность", даже если её понимать неформально, всё же предполагает некоторую транзитивность. А у Вас с этим может быть плохо.

Допустим, что $q_1$ и $q_2$ --- состояния первого автомата, а $p_1$ и $p_2$ --- состояния второго. Допустим, оба автомата приходят по слову $w$ в состояния $q_1$ и $p_1$, по слову $v$ --- в состояния $q_1$ и $p_2$, а по слову $u$ --- в состояния $q_2$ и $p_2$. Тогда $q_1 \sim p_1$, $q_1 \sim p_2$ и $q_2 \sim p_2$. Имея эти три "эквивалентности", логично было бы ожидать, что $q_2 \sim p_1$. Однако я не вижу резонов, по которым должно было бы найтись слово, переводящее первый автомат в $q_2$, а второй --- в $p_1$.

Конечно, если состояния $q_2$ и $p_1$ имеют разные типы (конечное/не конечное), то исходные автоматы не эквивалентны, ибо, в связи с наличием слов $u$, $v$ и $w$, тип состояния должен сохраняться вдоль всей цепочки $q_2 \to p_2 \to q_1 \to p_1$. Но всё же говорить про эквивалентность тут как-то неловко.

Я бы предпочёл всё излагать в терминах соответствий. Пусть $Q$ --- множество состояний первого автомата, а $P$ --- множество состояний второго. Нас интересует соответствие $S \subseteq Q \times P$, такое что

$$ \langle q,p \rangle \in S \Leftrightarrow \text{существует слово, переводящее автоматы в состояния }p \text{ и }q $$

Индуктивно $S$ можно задать так:

$$ S_0 = \langle q_0,p_0 \rangle : \text{состояния }q_0 \text{ и }p_0\text{ --- начальные;} $$

$$ S_{n+1} = S_n \cup \{ \langle f(q,a), f(p,a) \rangle : \langle q,p \rangle \in S_n, a \in \Sigma \} $$

$$ S = \bigcup_{n \in \mathbb{N}} S_n $$

Легко показать, что для некоторого $n$ справедливо

$$ S_0 \subset S_1 \subset \ldots \subset S_n = S_{n+1} = S_{n+2} = \ldots $$

и $S = S_n$ для этого $n$. Остаётся только найти требуемое $n$, что довольно просто сделать, пользуясь формулой перехода от $S_n$ к $S_{n+1}$. Это произойдёт довольно быстро, так как справедлива оценка $n \leqslant |Q| \cdot |P|$.

На а далее всё просто: автоматы эквивалентны тогда и только тогда, когда состояния из любой пары, входящей в $S$, имеют один и тот же тип.

Программируется всё довольно легко. Если хотите, можете реализовывать этот, свой алгоритм. По сложности он такой же, как и мой, основанный на минимизации и сравнении двух минимальных автоматов.