Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 16: Строка 16:
  
 
|proof=
 
|proof=
Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин.
+
Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одном из терминальных состояний.
  
  
Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на рёбрах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
+
Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
 
}}
 
}}
  
Строка 51: Строка 51:
 
}}
 
}}
  
Пусть <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>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 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 t_{1}, \epsilon \rangle</tex>, <tex>\langle p_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle</tex>
Строка 59: Строка 59:
 
<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>\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>s_{1}</tex>, <tex>s_{2}</tex> - стартовые состояния, <tex>t_{1}</tex>, <tex>t_{2}</tex> - допускающие состояния, <tex>u_{1}</tex>, <tex>u_{2}</tex> - недопускающие.
+
где <tex>s_{1}</tex>, <tex>s_{2}</tex> стартовые состояния, <tex>t_{1}</tex>, <tex>t_{2}</tex> допускающие состояния, <tex>u_{1}</tex>, <tex>u_{2}</tex> недопускающие.
  
Все ''бесполезные'' состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут. Введём ''сток'' - специальное недопускающее состояние, переходы по всем символам из которого ведут в него самого. Все переходы исходного автомата, которые отсутствовали или вели в бесполезные состояния, направим в сток.
+
Все состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами; назовём их '''бесполезными'''. Введём '''сток''' — специальное недопускающее состояние, переходы по всем символам из которого ведут в него самого. Все переходы исходного автомата, которые отсутствовали или вели в бесполезные состояния, направим в сток.
  
  
Строка 69: Строка 69:
  
  
Пусть <tex>eq(u, v)</tex> - функция, принимающая пару состояний из первого и второго автоматов и возвращающая некоторое значение булевского типа. Второй шаг алгоритма - установка <tex>eq(u, v)</tex> в <tex>false</tex> для всех пар <tex>\langle u, v \rangle</tex>, кроме <tex>\langle s_{1}, s_{2} \rangle</tex>. Также создаётся очередь, в которую помещается пара <tex>\langle s_{1}, s_{2} \rangle</tex>.
+
Пусть <tex>eq(u, v)</tex> функция, принимающая пару состояний из первого и второго автоматов и возвращающая некоторое значение булевского типа. Второй шаг алгоритма установка <tex>eq(u, v)</tex> в <tex>false</tex> для всех пар <tex>\langle u, v \rangle</tex>, кроме <tex>\langle s_{1}, s_{2} \rangle</tex>. Также создаётся очередь, в которую помещается пара <tex>\langle s_{1}, s_{2} \rangle</tex>.
  
  
Третий шаг алгоритма - [[Обход в ширину|обход в ширину]]. Пусть на текущем шаге из очереди получена пара <tex>\langle u \in A_{1}, v \in A_{2} \rangle</tex>. Тогда для всех символов <tex>c \in \Sigma</tex> рассматриваются пары <tex>\langle u', v' \rangle : \delta_{1} (u, c) = u', \delta_{2} (v, c) = v'</tex>. Если <tex>eq(u', v')</tex> возвращает <tex>false</tex>, данное значение устанавливается в <tex>true</tex>, а в очередь добавляется пара <tex>\langle u', v' \rangle</tex>.
+
Третий шаг алгоритма [[Обход в ширину|обход в ширину]]. Пусть на текущем шаге из очереди получена пара <tex>\langle u \in A_{1}, v \in A_{2} \rangle</tex>. Тогда для всех символов <tex>c \in \Sigma</tex> рассматриваются пары <tex>\langle u', v' \rangle : \delta_{1} (u, c) = u', \delta_{2} (v, c) = v'</tex>. Если <tex>eq(u', v')</tex> возвращает <tex>false</tex>, данное значение устанавливается в <tex>true</tex>, а в очередь добавляется пара <tex>\langle u', v' \rangle</tex>.
  
  
Строка 87: Строка 87:
  
  
Пусть такая пара <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> допускается первым автоматом, но не допускается вторым, значит, автоматы не эквивалентны.
+
Пусть такая пара <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> допускается первым автоматом, но не допускается вторым, значит, автоматы не эквивалентны.
 
}}
 
}}
  
Строка 152: Строка 152:
 
=== Алгоритм проверки на включение ===
 
=== Алгоритм проверки на включение ===
  
