|
такой
преобразователь. Конечное управляющее устройство снабжается дополнительной
управляющей головкой, всегда указывающей на
верхнюю
ячейку магазинной памяти; за один такт работы автомата (преобразователя)
управляющая головка может произвести следующие движения:
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