Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)
Пустота
Регулярный язык является пустым, если он не содержит ни одного слова. Язык, содержащий хотя бы одно слово, назовём непустым.
Утверждение: |
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных. |
Пусть язык содержит слово . Любой автомат , задающий этот язык, должен допускать . Тогда при переходе из стартового состояния по символам получится путь, оканчивающийся в одной из терминальных вершин.
|
Алгоритм проверки языка на пустоту
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
Псевдокод
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 revDfs(State v): v.seen = true for each State u in v.prev: if !u.seen: revDfs(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.seen: v = sink
void bfs(Automaton a, Automaton b) eq = new bool[a.statesNumber][b.statesNumber] 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.seen = false for each State v in a: if v.isFinal: revDfs(v) setSink(a) for each State v in b: v.seen = false for each State v in b: if v.isFinal: revDfs(v) setSink(b) bfs(a, b) for each State v in a: for each State u in b: if eq[v][u] && v.isFinal != u.isFinal: return false return true