Алгоритм проверки <tex>L_{1}</tex> на включение в <tex>L_{2}</tex> идентичен алгоритму проверки их совпадения, кроме одной особенности. Могут существовать слова из <tex>L_{2}</tex>, не входящие в <tex>L_{1}</tex>, поэтому существование пар <tex>\langle v \in L_{1}, u \in L_{2} \rangle : eq(v, u) == true, v \notin T_{1}, u \in T_{2}</tex>, где <tex>T_{i}</tex> - множества допускающих состояний, не нарушает факт вхождения <tex>L_{1}</tex> в <tex>L_{2}</tex>. Таким образом, <tex>L_{1}</tex> не входит в <tex>L_{2}</tex> тогда и только тогда, когда после окончания работы алгоритма, идентичного алгоритму проверки на совпадение, не существует такой пары <tex>\langle v, u \rangle</tex>, что <tex>eq(v, u)</tex> возвращает <tex>true</tex>, <tex>v \in T_{1}, u \notin T_{2}</tex>.
+
Алгоритм проверки <tex>L_{1}</tex> на включение в <tex>L_{2}</tex> идентичен алгоритму проверки их совпадения, кроме одной особенности. Могут существовать слова из <tex>L_{2}</tex>, не входящие в <tex>L_{1}</tex>, поэтому существование пар <tex>\langle v \in L_{1}, u \in L_{2} \rangle : eq(v, u) == true, v \notin T_{1}, u \in T_{2}</tex>, где <tex>T_{i}</tex> множества допускающих состояний, не нарушает факт вхождения <tex>L_{1}</tex> в <tex>L_{2}</tex>. Таким образом, <tex>L_{1}</tex> не входит в <tex>L_{2}</tex> тогда и только тогда, когда после окончания работы алгоритма, идентичного алгоритму проверки на совпадение, не существует такой пары <tex>\langle v, u \rangle</tex>, что <tex>eq(v, u)</tex> возвращает <tex>true</tex>, <tex>v \in T_{1}, u \notin T_{2}</tex>.
  
 
==== Псевдокод ====
 
==== Псевдокод ====
Строка 219: Строка 219:
 
Автомат <tex>A_{1}</tex> задаёт конечный язык тогда и только тогда, когда в <tex>A_{1}</tex> не существует состояния <tex>v</tex>, для которого выполняются три условия:
 
Автомат <tex>A_{1}</tex> задаёт конечный язык тогда и только тогда, когда в <tex>A_{1}</tex> не существует состояния <tex>v</tex>, для которого выполняются три условия:
 
1) <tex>v</tex> достижимо из стартового состояния <tex>s</tex>;
 
1) <tex>v</tex> достижимо из стартового состояния <tex>s</tex>;
 +
 
2) из <tex>v</tex> достижимо какое-либо из допускающих состояний;
 
2) из <tex>v</tex> достижимо какое-либо из допускающих состояний;
 +
 
3) из <tex>v</tex> по одному или более переходам достижимо <tex>v</tex>.
 
3) из <tex>v</tex> по одному или более переходам достижимо <tex>v</tex>.
  
 
|proof=
 
|proof=
Пусть такое состояние <tex>v</tex> существует, а строки <tex>x, y, z</tex> таковы, что <tex>\langle s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{*} \langle v, z \rangle \vdash ^{*} \langle t, \epsilon \rangle</tex>, <tex>t</tex> - допускающее, <tex>y</tex> - непустая. Рассмотрим строки вида <tex>xy^{k}z, k \in \mathbb{N}</tex>. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
+
Пусть такое состояние <tex>v</tex> существует, а строки <tex>x, y, z</tex> таковы, что <tex>\langle s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{*} \langle v, z \rangle \vdash ^{*} \langle t, \epsilon \rangle</tex>, <tex>t</tex> допускающее, <tex>y</tex> непустая. Рассмотрим строки вида <tex>xy^{k}z, k \in \mathbb{N}</tex>. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
  
  
Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено <tex>n! (n-1)^{| \Sigma |}</tex>, где <tex>n</tex> - количество состояний автомата: <tex>n!</tex> - количество перестановок состояний, <tex>(n-1)^{| \Sigma |}</tex> - количество совокупностей переходов по символам между ними. Таким образом, язык конечен.
+
Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено <tex>n! | \Sigma |^{n-1}</tex>, где <tex>n</tex> количество состояний автомата: <tex>n!</tex> количество перестановок состояний, <tex>| \Sigma |^{n-1}</tex> количество совокупностей переходов по символам между ними. Таким образом, язык конечен.
 
}}
 
}}
  
 
=== Алгоритм нахождения числа слов в языке ===
 
