Теорема Клини
Материал из Википедии — свободной энциклопедии
- Статья не полностью соответствует правилам Википедии или рекомендациям по оформлению статей. Желательно:
- проставить интервики
- викифицировать
Содержание |
[править] Теорема Клини
Классы регулярных множеств и автоматных языков совпадают
[править] Доказательство теоремы Клини
Любой конечный автомат и любой граф переходов всегда можно представить в нормализованной форме, в которой только одна начальная вершина только с исходящими ребрами и только одна заключительная вершина только с входными ребрами. С графом переходов, представленном в нормализованной форме, могут быть выполнены две операции редукции — редукция ребра и редукция вершины — с сохранением допускаемого этим графом переходов языка. Каждая операция редукции не меняет языка, распознаваемого графом переходов, но уменьшает либо число ребер, либо число вершин.
Следовательно, каждый автоматный язык является регулярным множеством.
Для каждого регулярного выражения R может быть построен конечный автомат (возможно недетерминированный), распознающий язык, задаваемый R. Определение таких автоматов дадим рекурсивно.
Следовательно, каждое регулярное множество является автоматным языком. Теорема доказана.
[править] Ссылки
- Карпов Ю.Г.Теория автоматов. — СПб.: Питер, 2002. С. 224. ISBN 5-318-00537-3
[править] См. также
- Минимизация конечных автоматов
- Конечные автоматы
- Эквивалентность детерминированных и недетерминированных конечных автоматов