АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ
Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматривать как бесконтекстные.
В отличие от конечных автоматов и преобразователей
,автоматы с магазинной памятью
снабжены дополнительной магазинной памятью (рабочей лентой).
На рис. 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
)→(
q
1
,
γ
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
&#
' = 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
q
1
=
q
,
q
2
,…,
qn
+1
=
q
’ Є
Q
Существует два способа определения языка, допускаемого магазинным автоматом. Согласно первому способу считается, что входная цепочка α
Є
V
*
принадлежит языку L
1
(
M
)
тогда, когда после просмотра последнего символа, входящего в эту цепочку,
в магазине автомата М
будет находиться пустая цепочка ε
. Другими словами,
L1
(M) = {
α
|
α
: (q0
, z0
) ├
*
(q,
ε
)}
где q
Є
Q
.
Согласно второму способу считается, что входная цепочка принадлежит языку L
2
(
M
)
тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М
окажется в одном из своих заключительных состояний q
f
Є
F
. Другими словами,
L
2
(
M
) = { α | α: (
q
0
,
z
0
) ├
*
(
qf
,
γ
)}
где γ
Є
V
*
m
,
qf
Є
F
Доказано, что множество языков, допускаемых произвольными магазинными автоматами согласно первому способу, совпадает с множеством языков, допускаемых согласно второму способу.
Доказано также, что если L
(
G
2
)
— бесконтекстный язык, порождаемый Грамматикой G2
= (
Vx
,
VT
,
Р,
S
)
, являющейся нормальной формой Грейбах, произвольной бесконтекстной грамматики G
, то существует недетерминированный магазинный автомат М такой, что L
1
(
M
) =
L
(
G
2
).
При этом
M = (V, Q, Vm
, δ, q0
, z0
, 0),
ГдеV=VT
; Q={q0
}; VM
=VN
; z0
=S
а для каждого правила G
2
вида
A→a
α
, a
Є
VT
, a
Є
V*
n
строится команда отображения δ
:
(q0
, a, A)→(q0
, a)
Apia логично для любого недетерминированного магазинного автомата М
, допускающего язык L
1
(
M
)
, можно построить бесконтекстную грамматику G
такую, что L
(
G
) =
L
1
(
M
).
Если для конечных автоматов детерминированные и недетерминированные модели эквивалентны по отношению к классу допускаемых языков, то этого нельзя сказать для магазинных автоматов. Детерминированные автоматы с магазинной памятью допускают лишь некоторое подмножество бесконтекстных языков, которые называют детерминированными бесконтекстными языками.
Список использованной литературы
КУЗИН Л.Т «Основы кибернетики» Т.2
УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ
ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
Р Е Ф Е Р А Т
По дискретной математике на тему:
«Автоматы с магазинной памятью»
Подготовил студент гр. 1киб-30
Кирчатов Роман Романович
Преподаватель
Бразинская Светлана Викторовна
ДНЕПРОПЕТРОВСК, 2002