Изменения

|definition = Два <em> автомата</em> <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{101}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{202}, T_2\subseteq Q_2 \rangle </tex> называются <em>эквивалентными</em>, если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</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> <br>'''Необходимо определить'''[[Изображение:Automata1.png]][[Изображение:Automata2.png]] Эквивалентны ли эти автоматы <br>

{{Лемма|statement =<emtex> \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 cw </tex> различает <tex> p_1 </tex> и <tex>Состояния p_2 </tex>B|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>Cq_2</tex> допускающие., <tex> t_1 \in T \Leftrightarrow t_2 \notin T </emtex>}}<br>Рассмотрим такие семейства множеств:* <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> \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>, тогда автоматы будут эквивалентны. Будем строить <tex> D_i </tex> в порядке увеличения <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> различает только пары состоящие из одного терминального состояния и одного нетерминального. Дальше будем получать <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>