Структуры данных и модели вычислений


Автоматное задание языков - часть 3


Финальное состояние автомата соединим дугой со стартовым состоянием автомата и пометим ее символом . В качестве возьмем стартовое состояние автомата , а в качестве финального состояния возьмем финальное состояние

автомата .

Для регулярного выражения , где — регулярное выражение, можно построить задающий автомат следующим образом. Пусть автомат

задает . Опять не уменьшая общности, считаем, что — одноэлементное и что . Добавляем к множеству два новых состояния — и . Соединяем -переходами пары состояний , , и .

В завершение заметим, что изложенные приемы, очевидно, позволяют по любому регулярному выражению построить недетерминированный автомат с -переходами, с одним стартовым и одним финальным состоянием, причем стартовое состояние отлично от финального, и при этом такой, что .

Таким образом, задача синтеза решена.

Избавление от -переходов. Покажем, как по недетерминированному автомату

с -переходами построить недетерминированный автомат ) без -переходов, такой, что . Назовем -путем путь в диаграмме автомата , возможно пустой, порождающий пустое слово. Обозначим через

множество состояний, достижимых из с помощью некоторого -пути.

Положим . Переходную функцию построим следующим образом

Заметим, что в полученном автомате множество финальных состояний может быть не одноэлементным.

Детерминизация.Покажем, как по недетерминированному автомату без -переходов построить детерминированный автомат , такой, что . Положим , , , а

определим следующим образом:

Нетрудно видеть, что построенный таким образом автомат

удовлетворяет условию .

Анализ. Для завершения доказательства теоремы покажем, как по заданному детерминированному конечному автомату ( построить регулярное выражение , такое, что . Именно это и называют задачей анализа. Правда, метод, который мы используем, можно применить и к недетерминированным автоматам. Метод заключается в том, что мы сводим задачу к решению стандартной системы уравнений. Итак, рассмотрим автомат .

Пусть , . Введем переменные , . Переменную для каждого будем интерпретировать как множество слов, которые можно прочитать, начиная от состояния и заканчивая в финальном состоянии, тогда должна удовлетворять уравнению




Начало  Назад  Вперед