Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов) — различия между версиями
Ateuhh (обсуждение | вклад) м (→Пустота регулярного языка) |
Ateuhh (обсуждение | вклад) м |
||
Строка 1: | Строка 1: | ||
− | Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] | + | Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]] языков. |
== Пустота регулярного языка == | == Пустота регулярного языка == |
Версия 20:53, 4 января 2017
Для различных операций с регулярными языками полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности автоматных и регулярных языков.
Содержание
Пустота регулярного языка
Определение: |
Регулярный язык называется пустым (англ. empty), если он не содержит ни одного слова. |
Язык, содержащий хотя бы одно слово, назовём непустым (англ. nonempty).
Теорема: |
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных. |
Доказательство: |
Пусть язык содержит слово детерминированный конечный автомат , задающий этот язык, должен допускать . Тогда при переходе из стартового состояния по символам получится путь, оканчивающийся в одном из терминальных состояний. . ЛюбойПусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку. |
Алгоритм проверки языка на пустоту
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
Совпадение регулярных языков
Определение: |
Два регулярных языка совпадают (англ. coincide), если любое слово или содержится в обоих языках, или не содержится ни в одном из них. |
Для проверки совпадения языков достаточно запустить алгоритм проверки эквивалентности задающих их автоматов.
Включение одного регулярного языка в другой
Определение: |
Регулярный язык входит (включается) (англ. included) в регулярный язык , если любое слово, принадлежащее , принадлежит . |
Пусть автомат задаёт язык , а автомат — язык . Для проверки включения в достаточно проверить эквивалентность и .
Конечность регулярного языка, подсчёт числа слов
Определение: |
Регулярный язык называется конечным (англ. finite), если принадлежащее ему множество слов конечно. |
Теорема: |
Детерминированный конечный автомат задаёт конечный язык тогда и только тогда, когда в не существует состояния , для которого выполняются три условия:
|
Доказательство: |
Пусть такое состояние существует, а строки таковы, что , — допускающее, — непустая. Рассмотрим строки вида . Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
|
Алгоритм нахождения числа слов в языке
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью обхода в глубину по обратным рёбрам определим полезные состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат топологически. Введём функцию , задающую число различных путей из в ; . Заметим, что если известны значения для всех , из которых существует переход в , то . Количеством слов в языке будет сумма для всех допускающих .
Источики информации
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177 — ISBN 5-8459-0261-4