АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ
  Автоматы и преобразователи с магазинной памятью играют важную роль при
построении автоматно-лингвистических моделей различного назначения,
связанных с использованием бесконтекстных (контекстно-свободных) языков. В
частности, такие устройства используются в большинстве работающих программ
для синтаксического анализа программ, написанных на различных языках
программирования, которые во многих случаях можно рассматривать как
бесконтекстные.
  В отличие от конечных автоматов и преобразователей,
автоматы с магазинной памятью снабжены дополнительной магазинной памятью
(рабочей лентой).
На рис. 1
|                                            |
такой преобразователь.   Конечное  управляющее устройство снабжается
дополнительной управляющей головкой, всегда указывающей на
верхнюю ячейку магазинной памяти; за один такт работы автомата
(преобразователя)   управляющая головка может произвести следующие
движения:
  1) стереть символ из верхней ячейки (при этом все символы, находящиеся на
рабочей ленте, перемещаются на  одну  ячейку вверх);
   2) стереть   символ  из  верхней ячейки  и записать  на рабочую ленту
непустую цепочку символов (при этом содержимое
рабочей  ленты сдвигается вниз ровно настолько,  какова длина
с   записываемой цепочки).
  Таким образом, устройство магазинной памяти можно сравнить  с  устройством
магазина боевого автомата: когда в него  вкладывается  патрон,  те,  которые
уже  были  внутри,  проталкиваются  вниз;  достать  можно   только   патрон,
вложенный последним.
  Формально детерминированный магазинный автомат определяется как  следующая
совокупность объектов:
                        M = (V, Q, VM, ?, q0, z0, F),
   где V, Q, q0 Є Q, F определяются так же, как и для конечного автомата;
  VM = {z0, z1,…,zp-1} — алфавит магазинных символов автомата;
  ? — функция, отображающая множество Q X (V U { ? }) X VM
в множество Q X VM, где е — пустая цепочка;
  z0 Є VM — так называемый граничный маркер,  т. е.  символ,
первым появляющийся в магазинной памяти.
  Недетерминированный магазинный автомат  отличается  от  детерминированного
только тем, что функция ? отображает множество Q X (V U  {  ?  })  X  VM.  в
множество конечных подмножеств Q x VM
  Как и в случае конечных автоматов, преобразователи  с  магазинной  памятью
отличаются от автоматов с магазинной памятью наличием выходной ленты.
  Далее будем рассматривать только недетерминированные магазинные автоматы.
  Рассмотрим  интерпретацию функции ? для   такого   автомата.  Эту  функцию
можно представить совокупностью команд вида
                       (q, a, z)>(q1, ?1),…,(qm, ?m),
               где q, q1,…qm Є Q, a Є V, z Є VM, ?1,…,?m Є V*m
  При этом считается, что если на входе читающей головки авто
мата находится символ а, автомат находится в состоянии q, а верхний символ
рабочей ленты z, то автомат может перейти к состоянию qi, записав при этом
на рабочую ленту цепочку  ?i(1 ? i ? m)
вместо символа z, передвинуть входную головку на один символ
вправо так, как это показано на рис. 1, и перейти в состояние qi. Крайний
левый символ ?i должен при этом оказаться в верхней
ячейке магазина. Команда (q, e, z)>(q1, ?1),…, (qm, ?m) означает,
что независимо от входного символа и, не передвигая входной го- +
ловки, автомат перейдет в состояние qi, заменив символ z магазина
на цепочку ?i(1 ? i ? m).    •
  Ситуацией магазинного автомата называется пара (q, ?), где
  q Є Q, ? Є V*m. Между ситуациями магазинного автомата (q, ?) и
  (q’, ?’),  устанавливается отношение, обозначаемое символом +, если среди
команд найдется такая, что
                       (q, a, z)>(q1, ?1),…,(qm, ?m),
  причем ? = z?, ?’ = ?i? q' = qi для некоторого 1 ? i ? m (z Є Vm,
  ? Є V*m  ).
  Говорят, что магазинный автомат переходит из состояния (q, ?) в  состояние
(q’, ?’) и обозначают это следующим образом:
                            a: (q, ?)+ (q’, ?’).
   Вводится и такое обозначение:
                        a1…an: (q, ?)+ * (q’, ?’),
  если справедливо, что
                    ai: (qi, ?i)+ (qi+1, ?i+1), 1 ? i ? m
  где
                    ai Є V, ?1 = ?, ?2,…, ?n+1 = ?’ Є V*m
                         q1 = q, q2,…, qn+1 = q’ Є Q
  Существует два способа определения языка, допускаемого магазинным
автоматом.   Согласно   первому  способу  считается,   что входная цепочка
? Є V* принадлежит языку L1 (M) тогда, когда после просмотра последнего
символа,  входящего в эту цепочку,
в магазине автомата М будет находиться пустая цепочка ?. Другими словами,
                   L1 (M) = { ? | ?: (q0, z0) + * (q, ?)}
  где q Є Q.
  Согласно второму способу считается, что входная цепочка принадлежит  языку
L2 (M) тогда, когда после просмотра  последнего  символа,  входящего  в  эту
цепочку, автомат М окажется в одном из своих заключительных состояний  qf  Є
F. Другими словами,
                   L2 (M) = { ? | ?: (q0, z0) + * (qf, ?)}
  где ? Є V*m, qf Є F
  Доказано, что  множество  языков,  допускаемых  произвольными  магазинными
автоматами  согласно  первому  способу,  совпадает  с   множеством   языков,
допускаемых согласно второму способу.
  Доказано также,  что  если  L  (G2)  —  бесконтекстный  язык,  порождаемый
Грамматикой G2 = (Vx, VT,  Р,  S),  являющейся  нормальной  формой  Грейбах,
произвольной бесконтекстной грамматики G, то существует  недетерминированный
магазинный автомат М такой, что L1 (M) = L (G2). При этом
                       M = (V, Q, Vm , ?, q0, z0, 0),
Где V=VT; Q={q0}; VM=VN; z0=S
а для каждого правила G2 вида
                            A>a?, a Є VT, a Є V*n
  строится команда отображения ?:
                             (q0, a, A)>(q0, a)
  Apia логично  для  любого  недетерминированного  магазинного  автомата  М,
допускающего язык  L1  (M),  можно  построить  бесконтекстную  грамматику  G
такую, что L (G) = L1 (M).
  Если для конечных автоматов детерминированные и недетерминированные модели
эквивалентны по отношению к классу допускаемых языков, то этого нельзя
сказать для магазинных автоматов. Детерминированные автоматы с магазинной
памятью допускают лишь некоторое подмножество бесконтекстных языков,
которые называют детерминированными бесконтекстными языками.
                      Список использованной литературы
  КУЗИН Л.Т «Основы кибернетики» Т.2
                         УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ
                     ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
                                Р Е Ф Е Р А Т
                      По дискретной математике на тему:
                       «Автоматы с магазинной памятью»
                                              Подготовил студент гр. 1киб-30
                                                    Кирчатов Роман Романович
                                                               Преподаватель
                                              Бразинская Светлана Викторовна
                            ДНЕПРОПЕТРОВСК, 2002