Преобразование недетерминированного автомата в детерминированный.

Имеется два способа:

1. Общий способ

Пример:

P = {a,b}

S = {I,B,C}

M(S) = {[I] , [B] , [C] , [IB] , [IC] , [BC] , [IBC] , o}

φ( I , a) = [I , c]

φ( I , b) = [B]

φ( B , a) = [C]

φ( B , b) = []

φ( C , a) = [B]

φ( C , b) = [B]

φ( IB , a) = [IC]

φ( IB , b) = [B]

φ( IC , a) = [I ,C , B]

φ( IC , b) = [B]

φ( BC , a) = [BC]

φ( BC , b) = [B]

φ( IBC , a) = [IBC]

φ( IBC , b) = [B]

Вершины IBиBCявляются недостижимыми, а вершины 0 нет в выходном сигнале для состоянияB, следовательно граф упроститься:

Это общий способ построения автомата.

Недостаток заключается в том, сто в процессе преобразования возникает большое число недостижимых вершин, которые необходимо удалять.

2 способ. Сокращенный способ.

1. Строится заготовка таблицы переходов детерминированного конечного автомата.

2. В качестве начального состояния выбирается начальное состояние недетерминированного автомата и для него строим подмножество состояний, в которое переходим из начального. Строку заносим в заготовку таблицы переходов.

3. Если полученное подмножество состояний или состояния отсутствуют в левой части таблицы переходов, то они заносятся туда и осуществляется переход к пункту 2.

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

Пример:

Пример :Недетерминированный конечный автомат.

D– конечная вершина.