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

Пустота

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

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

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

[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! (n-1)^{| \Sigma |}[/math], где [math]n[/math] - количество состояний автомата: [math]n![/math] - количество перестановок состояний, [math](n-1)^{| \Sigma |}[/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