Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов) — различия между версиями
Shevchen (обсуждение | вклад) м |
м (rollbackEdits.php mass rollback) |
||
(не показано 30 промежуточных версий 11 участников) | |||
Строка 1: | Строка 1: | ||
− | == Пустота == | + | Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]] языков. |
+ | |||
+ | == Пустота регулярного языка == | ||
{{Определение | {{Определение | ||
|id=empty | |id=empty | ||
|definition= | |definition= | ||
− | [[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''пустым''', если он не содержит ни одного слова. | + | [[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''пустым''' (англ. ''empty''), если он не содержит ни одного слова. |
}} | }} | ||
− | + | {{Определение | |
+ | |id=nonempty | ||
+ | |definition= | ||
+ | [[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] содержащий хотя бы одно слово, называется '''непустым''' (англ. ''nonempty''). | ||
+ | }} | ||
− | {{ | + | {{Теорема |
|id= | |id= | ||
regEmpty | regEmpty | ||
Строка 16: | Строка 22: | ||
|proof= | |proof= | ||
− | + | <tex>\Rightarrow</tex> | |
+ | :Пусть язык содержит слово <tex>w</tex>. Любой [[Детерминированные конечные автоматы| детерминированный конечный автомат]] <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одном из терминальных состояний. | ||
− | Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку. | + | <tex>\Leftarrow</tex> |
+ | :Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку. | ||
}} | }} | ||
Строка 26: | Строка 34: | ||
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина. | Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина. | ||
− | + | == Совпадение регулярных языков == | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == Совпадение == | ||
{{Определение | {{Определение | ||
|id=equal | |id=equal | ||
|definition= | |definition= | ||
− | Два [[Регулярные языки: два определения и их эквивалентность|регулярных языка]] '''совпадают''', если любое слово или содержится в обоих языках, или не содержится ни в одном из них | + | Два [[Регулярные языки: два определения и их эквивалентность|регулярных языка]] '''совпадают''' (англ. ''coincide''), если любое слово или содержится в обоих языках, или не содержится ни в одном из них. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
}} | }} | ||
− | + | Для проверки совпадения языков достаточно запустить алгоритм проверки [[Эквивалентность_состояний_ДКА|эквивалентности]] задающих их автоматов. | |
− | + | === Пример проверки на совпадение регулярных языков=== | |
− | + | Для того, чтобы узнать равен ли язык своему замыканию Клини, нужно проверить на [[Эквивалентность_состояний_ДКА|эквивалентность]] автомат, задающий язык, и автомат, задающий замыкание Клини языка. Если автоматы эквивалентны, то язык равен своему замыканию Клини. | |
− | |||
− | |||
− | |||
− | + | == Включение одного регулярного языка в другой == | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == Включение == | ||
{{Определение | {{Определение | ||
|id=inclusion | |id=inclusion | ||
|definition= | |definition= | ||
− | [[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] <tex>L_{1}</tex> '''входит (включается)''' в регулярный язык <tex>L_{2}</tex>, если любое слово, принадлежащее <tex>L_{1}</tex>, принадлежит <tex>L_{2}</tex>. | + | [[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] <tex>L_{1}</tex> '''входит (включается)''' (англ. ''included'') в регулярный язык <tex>L_{2}</tex>, если любое слово, принадлежащее <tex>L_{1}</tex>, принадлежит <tex>L_{2}</tex>. |
}} | }} | ||
− | + | Пусть автомат <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>. | |
− | |||
− | |||
− | |||
− | |||
− | + | == Конечность регулярного языка, подсчёт числа слов == | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == Конечность языка, подсчёт числа слов == | ||
{{Определение | {{Определение | ||
|id=finite | |id=finite | ||
|definition= | |definition= | ||
− | [[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''конечным''', если принадлежащее ему множество слов конечно. | + | [[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''конечным''' (англ. ''finite''), если принадлежащее ему множество слов конечно. |
}} | }} | ||
− | {{ | + | {{Теорема |
|id= | |id= | ||
regFinite | regFinite | ||
Строка 230: | Строка 83: | ||
=== Алгоритм нахождения числа слов в языке === | === Алгоритм нахождения числа слов в языке === | ||
− | Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <tex>paths(v)</tex>, задающую число различных путей из <tex>s</tex> в <tex>v</tex>; <tex>paths(s) = 1</tex>. Заметим, что если известны значения <tex>paths(u)</tex> для всех <tex>u</tex>, из которых существует переход в <tex>v</tex>, то <tex>paths(v) = \sum\limits_{u}paths(u)</tex>. Количеством слов в языке будет сумма <tex>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>. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | * | + | == См. также == |
+ | * [[Замкнутость регулярных языков относительно различных операций]] | ||
+ | * [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] | ||
+ | * [[Доказательство нерегулярности языков: лемма о разрастании]] | ||
+ | == Источики информации == | ||
− | + | * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177 — ISBN 5-8459-0261-4 | |
− | + | [[Категория: Теория формальных языков]] | |
+ | [[Категория: Автоматы и регулярные языки]] | ||
+ | [[Категория: Свойства конечных автоматов]] |
Текущая версия на 19:25, 4 сентября 2022
Для различных операций с регулярными языками полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности автоматных и регулярных языков.
Содержание
Пустота регулярного языка
Определение: |
Регулярный язык называется пустым (англ. empty), если он не содержит ни одного слова. |
Определение: |
Регулярный язык содержащий хотя бы одно слово, называется непустым (англ. nonempty). |
Теорема: |
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных. |
Доказательство: |
|
Алгоритм проверки языка на пустоту
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
Совпадение регулярных языков
Определение: |
Два регулярных языка совпадают (англ. coincide), если любое слово или содержится в обоих языках, или не содержится ни в одном из них. |
Для проверки совпадения языков достаточно запустить алгоритм проверки эквивалентности задающих их автоматов.
Пример проверки на совпадение регулярных языков
Для того, чтобы узнать равен ли язык своему замыканию Клини, нужно проверить на эквивалентность автомат, задающий язык, и автомат, задающий замыкание Клини языка. Если автоматы эквивалентны, то язык равен своему замыканию Клини.
Включение одного регулярного языка в другой
Определение: |
Регулярный язык входит (включается) (англ. included) в регулярный язык , если любое слово, принадлежащее , принадлежит . |
Пусть автомат задаёт язык , а автомат — язык . Для проверки включения в достаточно проверить эквивалентность и .
Конечность регулярного языка, подсчёт числа слов
Определение: |
Регулярный язык называется конечным (англ. finite), если принадлежащее ему множество слов конечно. |
Теорема: |
Детерминированный конечный автомат задаёт конечный язык тогда и только тогда, когда в не существует состояния , для которого выполняются три условия:
|
Доказательство: |
Пусть такое состояние существует, а строки таковы, что , — допускающее, — непустая. Рассмотрим строки вида . Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
|
Алгоритм нахождения числа слов в языке
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью обхода в глубину по обратным рёбрам определим полезные состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат топологически. Введём функцию , задающую число различных путей из в ; . Заметим, что если известны значения для всех , из которых существует переход в , то . Количеством слов в языке будет сумма для всех допускающих .
См. также
- Замкнутость регулярных языков относительно различных операций
- Теорема Клини (совпадение классов автоматных и регулярных языков)
- Доказательство нерегулярности языков: лемма о разрастании
Источики информации
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177 — ISBN 5-8459-0261-4