2.7 Преобразование неукорачивающих грамматик.

Определение.Грамматика называетсянеукорачивающейили грамматикой без аннулирующих правил, если либо  1)схема грамматики не содержит аннулирующих правил,  2)либо схема грамматики содержит только одно правило вида <I>$, где <I> - начальный символ грамматики, и символ I не встречается в правых частях остальных правил грамматики.

Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.

Утверждение. Для каждой КС-грамматики Г', содержащей аннулирующие правила, можно  построить эквивалентную ей неукорачивающую грамматику Г, такую что L(Г')=L(Г).

Построение неукорачивающей грамматики предполагает увеличение числа правил заданной грамматики путем построения дополнительных правил, получаемых в результате исключения нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики. Если же в грамматике есть правило вида <I> $ и символ <I> входит в правые части других правил грамматики, то следует ввести новый начальный символ <I'> и заменить правило <I>$ двумя новыми правилами: <I'>$ и <I'><I> . В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие  правила из следующей грамматики:

                                                       Г_{2. 3} :       R = { <I>  a<I>b<I>,                                                                                <I>  b<I>a<I>,                                                                                <I>    $ }Выполняя все возможные замены символа I в первом правиле грамматики, получаем четыре правила вида:

<I>  a<I>b<I>,   <I>  ab<I>,    <I> a<I>b,    <I> ab .

Поступая аналогично со вторым правилом, имеем:  

<I> b<I>a<I>,    <I> ba<I>,    <I>  b<I>a,    <I>  ba.

Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило <I> $ правилами вида <I'>$  и  <I'><I> . Построенная совокупность правил образует схему искомой неукорачивающей грамматики. Все приведенные выше преобразования грамматик могут быть использованы и оказаться полезными при построении как конечных, так и магазинных автоматов.

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

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

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

 

Определение.Магазинный автоматМ определяется следующей совокупностью     семи объектов:            M={P , S , sо , f , F , H , hо },

где          P - входной алфавит,          S - алфавит состояний,          s_о- начальное состояние,          s_о  S ,          F- множество конечных состояний ,F является подмножеством S,          H- алфавит магазинных символов, записываемых на вспомогательную ленту,          h_о- маркер дна, он всегда записывается на дно магазина , h_о    H,           f - функция переходов           f : {P  {}} x S x HS x H* ,            если М-автомат - детерминированный, и           f:{P  {}} x S x HM(S x H*) ,            если М-автомат - недетерминированный.

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

f⁰( s, h) = ( s', ),

которая, независимо от того какой символ находится под читаюшей гловкой входной ленты, предписывает прочитать символ h из вершины магазина, изменить состояние автомата на s' и записать цепочку в магазин. 2)функция переходов с определенным входным символом:

f*( s, ah) = ( s', ),

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