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