Конечные автоматы с однобуквенными переходами

Лемма 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. Существуют ли автоматный язык, который не распознается никаким конечным автоматом, содержащим только переходы с метками длины единица и имеющим ровно одно начальное состояние и ровно одно заключительное состояние?