Автоматы с магазинной памятью
АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ
Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстВнных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматриВнвать как бесконтекстные.
В отличие от конечных автоматов и преобразователей,автоматы с магазинной памятью снабжены дополнительной магазинной памятью (рабочей лентой).
На рис. 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
Вместе с этим смотрят:
Адаптивное параметрическое оценивание квадратно-корневыми информационными алгоритмамиАксиоматический методАксиомыАлгебра Дж. Буля и ее применение в информатике