Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]]  языков.
 
Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]]  языков.
  

Текущая версия на 19:25, 4 сентября 2022

Для различных операций с регулярными языками полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности автоматных и регулярных языков.

Пустота регулярного языка

Определение:
Регулярный язык называется пустым (англ. empty), если он не содержит ни одного слова.


Определение:
Регулярный язык содержащий хотя бы одно слово, называется непустым (англ. nonempty).


Теорема:
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Пусть язык содержит слово [math]w[/math]. Любой детерминированный конечный автомат [math]A[/math], задающий этот язык, должен допускать [math]w[/math]. Тогда при переходе из стартового состояния [math]A[/math] по символам [math]w[/math] получится путь, оканчивающийся в одном из терминальных состояний.

[math]\Leftarrow[/math]

Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
[math]\triangleleft[/math]

Алгоритм проверки языка на пустоту

Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.

Совпадение регулярных языков

Определение:
Два регулярных языка совпадают (англ. coincide), если любое слово или содержится в обоих языках, или не содержится ни в одном из них.


Для проверки совпадения языков достаточно запустить алгоритм проверки эквивалентности задающих их автоматов.

Пример проверки на совпадение регулярных языков

Для того, чтобы узнать равен ли язык своему замыканию Клини, нужно проверить на эквивалентность автомат, задающий язык, и автомат, задающий замыкание Клини языка. Если автоматы эквивалентны, то язык равен своему замыканию Клини.

Включение одного регулярного языка в другой

Определение:
Регулярный язык [math]L_{1}[/math] входит (включается) (англ. included) в регулярный язык [math]L_{2}[/math], если любое слово, принадлежащее [math]L_{1}[/math], принадлежит [math]L_{2}[/math].


Пусть автомат [math]M_1[/math] задаёт язык [math]L_1[/math], а автомат [math]M_2[/math] — язык [math]L_1 \cap L_2[/math]. Для проверки включения [math]L_1[/math] в [math]L_2[/math] достаточно проверить эквивалентность [math]M_1[/math] и [math]M_2[/math].

Конечность регулярного языка, подсчёт числа слов

Определение:
Регулярный язык называется конечным (англ. finite), если принадлежащее ему множество слов конечно.


Теорема:
Детерминированный конечный автомат [math]A_{1}[/math] задаёт конечный язык тогда и только тогда, когда в [math]A_{1}[/math] не существует состояния [math]v[/math], для которого выполняются три условия:
  • [math]v[/math] достижимо из стартового состояния [math]s[/math];
  • из [math]v[/math] достижимо какое-либо из допускающих состояний;
  • из [math]v[/math] по одному или более переходам достижимо [math]v[/math].
Доказательство:
[math]\triangleright[/math]

Пусть такое состояние [math]v[/math] существует, а строки [math]x, y, z[/math] таковы, что [math]\langle s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{*} \langle v, z \rangle \vdash ^{*} \langle t, \epsilon \rangle[/math], [math]t[/math] — допускающее, [math]y[/math] — непустая. Рассмотрим строки вида [math]xy^{k}z, k \in \mathbb{N}[/math]. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.


Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено [math]n! | \Sigma |^{n-1}[/math], где [math]n[/math] — количество состояний автомата: [math]n![/math] — количество перестановок состояний, [math]| \Sigma |^{n-1}[/math] — количество совокупностей переходов по символам между ними. Таким образом, язык конечен.
[math]\triangleleft[/math]

Алгоритм нахождения числа слов в языке

Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью обхода в глубину по обратным рёбрам определим полезные состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат топологически. Введём функцию [math]\mathrm{paths} (v)[/math], задающую число различных путей из [math]s[/math] в [math]v[/math]; [math]\mathrm{paths} (s) = 1[/math]. Заметим, что если известны значения [math]\mathrm{paths} (u)[/math] для всех [math]u[/math], из которых существует переход в [math]v[/math], то [math]\mathrm{paths} (v) = \sum\limits_{u}\mathrm{paths} (u)[/math]. Количеством слов в языке будет сумма [math]\mathrm{paths} (t)[/math] для всех допускающих [math]t[/math].

См. также

Источики информации

  • Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177 — ISBN 5-8459-0261-4