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