Изменения

Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]] языков. == Пустота регулярного языка ==

[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''пустым'''(англ. ''empty''), если он не содержит ни одного слова.

Язык, {{Определение|id=nonempty|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] содержащий хотя бы одно слово, назовём называется '''непустым'''(англ. ''nonempty'').}}

{{УтверждениеТеорема

Пусть язык содержит слово <tex>w\Rightarrow</tex>. Любой [[Детерминированные конечные автоматы| детерминированный конечный автомат]] <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одном из терминальных состояний.

<tex>\Leftarrow</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: v.seen = false return dfs(a.start)  == Совпадение регулярных языков ==

Два [[Регулярные языки: два определения и их эквивалентность|регулярных языка]] '''совпадают'''(англ. ''coincide''), если любое слово или содержится в обоих языках, или не содержится ни в одном из них.}} Пусть <tex>A_{1}</tex> и <tex>A_{2}</tex> — [[Детерминированные конечные автоматы| детерминированные конечные автоматы]], задающие языки <tex>L_{1}</tex> и <tex>L_{2}</tex> над одним алфавитом <tex>\Sigma</tex>, соответственно. Совпадение языков ('''эквивалентность''' задающих их автоматов) означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния <tex>p_{1}</tex> из <tex>A_{1}</tex> и <tex>p_{2}</tex> из <tex>A_{2}</tex> '''различимыми''', если существует строка <tex>w</tex> из символов <tex>\Sigma</tex>, для которой выполняется  <tex>\langle p_{1}, w \rangle \rightarrow \langle t_{1}, \epsilon \rangle</tex>, <tex>\langle p_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle</tex> или <tex>\langle p_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle</tex>, <tex>\langle p_{2}, w \rangle \rightarrow \langle t_{2}, \epsilon \rangle</tex>, где <tex>t_{1}</tex>, <tex>t_{2}</tex> — допускающие состояния, <tex>u_{1}</tex>, <tex>u_{2}</tex> — недопускающие. Все состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами; назовём их '''бесполезными'''. Введём '''сток'''<ref>Другое название стока - «дьявольское состояние».</ref> — специальное недопускающее состояние, переходы по всем символам из которого ведут в него самого. Все переходы исходного автомата, которые отсутствовали или вели в бесполезные состояния, направим в сток.  === Алгоритм проверки языков на совпадение === Первым шагом алгоритма является избавление автоматов от состояний, из которых недостижимы допускающие. Проще всего это реализовать обходом [[Обход в глубину, цвета вершин|в глубину]] или [[Обход в ширину|в ширину]] из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов, вместо них вводится описанный выше сток.  Пусть <tex>eq(v, u)</tex> — функция, принимающая пару состояний из первого и второго автоматов и возвращающая некоторое значение булевского типа. Второй шаг алгоритма — установка <tex>eq(v, u)</tex> в <tex>false</tex> для всех пар <tex>\langle v, u \rangle</tex>, кроме <tex>\langle s_{1}, s_{2} \rangle</tex>. Также создаётся очередь, в которую помещается пара <tex>\langle s_{1}, s_{2} \rangle</tex>.  Третий шаг алгоритма — [[Обход в ширину|обход в ширину]]. Пусть на текущем шаге из очереди получена пара <tex>\langle v \in A_{1}, u \in A_{2} \rangle</tex>. Тогда для всех символов <tex>c \in \Sigma</tex> рассматриваются пары <tex>\langle v', u' \rangle : \delta_{1} (v, c) = v', \delta_{2} (u, c) = u'</tex>. Если <tex>eq(v', u')</tex> возвращает <tex>false</tex>, данное значение устанавливается в <tex>true</tex>, а в очередь добавляется пара <tex>\langle v', u' \rangle</tex>.  {{Утверждение|id=regEqual|statement=Автоматы <tex>A_{1}</tex> и <tex>A_{2}</tex> эквивалентны тогда и только тогда, когда после окончания работы алгоритма не существует такой пары <tex>\langle v, u \rangle</tex>, что <tex>eq(v, u)</tex> возвращает <tex>true</tex> и ровно одно из <tex>\langle v, u \rangle</tex> допускающее. |proof=Пусть такой пары не существует. Возьмём произвольное слово <tex>w</tex> длины <tex>n</tex> и выпишем последовательность пар состояний <tex>\langle v_{i}, u_{i} \rangle</tex>: <tex>v_{0} = s_{1}, u_{0} = s_{2}</tex> и <tex>\forall i = 1 .. n</tex> справедливо <tex>\delta_{1} (v_{i-1}, w[i-1]) = v_{i}, \delta_{2} (u_{i-1}, w[i-1]) = u_{i}</tex>. Так как пара <tex>\langle v_{0}, u_{0} \rangle</tex> была в очереди, каждая из последующих пар в процессе алгоритма также побывала в очереди, значит, <tex>eq</tex> для них возвращает <tex>true</tex>. По предположению, или оба состояния <tex>\langle v_{n}, u_{n} \rangle</tex> допускающие в своих автоматах, или оба недопускающие. Таким образом, строка <tex>w</tex> или входит в оба языка, или не входит ни в один.  Пусть такая пара <tex>\langle v, u \rangle</tex> существует. Для определённости скажем, что <tex>v \in A_{1}</tex> — допускающее. Рассмотрим строку <tex>w</tex>, состоящую из символов, в результате переходов по которым из <tex>\langle s_{1}, s_{2} \rangle</tex> в процессе обхода в ширину <tex>eq(v, u)</tex> было установлено в <tex>true</tex>. Строка <tex>w</tex> допускается первым автоматом, но не допускается вторым, значит, автоматы не эквивалентны.

void reverseDfs(State v): v.canReach = true== Пример проверки на совпадение регулярных языков=== for each State u in vДля того, чтобы узнать равен ли язык своему замыканию Клини, нужно проверить на [[Эквивалентность_состояний_ДКА|эквивалентность]] автомат, задающий язык, и автомат, задающий замыкание Клини языка.prev: if !uЕсли автоматы эквивалентны, то язык равен своему замыканию Клини.canReach: reverseDfs(u)

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.canReach: v = sink  void bfs(Automaton a, Automaton b, boolean[][] eq) fill(eq, false) eq[a.start][b.start] = true Queue q = new Queue q.add((a.start, b.start)) while !q.isEmpty: (v, u) = q.remove() for each symbol c in a.alphabet: // a.alphabet == b.alphabet v' = v.next(c) u' = u.next(c) if !eq[v'][u']: eq[v'][u'] = true q.add((v', u'))  boolean areEqual(Automaton a, Automaton b) for each State v in a: v.canReach = false for each State v in a: if v.isFinal: reverseDfs(v) setSink(a) for each State v in b: v.canReach = false for each State v in b: if v.isFinal: reverseDfs(v) setSink(b) eq = new boolean[a.statesNumber][b.statesNumber] bfs(a, b, eq) for each State v in a: for each State u in b: if eq[v][u] && v.isFinal != u.isFinal: return false return true  == Включение одного регулярного языка в другой ==

[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] <tex>L_{1}</tex> '''входит (включается)''' (англ. ''included'') в регулярный язык <tex>L_{2}</tex>, если любое слово, принадлежащее <tex>L_{1}</tex>, принадлежит <tex>L_{2}</tex>.

=== Алгоритм проверки на включение === Алгоритм проверки Пусть автомат <tex>L_{1}M_1</tex> на включение в задаёт язык <tex>L_{2}L_1</tex> идентичен алгоритму проверки их совпадения, кроме одной особенности. Могут существовать слова из а автомат <tex>L_{2}M_2</tex>, не входящие в — язык <tex>L_{1}</tex>, поэтому существование пар <tex>\langle v \in L_{1}, u L_1 \in L_{2} \rangle : eq(v, u) == true, v \notin T_{1}, u \in T_{2}cap L_2</tex>, где <tex>T_{i}</tex> — множества допускающих состояний, не нарушает факт вхождения . Для проверки включения <tex>L_{1}L_1</tex> в <tex>L_{2}L_2</tex>. Таким образом, достаточно проверить [[Эквивалентность_состояний_ДКА|эквивалентность]] <tex>L_{1}M_1</tex> не входит в <tex>L_{2}</tex> тогда и только тогда, когда после окончания работы алгоритма, идентичного алгоритму проверки на совпадение, не существует такой пары <tex>\langle v, u \rangle</tex>, что <tex>eq(v, u)M_2</tex> возвращает <tex>true</tex>, <tex>v \in T_{1}, u \notin T_{2}</tex>. ==== Псевдокод ====  void reverseDfs(State v): v.canReach = true for each State u in v.prev: if !u.canReach: reverseDfs(u)  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.canReach: v = sink  void bfs(Automaton a, Automaton b, boolean[][] eq) fill(eq, false) eq[a.start][b.start] = true Queue q = new Queue q.add((a.start, b.start)) while !q.isEmpty: (v, u) = q.remove() for each symbol c in a.alphabet: // a.alphabet == b.alphabet v' = v.next(c) u' = u.next(c) if !eq[v'][u']: eq[v'][u'] = true q.add((v', u'))  boolean belongs(Automaton a, Automaton b) for each State v in a: v.canReach = false for each State v in a: if v.isFinal: reverseDfs(v) setSink(a) for each State v in b: v.canReach = false for each State v in b: if v.isFinal: reverseDfs(v) setSink(b) eq = new boolean[a.statesNumber][b.statesNumber] bfs(a, b, eq) for each State v in a: for each State u in b: if eq[v][u] && v.isFinal && !u.isFinal: return false return true 

== Конечность регулярного языка, подсчёт числа слов ==

[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''конечным'''(англ. ''finite''), если принадлежащее ему множество слов конечно.

{{УтверждениеТеорема

1) * <tex>v</tex> достижимо из стартового состояния <tex>s</tex>; 2) * из <tex>v</tex> достижимо какое-либо из допускающих состояний; 3) * из <tex>v</tex> по одному или более переходам достижимо <tex>v</tex>.

Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <tex>\mathrm{paths} (v)</tex>, задающую число различных путей из <tex>s</tex> в <tex>v</tex>; <tex>\mathrm{paths} (s) = 1</tex>. Заметим, что если известны значения <tex>\mathrm{paths} (u)</tex> для всех <tex>u</tex>, из которых существует переход в <tex>v</tex>, то <tex>\mathrm{paths} (v) = \sum\limits_{u}\mathrm{paths} (u)</tex>. Количеством слов в языке будет сумма <tex>\mathrm{paths} (t)</tex> для всех допускающих <tex>t</tex>. Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они были разделены. ==== Псевдокод ====  Stack topSort(Automaton a): for each State v in a: v.seen = false Stack sorted = new Stack dfsSort(a.start, sorted) return sorted  void dfsSort(State v, Stack sorted): v.seen = true for each State u in v.next: if !u.seen: dfsSort(u, sorted) sorted.push(v)  void reverseDfs(State v): v.canReach = true for each State u in v.prev: if !u.canReach: reverseDfs(u)  boolean dfs(State v): // returns true iff there is a cycle v.color = GREY for each State u in v.next: if u.color == GREY: return true if u.canReach && u.color == WHITE && dfs(u): return true v.color = BLACK return false   int words(Automaton a): for each State v in a: v.canReach = false for each State v in a: if v.isFinal: reverseDfs(v) for each State v in a: v.color = WHITE if dfs(a.start): return infinity Stack sorted = topSort(a) paths = new int[a.statesNumber] fill(paths, 0) paths[0] = 1 while !sorted.isEmpty: State v = sorted.pop() for each State u in v.next: paths[u] += paths[v] int result = 0 for each State v in a: if v.isFinal: result += paths[v] return result  == Литература ==

== См. также ==* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, [[Замкнутость регулярных языков относительно различных операций]]* [[Теорема Клини (совпадение классов автоматных и вычислений, 2-е изд. / Пер. с англ. — Москварегулярных языков)]]* [[Доказательство нерегулярности языков: Издательский дом «Вильямс», 2002. — с. 169-177: ISBN 5-8459-0261-4 (рус.)лемма о разрастании]]