Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)
Для различных операций с регулярными языками полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт эквивалентности автоматных и регулярных языков.
Содержание
Пустота регулярного языка
Определение: |
Регулярный язык называется пустым, если он не содержит ни одного слова. |
Язык, содержащий хотя бы одно слово, назовём непустым.
Теорема: |
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных. |
Доказательство: |
Пусть язык содержит слово детерминированный конечный автомат , задающий этот язык, должен допускать . Тогда при переходе из стартового состояния по символам получится путь, оканчивающийся в одном из терминальных состояний. . ЛюбойПусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку. |
Алгоритм проверки языка на пустоту
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
Псевдокод
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)
Совпадение регулярных языков
Определение: |
Два регулярных языка совпадают, если любое слово или содержится в обоих языках, или не содержится ни в одном из них. |
Для проверки совпадения языков достаточно запустить алгоритм проверки эквивалентности задающих их автоматов.
Включение одного регулярного языка в другой
Определение: |
Регулярный язык входит (включается) в регулярный язык , если любое слово, принадлежащее , принадлежит . |
Пусть автомат задаёт язык , а автомат — язык . Для проверки включения в достаточно проверить эквивалентность и .
Конечность регулярного языка, подсчёт числа слов
Определение: |
Регулярный язык называется конечным, если принадлежащее ему множество слов конечно. |
Теорема: |
Детерминированный конечный автомат задаёт конечный язык тогда и только тогда, когда в не существует состояния , для которого выполняются три условия:
|
Доказательство: |
Пусть такое состояние существует, а строки таковы, что , — допускающее, — непустая. Рассмотрим строки вида . Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
|
Алгоритм нахождения числа слов в языке
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью обхода в глубину по обратным рёбрам определим полезные состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат топологически. Введём функцию , задающую число различных путей из в ; . Заметим, что если известны значения для всех , из которых существует переход в , то . Количеством слов в языке будет сумма для всех допускающих .
Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они разделены.
Псевдокод
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 (рус.)