WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

Ссылки

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

См. также

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

Литература

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

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