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


Магазинные автоматы - часть 2


/p>

 
где
          P - входной алфавит,
          S - алфавит состояний,
          sо - начальное состояние,


          sо О S ,


          F - множество конечных состояний ,F является подмножеством S,
          H - алфавит

магазинных символов, записываемых на вспомогательную ленту,
          hо- маркер дна, он всегда записывается на дно магазина , hо О   H,


           f - функция переходов
           f : {P И {e

}} x S x H  ®  S x H* ,
           если М-автомат - детерминированный, и 
           f:{P И {e

}} x S x H  ®  M(S x H*) ,
           если М-автомат - недетерминированный.

    Функция f отображает тройки ( pi , sj , hk ) в пары ( sr , u

    ) , где u О

    H*  и  hk - символ в вершине магазина, для детерминированного автомата или в множество пар для недетерминированного автомата.
    Эта функция описывает изменение состояния магазинного автомата, происходящее при чтении символа с входной ленты и премещении входной головки.
    В дальнейшем при построении магазинных автоматов потребуются две разновидности функций переходов, изменяющих состояние автомата без  перемещения входной головки: 1) функция переходов с пустым символом в качестве входного символа:

              f0( s, e, h) = ( s', b),

    которая, независимо от того какой символ находится под читаюшей гловкой входной ленты, предписывает прочитать символ h

    из вершины магазина, изменить состояние автомата на s' и записать цепочку

    b в магазин. 


    2)функция переходов с определенным входным символом:

              f*( s, a, h) = ( s', b),

    которая предписывает изменение состояния и запись цепочки в магазин при условии, что символ a  читается входной головкой, а  в  вершине магазина находится символ  h .
     

  •  

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

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


  •  




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