Реферат: Автоматы с магазинной памятью

Автоматы и преобразователи смагазинной памятью играют важную роль при построении автоматно-лингвистическихмоделей различного назначения, связанных с использованием бесконтекст­ных(контекстно-свободных) языков. В частности, такие устройства используются вбольшинстве работающих программ для синтаксического анализа программ,написанных на различных языках программирования, которые во многих случаяхможно рассматри­вать как бесконтекстные.

В отличие отконечных автоматов и преобразователей,
автоматы с магазинной памятью снабжены дополнительной магазинной памятью(рабочей лентой).

Нарис. 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≤ im).                                   •

Ситуациеймагазинного автомата называется пара (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

еще рефераты
Еще работы по математике