Изменения
Нет описания правки
Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Все допускающие состояния автоматов эквивалентны между собой.
{{Лемма
|statement =
<tex> \mathcal{A} = \langle Q, \Sigma, \delta, s, T \rangle </tex>* , <tex> p_1, p_2, q_1, q_2 \in Q </tex>* , <tex> q_i = \delta(p_i, c) </tex>* , <tex> w \in \Sigma^*</tex> различает <tex> q_1 </tex> и <tex> q_2 \Rightarrow </tex>. Тогда <tex>cw </tex> различает <tex> p_1 </tex> и <tex> p_2 </tex>.
|proof =
<tex> \langle p_i, cw \rangle \vdash \langle q_i, w \rangle \vdash^* \langle t_i, \varepsilon \rangle </tex>
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex>
}}
== Алгоритм проверки эквивалентности автоматов ==
===Постановка задачи===
Даны два детерминированных конечных автомата <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> 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> E_i = D_i \setminus D_{i - 1} </tex>.
Для <tex> D_i </tex> существует рекуррентная формула:
* <tex> D_i = D_{i - 1} \cup \lbrace \langle p, q \rangle | \exists c \in \Sigma : \langle \delta(p, c), \delta(q, c) \rangle \in E_{i - 1} \rbrace </tex>.То есть <tex> D_i </tex> {{---}} объединение множества всех пар состояний, которые различаются строками длины, меньшей <tex> i </tex>, с множеством всех пар состояний, которые различаются строками длины ровно <tex> i </tex>.
Заметим, что <tex> \exists k : E_k = \varnothing </tex>, причем <tex> k \le |Q| ^ 2</tex>. И еще Также заметим, что <tex> E_k = \varnothing \Rightarrow E_{k + 1} = \varnothing </tex>, так как в <tex> D_{k+1}</tex> новых элементов не добавится, поэтому <tex> D_{k+1} = D_k </tex>.
Значит:
* <tex> E_k = \varnothing \Rightarrow D_k = \lbrace \langle q, p\rangle | q \in Q_1, p \in Q_2, \exists w : w </tex> различает <tex> q </tex> и <tex> p \rbrace = \lbrace \langle q, p\rangle | (q \nsim p)\rbrace</tex>.
Осталось найти такое <tex> k </tex> и <tex> D_k </tex>, что <tex> E_k = \varnothing </tex> тогда мы узнаем пары неэквивалентных состояний, останется только проверить, что <tex> \langle s_1, s_2 \rangle \notin D_k </tex>, тогда автоматы будут эквивалентны.
