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



Распознавателя - часть 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 , $ , $ ) .

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

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

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




Содержание  Назад  Вперед