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

Распознавателя


    Способ построения распознавателя предусматривает сопоставление каждому правилу грамматики команды распознавателя .
    Согласно общему способу построения распознавателей для КС-грамматик, описанному в предыдущем разделе, каждому правилу разделенной грамматики, которые имеют вид:
    <A>  ® a a , где a

    - цепочка символов полного словаря и a принадлежит
    терминальному словарю, нужно поставить в соответствие команду

       

          (*)    f 0( s0 , e , <A> ) = ( s0

          , a

          ' a) ,

         

      которая задает такт работы без сдвига входной головки и в которой

      a ' представляет собой зеркальное отображение цепочки a

      . Отметим, что в результате выполнения этой команды, в вершине магазина окажется терминал a. Общий способ построения  редусматривает также построение для каждого a

      символа грамматики команды:
       

                 (**)    

          f ( s0 , a , a ) = ( s0 , $ )



         

      которая удаляет этот терминал из магазина и сдвигает входную головку.
      Учитывая, что в разделенной грамматике каждое правило начинается с терминального символа, и что эти терминалы не повторяются, можно сделать вывод о том , что команда (*) должна выполняться только в том случае, когда под входной головкой находится  терминал

      a, и после нее всегда должна выполняться команда (**).
      Чтобы исключить неопределенность правил вида (*) и уменьшить число тактов работы распознавателя, объединим команды вида (*) и (**) в одну команду. Построение такой команды должно выполняться следующим образом: каждому правилу разделенной грамматики <A>  ® a a

      поставим в соответствие команду
       

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

          ') ,

         

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

        f ( s0 , b , b ) = ( s0


        , $ )


       

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


          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 , $ , $ ) .

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


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

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


      Содержание раздела