105
правок
Изменения
м
== Пустота ==Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]] языков.
'''== Пустота''' [[Регулярные языки: два определения и их эквивалентность|регулярного языка]] — свойство языка не содержать ни одного слова. Язык, содержащий хотя бы одно слово, назовём '''непустым'''.==
Пусть язык содержит слово <tex>w\Rightarrow</tex>. Любой автомат <tex>A</tex>, соответствующий этому языку, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин.
boolean dfs(State v) { v.seen = true; if (v.isFinal) { return false; } for (State u : v.next) { if (!u.seen && !dfs(u)) { return false; } } return true; } boolean isEmpty(Automaton a) { for (State v : a) { 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>w</tex> из символов <tex>\Sigma</tex>, для которой выполняется == Включение одного регулярного языка в другой ==
где <tex>s_{1}</tex>== Конечность регулярного языка, <tex>s_{2}</tex> - стартовые состояния.подсчёт числа слов ==
На основе заданного отношения разобьём состояния автоматов на классы эквивалентности: состояния <tex>p</tex> и <tex>q</tex> принадлежат одному классу тогда и только тогда, когда существует последовательность состояний <tex>p_{0}...p_{k}</tex>, где <tex>p Определение|id= p_{0}</tex>, <tex>q finite|definition= p_{k}</tex> [[Регулярные языки: два определения и <tex>\forall i = 1..k</tex> <tex>p_{i - 1}</tex> идентично <tex>p_{i}</tex>их эквивалентность|Регулярный язык]] называется '''конечным''' (англ. Все состояния, из которых не достигаются допускающие''finite''), не влияют на если принадлежащее ему множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будутконечно.}}
regEqClassesregFinite
Автоматы [[Детерминированные конечные автоматы|Детерминированный конечный автомат]] <tex>A_{1}</tex> задаёт конечный язык тогда и только тогда, когда в <tex>A_{21}</tex> эквивалентны тогда и только тогдане существует состояния <tex>v</tex>, когда в любом классе содержатся для которого выполняются три условия:* <tex>v</tex> достижимо из стартового состояния <tex>s</tex>;* из <tex>v</tex> достижимо какое-либо из допускающих состояний;* из <tex>v</tex> по одному или только допускающие, или только недопускающие состоянияболее переходам достижимо <tex>v</tex>.
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{j}, \epsilon \rangle</tex>,
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{j+1}, \epsilon \rangle</tex>. Таким образом, слово <tex>w</tex> допускается первым автоматом и не допускается вторым, значит, автоматы неэквивалентны. Пусть в любом классе содержатся только допускающие или только недопускающие такого состоянияне существует. Рассмотрим любую строку <tex>w</tex> и такие Тогда любой путь из стартового состояния <tex>u_{1}</tex> и <tex>u_{2}</tex>, что <tex>\langle s_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle</tex>, <tex>\langle s_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle</tex>в какое-либо из допускающих является простым. Состояния <tex>u_{1}</tex> и <tex>u_{2}</tex> идентичны, следовательно, принадлежат одному классу эквивалентности. Таким образом, любая строка оканчивается либо допускающими состояниями Количество слов в обоих автоматахязыке равно количеству таких путей; количество путей, либо в обоих не допускаетсясвою очередь, значит, автоматы эквивалентны.}} {{Утверждение|id=regEqClasses|statement=Если состояния <tex>p</tex> и <tex>q</tex> принадлежат одному классу эквивалентности, то для любого символа <tex>c</tex> из алфавита ограничено <tex>n! | \delta (p, c)</tex> и <tex>\delta (q, c)</tex> также принадлежат одному классу. Sigma |proof=Рассмотрим последовательность <tex>p_^{0}...p_{k}</tex>, где <tex>p = p_{0}</tex>, <tex>q = p_{k}</tex> и <tex>\forall i = 1..k</tex> <tex>p_{i n- 1}</tex> идентично <tex>p_{i}</tex> по строке <tex>w_{i}</tex>. Тогда для последовательности <tex>p'_{0}...p'_{k}</tex>, где <tex>\delta (p, c) = p'_{0}n</tex>, — количество состояний автомата: <tex>\delta (q, c) = p_{k}n!</tex> будет верно: — количество перестановок состояний, <tex>| \forall i = 1..k</tex> <tex>p'_Sigma |^{i n- 1}</tex> идентично <tex>p'_{i}</tex> — количество совокупностей переходов по строке <tex>w_{i}c</tex>символам между ними. Таким образом, <tex>\delta (p, c)</tex> и <tex>\delta (q, c)</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>.
Второй шаг - обход в ширину, объединяющий классы эквивалентности== См. Изначально каждое состояние принадлежит отдельному классу, кроме двух стартовых, объединённых в один класс. Для определения класса по состоянию используется также ==* [[СНМ(наивные реализации)|система непересекающихся множествЗамкнутость регулярных языков относительно различных операций]]. Очередь обхода в ширину хранит пары состояний <tex>p_{1} \in A_{1}</tex>, <tex>p_{2} \in A_{2}</tex>, для которых существует строка <tex>w</tex> * [[Теорема Клини (для <tex>s_{1}</tex> совпадение классов автоматных и <tex>s_{2}</tex> равная <tex>\epsilon</tex>регулярных языков)]]* [[Доказательство нерегулярности языков:лемма о разрастании]]
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{1}, \epsilon \rangle</tex>,== Источики информации ==
<tex>\langle s_{2}* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — Введение в теорию автоматов, языков и вычислений, w \rangle \rightarrow \langle p_{2}-е изд. : Пер. с англ. — Москва: Издательский дом «Вильямс», \epsilon \rangle</tex>2002. — с.169-177 — ISBN 5-8459-0261-4
Для пары состояний изучаются переходы из них по всем символам алфавита. Пусть <tex>\delta (p_{1}, c) = q_{1}</tex>, <tex>\delta (p_{2}, c) = q_{2}</tex>. Если <tex>q_{1}</tex> [[Категория: Теория формальных языков]][[Категория: Автоматы и <tex>q_{2}</tex> принадлежат разным классам, их классы объединяются, а пара <tex>\langle q_{1}, q_{2} \rangle</tex> добавляется в очередь.регулярные языки]][[Категория: Свойства конечных автоматов]]
Дмитрий Мурзин переименовал страницу Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)…
{{УтверждениеОпределение|id=empty|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''пустым''' (англ. ''empty''), если он не содержит ни одного слова.}} {{Определение|id=nonempty|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] содержащий хотя бы одно слово, называется '''непустым''' (англ. ''nonempty'').}} {{Теорема
|id=
regEmpty
|statement=
Регулярный язык является непустым тогда и только тогда, когда в любом соответствующем ему задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.
|proof=
:Пусть язык содержит слово <tex>w</tex>. Любой [[Детерминированные конечные автоматы| детерминированный конечный автомат]] <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одном из терминальных состояний.
<tex>\Leftarrow</tex>:Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на рёбрахпереходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
}}
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
{{Определение
|id=equal
|definition=
Два [[Регулярные языки: два определения и их эквивалентность|регулярных языка]] '''совпадают''' (англ. ''coincide''), если любое слово или содержится в обоих языках, или не содержится ни в одном из них.
}}
{{Определение|id=inclusion|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] <tex>\langle s_L_{1}</tex> '''входит (включается)''' (англ. ''included'') в регулярный язык <tex>L_{2}</tex>, w \rangle \rightarrow \langle p_если любое слово, принадлежащее <tex>L_{1}</tex>, \epsilon \rangleпринадлежит <tex>L_{2}</tex>,.}}
Пусть автомат <tex>\langle s_{2}M_1</tex> задаёт язык <tex>L_1</tex>, w а автомат <tex>M_2</tex> — язык <tex>L_1 \rangle \rightarrow \langle p_{2}, \epsilon \ranglecap L_2</tex>. Для проверки включения <tex>L_1</tex> в <tex>L_2</tex> достаточно проверить [[Эквивалентность_состояний_ДКА|эквивалентность]] <tex>M_1</tex> и <tex>M_2</tex>,.
{{Теорема
|id=
|statement=
|proof=
Пусть в каком-либо классе содержатся допускающее такое состояние <tex>tv</tex> и недопускающее существует, а строки <tex>ux, y, z</tex>. По построению классов эквивалентноститаковы, существует последовательность что <tex>p_\langle s, xyz \rangle \vdash ^{0*}...p_\langle v, yz \rangle \vdash ^{k*}</tex>\langle v, где <tex>t = p_z \rangle \vdash ^{0*}</tex>\langle t, <tex>u = p_{k}</tex> и <tex>\forall i = 1..kepsilon \rangle</tex> , <tex>p_{i - 1}t</tex> идентично — допускающее, <tex>p_{i}y</tex>— непустая. Тогда найдётся пара Рассмотрим строки вида <tex>p_xy^{jk}</tex>z, <tex>p_k \in \mathbb{j+1N}</tex>: <tex>p_{j}</tex> является допускающим. Их бесконечное количество, а <tex>p_{j+1}</tex> - нет. Для определённостии все они, пусть <tex>p_{j}</tex> принадлежит первому автоматукак легко увидеть, а <tex>p_{j+1}</tex> - второмудопускаются автоматом. Так как эти состояния идентичныЗначит, <tex>\exists w</tex>:язык бесконечен.
}}
