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

Лемма 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.4.1. Каждый автоматный язык является праволинейным.

Без ограничения общности можно предположить, что исходный язык задан конечным автоматом , где и I = {q₀}. Положим N = Q, S = q₀ и

Пример 2.4.2. Язык, распознаваемый конечным автоматом из примера 2.1.2, порождается грамматикой

Теорема 2.4.3. Каждый праволинейный язык является автоматным.

Доказательство. Без ограничения общности можно предположить, что исходный язык задан праволинейной грамматикой, не содержащей правил вида , где . Положим Q = N, I = {S}, и .