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