Хелпикс

Главная

Контакты

Случайная статья



Переход от НДА к ДА

⇐ ПредыдущаяСтр 2 из 2


2. Переход от НДА к ДА

Переход от недетерменированного автомата к детерменированному происходит в два этапа:

1) по недетерменированному автомату строится эквивалентный ему недетерменированный автомат без ε-переходов;

2) по недетерменированному автомату без ε-переходов строится эквивалентный ему детерменированный автомат.

Рассмотрим переход от НДА к ДА на примере.

Пусть задан НДА:

  ε a b
Q0 Q1 - Q2
Q1 - Q3, Q2 -
Q2 - - Q3, Q2
Q3 Q2 Q3, Q0 -

Выполним первый этап.

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

ε-замыкания для некоторого состояния Qi  называют множество, включающее в себя само состояние Qi , а также все состояния Qj , в которые автомат может перейти под действием пустого символа ε, т.е.:

Состоянием недетерменированного автомата-распознавателя без ε-переходов будут являться ε-замыкания исходного недетерменированного автомата.

Для автомата рисунка 1:

Ξ(Q0)={Q0, Q1}=q0,

Ξ(Q1)={Q1}=q1,

Ξ(Q2)={Q2}=q2,

Ξ(Q3)={Q3, Q2}=q3.

Состояние q3 является финальным, т.к. в его входит финальное состояние Q3 исходного НДА.

  a b
q0 {Ξ(Q3),Ξ(Q2)}→{q2,q3} {Ξ(Q2)}→{q2}
q1 {Ξ(Q3),Ξ(Q2)}→{q2,q3} -
q2 - {Ξ(Q3),Ξ(Q2)}→{q2,q3}
q3+ {Ξ(Q0),Ξ(Q3)}→ {q0,q3} {Ξ(Q3),Ξ(Q2)}→{q2,q3}

 

Граф переходов этого недетерминированного автомата представлен на следующем рисунке .

 

Рисунок . Недетерминированный конечный автомат-распознаватель без ε-переходов

Второй этап.

Построение эквивалентного детерменированного автомата.

Рассмотрим теперь алгоритм построения по заданному недетерминированному автомату Ан=<Q,X,Q0,δн,Fн> без ε-переходов эквивалентного ему детерминированного автомата.

Заметим, что в автомате Ан множество начальных состояний может содержать несколько состояний (в данном примере - два начальных состояния: {q0, q1}).

В качестве состояний искомого детерминированного автомата естественно выбрать множества состояний исходного недетерминированного автомата.

Множество Fд заключительных состояний искомого автомата состоит из всех таких множеств состояний, которые включают хотя бы одно заключительное состояние исходного автомата.

  a b
{q0,q1} {q2,q3} {q2}
{q2,q3} {q0,q3} {q2,q3}
{q2} - {q2,q3}
{q0,q3} {q0,q2,q3} {q2,q3}
{q0,q2,q3} {q0,q2,q3} {q2,q3}

 

Введем следующие переобозначения:

Тогда:

  a b
→S0 S1 S2
S1+ S3 S1
S2 - S1
S3+ S4 S1
S4+ S4 S1

  S0 S1+ S2 S3+ S4+
a S1 S3 - S4 S4
b S2 S1 S1 S1 S1

После минимизации данного детерминированного автомата-распознавателя имеем:

Таким образом, недетерминированные автоматные распознаватели распознают то же множество языков, что и детерминированные.

Пример.

 
- -
a
b
c

:  

:  

:        

 

 
a → , →{ , } , →{ , }
b → , →{ , } , →{ , }
c → → , →{ , }

 

Граф недетерминированного автомата-распознавателя без ε-переходов:

        :

        :

        :

            :

            :

         :

           :

           :

            :

Граф детерминированного автомата-распознавателя:


⇐ Предыдущая12
  

© helpiks.su При использовании или копировании материалов прямая ссылка на сайт обязательна.