Изменения

|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> называются <em>'''эквивалентными</em>''' (англ. ''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> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \notin T \Leftrightarrow t_2 \in T ) </tex>.

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

== Алгоритм проверки Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности автоматов == '''Задано''': Два детерминированных конечных автомата |отношением эквивалентности]]. Так как <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle Leftrightarrow </tex> (равносильность) является отношением эквивалентности и <tex>\mathcal{A}_2 = \langle Q_2в детерминированном автомате всегда существует путь по любому слову,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> <br>'''Необходимо определить''': Эквивалентны ли эти автоматы <br>описанное нами отношение является отношением эквивалентности.

<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>.

Для === Пример ===[[Файл:avtomat2.png|200px]] [[Файл:avtomat3.png|200px]] Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> D_i \lbrace 0, 1\rbrace </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_mathcal{i - 1A} \rbrace _1 </tex>То есть со стартовым состоянием <tex> D_i s_1 </tex> {{---}} объединение множества всех пар состояний, которые различаются строками длины, меньшей и <tex> i \mathcal{A}_2 </tex>, с множеством всех пар состояний, которые различаются строками длины ровно со стартовым состоянием <tex> i s_2 </tex>соответственно. Нужно проверить их на эквивалентность.

Заметим, что '''Замечание:''' для реализации оба автомата обязательно должны иметь [[Детерминированные_конечные_автоматы#допускает|дьявольские состояния]].=== Проверка через минимизацию ===Для этого построим автомат <tex> \exists k : E_k = \varnothing mathcal{A} </tex>, причем содержащий все состояния обоих автоматов и изначальные переходы между ними. Стартовым состоянием в новом автомате можно сделать <tex> s_1 </tex> или <tex> k \le |Q| ^ 2s_2 </tex>— это не имеет значения. И еще заметимПри этом состояния одного из автоматов станут недостижимыми из новой стартовой вершины в новом автомате, что но для алгоритма это и не важно.<br>[[Файл:auto_equiq.png|470px]]<br>Осталось лишь проверить на эквивалентность состояния <tex> E_k = \varnothing \Rightarrow E_{k + 1} = \varnothing s_1 </tex>, так как в и <tex> D_{k+1}s_2 </tex> новых элементов не добавится, поэтому в полученном автомате. Их эквивалентность совпадает с эквивалентностью автоматов <tex> D_\mathcal{k+1A} = D_k _1 </tex>.Значит:* и <tex> E_k = \varnothing \Rightarrow D_k = \lbrace \langle q, p\rangle | q \in Q_1, p \in Q_2, \exists w : w mathcal{A}_2 </tex> различает . Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния на классы эквивалентности. Если состояния <tex> q s_1</tex> и <tex> p \rbrace = \lbrace \langle q, p\rangle | (q \nsim p)\rbraces_2</tex>нового автомата в одном классе эквивалентности {{---}} исходные автоматы эквивалентны.

Осталось найти такое <tex> k </tex> Также можно минимизировать каждый автомат отдельно и <tex> D_k </tex>, что <tex> E_k = \varnothing </tex> тогда мы узнаем пары неэквивалентных состояний, останется только проверить, что <tex> \langle s_1, s_2 \rangle \notin D_k </tex>, тогда автоматы будут эквивалентныминимизированные версии на изоморфизм.

Будем строить <tex> D_i </tex> === Проверка через BFS ===Два автомата можно также проверить на эквивалентность, используя [[Обход в ширину | обход в порядке увеличения <tex> i </tex>, пока <tex> D_i \neq D_{i - 1}</tex>ширину]].Заметим, что <tex> D_0 = \lbrace \langle pБудем синхронно обходить два автомата, q\rangle | p \in T_1 \Leftrightarrow q \notin T_2 \rbrace </tex>начиная со стартовых состояний, так как строка длины 0 одна {{---}} это <tex> \varepsilon </tex>в поисках такой строки, а <tex> \varepsilon </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> D_i 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''

Это можно реализовать проще: будем хранить для каждого состоянияКорректность алгоритма следует из строго доказательства того факта, из какого что если два состояния есть переход по символу <tex> c </tex> в наше. В очередь будем класть пары неэквивалентных состояний. Дальше вытаскивая из очереди пару, рассмотрим все пары состояний, из которых есть переход по одинаковому символу в элементы пары из очереди. Пометим их неэквивалентными $u$ и положим в очередь. Псевдокод:<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>$v$ различаются какой-то строкой, <tex>p_2</tex>] = True; while not isEmptyто они различаются строкой длины $O(qn): <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>

Интуитивное понимание алгоритма такое: пусть по строке $w$ мы пришли в состояния $ \langle u, v \rangle $, и пусть они оба нетерминальные. После этого совершим переход по символу $c$ в состояния $ \langle u', v' \rangle $.  Тогда если $\mathtt{isTerminal1[u']} \ne \mathtt{isTerminal2[v']}$, то строка $wc$ различает эти два состояния. А значит автоматы не эквивалентны. == См. также == * [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|Алгоритм будет работать за <tex> \mathcal минимизации ДКА]]* [[Минимизация ДКА, алгоритм Хопкрофта (сложность 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]