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

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

Формулировка

Пусть $V={a_{1},...,a_{n}}$ — произвольный алфавит. Язык $L\subseteq V^{*}$ является элементом полукольца регулярных языков $R(V)$ в алфавите $V$ тогда и только тогда, когда он допускается некоторым конечным автоматом.

Доказательство

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

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

---

---

---

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

---

---

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

Ссылки

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

См. также

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

Литература

• Белоусов А. И., Ткачев С. Б. Дискретная математика. — М. : МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.