=== Алгоритм нахождения числа слов в языке ===
  
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим ''полезные'' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <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>.
+
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <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>.
  
 
Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они были разделены.
 
Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они были разделены.

Версия 08:17, 28 октября 2011

Пустота

Определение:
Регулярный язык называется пустым, если он не содержит ни одного слова.


Язык, содержащий хотя бы одно слово, назовём непустым.

Утверждение:
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.
[math]\triangleright[/math]

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


Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
[math]\triangleleft[/math]

Алгоритм проверки языка на пустоту

Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.

Псевдокод

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)


Совпадение

Определение:
Два регулярных языка совпадают, если любое слово или содержится в обоих языках, или не содержится ни в одном из них.


Пусть [math]A_{1}[/math] и [math]A_{2}[/math] — детерминированные конечные автоматы, соответствующие языкам [math]L_{1}[/math] и [math]L_{2}[/math] над одним алфавитом [math]\Sigma[/math], соответственно. Совпадение языков на языке конечных автоматов (эквивалентность) означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния [math]p_{1} \in A_{1}[/math] и [math]p_{2} \in A_{2}[/math] различимыми, если существует строка [math]w[/math] из символов [math]\Sigma[/math], для которой выполняется

[math]\langle p_{1}, w \rangle \rightarrow \langle t_{1}, \epsilon \rangle[/math], [math]\langle p_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle[/math]

или

[math]\langle p_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle[/math], [math]\langle p_{2}, w \rangle \rightarrow \langle t_{2}, \epsilon \rangle[/math],

где [math]s_{1}[/math], [math]s_{2}[/math] — стартовые состояния, [math]t_{1}[/math], [math]t_{2}[/math] — допускающие состояния, [math]u_{1}[/math], [math]u_{2}[/math] — недопускающие.

Все состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами; назовём их бесполезными. Введём сток — специальное недопускающее состояние, переходы по всем символам из которого ведут в него самого. Все переходы исходного автомата, которые отсутствовали или вели в бесполезные состояния, направим в сток.


Алгоритм проверки языков на совпадение

Первым шагом алгоритма является избавление автоматов от состояний, из которых недостижимы допускающие. Проще всего это реализовать обходом в глубину или в ширину из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов, вместо них вводится описанный выше сток.


Пусть [math]eq(u, v)[/math] — функция, принимающая пару состояний из первого и второго автоматов и возвращающая некоторое значение булевского типа. Второй шаг алгоритма — установка [math]eq(u, v)[/math] в [math]false[/math] для всех пар [math]\langle u, v \rangle[/math], кроме [math]\langle s_{1}, s_{2} \rangle[/math]. Также создаётся очередь, в которую помещается пара [math]\langle s_{1}, s_{2} \rangle[/math].


Третий шаг алгоритма — обход в ширину. Пусть на текущем шаге из очереди получена пара [math]\langle u \in A_{1}, v \in A_{2} \rangle[/math]. Тогда для всех символов [math]c \in \Sigma[/math] рассматриваются пары [math]\langle u', v' \rangle : \delta_{1} (u, c) = u', \delta_{2} (v, c) = v'[/math]. Если [math]eq(u', v')[/math] возвращает [math]false[/math], данное значение устанавливается в [math]true[/math], а в очередь добавляется пара [math]\langle u', v' \rangle[/math].


Утверждение:
Автоматы [math]A_{1}[/math] и [math]A_{2}[/math] эквивалентны тогда и только тогда, когда после окончания работы алгоритма не существует такой пары [math]\langle u, v \rangle[/math], что [math]eq(u, v)[/math] возвращает [math]true[/math] и ровно одно из [math]\langle u, v \rangle[/math] допускающее.
[math]\triangleright[/math]

Пусть такой пары не существует. Возьмём произвольное слово [math]w[/math] длины [math]n[/math] и выпишем последовательность пар состояний [math]\langle u_{i}, v_{i} \rangle[/math]:

