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

ДОКАЗАТЕЛЬСТВО.
A. Пусть задана регулярная грамматика , где

B. Введем дополнительный нетерминальный знак . Заменим в множестве продукций все продукции вида на продукции вида и добавим продукцию вида . Очевидно, что мы получили грамматику, эквивалентную исходной, порождающую тот же язык .
Обоснование этого факта заключается в том, что произвольный вывод в исходной грамматике имеет соответствующий ему вывод в преобразованной грамматике, отличающейся от исходной применением продукции в конце вывода.
Верно и обратное. Следовательно грамматики совпадают.
C. Построим конечный автомат порождающий язык , где — грамматика построенная в пункте В.
Тогда конечный автомат есть , где система команд конечного автомата получена из множества продукций грамматики следующим образом: если имеется продукция вида , то в систему команд добавляется команда
D. Покажем, что построенный автомат порождает тот же язык, что и грамматика

Показывается аналогично тому, как это делалось в пункте В.
E. Синтез конечных автоматов. Построим конечный автомат, распознающий ( принимающий) строки языка , вида , где построим следующим образом: для каждой продукции грамматики вида в систему команд конечного автомата добавляем продукцию вида .
F.

Доказательство того, что построенный автомат распознает (принимает) строки языка выполняем аналогично тому, как это сделано в пункте D.
G. Анализ конечных автоматов. Покажем обратное утверждение теоремы.
Пусть задан конечный автомат , где
H. Построим грамматику , где аксиома .
Множество продукций построим следующим образом: обозначим заключительное состояние как . Для каждой команды конечного автомата вида в множество продукций грамматики добавляем продукцию вида и одну продукцию вида .
Очевидно, что построенная грамматика порождает тот же язык, что и конечный автомат .
I. Построим грамматику , которая порождает язык, принимаемый конечным автоматом следующим образом: для каждой команды конечного автомата вида в множество продукций грамматики добавляем продукцию вида и одну продукцию вида .
Очевидно, что полученная грамматика порождает язык, принимаемый автоматом .
Вывод. Таким образом произвольный конечный автомат описывается двумя регулярными грамматиками, имеющими общий алфавит нетерминальных знаков и аксиому.
Окончание доказательства.

Пример. Произведем анализ конечного автомата.
Пусть задан конечный автомат графом переходов.

Автомат недетерминированный.
Используя теорему 2.10 запишем продукции грамматики, порождающей язык, строки которого распознаются данным конечным автоматом , где множество продукций
Построим грамматику, которая порождает язык, порождаемый конечным автоматом.
, где множество продукций