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

       

Магазинные автоматы


КС-грамматика определяет структуру цепочек и позволяет строить цепочки определенного языка. Магазинные автоматы, подобно рассмотренным ранее конечным автоматам, позволяют решать для контекстно-свободных языков задачу  распознавания, которая заключается в том, что по заданной цепочке необходимо определить принадлежит ли она заданному языку.
В работах, связанных с формальными языками и грамматиками,используется модель магазинного автомата, состоящая из входной ленты, устройства

управления и вспомогательной ленты, называемой магазином

или стеком.
Входная лента

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

магазина. Связь устройства управления с  лентами осуществляется двумя головками, которые могут перемещаться вдоль лент.

Головка входной ленты может перемещаться только в одну сторону - вправо или
оставаться на месте. Она может выполнять только чтение. Головка  вспомогательной ленты способна выполнять как чтение, так и запись, но эти операции связаны с перемещением головки определенным образом:
- при записи головка предварительно сдвигается на одну позицию вверх,  а затем символ заносится на ленту,
- при чтении символ, находящийся под головкой считывается с ленты,  а затем головка сдвигается на одну позицию вниз,т.о.головка всегда  установлена против последнего записанного символа. Позицию, находящуюся  в рассматриваемый момент времени под головкой, называют

вершиной магазина.

 

    Определение.Магазинный автомат М определяется следующей совокупностью 

            семи объектов:            M={P , S , sо , f , F , H , hо



        },

<
 
где
          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 .
         

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

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

         


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