[math]u_{0} = s_{1}, v_{0} = s_{2}[/math] и [math]\forall i = 1 .. n[/math] справедливо [math]\delta_{1} (u_{i-1}, s[i-1]) = u_{i}, \delta_{2} (v_{i-1}, s[i-1]) = v_{i}[/math]. Так как пара [math]\langle u_{0}, v_{0} \rangle[/math] была в очереди, каждая из последующих пар в процессе алгоритма также побывала в очереди, значит, [math]eq[/math] для них возвращает [math]true[/math]. По предположению, или оба состояния [math]\langle u_{n}, v_{n} \rangle[/math] допускающие в своих автоматах, или оба недопускающие. Таким образом, строка [math]w[/math] или входит в оба языка, или не входит ни в один.


Пусть такая пара [math]\langle u, v \rangle[/math] существует. Для определённости скажем, что [math]u \in A_{1}[/math] — допускающее. Рассмотрим строку [math]w[/math], состоящую из символов, в результате переходов по которым из [math]\langle s_{1}, s_{2} \rangle[/math] в процессе обхода в ширину [math]eq(u, v)[/math] было установлено в [math]true[/math]. Строка [math]w[/math] допускается первым автоматом, но не допускается вторым, значит, автоматы не эквивалентны.
[math]\triangleleft[/math]

Псевдокод

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


Включение

Определение:
Регулярный язык [math]L_{1}[/math] входит (включается) в регулярный язык [math]L_{2}[/math], если любое слово, принадлежащее [math]L_{1}[/math], принадлежит [math]L_{2}[/math].


Алгоритм проверки на включение

Алгоритм проверки [math]L_{1}[/math] на включение в [math]L_{2}[/math] идентичен алгоритму проверки их совпадения, кроме одной особенности. Могут существовать слова из [math]L_{2}[/math], не входящие в [math]L_{1}[/math], поэтому существование пар [math]\langle v \in L_{1}, u \in L_{2} \rangle : eq(v, u) == true, v \notin T_{1}, u \in T_{2}[/math], где [math]T_{i}[/math] — множества допускающих состояний, не нарушает факт вхождения [math]L_{1}[/math] в [math]L_{2}[/math]. Таким образом, [math]L_{1}[/math] не входит в [math]L_{2}[/math] тогда и только тогда, когда после окончания работы алгоритма, идентичного алгоритму проверки на совпадение, не существует такой пары [math]\langle v, u \rangle[/math], что [math]eq(v, u)[/math] возвращает [math]true[/math], [math]v \in T_{1}, u \notin T_{2}[/math].

Псевдокод

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

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

Определение:
Регулярный язык называется конечным, если принадлежащее ему множество слов конечно.


Утверждение:
Автомат [math]A_{1}[/math] задаёт конечный язык тогда и только тогда, когда в [math]A_{1}[/math] не существует состояния [math]v[/math], для которого выполняются три условия:

1) [math]v[/math] достижимо из стартового состояния [math]s[/math];

2) из [math]v[/math] достижимо какое-либо из допускающих состояний;

3) из [math]v[/math] по одному или более переходам достижимо [math]v[/math].
[math]\triangleright[/math]

Пусть такое состояние [math]v[/math] существует, а строки [math]x, y, z[/math] таковы, что [math]\langle s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{*} \langle v, z \rangle \vdash ^{*} \langle t, \epsilon \rangle[/math], [math]t[/math] — допускающее, [math]y[/math] — непустая. Рассмотрим строки вида [math]xy^{k}z, k \in \mathbb{N}[/math]. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.


Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено [math]n! | \Sigma |^{n-1}[/math], где [math]n[/math] — количество состояний автомата: [math]n![/math] — количество перестановок состояний, [math]| \Sigma |^{n-1}[/math] — количество совокупностей переходов по символам между ними. Таким образом, язык конечен.
[math]\triangleleft[/math]

Алгоритм нахождения числа слов в языке

Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью обхода в глубину по обратным рёбрам определим полезные состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат топологически. Введём функцию [math]paths(v)[/math], задающую число различных путей из [math]s[/math] в [math]v[/math]; [math]paths(s) = 1[/math]. Заметим, что если известны значения [math]paths(u)[/math] для всех [math]u[/math], из которых существует переход в [math]v[/math], то [math]paths(v) = \sum\limits_{u}paths(u)[/math]. Количеством слов в языке будет сумма [math]paths(t)[/math] для всех допускающих [math]t[/math].

Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они были разделены.

Псевдокод

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