Изменения

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

|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>, если

|definition = Два <em> состояния</em> <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует [[Основные определения, связанные со строками#string|строки]], которая их различает, то есть <tex>\forall z \in \Sigma^*</tex> верно, что

Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и <tex> \forall z \in \Sigma^*\ \forall q \in Q \ \exists ! t : \langle q, z \rangle \vdash^* \langle t, \varepsilon \rangle </tex>в детерминированном автомате всегда существует путь по любому слову, поэтому описанное нами отношение является отношением эквивалентности.

=== Пример ===[[Файл:avtomat2.png|350px200px]] [[Файл:avtomat3.png|350px200px]]

== Алгоритм проверки эквивалентности автоматов ==[[Категория: Теория формальных языков]][[Категория: Автоматы и регулярные языки]] ===Постановка задачи=Проверка ДКА на эквивалентность ==Даны Заданы два детерминированных конечных автомата : <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> со стартовым состоянием <tex> s_1 </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex>со стартовым состоянием <tex> s_2 </tex> соответственно. Требуется определить, эквивалентны ли ониНужно проверить их на эквивалентность. '''Замечание:''' для реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].===АлгоритмПроверка через минимизацию ===Рассмотрим такие семейства множеств:* Для этого построим автомат <tex> D_i = \lbrace \langle qmathcal{A} </tex>, p\rangle | q \in Q_1содержащий все состояния обоих автоматов и изначальные переходы между ними. Стартовым состоянием в новом автомате можно сделать <tex> s_1 </tex> или <tex> s_2 </tex> — это не имеет значения. При этом состояния одного из автоматов станут недостижимыми из новой стартовой вершины в новом автомате, p \in Q_2, \exists w но для алгоритма это и не важно.<br>[[Файл: auto_equiq.png|w| \le i, w 470px]]<br>Осталось лишь проверить на эквивалентность состояния <tex> s_1 </tex> различает и <tex> q s_2 </tex> и в полученном автомате. Их эквивалентность совпадает с эквивалентностью автоматов <tex> p \rbrace mathcal{A}_1 </tex>;* и <tex> E_i = D_i \setminus D_mathcal{i - 1A} _2 </tex>. Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния на классы эквивалентности. Если состояния <tex>s_1</tex> и <tex>s_2</tex>нового автомата в одном классе эквивалентности {{---}} исходные автоматы эквивалентны. Также можно минимизировать каждый автомат отдельно и проверить минимизированные версии на изоморфизм.

Для <tex> D_i </tex> существует рекуррентная формула:=== Проверка через BFS ===* <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>но не будет принадлежать языку другого.

ЗаметимПоскольку эквивалентные автоматы допускают один и тот же язык, при переходе по одним и тем же символам в обоих автоматах, слово должно приниматься обоими автоматами одновременно. То есть вершины, в которые мы перешли, должны быть либо одновременно терминальными, либо одновременно нетерминальными, что и проверяет приведённый алгоритм. ==== Псевдокод ==== <texfont color=green> // $\exists k : E_k = \varnothing mathtt{aut}[i][c]$ {{---}} номер состояния, в которое есть переход из состояния $i$ по символу $c$</texfont> '''boolean''' $\mathtt{bfsEquivalenceCheck}$($\mathtt{aut1}$ : '''int[][]''', причем <tex> k $\le |mathtt{aut2}$ : '''int[][]'''): $Q| ^ 2</tex>. Также заметим, что <tex> E_k = \varnothing \Rightarrow E_mathtt{k + 1push} = (\langle s_1, s_2 \varnothing rangle) $ <font color=green>//tex>, так как в <tex> D_{k+1}Q </tex> новых элементов не добавится, поэтому <tex> D_{k+1{---} = D_k } очередь из пар состояний</texfont>.Значит: '''while''' $Q \ne \varnothing $ * <tex> E_k = $u, v \leftarrow Q.\varnothing mathtt{pop}()$ '''if''' $\Rightarrow D_k = mathtt{isTerminal1[u]} \lbrace ne \langle q, pmathtt{isTerminal2[v]}$ '''return''' ''false'' $\rangle | q mathtt{used[u][v]} \in Q_1, p leftarrow $ ''true'' '''for''' $c \in Q_2, \exists w : w </tex> различает <tex> q </tex> и <tex> p Sigma$ '''if''' '''not''' $\rbrace = mathtt{used[aut1[u][c]][aut2[v][c]]}$ $Q.\lbrace mathtt{push}(\langle q\mathtt{aut1}[u][c], p\mathtt{aut2}[v][c] \rangle | (q \nsim p)\rbrace</tex>.$ '''return''' ''true''

Осталось найти такое <tex> k </tex> и <tex> D_k </tex>Корректность алгоритма следует из строго доказательства того факта, что <tex> E_k = \varnothing </tex> тогда мы узнаем пары неэквивалентных состояний, останется только проверить, что <tex> \langle s_1, s_2 \rangle \notin D_k </tex>если два состояния $u$ и $v$ различаются какой-то строкой, тогда автоматы будут эквивалентныто они различаются строкой длины $O(n)$.

Будем строить <tex> D_i </tex> Интуитивное понимание алгоритма такое: пусть по строке $w$ мы пришли в порядке увеличения <tex> i </tex>, пока <tex> D_i \neq D_{i - 1}</tex>.Заметим, что <tex> D_0 = \lbrace состояния $ \langle pu, qv \rangle | p \in T_1 \Leftrightarrow q \notin T_2 \rbrace </tex>$, так как строка длины 0 одна {{---}} это <tex> и пусть они оба нетерминальные. После этого совершим переход по символу $c$ в состояния $ \varepsilon </tex>langle u', а <tex> v' \varepsilon </tex> различает только пары состоящие из одного терминального состояния и одного нетерминальногоrangle $.

Дальше будем получать <tex> D_i </tex> по рекуррентной формулеТогда если $\mathtt{isTerminal1[u']} \ne \mathtt{isTerminal2[v']}$, пока то строка $wc$ различает эти два состояния. А значит автоматы не выполнится условие остановкиэквивалентны.

Это можно реализовать проще: будем хранить для каждого состояния, из какого состояния есть переход по символу <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_алгоритм_за_O(qn%5E2) <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> if neq[<tex>e_1</tex>, <tex>e_2</tex>_с_построением_пар_различимых_состояний|Алгоритм минимизации ДКА] continue 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>===Время работы алгоритма===Оценим время работы алгоритма. Заметим, что каждая пара состояния будет добавлена в очередь, не более одного раза. Поэтому цикл ''while'' выполнится не более чем <tex> |Q_1|\cdot |Q_2| </tex> раз. А значит в этом же цикле каждая пара ребер будет просмотрена не более одного раза, потому что для каждой вершины мы просматриваем все входящие ребра. А значит внутренний <font size = 3><tt> if neq[<tex>e_1</tex>Минимизация ДКА, <tex>e_2</tex>] </tt> </font> выполнится порядка <tex> |Q_1||Q_2||\Sigma|^2 </tex>, потому что это верхняя оценка на количество ребер в детерминированном автомате {{---}} <tex> |Q||\Sigma|</tex>.А значит алгоритм будет работать за <tex> Хопкрофта (сложность O(|Q_1||Q_2||\Sigma|^2n log n))</tex>.]]

[[Категория: Теория формальных языков]]== Источники информации ==* [[Категорияhttp: Автоматы и регулярные языки]//stackoverflow.com/questions/6905043/equivalence-between-two-automata/12623361#12623361 StackOverflow {{---}} Equivalence between two automata]