}}
=== Алгоритм проверки на включение === Алгоритм проверки Пусть автомат <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
== Конечность регулярного языка, подсчёт числа слов ==
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <tex>paths(v)</tex>, задающую число различных путей из <tex>s</tex> в <tex>v</tex>; <tex>paths(s) = 1</tex>. Заметим, что если известны значения <tex>paths(u)</tex> для всех <tex>u</tex>, из которых существует переход в <tex>v</tex>, то <tex>paths(v) = \sum\limits_{u}paths(u)</tex>. Количеством слов в языке будет сумма <tex>paths(t)</tex> для всех допускающих <tex>t</tex>.
Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они были разделены.
==== Псевдокод ====
