Теорема Клини (совпадение классов автоматных и регулярных языков) — различия между версиями
(→Источники информации) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 58: | Строка 58: | ||
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%BB%D0%B8%D0%BD%D0%B8 Википедия {{---}} Теорема Клини] | * [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%BB%D0%B8%D0%BD%D0%B8 Википедия {{---}} Теорема Клини] | ||
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4 | * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4 | ||
− | |||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Автоматы и регулярные языки]] | [[Категория: Автоматы и регулярные языки]] |
Текущая версия на 19:39, 4 сентября 2022
Теорема (Клини): |
Классы автоматных и регулярных языков совпадают. |
Доказательство: |
Для доказательства будем строить автоматы, допускающие регулярные языки (см. картинки справа). При этом будем использовать индукцию по номеру поколения регулярного языка. База
Индукционный переход
Заметим, что по предположению индукции автоматы для могут быть построены.Итого, мы можем по регулярному выражению построить автомат, допускающий тот же язык.
Для доказательства будем строить регулярное выражение, допускающее язык, заданный каким-то автоматом. Пусть задан автомат с набором состояний .Определим регулярные выражения, задающие следующие множества слов:
|
См. также
Источники информации
- Википедия — Теорема Клини
- Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 61.— ISBN 5-8459-0261-4