Изменения
→Алгоритм проверки эквивалентности автоматов
== Алгоритм проверки эквивалентности автоматов ==
===Постановка задачи===
Даны два детерминированных конечных автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex>. Требуется определить, эквивалентны ли они.
{{Лемма
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex>
}}
Рассмотрим такие семейства множеств:
* <tex> D_i = \lbrace \langle q, p\rangle | q \in Q_1, p \in Q_2, \exists w : |w| \le i, w </tex> различает <tex> q </tex> и <tex> p \rbrace </tex>
Дальше будем получать <tex> D_i </tex> по рекуррентной формуле, пока не выполнится условие остановки.
Это можно реализовать проще: будем хранить для каждого состояния, из какого состояния есть переход по символу <tex> c </tex> в наше. В очередь будем класть пары неэквивалентных состояний. Дальше вытаскивая из очереди пару, рассмотрим все пары состояний, из которых есть переход по одинаковому символу в элементы пары из очереди. Пометим их неэквивалентными и положим в очередь. ===Псевдокод:===
<font size = 3>
<tex> q = \varnothing </tex>
fill(neq, false)
for <tex> p_1 \in Q_1 </tex>: for <tex> p_2 \in Q_2 </tex>: if <tex> (p_1 \in T_1) \neq (p_2 \in T_2) </tex>:
q.push(<tex>p_1</tex>,<tex> p_2</tex>)
neq[<tex>p_1</tex>, <tex>p_2</tex>] = True; while not isEmpty(q):
<tex> \langle p_1, p_2 \rangle </tex> = q.pop()
for <tex> c \in \Sigma </tex> : for <tex> \delta(e_1, c) = p_1 </tex>: for <tex> \delta(e_2, c) = p_2 </tex>:
q.push(<tex>e_1</tex>, <tex>e_2</tex>)
neq[<tex>e_1</tex>, <tex>e_2</tex>] = True
if neq[<tex>s_1</tex>, <tex>s_2</tex>]:
print("Not equivalent")
else
print("Equivalent")
</font>
===Время работы алгоритма===Алгоритм будет работать за <tex> \mathcal O(|Q_1||Q_2||\Sigma|^2)</tex>.
[[Категория: Теория формальных языков]]
