== Пустота ==
'''Пустота''' [[Регулярные языки: два определения и их эквивалентность|регулярного языкаРегулярный язык]] — свойство языка является '''пустым''', если он не содержать содержит ни одного слова. Язык, содержащий хотя бы одно слово, назовём '''непустым'''.
{{Утверждение
regEmpty
|statement=
Регулярный язык является непустым тогда и только тогда, когда в любом соответствующем ему задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.
|proof=
Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, соответствующий этому языкузадающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин.
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
==== Псевдокод ==== boolean dfs(State v) {: v.seen = true; if (v.isFinal) {: return false; } for (each State u : in v.next) {: if (!u.seen && !dfs(u)) {: return false; } } return true; } boolean isEmpty(Automaton a) {: for (each State v in a: a) { v.seen = false; } return dfs(a.start); }
== Совпадение ==
'''Совпадение''' двух Два [[Регулярные языки: два определения и их эквивалентность|регулярных языковязыка]] — свойство'''совпадают''', при выполнении которого если любое словоили содержится в обоих языках, принадлежащее одному или не содержится ни в одном из языков, принадлежит второмуних.
Пусть <tex>A_{1}</tex> и <tex>A_{2}</tex> - детерминированные конечные автоматы, соответствующие языкам <tex>L_{1}</tex> и <tex>L_{2}</tex> над одним алфавитом <tex>\Sigma</tex>, соответственно. Совпадение языков на языке конечных автоматов (''эквивалентность'') означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния <tex>p_{1} \in A_{1}</tex> и <tex>p_{2} \in A_{2}</tex> '''идентичнымиразличимыми''', если существует строка <tex>w</tex> из символов <tex>\Sigma</tex>, для которой выполняется
<tex>\langle s_p_{1}, w \rangle \rightarrow \langle p_t_{1}, \epsilon \rangle</tex>,<tex>\langle p_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle</tex>
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{2}, \epsilon \rangle</tex>,или
где <tex>s_\langle p_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle</tex>, <tex>s_\langle p_{2}, w \rangle \rightarrow \langle t_{2}, \epsilon \rangle</tex> - стартовые состояния.,
На основе заданного отношения разобьём состояния автоматов на классы эквивалентности: состояния <tex>p</tex> и <tex>q</tex> принадлежат одному классу тогда и только тогда, когда существует последовательность состояний где <tex>p_s_{0}...p_{k1}</tex>, где <tex>p = p_s_{02}</tex>- стартовые состояния, <tex>q = p_t_{k}</tex> и <tex>\forall i = 1..k</tex> <tex>p_{i - 1}</tex> идентично , <tex>p_t_{i2}</tex>. Все - допускающие состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут. {{Теорема|id=regEqClasses|statement=Автоматы <tex>A_u_{1}</tex> и , <tex>A_u_{2}</tex> эквивалентны тогда и только тогда, когда в любом классе содержатся или только допускающие, или только - недопускающие состояния.
|proof=Пусть в каком-либо классе содержатся допускающее состояние <tex>t</tex> и недопускающее <tex>u</tex>. По построению классов эквивалентностиВсе ''бесполезные'' состояния, из которых не достигаются допускающие, существует последовательность <tex>p_{0}...p_{k}</tex>не влияют на множество слов, где <tex>t = p_{0}</tex>допускаемых автоматами, <tex>u = p_{k}</tex> и <tex>\forall i = 1поэтому далее они рассматриваться не будут..k</tex> <tex>p_{i Введём ''сток'' - 1}</tex> идентично <tex>p_{i}</tex>. Тогда найдётся пара <tex>p_{j}</tex>специальное недопускающее состояние, <tex>p_{j+1}</tex>: <tex>p_{j}</tex> является допускающим, а <tex>p_{j+1}</tex> - нетпереходы по всем символам из которого ведут в него самого. Для определённостиВсе переходы исходного автомата, пусть <tex>p_{j}</tex> принадлежит первому автоматукоторые отсутствовали или вели в бесполезные состояния, а <tex>p_{j+1}</tex> - второмунаправим в сток. Так как эти состояния идентичны, <tex>\exists w</tex>:
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{j}, \epsilon \rangle</tex>,
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{j+1}, \epsilon \rangle</tex>.=== Алгоритм проверки языков на совпадение ===
Таким образомПервым шагом алгоритма является избавление автоматов от состояний, слово <tex>w</tex> допускается первым автоматом и не допускается вторымиз которых недостижимы допускающие. Проще всего это реализовать обходом [[Обход в глубину, значитцвета вершин|в глубину]] или [[Обход в ширину|в ширину]] из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов, автоматы неэквивалентнывместо них вводится описанный выше сток.
Пусть <tex>eq(u, v)</tex> - функция, принимающая пару состояний из первого и второго автоматов и возвращающая некоторое значение булевского типа. Второй шаг алгоритма - установка <tex>eq(u, v)</tex> в любом классе содержатся только допускающие или только недопускающие состояния. Рассмотрим любую строку <tex>wfalse</tex> для всех пар <tex>\langle u, v \rangle</tex> и такие состояния , кроме <tex>u_\langle s_{1}, s_{2} \rangle</tex> и . Также создаётся очередь, в которую помещается пара <tex>u_\langle s_{1}, s_{2}\rangle</tex>, что.
<tex>\langle s_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle</tex>,
Третий шаг алгоритма - [[Обход в ширину|обход в ширину]]. Пусть на текущем шаге из очереди получена пара <tex>\langle s_u \in A_{1}, v \in A_{2}\rangle</tex>. Тогда для всех символов <tex>c \in \Sigma</tex> рассматриваются пары <tex>\langle u', w v' \rangle : \rightarrow delta_{1} (u, c) = u', \langle u_delta_{2}(v, c) = v'</tex>. Если <tex>eq(u', v')</tex> возвращает <tex>false</tex>, данное значение устанавливается в <tex>true</tex>, а в очередь добавляется пара <tex>\epsilon langle u', v' \rangle</tex>.
Состояния <tex>u_{1}</tex> и <tex>u_{2}</tex> идентичны, следовательно, принадлежат одному классу эквивалентности. Таким образом, любая строка оканчивается либо допускающими состояниями в обоих автоматах, либо в обоих не допускается, значит, автоматы эквивалентны.
}}
{{Утверждение
|id=
regEqClassesregEqual
|statement=
Если состояния Автоматы <tex>pA_{1}</tex> и <tex>qA_{2}</tex> принадлежат одному классу эквивалентностиэквивалентны тогда и только тогда, то для любого символа когда после окончания работы алгоритма не существует такой пары <tex>c\langle u, v \rangle</tex> из алфавита , что <tex>\delta eq(pu, cv)</tex> возвращает <tex>true</tex> и ровно одно из <tex>\delta (qlangle u, c)v \rangle</tex> также принадлежат одному классудопускающее.
|proof=
Рассмотрим Пусть такой пары не существует. Возьмём произвольное слово <tex>w</tex> длины <tex>n</tex> и выпишем последовательность пар состояний <tex>p_\langle u_{0i}...p_, v_{ki}\rangle</tex>, где : <tex>p u_{0} = p_s_{1}, v_{0}</tex>, <tex>q = p_s_{k2}</tex> и <tex>\forall i = 1..kn</tex> справедливо <tex>p_\delta_{1} (u_{i - 1}</tex> идентично <tex>p_{, s[i}</tex> по строке <tex>w_-1]) = u_{i}</tex>. Тогда для последовательности <tex>p'_, \delta_{02}...p'_(v_{ki-1}</tex>, где <tex>\delta (p, cs[i-1]) = p'_v_{0i}</tex>, . Так как пара <tex>\delta (qlangle u_{0}, c) = p_v_{k0}\rangle</tex> будет верно: была в очереди, каждая из последующих пар в процессе алгоритма также побывала в очереди, значит, <tex>\forall i = 1..keq</tex> для них возвращает <tex>p'_{i - 1}true</tex> идентично . По предположению, или оба состояния <tex>p'_\langle u_{in}</tex> по строке <tex>w_, v_{in}c\rangle</tex>допускающие в своих автоматах, или оба недопускающие. Таким образом, строка <tex>\delta (p, c)w</tex> и <tex>\delta (qили входит в оба языка, c)</tex> также принадлежат одному классуили не входит ни в один.}}
По индукции, утверждение верно и для большего числа переходов.
=== Алгоритм проверки языков на эквивалентность ===Пусть такая пара <tex>\langle u, v \rangle</tex> существует. Для определённости скажем, что <tex>u \in A_{1}</tex> - допускающее. Рассмотрим строку <tex>w</tex>, состоящую из символов, в результате переходов по которым из <tex>\langle s_{1}, s_{2} \rangle</tex> в процессе обхода в ширину <tex>eq(u, v)</tex> было установлено в <tex>true</tex>. Строка <tex>w</tex> допускается первым автоматом, но не допускается вторым, значит, те не эквивалентны.}}
Первым шагом алгоритма является избавление автоматов от состояний, из которых недостижимы допускающие. Проще всего это реализовать обходом [[Обход в глубину, цвета вершин|в глубину]] или [[Обход в ширину|в ширину]] из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов.==== Псевдокод ====
Второй шаг - обход в ширину, объединяющий классы эквивалентности. Изначально каждое состояние принадлежит отдельному классу, кроме двух стартовых, объединённых в один класс. Для определения класса по состоянию используется [[СНМ void revDfs(наивные реализацииState v)|система непересекающихся множеств]]: v. Очередь обхода в ширину хранит пары состояний <tex>p_{1} \seen = true for each State u in A_{1}</tex>, <tex>p_{2} \in A_{2}</tex>, для которых существует строка <tex>w</tex> v.prev: if !u.seen: revDfs(для <tex>s_{1}</tex> и <tex>s_{2}</tex> равная <tex>\epsilon</tex>u):
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{1}, \epsilon \rangle</tex>, void setSink(Automaton a): State sink = new State for each symbol c in a.alphabet: sink.next(c) = sink for each State v in a: if !v.seen: v = sink
<tex>\langle s_{2} void bfs(Automaton a, w \rangle \rightarrow \langle p_{2}Automaton b) eq = new bool[a.statesNumber][b.statesNumber] fill(eq, false) eq[a.start][b.start] = true Queue q = new Queue q.add((a.start, b.start)) while !q.isEmpty: (v, \epsilon \rangle<u) = q.remove() for each symbol c in a.alphabet: /tex>/ a.alphabet == b.alphabet v' = v.next(c) u' = u.next(c) if !eq[v'][u']: eq[v'][u'] = true q.add((v', u'))
Для пары состояний изучаются переходы из них по всем символам алфавита. Пусть <tex>\delta boolean areEqual(p_{1}Automaton a, cAutomaton b) for each State v in a: v.seen = q_{1}</tex>, <tex>\delta false for each State v in a: if v.isFinal: revDfs(v) setSink(p_{2}, ca) for each State v in b: v.seen = q_{2}</tex>false for each State v in b: if v. Если <tex>q_{1}</tex> и <tex>q_{2}</tex> принадлежат разным классамisFinal: revDfs(v) setSink(b) bfs(a, их классы объединяются, а пара <tex>\langle q_{1}, q_{2} \rangle</tex> добавляется в очередьb) for each State v in a: for each State u in b: if eq[v][u] && v.isFinal != u.isFinal: return false return true
