Теорема Клини

Главный тезис Теоремы Клини: «Классы регулярных множеств и автоматных языков совпадают».

Доказательство теоремы Клини

Любой граф переходов конечного автомата всегда можно представить в нормализованной форме, в которой только одна начальная вершина только с исходящими ребрами и только одна заключительная вершина только с входящими ребрами.

Над графом переходов, представленным в нормализованной форме, могут быть выполнены две операции редукции — редукция ребра и редукция вершины — с сохранением допускаемого этим графом переходов языка. Каждая операция редукции не меняет языка, распознаваемого графом переходов, но уменьшает либо число ребер, либо число вершин.

---

---

---

Следовательно, каждый автоматный язык является регулярным множеством.
Для каждого регулярного выражения R может быть построен конечный автомат (возможно недетерминированный), распознающий язык, задаваемый R. Определение таких автоматов дадим рекурсивно.

---

---

Следовательно, каждое регулярное множество является автоматным языком. Теорема доказана.

Ссылки

• Карпов Ю. Г. Теория автоматов. — СПб.: Питер, 2002. С. 224. ISBN 5-318-00537-3

См. также

• Конечные автоматы
• Эквивалентность детерминированных и недетерминированных конечных автоматов
• Стивен Клини

Для улучшения этой статьи по математике желательно?: Переработать оформление в соответствии с правилами написания статей. Викифицировать статью.