Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов) — различия между версиями
Ateuhh (обсуждение | вклад) м (→Пустота регулярного языка) |
Ateuhh (обсуждение | вклад) м |
||
Строка 81: | Строка 81: | ||
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <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>\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>. | ||
+ | |||
+ | == См. также == | ||
+ | * [[Замкнутость регулярных языков относительно различных операций]] | ||
+ | * [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] | ||
+ | * [[Доказательство нерегулярности языков: лемма о разрастании]] | ||
== Источики информации == | == Источики информации == |
Версия 23:15, 4 января 2017
Для различных операций с регулярными языками полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности автоматных и регулярных языков.
Содержание
Пустота регулярного языка
Определение: |
Регулярный язык называется пустым (англ. empty), если он не содержит ни одного слова. |
Определение: |
Регулярный язык содержащий хотя бы одно слово, называется непустым (англ. nonempty). |
Теорема: |
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных. |
Доказательство: |
|
Алгоритм проверки языка на пустоту
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
Совпадение регулярных языков
Определение: |
Два регулярных языка совпадают (англ. coincide), если любое слово или содержится в обоих языках, или не содержится ни в одном из них. |
Для проверки совпадения языков достаточно запустить алгоритм проверки эквивалентности задающих их автоматов.
Включение одного регулярного языка в другой
Определение: |
Регулярный язык входит (включается) (англ. included) в регулярный язык , если любое слово, принадлежащее , принадлежит . |
Пусть автомат задаёт язык , а автомат — язык . Для проверки включения в достаточно проверить эквивалентность и .
Конечность регулярного языка, подсчёт числа слов
Определение: |
Регулярный язык называется конечным (англ. finite), если принадлежащее ему множество слов конечно. |
Теорема: |
Детерминированный конечный автомат задаёт конечный язык тогда и только тогда, когда в не существует состояния , для которого выполняются три условия:
|
Доказательство: |
Пусть такое состояние существует, а строки таковы, что , — допускающее, — непустая. Рассмотрим строки вида . Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
|
Алгоритм нахождения числа слов в языке
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью обхода в глубину по обратным рёбрам определим полезные состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат топологически. Введём функцию , задающую число различных путей из в ; . Заметим, что если известны значения для всех , из которых существует переход в , то . Количеством слов в языке будет сумма для всех допускающих .
См. также
- Замкнутость регулярных языков относительно различных операций
- Теорема Клини (совпадение классов автоматных и регулярных языков)
- Доказательство нерегулярности языков: лемма о разрастании
Источики информации
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177 — ISBN 5-8459-0261-4