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

Пустота

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

Утверждение:

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

[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 (State u : v.next) {
     if (!u.seen && !dfs(u)) {
       return false;
     }
  }
  return true;
}

boolean isEmpty(Automaton a) {
  for (State v : 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 s_{1}, w \rangle \rightarrow \langle p_{1}, \epsilon \rangle[/math],

[math]\langle s_{2}, w \rangle \rightarrow \langle p_{2}, \epsilon \rangle[/math],

где [math]s_{1}[/math], [math]s_{2}[/math] - стартовые состояния.

На основе заданного отношения разобьём состояния автоматов на классы эквивалентности: состояния [math]p[/math] и [math]q[/math] принадлежат одному классу тогда и только тогда, когда существует последовательность состояний [math]p_{0}...p_{k}[/math], где [math]p = p_{0}[/math], [math]q = p_{k}[/math] и [math]\forall i = 1..k[/math] [math]p_{i - 1}[/math] идентично [math]p_{i}[/math]. Все состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут.

Теорема:

Автоматы [math]A_{1}[/math] и [math]A_{2}[/math] эквивалентны тогда и только тогда, когда в любом классе содержатся или только допускающие, или только недопускающие состояния.

Доказательство:

[math]\triangleright[/math]

Пусть в каком-либо классе содержатся допускающее состояние [math]t[/math] и недопускающее [math]u[/math]. По построению классов эквивалентности, существует последовательность [math]p_{0}...p_{k}[/math], где [math]t = p_{0}[/math], [math]u = p_{k}[/math] и [math]\forall i = 1..k[/math] [math]p_{i - 1}[/math] идентично [math]p_{i}[/math]. Тогда найдётся пара [math]p_{j}[/math], [math]p_{j+1}[/math]: [math]p_{j}[/math] является допускающим, а [math]p_{j+1}[/math] - нет. Для определённости, пусть [math]p_{j}[/math] принадлежит первому автомату, а [math]p_{j+1}[/math] - второму. Так как эти состояния идентичны, [math]\exists w[/math]: [math]\langle s_{1}, w \rangle \rightarrow \langle p_{j}, \epsilon \rangle[/math], [math]\langle s_{2}, w \rangle \rightarrow \langle p_{j+1}, \epsilon \rangle[/math]. Таким образом, слово [math]w[/math] допускается первым автоматом и не допускается вторым, значит, автоматы неэквивалентны. Пусть в любом классе содержатся только допускающие или только недопускающие состояния. Рассмотрим любую строку [math]w[/math] и такие состояния [math]u_{1}[/math] и [math]u_{2}[/math], что [math]\langle s_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle[/math], [math]\langle s_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle[/math]. Состояния [math]u_{1}[/math] и [math]u_{2}[/math] идентичны, следовательно, принадлежат одному классу эквивалентности. Таким образом, любая строка оканчивается либо допускающими состояниями в обоих автоматах, либо в обоих не допускается, значит, автоматы эквивалентны.

[math]\triangleleft[/math]

Утверждение:

Если состояния [math]p[/math] и [math]q[/math] принадлежат одному классу эквивалентности, то для любого символа [math]c[/math] из алфавита [math]\delta (p, c)[/math] и [math]\delta (q, c)[/math] также принадлежат одному классу.

[math]\triangleright[/math]

Рассмотрим последовательность [math]p_{0}...p_{k}[/math], где [math]p = p_{0}[/math], [math]q = p_{k}[/math] и [math]\forall i = 1..k[/math] [math]p_{i - 1}[/math] идентично [math]p_{i}[/math] по строке [math]w_{i}[/math]. Тогда для последовательности [math]p'_{0}...p'_{k}[/math], где [math]\delta (p, c) = p'_{0}[/math], [math]\delta (q, c) = p_{k}[/math] будет верно: [math]\forall i = 1..k[/math] [math]p'_{i - 1}[/math] идентично [math]p'_{i}[/math] по строке [math]w_{i}c[/math]. Таким образом, [math]\delta (p, c)[/math] и [math]\delta (q, c)[/math] также принадлежат одному классу.

[math]\triangleleft[/math]

По индукции, утверждение верно и для большего числа переходов.

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

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

Второй шаг - обход в ширину, объединяющий классы эквивалентности. Изначально каждое состояние принадлежит отдельному классу, кроме двух стартовых, объединённых в один класс. Для определения класса по состоянию используется система непересекающихся множеств. Очередь обхода в ширину хранит пары состояний [math]p_{1} \in A_{1}[/math], [math]p_{2} \in A_{2}[/math], для которых существует строка [math]w[/math] (для [math]s_{1}[/math] и [math]s_{2}[/math] равная [math]\epsilon[/math]):

[math]\langle s_{1}, w \rangle \rightarrow \langle p_{1}, \epsilon \rangle[/math],

[math]\langle s_{2}, w \rangle \rightarrow \langle p_{2}, \epsilon \rangle[/math].

Для пары состояний изучаются переходы из них по всем символам алфавита. Пусть [math]\delta (p_{1}, c) = q_{1}[/math], [math]\delta (p_{2}, c) = q_{2}[/math]. Если [math]q_{1}[/math] и [math]q_{2}[/math] принадлежат разным классам, их классы объединяются, а пара [math]\langle q_{1}, q_{2} \rangle[/math] добавляется в очередь.