105
правок
Изменения
м
== Пустота ==Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]] языков.
[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] является '''пустым''', если он не содержит ни одного слова. Язык, содержащий хотя бы одно слово, назовём '''непустым'''.== Пустота регулярного языка ==
Пусть язык содержит слово <tex>w\Rightarrow</tex>. Любой автомат <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин.
boolean dfs(State v):{{Определение v.seen |id= trueequal if v.isFinal:|definition= return false for each State u in v.nextДва [[Регулярные языки: if !uдва определения и их эквивалентность|регулярных языка]] '''совпадают''' (англ.seen && !dfs(u''coincide''): return false, если любое слово или содержится в обоих языках, или не содержится ни в одном из них. return true}}
boolean isEmpty(Automaton a): for each State v in a: vДля проверки совпадения языков достаточно запустить алгоритм проверки [[Эквивалентность_состояний_ДКА|эквивалентности]] задающих их автоматов.seen = false return dfs(a.start)
Два {{Определение|id=inclusion|definition=[[Регулярные языки: два определения и их эквивалентность|регулярных языкаРегулярный язык]] <tex>L_{1}</tex> '''входит (включается)''совпадают'(англ. ''included'') в регулярный язык <tex>L_{2}</tex>, если любое слово или содержится в обоих языках, или не содержится ни в одном из нихпринадлежащее <tex>L_{1}</tex>, принадлежит <tex>L_{2}</tex>.}}
<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 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>. {{УтверждениеТеорема
regEqualregFinite
Автоматы [[Детерминированные конечные автоматы|Детерминированный конечный автомат]] <tex>A_{1}</tex> задаёт конечный язык тогда и только тогда, когда в <tex>A_{21}</tex> эквивалентны тогда и только тогда, когда после окончания работы алгоритма не существует такой пары состояния <tex>\langle u, v \rangle</tex>, что для которого выполняются три условия:* <tex>eq(u, v)</tex> возвращает достижимо из стартового состояния <tex>trues</tex> и ровно одно ;* из <tex>v</tex> достижимо какое-либо из допускающих состояний;* из <tex>\langle u, v \rangle</tex> допускающеепо одному или более переходам достижимо <tex>v</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 !q2-е изд.isEmpty: (v, u) = qПер.remove() for each symbol c in aс англ.alphabet— Москва: // a.alphabet == b.alphabet v' = vИздательский дом «Вильямс», 2002.next(c) u' = u— с.next(c) if !eq[v'][u']: eq[v'][u'] = true q.add((v', u'))169-177 — ISBN 5-8459-0261-4
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
Дмитрий Мурзин переименовал страницу Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)…
{{УтверждениеОпределение|id=empty|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''пустым''' (англ. ''empty''), если он не содержит ни одного слова.}} {{Определение|id=nonempty|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] содержащий хотя бы одно слово, называется '''непустым''' (англ. ''nonempty'').}} {{Теорема
|id=
regEmpty
|proof=
:Пусть язык содержит слово <tex>w</tex>. Любой [[Детерминированные конечные автоматы| детерминированный конечный автомат]] <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одном из терминальных состояний.
<tex>\Leftarrow</tex>:Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на рёбрахпереходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
}}
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
==== Псевдокод ==Совпадение регулярных языков ==
=== Пример проверки на совпадение регулярных языков===
Для того, чтобы узнать равен ли язык своему замыканию Клини, нужно проверить на [[Эквивалентность_состояний_ДКА|эквивалентность]] автомат, задающий язык, и автомат, задающий замыкание Клини языка. Если автоматы эквивалентны, то язык равен своему замыканию Клини.
== Совпадение Включение одного регулярного языка в другой ==
Пусть автомат <tex>A_{1}M_1</tex> и задаёт язык <tex>A_{2}L_1</tex> - детерминированные конечные автоматы, соответствующие языкам а автомат <tex>L_{1}M_2</tex> и <tex>L_{2}</tex> над одним алфавитом — язык <tex>L_1 \Sigmacap L_2</tex>, соответственно. Совпадение языков на языке конечных автоматов (''эквивалентность'') означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния Для проверки включения <tex>p_{1} \in A_{1}L_1</tex> и в <tex>p_{2} \in A_{2}L_2</tex> '''различимыми''', если существует строка достаточно проверить [[Эквивалентность_состояний_ДКА|эквивалентность]] <tex>wM_1</tex> из символов и <tex>\SigmaM_2</tex>, для которой выполняется .
{{Определение
|id=finite
|definition=
[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''конечным''' (англ. ''finite''), если принадлежащее ему множество слов конечно.
}}
|id=
|statement=
|proof=
Пусть такой пары не существует. Возьмём произвольное слово такое состояние <tex>wv</tex> длины существует, а строки <tex>nx, y, z</tex> и выпишем последовательность пар состояний таковы, что <tex>\langle u_s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{i*}\langle v, v_z \rangle \vdash ^{i*} \langle t, \epsilon \rangle</tex>:, <tex>t</tex> — допускающее, <tex>y</tex> — непустая. Рассмотрим строки вида <tex>xy^{k}z, k \in \mathbb{N}</tex>. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено <tex>n! | \Sigma |^{n-1}</tex>, где <tex>n</tex> — количество состояний автомата: <tex>n!</tex> — количество перестановок состояний, <tex>| \Sigma |^{n-1}</tex> — количество совокупностей переходов по символам между ними. Таким образом, язык конечен.
}}
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <tex>\mathrm{paths} (v)</tex>, задающую число различных путей из <tex>s</tex> в <tex>v</tex>; <tex>\mathrm{paths} (s) =1</tex>. Заметим, что если известны значения <tex>\mathrm{paths} (u)</tex> для всех <tex>u</tex>, из которых существует переход в <tex>v</tex>, то <tex>\mathrm{paths} (v) === Псевдокод ====\sum\limits_{u}\mathrm{paths} (u)</tex>. Количеством слов в языке будет сумма <tex>\mathrm{paths} (t)</tex> для всех допускающих <tex>t</tex>.
