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

Пустота

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

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

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

[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 revDfs(State v):
  v.seen = true
  for each State u in v.prev:
    if !u.seen:
      revDfs(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.seen:
      v = sink

void bfs(Automaton a, 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, 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.seen = false
  for each State v in a:
    if v.isFinal:
      revDfs(v)
  setSink(a)
  for each State v in b:
    v.seen = false
  for each State v in b:
    if v.isFinal:
      revDfs(v)
  setSink(b)
  bfs(a, 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