Лемма 2.3.1. Каждый автоматный язык распознается некоторым конечным автоматом, не содержащим переходов с метками длины больше единицы и имеющим ровно одно начальное состояние и ровно одно заключительное состояние.
Пример 2.3.2. Рассмотрим язык, заданный конечным автоматом 
, где Q = {1,2}, 
, I = {1,2}, F = {1,2},
Тот же язык распознается конечным автоматом 
, где Q' = {0,1,2,3,4,5}, I' = {0}, F' = {5},
Здесь первые два перехода заменяют старый переход 
и следующие два перехода заменяют старый переход 
. Чтобы обеспечить единственность начального состояния, добавлены переходы 
и 
. Последние два перехода в 
обеспечивают единственность заключительного состояния.
Лемма 2.3.3. Каждый автоматный язык распознается некоторым конечным автоматом, содержащим только переходы с метками длины единица и имеющим ровно одно начальное состояние.
Доказательство. Согласно лемме 2.3.1 можно предположить, что исходный язык задан конечным автоматом , не содержащим переходов с метками длины больше единицы, причем |I| = 1. Построим искомый конечный автомат , положив Q' = Q, I' = I,
Пример 2.3.4. Пусть 
, где Q = {1,2,3}, 
, I = {1}, F = {3},
Легко убедиться, что 
. Тот же язык распознается конечным автоматом 
, где F' = {2,3} и
Упражнение 2.3.5. Найти конечный автомат с однобуквенными переходами, распознающий язык 
Упражнение 2.3.6. Найти конечный автомат с однобуквенными переходами, распознающий язык 
Упражнение 2.3.7. Существуют ли автоматный язык, который не распознается никаким конечным автоматом, содержащим только переходы с метками длины единица и имеющим ровно одно начальное состояние и ровно одно заключительное состояние?
