Реферат: Автоматы с магазинной памятью
Автоматы и преобразователи смагазинной памятью играют важную роль при построении автоматно-лингвистическихмоделей различного назначения, связанных с использованием бесконтекстных(контекстно-свободных) языков. В частности, такие устройства используются вбольшинстве работающих программ для синтаксического анализа программ,написанных на различных языках программирования, которые во многих случаяхможно рассматривать как бесконтекстные.
В отличие отконечных автоматов и преобразователей,
автоматы с магазинной памятью снабжены дополнительной магазинной памятью(рабочей лентой).
Нарис. 1
такойпреобразователь. Конечное управляющее устройство снабжается дополнительнойуправляющей головкой, всегда указывающей на
верхнююячейку магазинной памяти; за один такт работы автомата (преобразователя) управляющая головка может произвести следующие движения:
1)стереть символ из верхней ячейки (при этом все символы, находящиеся на рабочейленте, перемещаются на одну ячейку вверх);
2) стереть символ из верхней ячейки изаписать на рабочую ленту непустую цепочку символов (при этом содержимое
рабочей ленты сдвигается вниз ровно настолько, какова длина
с записываемой цепочки).
Таким образом, устройство магазиннойпамяти можно сравнить с устройством магазина боевого автомата: когда в неговкладывается патрон, те, которые уже были внутри, проталкиваются вниз; достатьможно только патрон, вложенный последним.
Формально детерминированныймагазинный автомат определяется как следующая совокупностьобъектов:
M =(V, Q, VM, δ, q0, z0,F),
где V, Q, q0Є Q, Fопределяются так же, как и для конечного автомата;
VM = {z0, z1,…,zp-1} — алфавит магазинных символов автомата;
δ — функция, отображающаямножество QX(VU{ε}) XVM
в множество QXVM, гдее — пустая цепочка;
z0Є VM — так называемый граничный маркер, т. е. символ,
первым появляющийся в магазинной памяти.
Недетерминированный магазинный автоматотличается от детерминированного только тем, что функция δ отображает множество QX(VU{ε}) XVM. вмножество конечных подмножеств QxVM
Как и в случае конечных автоматов,преобразователи с магазинной памятью отличаются от автоматов с магазинной памятьюналичием выходной ленты.
Далее будем рассматривать тольконедетерминированные магазинные автоматы.
Рассмотрим интерпретацию функции δдля такого автомата. Эту функцию можно представить совокупностью команд вида
(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) = { α | α: (q, z) ├ * (qf, γ)}
где γЄ V*m, qf<sub/>Є 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<sub/>ЄVT,a ЄV*n
строится команда отображения δ:
(q0, a,A)→(q0, a)
Apiaлогично для любого недетерминированного магазинного автомата М,допускающего язык L1(M), можно построить бесконтекстнуюграмматику G такую, что L(G) = L1(M).
Если для конечных автоматов детерминированные инедетерминированные модели эквивалентны по отношению к классу допускаемыхязыков, то этого нельзя сказать для магазинных автоматов. Детерминированныеавтоматы с магазинной памятью допускают лишь некоторое подмножествобесконтекстных языков, которые называют детерминированными бесконтекстнымиязыками.
Список использованной литературы
КУЗИН Л.Т «Основы кибернетики» Т.2
УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ
ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
Р Е Ф Е Р А Т
По дискретнойматематике на тему:
«Автоматы смагазинной памятью»
Подготовил студент гр. 1киб-30
Кирчатов Роман Романович
Преподаватель
Бразинская Светлана Викторовна
ДНЕПРОПЕТРОВСК, 2002