Конструкция подмножеств. Теорема эквивалентности детерминированных и недетерминированных конечных автоматов

Предположим есть D-ДКА и есть N-НКА, каждый из этих автоматов допускает язык для D-L(D) и N-L(N), тогда автоматы D и N будем называть эквивалентными если их язык совпадают (т.е. D-ДКА N-НКА) если L(D) = L(N).

Задача. Есть N, построим D такой что языки у них совпадают L(D) = L(N). Это делается с помощью конструкций подмножеств.

Дано , будем строить .

Начнем с множества состояний . Рассмотрим все его подмножества , т.е. возникает булеан = . Начальное состояние нового автомата будет подмножество состояний из одного элемента , . Определим множество заключительных состояний. есть множество подмножества в S множества , для которого . В качестве заключительного состояния нового автомата мы берем все подмножества из булеана которые содержат хотя бы одно состояние из . Определим функцию , мы должны взять т.е S подмножество ( ).

Теорема. Если детерминированный конечный автомат построен из недетерминированного автомата , с помощью конструкций подмножеств, то L(D) = L(N) (языки допускаемые этими автоматами совпадают).

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

Установим равенство , считаем что при этом т.к. . Индукция по тогда слово можно представить . . Предполагаем что наша формула верна для всех слов значит для всех х наша формула справедлива. значение функции являются: состояния , если детерминированный автомат то это множество воспринимаем как один элемент, а если недетерминированный то разные множества состояния. .

Заметим что детерминированный автомат D и недетерминированный N допускают слово когда или соответственно содержат некоторое состояние из .

Теорема доказана.

4. Конечные автоматы с ε-переходами. Эпсилон ε -замыкание. Расширенные переходы и языки ε -НКА.

Конечные автоматы с ε -переходами – это обобщение недетерминированных конечных автоматов. Вводим возможность для автомата переходить из одного состояния в другое по ε, то есть не получая на вход ни одного символа. Эта особенность не расширяет язык автомата, но дает удобство при программировании.

Опр.конечные автоматы с ε-переходами – это пятерка , где -непустое конечное множество состояний, - алфавит, множество входных символов, - фиксированный единственный символ, называемый начальным состоянием, - множество допустимых (заключительных) состояний, - функция перехода, зависит от 2-х параметров

Расширение функции переходов .

Эпсилон ε -– замыкание. Обозначается . Определяется индуктивно:

Базис:

Индукция: Если и существует ε-переход из состояния в состояние , то (состояния, ведущие в данное)

Точнее, если - функция перехода для ε –НКА и замыкание

- содержит все состояния, в которые можно перейти по ε из данного.

Расширение функции переходов :

;

Индукцией по длине слова. Базис

Индукция по: - дописываем к слову некоторый символ. Вычисляем : 1) , и т.к. , то по индукции множество определено, т.е. - те и только те состояния, в которое можно попасть из q по маршруту, помеченному словом X.Этот маршрут может оканчиваться одним или несколькими ε и может содержать другие ε –переходы. 2) - т.е. нужно совершить все переходы, отмеченные символом , из тех состояний, в которые мы можем попасть из по пути, отмеченному словом . Состояния лишь некоторые из тех, в которые мы можем попасть по маршруту, отмеченному словом . 3) В остальные состояния можно попасть из состояния посредством ε –переходов. - на этом дополнительном шаге мы берем замыкание и добавляем к нему все выходящие из пути, помеченные символом . Здесь же учитывается возможность существования дополнительных дуг, отмеченных символом ε, переход по которому м.б. совершен после перехода по последнему непустому символу .

Язык ε –НКА. Опр. Если ε –НКА - , тогда языком этого автомата будет

Устранение ε – переходов: хотим по ε –НКА построить ДКА. - ε –НКА. С помощью конструкции подмножеств построим эквивалентный ему ДКА . 1) - множество подмножеств : . Для автомата допустимыми состояниями являются только ε – замкнутые подмножества из : . ε – замкнутые множества S - это такие множества, у которых всякий ε – переход из состояния, принадлежащего этому множеству вновь приводит в это множество. Заметим, что является ε – замкнутые подмножеством

2) , 3) 4) , определяется следующим образом: а) , вычислим б)

Теорема. Язык допускается ε –НКА этот язык допускается некоторым ДКА

Доказательство: допускается ε –НКА, тогда с помощью конструкции подмножеств строим ДКА . Покажем . По индукции по длине слова: покажем, что . Базис: , / Предположение индукции: равенство верно для всех . Покажем для , , , , по построению автомата

, автомат дан, построим ε –НКА . Преобразуем в , добавив ε –переходы: , переходы типа