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

Для различных операций с регулярными языками полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт эквивалентности автоматных и регулярных языков.

Пустота регулярного языка

Определение:

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

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

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

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

[math]\triangleright[/math]

[math]\Rightarrow[/math] Пусть язык содержит слово [math]w[/math]. Любой детерминированный конечный автомат [math]A[/math], задающий этот язык, должен допускать [math]w[/math]. Тогда при переходе из стартового состояния [math]A[/math] по символам [math]w[/math] получится путь, оканчивающийся в одном из терминальных состояний. [math]\Leftarrow[/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}[/math] из [math]A_{1}[/math] и [math]p_{2}[/math] из [math]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]t_{1}[/math], [math]t_{2}[/math] — допускающие состояния, [math]u_{1}[/math], [math]u_{2}[/math] — недопускающие.

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

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

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

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

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

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

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

[math]\triangleright[/math]

Пусть такой пары не существует. Возьмём произвольное слово [math]w[/math] длины [math]n[/math] и выпишем последовательность пар состояний [math]\langle v_{i}, u_{i} \rangle[/math]: [math]v_{0} = s_{1}, u_{0} = s_{2}[/math] и [math]\forall i = 1 .. n[/math] справедливо [math]\delta_{1} (v_{i-1}, w[i-1]) = v_{i}, \delta_{2} (u_{i-1}, w[i-1]) = u_{i}[/math]. Так как пара [math]\langle v_{0}, u_{0} \rangle[/math] была в очереди, каждая из последующих пар в процессе алгоритма также побывала в очереди, значит, [math]eq[/math] для них возвращает [math]true[/math]. По предположению, или оба состояния [math]\langle v_{n}, u_{n} \rangle[/math] допускающие в своих автоматах, или оба недопускающие. Таким образом, строка [math]w[/math] или входит в оба языка, или не входит ни в один. Пусть такая пара [math]\langle v, u \rangle[/math] существует. Для определённости скажем, что [math]v \in A_{1}[/math] — допускающее. Рассмотрим строку [math]w[/math], состоящую из символов, в результате переходов по которым из [math]\langle s_{1}, s_{2} \rangle[/math] в процессе обхода в ширину [math]eq(v, u)[/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], для которого выполняются три условия: [math]v[/math] достижимо из стартового состояния [math]s[/math]; из [math]v[/math] достижимо какое-либо из допускающих состояний; из [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 if and only if 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

Литература

• Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. / Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177: ISBN 5-8459-0261-4 (рус.)