Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов) — различия между версиями
Shevchen (обсуждение | вклад) м |
Shevchen (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
== Пустота == | == Пустота == | ||
− | + | [[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] является '''пустым''', если он не содержит ни одного слова. Язык, содержащий хотя бы одно слово, назовём '''непустым'''. | |
{{Утверждение | {{Утверждение | ||
Строка 7: | Строка 7: | ||
regEmpty | regEmpty | ||
|statement= | |statement= | ||
− | Регулярный язык является непустым тогда и только тогда, когда в любом | + | Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных. |
|proof= | |proof= | ||
− | Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, | + | Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин. |
Строка 20: | Строка 20: | ||
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина. | Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина. | ||
− | boolean dfs(State v) | + | ==== Псевдокод ==== |
− | v.seen = true | + | |
− | if | + | boolean dfs(State v): |
− | return false | + | v.seen = true |
− | + | if v.isFinal: | |
− | for | + | return false |
− | if | + | for each State u in v.next: |
− | return false | + | if !u.seen && !dfs(u): |
− | + | return false | |
− | + | return true | |
− | return true | + | |
− | + | boolean isEmpty(Automaton a): | |
− | + | for each State v in a: | |
− | boolean isEmpty(Automaton a) | + | v.seen = false |
− | for | + | return dfs(a.start) |
− | v.seen = false | ||
− | |||
− | return dfs(a.start) | ||
− | |||
== Совпадение == | == Совпадение == | ||
− | + | Два [[Регулярные языки: два определения и их эквивалентность|регулярных языка]] '''совпадают''', если любое слово или содержится в обоих языках, или не содержится ни в одном из них. | |
− | Пусть <tex>A_{1}</tex> и <tex>A_{2}</tex> - детерминированные конечные автоматы, соответствующие языкам <tex>L_{1}</tex> и <tex>L_{2}</tex> над одним алфавитом <tex>\Sigma</tex>, соответственно. Совпадение языков на языке конечных автоматов (''эквивалентность'') означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния <tex>p_{1} \in A_{1}</tex> и <tex>p_{2} \in A_{2}</tex> ''' | + | Пусть <tex>A_{1}</tex> и <tex>A_{2}</tex> - детерминированные конечные автоматы, соответствующие языкам <tex>L_{1}</tex> и <tex>L_{2}</tex> над одним алфавитом <tex>\Sigma</tex>, соответственно. Совпадение языков на языке конечных автоматов (''эквивалентность'') означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния <tex>p_{1} \in A_{1}</tex> и <tex>p_{2} \in A_{2}</tex> '''различимыми''', если существует строка <tex>w</tex> из символов <tex>\Sigma</tex>, для которой выполняется |
− | <tex>\langle | + | <tex>\langle p_{1}, w \rangle \rightarrow \langle t_{1}, \epsilon \rangle</tex>, <tex>\langle p_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle</tex> |
− | + | или | |
− | + | <tex>\langle p_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle</tex>, <tex>\langle p_{2}, w \rangle \rightarrow \langle t_{2}, \epsilon \rangle</tex>, | |
− | + | где <tex>s_{1}</tex>, <tex>s_{2}</tex> - стартовые состояния, <tex>t_{1}</tex>, <tex>t_{2}</tex> - допускающие состояния, <tex>u_{1}</tex>, <tex>u_{2}</tex> - недопускающие. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Все ''бесполезные'' состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут. Введём ''сток'' - специальное недопускающее состояние, переходы по всем символам из которого ведут в него самого. Все переходы исходного автомата, которые отсутствовали или вели в бесполезные состояния, направим в сток. | |
− | |||
− | |||
− | + | === Алгоритм проверки языков на совпадение === | |
− | + | Первым шагом алгоритма является избавление автоматов от состояний, из которых недостижимы допускающие. Проще всего это реализовать обходом [[Обход в глубину, цвета вершин|в глубину]] или [[Обход в ширину|в ширину]] из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов, вместо них вводится описанный выше сток. | |
− | Пусть в | + | Пусть <tex>eq(u, v)</tex> - функция, принимающая пару состояний из первого и второго автоматов и возвращающая некоторое значение булевского типа. Второй шаг алгоритма - установка <tex>eq(u, v)</tex> в <tex>false</tex> для всех пар <tex>\langle u, v \rangle</tex>, кроме <tex>\langle s_{1}, s_{2} \rangle</tex>. Также создаётся очередь, в которую помещается пара <tex>\langle s_{1}, s_{2} \rangle</tex>. |
− | |||
− | <tex>\langle | + | Третий шаг алгоритма - [[Обход в ширину|обход в ширину]]. Пусть на текущем шаге из очереди получена пара <tex>\langle u \in A_{1}, v \in A_{2} \rangle</tex>. Тогда для всех символов <tex>c \in \Sigma</tex> рассматриваются пары <tex>\langle u', v' \rangle : \delta_{1} (u, c) = u', \delta_{2} (v, c) = v'</tex>. Если <tex>eq(u', v')</tex> возвращает <tex>false</tex>, данное значение устанавливается в <tex>true</tex>, а в очередь добавляется пара <tex>\langle u', v' \rangle</tex>. |
− | |||
− | |||
{{Утверждение | {{Утверждение | ||
|id= | |id= | ||
− | + | regEqual | |
|statement= | |statement= | ||
− | + | Автоматы <tex>A_{1}</tex> и <tex>A_{2}</tex> эквивалентны тогда и только тогда, когда после окончания работы алгоритма не существует такой пары <tex>\langle u, v \rangle</tex>, что <tex>eq(u, v)</tex> возвращает <tex>true</tex> и ровно одно из <tex>\langle u, v \rangle</tex> допускающее. | |
|proof= | |proof= | ||
− | + | Пусть такой пары не существует. Возьмём произвольное слово <tex>w</tex> длины <tex>n</tex> и выпишем последовательность пар состояний <tex>\langle u_{i}, v_{i} \rangle</tex>: | |
− | + | ||
+ | <tex>u_{0} = s_{1}, v_{0} = s_{2}</tex> и <tex>\forall i = 1 .. n</tex> справедливо <tex>\delta_{1} (u_{i-1}, s[i-1]) = u_{i}, \delta_{2} (v_{i-1}, s[i-1]) = v_{i}</tex>. Так как пара <tex>\langle u_{0}, v_{0} \rangle</tex> была в очереди, каждая из последующих пар в процессе алгоритма также побывала в очереди, значит, <tex>eq</tex> для них возвращает <tex>true</tex>. По предположению, или оба состояния <tex>\langle u_{n}, v_{n} \rangle</tex> допускающие в своих автоматах, или оба недопускающие. Таким образом, строка <tex>w</tex> или входит в оба языка, или не входит ни в один. | ||
− | |||
− | + | Пусть такая пара <tex>\langle u, v \rangle</tex> существует. Для определённости скажем, что <tex>u \in A_{1}</tex> - допускающее. Рассмотрим строку <tex>w</tex>, состоящую из символов, в результате переходов по которым из <tex>\langle s_{1}, s_{2} \rangle</tex> в процессе обхода в ширину <tex>eq(u, v)</tex> было установлено в <tex>true</tex>. Строка <tex>w</tex> допускается первым автоматом, но не допускается вторым, значит, те не эквивалентны. | |
+ | }} | ||
− | + | ==== Псевдокод ==== | |
− | + | 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 |
Версия 06:36, 26 октября 2011
Содержание
Пустота
Регулярный язык является пустым, если он не содержит ни одного слова. Язык, содержащий хотя бы одно слово, назовём непустым.
Утверждение: |
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных. |
Пусть язык содержит слово . Любой автомат , задающий этот язык, должен допускать . Тогда при переходе из стартового состояния по символам получится путь, оканчивающийся в одной из терминальных вершин.
|
Алгоритм проверки языка на пустоту
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
Псевдокод
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