Формальные языки


Распознавателя - часть 2


, $ )

 

Для перехода в заключительное состояние добавим правило:
 

          f ( s0 , $ ,h0 ) = ( s1 , $ ) ,

а в качестве начальной конфигурации распознавателя примем, как
обычно, следующее выражение :
 

( s0 , a

, h0<I> ) ,

где <I> - начальный символ грамматики, а  a - заданная входная цепочка.

Применяя приведенные выше правила, построим распознаватель для разделенной грамматики
Г3. 0

. В результате получаем:  М 4 :           P = { a , b },  H = { a , b ,<I> , <B> , h0 }, S = {s0}, F= {s0},

f ( s0 , a , <I>) = ( s0

, <B>b )


f ( s0 , a , <B>) = ( s0

, $ )


f ( s0 , b , <I> ) = ( s0

, <I> b <B> )


f ( s0 , b , <B> ) = ( s0

, <B> )


f ( s0 , b , b ) = ( s0

, $ )


f ( s0 , e

, h0 ) = ( s0 , $ )

 

Работу построенного автомата покажем на примере анализа цепочки bbabab.
  ( s0 , bbababa , h0<I> ) |---

( s0 , bababa , h0<I>b<B> ) |---

( s0 , ababa , h0<I>b<B> ) |---

( s0 , baba , h0<I>b ) |---

( s0 , aba , h0<I> ) |---

( s0 , ba , h0<B>b ) |---

( s0 , a , h0<B> )

|--- ( s0 , $ , h0

) |--- ( s0 , $ , $ ) .

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

  • Пред.Страница 

    След.Страница   Раздел   Содержание




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