Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

Автоматы с магазинной памятью



 Другие рефераты
Реактивные двигатели, устройство, принцип работы Сатурн. Мир ледяных лун Советские авиационные конструкторы А.М.Люлька и Н.Д.Кузнецов Спутниковая система ГЛОНАСС

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

автоматы с магазинной памятью снабжены дополнительной магазинной памятью
(рабочей лентой).
На рис. 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

скачать работу


 Другие рефераты
Литература XIX века
Ер Жәнібек
Оценка эффективности инновационного проекта
Организация управления проектами


 

Отправка СМС бесплатно

На правах рекламы


     ZERO.kz          
 
Модератор сайта RESURS.KZ