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


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


Язык , порождаемый таким автоматом , определяется аналогично тому, как это было для недетерминированных автоматов.

Теорема.

Классы языков, задаваемые детерминированными конечными автоматами, недетерминированными конечными автоматами с -переходами, недетерминированными конечными автоматами без -переходов, регулярными выражениями совпадают.

Доказательство.

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

Синтез. Регулярное выражение представляется автоматом

где , алфавит — произволен, — начальное состояние, — множество финальных состояний и переходная функция задается соотношениями

Регулярное выражение представляется автоматом , где , алфавит — произволен, — начальное состояние, — множество финальных состояний и переходная функция

задается соотношениями и , .

Регулярное выражение представляется автоматом , где , — начальное состояние, — множество финальных состояний и переходная функция

задается соотношениями

и .

Для регулярного выражения , где

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

задает , а автомат задает . Не уменьшая общности, можно считать, что и — одноэлементные и что , . Положим , где , — новые состояния, и поясним построение автомата на языке диаграмм. Состояние соединим дугами со стартовыми состояниями , автоматов , и пометим их символом . Состояния и автоматов , соединим дугами с новым состоянием и также пометим их символом . Начальным состоянием построенного автомата объявим , а финальным — .




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



Книжный магазин