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

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

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

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

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

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

Теорема:

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

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

[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]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 (рус.)