Структуры данных и модели вычислений
Финальное состояние автомата соединим дугой
Финальное состояние автомата соединим дугой со стартовым состоянием автомата и пометим ее символом . В качестве возьмем стартовое состояние автомата , а в качестве финального состояния возьмем финальное состояние
автомата .
Для регулярного выражения , где — регулярное выражение, можно построить задающий автомат следующим образом. Пусть автомат
задает . Опять не уменьшая общности, считаем, что — одноэлементное и что . Добавляем к множеству два новых состояния — и . Соединяем -переходами пары состояний , , и .
В завершение заметим, что изложенные приемы, очевидно, позволяют по любому регулярному выражению построить недетерминированный автомат с -переходами, с одним стартовым и одним финальным состоянием, причем стартовое состояние отлично от финального, и при этом такой, что .
Таким образом, задача синтеза решена.
Избавление от -переходов. Покажем, как по недетерминированному автомату
с -переходами построить недетерминированный автомат ) без -переходов, такой, что . Назовем -путем путь в диаграмме автомата , возможно пустой, порождающий пустое слово. Обозначим через
множество состояний, достижимых из с помощью некоторого -пути.
Положим . Переходную функцию построим следующим образом Заметим, что в полученном автомате множество финальных состояний может быть не одноэлементным.
Детерминизация.Покажем, как по недетерминированному автомату без -переходов построить детерминированный автомат , такой, что . Положим , , , а
определим следующим образом: Нетрудно видеть, что построенный таким образом автомат
удовлетворяет условию .
Анализ. Для завершения доказательства теоремы покажем, как по заданному детерминированному конечному автомату ( построить регулярное выражение , такое, что . Именно это и называют задачей анализа. Правда, метод, который мы используем, можно применить и к недетерминированным автоматам. Метод заключается в том, что мы сводим задачу к решению стандартной системы уравнений. Итак, рассмотрим автомат .
Пусть , . Введем переменные , . Переменную для каждого будем интерпретировать как множество слов, которые можно прочитать, начиная от состояния и заканчивая в финальном состоянии, тогда должна удовлетворять уравнению
