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