Автоматы с магазинной памятью
АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ
Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматривать как бесконтекстные.
В
отличие от конечных автоматов и
преобразователей,
автоматы с
магазинной памятью снабжены
дополнительной магазинной памятью
(рабочей лентой).
На рис. 1
верхнюю ячейку магазинной памяти; за один такт работы автомата (преобразователя) управляющая головка может произвести следующие движения:
1) стереть символ из верхней ячейки (при этом все символы, находящиеся на рабочей ленте, перемещаются на одну ячейку вверх);
2) стереть символ из верхней ячейки и записать на рабочую ленту непустую цепочку символов (при этом содержимое
рабочей ленты сдвигается вниз ровно настолько, какова длина
с записываемой цепочки).
Таким образом, устройство магазинной памяти можно сравнить с устройством магазина боевого автомата: когда в него вкладывается патрон, те, которые уже были внутри, проталкиваются вниз; достать можно только патрон, вложенный последним.
Формально детерминированный магазинный автомат определяется как следующая совокупность объектов:
M = (V, Q, V>M>, δ, q>0>, z>0>, F),
где V, Q, q>0> >Є> Q, F определяются так же, как и для конечного автомата;
V>M> = {z>0>, z>1>,…,z>p>>-1>} — алфавит магазинных символов автомата;
δ
— функция, отображающая множество Q
X
(V
U
{
ε
}) X
V>M>
в
множество Q
X
V>M>,
где е — пустая цепочка;
z>0>
>Є>
V>M>
—
так называемый граничный маркер, т. е.
символ,
первым появляющийся в магазинной
памяти.
Недетерминированный магазинный автомат отличается от детерминированного только тем, что функция δ отображает множество Q X (V U { ε }) X V>M>. в множество конечных подмножеств Q x V>M>
Как и в случае конечных автоматов, преобразователи с магазинной памятью отличаются от автоматов с магазинной памятью наличием выходной ленты.
Далее будем рассматривать только недетерминированные магазинные автоматы.
Рассмотрим интерпретацию функции δ для такого автомата. Эту функцию можно представить совокупностью команд вида
(q, a, z)→(q>1>, γ>1>),…,(q>m>, γ>m>),
где q, q>1>,…q>m> Є Q, a Є V, z Є V>M>, γ>1>,…,γ>m> Є V*>m>
При
этом считается, что если на входе читающей
головки авто
мата находится символ
а,
автомат находится в состоянии q,
а верхний символ рабочей ленты z,
то автомат может перейти к состоянию
q>i>,
записав при этом на рабочую ленту цепочку
γ>i>(1
≤ i
≤ m)
вместо
символа z,
передвинуть входную головку на один
символ
вправо так, как это показано
на рис. 1, и перейти в состояние q>i>.
Крайний левый символ γ>i>
должен при этом оказаться в верхней
ячейке магазина. Команда (q,
e,
z)→(q>1>,
γ>1>),…,
(q>m>,
γ>m>)
означает,
что независимо от входного
символа и, не передвигая входной го-
+
ловки, автомат перейдет в состояние
q>i>,
заменив символ z
магазина
на цепочку γ>i>(1
≤ i
≤ m). •
Ситуацией магазинного автомата называется пара (q, γ), где
q Є Q, γ Є V*>m>. Между ситуациями магазинного автомата (q, γ) и
(q’, γ’), устанавливается отношение, обозначаемое символом ├, если среди команд найдется такая, что
(q, a, z)→(q>1>, γ>1>),…,(q>m>, γ>m>),
причем γ = zβ, γ’ = γ>i>β q' = q>i> для некоторого 1 ≤ i ≤ m (z Є V>m>,
β Є V*>m> ).
Говорят, что магазинный автомат переходит из состояния (q, γ) в состояние (q’, γ’) и обозначают это следующим образом:
a: (q, γ)├ (q’, γ’).
Вводится и такое обозначение:
a>1>...a>n>: (q, γ)├ >*> (q’, γ’),
если справедливо, что
a>i>: (q>i>, γ>i>)├ (q>i+1>, γ>i+1>), 1 ≤ i ≤ m
где
a>i> Є V, γ>1> = γ, γ>2>,…, γ>n>>+1> = γ’ Є V*>m>
q>1> = q, q>2>,…, q>n>>+1> = q’ Є Q
Существует два способа определения языка, допускаемого магазинным автоматом. Согласно первому способу считается, что входная цепочка α Є V* принадлежит языку L>1> (M) тогда, когда после просмотра последнего символа, входящего в эту цепочку,
в магазине автомата М будет находиться пустая цепочка ε. Другими словами,
L>1> (M) = { α | α: (q>0>, z>0>) ├ >* >(q, ε)}
где q Є Q.
Согласно второму способу считается, что входная цепочка принадлежит языку L>2> (M) тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М окажется в одном из своих заключительных состояний q>f> Є F. Другими словами,
L>2> (M) = { α | α: (q>0>, z>0>) ├ >* >(q>f>, γ)}
где γ Є V*>m>, q>f>> >Є F
Доказано, что множество языков, допускаемых произвольными магазинными автоматами согласно первому способу, совпадает с множеством языков, допускаемых согласно второму способу.
Доказано также, что если L (G>2>) — бесконтекстный язык, порождаемый Грамматикой G>2> = (Vx, V>T>, Р, S), являющейся нормальной формой Грейбах, произвольной бесконтекстной грамматики G, то существует недетерминированный магазинный автомат М такой, что L>1> (M) = L (G>2>). При этом
M = (V, Q, V>m>
, δ, q>0>,
z>0>,
0),
Где V=V>T>; Q={q>0>}; V>M>=V>N>; z>0>=S
а для каждого правила G>2> вида
A→aα, a> >Є V>T>, a Є V*>n>
строится команда отображения δ:
(q>0>, a, A)→(q>0>, a)
Apia логично для любого недетерминированного магазинного автомата М, допускающего язык L>1> (M), можно построить бесконтекстную грамматику G такую, что L (G) = L>1> (M).
Если для конечных автоматов детерминированные и недетерминированные модели эквивалентны по отношению к классу допускаемых языков, то этого нельзя сказать для магазинных автоматов. Детерминированные автоматы с магазинной памятью допускают лишь некоторое подмножество бесконтекстных языков, которые называют детерминированными бесконтекстными языками.
Список использованной литературы
КУЗИН Л.Т «Основы кибернетики» Т.2
УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ
ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
Р Е Ф Е Р А Т
По дискретной математике на тему:
«Автоматы с магазинной памятью»
Подготовил студент гр. 1киб-30
Кирчатов Роман Романович
Преподаватель
Бразинская Светлана Викторовна
ДНЕПРОПЕТРОВСК, 2002