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