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

АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮАвтоматы и преобразователи с магазинной памятью играют важную роль припостроении автоматно-лингвистических моделей различного назначения, связанных сиспользованием бесконтекст ных контекстно-свободных языков.В частности,такие устройства используются в большинстве работающих программ длясинтаксического анализа программ, написанных на различных языкахпрограммирования, которые во многих случаях можно рассматри вать какбесконтекстные.В отличие отконечных автоматов и преобразователей,автоматы с магазинной памятью снабжены дополнительной магазинной памятью рабочей лентой .На рис. 1 такой преобразователь.

Конечное управляющее устройствоснабжается дополнительной управляющей головкой, всегда указывающей на верхнюю ячейку магазинной памяти за один такт работыавтомата преобразователя управляющая головка может произвестиследующие движения 1 стереть символ из верхней ячейки при этом все символы, находящиеся на рабочей ленте, перемещаются на одну ячейку вверх 2 стереть символ из верхней ячейки и записать на рабочую ленту непустую цепочкусимволов при этом содержимоерабочей лентысдвигается вниз ровно настолько, каковадлинас записываемойцепочки .Таким образом,устройство магазинной памяти можно сравнить с устройством магазина боевогоавтомата когда в него вкладывается патрон, те, которые уже были внутри,проталкиваются вниз до стать можно только патрон, вложенный последним.Формальнодетерминированный магазинный автомат определя ется как следующаясовокупность объектов M V, Q, VM, 948 , q0, z0,F , где V, Q, q0 Q, F определяются так же, как и для конечного автомата VM z0, z1, ,zp-1 алфавит магазинных символов авто мата 948 функция, отображающая множество Q X V U 949 X VMв множество Q X VM, где е пустая цепочка zVM такназываемый граничный маркер, т. е. символ,первым появляющийся в магазинной памяти.

Недетерминированныймагазинный автомат отличается от де терминированноготолько тем, что функция 948 отображает множество Q X V U 949 X VM. вмножество конечных подмножеств Q x VMКак и в случаеконечных автоматов, преобразователи с магазинной памятью отличаются отавтоматов с магазинной памятью нали чием выходной ленты.Далее будемрассматривать только недетерминированные магазин ные автоматы.Рассмотрим интерпретацию функции 948 для такого автомата. Эту функциюможно представить совокупностью команд вида q, a, z 8594 q1, 947 1 qm, 947 m ,где q, q1, qm Q, a V, z VM, 947 1 947 m V m При этом считается,что если на входе читающей головки авто мата находится символ а, автомат находится в состоянии q, а верхний символ рабочей ленты z, то автомат может перейти ксостоянию qi, записав при этом на рабочую ленту цепочку 947 i 1 8804 i 8804 m вместо символа z,передвинуть входную головку на один символвправо так, как это показано на рис. 1, и перейти в состояние qi.Крайний левый символ 947 i должен при этом оказаться в верхней ячейке магазина.

Команда q, e, z 8594 q1, 947 1 qm, 947 m означает,что независимо от входного символа и, не передвигая входной го- ловки, автомат перейдет в состояние qi, заменив символ z магазина на цепочку 947 i 1 8804 i 8804 m . Ситуацией магазинного автомата называется пара q, 947 , где q Q, 947 V m. Между ситуациями магазинного автомата q, 947 и q , 947 , устанавливается отношение, обозначаемоесимволом 9500 , если среди команд найдется такая, что q,a, z 8594 q1, 947 1 qm, 947 m ,причем 947 z 946 , 947 947 i 946 q qi для некоторого 1 8804 i 8804 m z Vm, 946 V m .Говорят,что магазинный автомат переходит из состояния q, 947 в состояние q , 947 и обозначают этоследующим образом a q, 947 9500 q , 947 . Вводится и такое обозначение a1 an q, 947 9500 q , 947 , если справедливо, чтоai qi, 947 i 9500 qi 1, 947 i 1 ,1 8804 i 8804 mгдеai V, 947 1 947 , 947 2 947 n 1 947 V m q1 q, q2 qn 1 q Q Существует два способа определенияязыка, допускаемого ма газинным автоматом. Согласно первому способу считается, что входная цепочка 945 V принадлежит языку L1 M тогда, когда после просмотра последнего символа, входящего в эту цепочку,в магазине автомата М будет находиться пустаяцепочка 949 . Другими словами,L1 M 945 945 q0, z0 9500 q, 949 где q Q.Согласновторому способу считается, что входная цепочка при надлежит языку L2 M тогда, когда послепросмотра последнего символа, входящего в эту цепочку, автомат Мокажется в одном из своих заключительных состояний qf F. Другими словами,L2 M 945 945 q0, z0 9500 qf, 947 где 947 V m, qf F Доказано, что множествоязыков, допускаемых произвольными магазинными автоматами согласно первомуспособу, совпадает с множеством языков, допускаемых согласно второму способу.

Доказанотакже, что если L G2 бесконтекстныйязык, по рождаемый Грамматикой G2 Vx, VT, Р, S , являющейся нормаль нойформой Грейбах, произвольной бесконтекстной грамматики G, то существует недетерминированныймагазинный автомат М такой, что L1 M L G2 . При этомM V, Q, Vm , 948 , q0, z0, 0 ,Где V VT Q q0 VM VN z0 Sа для каждого правила G2 видаA 8594 a 945 , a VT, a V nстроится командаотображения 948 q0, a, A 8594 q0,a Apia логично для любого недетерминированного магазинногоавтомата М, допускающего язык L1 M ,можно построить бескон текстную грамматику G такую, что L G L1 M .Если для конечных автоматов детерминированные инедетерми нированные модели эквивалентны по отношению к классу допускае мыхязыков, то этого нельзя сказать для магазинных автоматов. Детерминированныеавтоматы с магазинной памятью допускают лишь некоторое подмножествобесконтекстных языков, которые называют детерминированными бесконтекстнымиязыками.Списокиспользован ной литературы КУЗИН Л.Т Основы кибернетики Т.2 УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ Р Е Ф Е Р А ТПо дискретнойматематике на тему Автоматы смагазинной памятью Подготовил студент гр. 1киб-30Кирчатов Роман Романович Преподаватель Бразинская Светлана Викторовна ДНЕПРОПЕТРОВСК, 2002.