Изменения

== Основные определения Связь эквивалентности состояний и различимости состояний ==

|definition = Два автомата <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> называются '''эквивалентными''' (англ. '''equivalent'''), если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.

|definition = [[Основные определения, связанные со строками#string|Слово]] <tex>z \in \Sigma^*</tex> '''различает''' (англ. '''distinguish''') два состояния <tex>q_i</tex> и <tex>q_j</tex>, если

Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними. Стартовым состоянием в новом автомате можно сделать <tex> s_1 </tex> или <tex> s_2 </tex> — это не имеет значения. При этом состояния одного из автоматов станут недостижимыми из новый новой стартовой вершины в новом автомате, но для алгоритма это и не важно.<br>

Осталось лишь проверить на эквивалентность состояния <tex> s_1 </tex> и <tex> s_2 </tex> в полученном автомате. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>. Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния на классы эквивалентности. Если состояния <tex>s_1</tex> и <tex>s_2</tex> нового автомата в одном классе эквивалентности {{- --}} исходные автоматы эквивалентны. Также можно минимизировать каждый автомат отдельно и проверить минимизированные версии на изоморфизм.

Алгоритм заключается Два автомата можно также проверить на эквивалентность, используя [[Обход в синхронном обходе ширину | обход в ширину]]. Будем синхронно обходить два автомата, начиная со стартовых состояний, в поисках такой строки, которая различает два состояния этих автоматов . То есть она будет допускаться одним автоматом, но не будет принадлежать языку другого. Поскольку эквивалентные автоматы допускают один и тот же язык, при переходе по одним и тем же символам в ширинуобоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно терминальными, проверяялибо одновременно нетерминальными, что и проверяет приведённый алгоритм. ==== Псевдокод ==== <font color=green>// $\mathtt{aut}[i][c]$ {{---}} номер состояния, в которое есть переход из состояния $i$ по пути сохраняются терминальные состояниясимволу $c$</font> '''boolean''' $\mathtt{bfsEquivalenceCheck}$($\mathtt{aut1}$ : '''int[][]''', $\mathtt{aut2}$ : '''int[][]'''): $Q.\mathtt{push}(\langle s_1, s_2 \rangle) $ <font color=green>// <tex> Q </tex> {{---}} очередь из пар состояний</font> '''while''' $Q \ne \varnothing $ $u, v \leftarrow Q.\mathtt{pop}()$ '''if''' $\mathtt{isTerminal1[u]} \ne \mathtt{isTerminal2[v]}$ '''return''' ''false'' $\mathtt{used[u][v]} \leftarrow $ ''true'' '''for''' $c \in \Sigma$ '''if''' '''not''' $\mathtt{used[aut1[u][c]][aut2[v][c]]}$ $Q.\mathtt{push}(\langle \mathtt{aut1}[u][c], \mathtt{aut2}[v][c] \rangle)$ '''return''' ''true''

Псевдокод: bfs_equivalence_check(aut1, aut2) '''insert''' <tex>\{s_1Корректность алгоритма следует из строго доказательства того факта, s_2\}</tex> in <tex>Q </tex> used1[0] <tex> \leftarrow </tex> true; used2[0] <tex> \leftarrow </tex> true; '''while''' <tex>Q \ne \varnothing </tex> что если два состояния $u <tex> \leftarrow </tex> Q.front.first; $ и $v <tex> \leftarrow </tex> Q.front.second; pop$ различаются какой-то строкой, то они различаются строкой длины $O(Qn); '''if'''(isTerminal1[u] != isTerminal2[v]) '''return''' false; '''for''' <tex>i \in \Sigma</tex> '''if'''(!used1[aut1[u][i]] || !used2[aut2[v][i]]) '''insert''' <tex>\{</tex>aut1[u][i], aut2[v][i]<tex>\}</tex> in <tex>Q</tex> used1[aut1[u][i]] <tex> \leftarrow </tex> true; used2[aut2[v][i]] <tex> \leftarrow </tex> true; '''return''' true;$.

ЗамечаниеИнтуитивное понимание алгоритма такое: пусть по строке $w$ мы пришли в данной реализации состояния $ \langle u, v \rangle $, и пусть они оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские нетерминальные. После этого совершим переход по символу $c$ в состояния]]$ \langle u', v' \rangle $.

* [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм Алгоритм минимизации ДКА]]

* [http://stackoverflow.com/questions/6905043/equivalence-between-two-automata/12623361#12623361| equivalence StackOverflow {{---}} Equivalence between two automata]