Математическая теория формальных языков
Преобразование конечного автомата к детерминированному виду
Теорема 2.7.1
Каждый автоматный язык распознается некоторым полным детерминированным конечным автоматом.
Доказательство. Без ограничения общности можно предположить, что исходный язык задан конечным автоматом , содержащим только переходы с метками длины единица. Для любых
и
обозначим
Обозначим через
множество всех подмножеств множества Q. Построим искомый полный детерминированный конечный автомат , положив ,
и .
Пример 2.7.2.
Пусть . Рассмотрим конечный автомат , где
Если применить конструкцию из доказательства теоремы 2.7.1. и затем удалить состояния, не достижимые из начального состояния, то получится полный детерминированный конечный автомат
где
Упражнение 2.7.3. Найти полный детерминированный конечный автомат, эквивалентный автомату, изображенному на диаграмме.
Упражнение 2.7.4. Найти детерминированный конечный автомат для языка, порождаемого грамматикой
Упражнение 2.7.5. Найти детерминированный конечный автомат, распознающий язык
