Автоматы с магазинной памятью

АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ

 

 

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

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

На рис. 1

такой преобразователь.   Конечное  управляющее устройство снабжается дополнительной управляющей  головкой, всегда указывающей на   

верхнюю ячейку магазинной памяти; за один такт работы автомата  (преобразователя)   управляющая головка может произвести следующие движения:           

1) стереть  символ из верхней ячейки (при  этом все символы, находящиеся  на рабочей ленте, перемещаются  на  одну  ячейку вверх);                                                       

   2) стереть   символ  из  верхней ячейки  и записать  на рабочую ленту непустую цепочку символов (при этом содержимое

рабочей  ленты  сдвигается вниз ровно настолько,  какова длина

с   записываемой цепочки).

Таким образом, устройство магазинной памяти можно  сравнить с устройством магазина боевого автомата: когда в него вкладывается патрон, те, которые уже  были внутри, проталкиваются вниз; достать можно только патрон, вложенный последним.

Формально детерминированный магазинный автомат определяется как следующая совокупность объектов:

M = (V, Q, V_M, δ, q₀, z₀, F),

 

 где V, Q, q_{0 Є} Q, F определяются так же, как и для конечного автомата;

V_M = {z₀, z₁,…,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₁, γ₁),…,(q_m, γ_m),

где q, q₁,…q_m Є Q, a Є V, z Є V_M, γ₁,…,γ_m Є V^*_m

 

При этом считается, что если на входе читающей головки  авто 
мата находится символ а, автомат находится в состоянии q, а верхний символ рабочей ленты z, то автомат может перейти к состоянию q_i, записав при этом на рабочую ленту цепочку  γ_i(1 ≤ i ≤ m) 
вместо символа z, передвинуть входную головку на один символ 
вправо так, как это показано на рис. 1, и перейти в состояние q_i. Крайний левый символ γ_i должен при этом оказаться в верхней  
ячейке магазина. Команда (q, e, z)→(q₁, γ₁),…, (q_m, γ_m) означает, 
что независимо от входного символа и, не передвигая входной го- + 
ловки, автомат перейдет в состояние q_i, заменив символ z магазина  
на цепочку γ_i(1 ≤ i ≤ m). •

Ситуацией магазинного автомата называется пара (q, γ), где

q Є Q, γ Є V^*_m. Между ситуациями магазинного автомата (q, γ) и

(q’, γ’),  устанавливается отношение, обозначаемое символом ├, если среди команд найдется такая, что

(q, a, z)→(q₁, γ₁),…,(q_m, γ_m),

причем γ = zβ, γ’ = γ_iβ q' = q_i для некоторого 1 ≤ i ≤ m (z Є V_m,

β Є V^*_m  ).

Говорят, что  магазинный автомат переходит из состояния (q, γ) в состояние (q’, γ’) и обозначают это следующим образом:

a: (q, γ)├ (q’, γ’).

 Вводится  и такое обозначение:

a₁...a_n: (q, γ)├ _* (q’, γ’),

если справедливо, что

a_i: (q_i, γ_i)├ (q_i+1, γ_i+1), 1 ≤ i ≤ m

где

a_i Є V, γ₁ = γ, γ₂,…, γ_n+1 = γ’ Є V^*_m 

q₁ = q, q₂,…, q_n+1 = q’ Є Q 

Существует  два способа определения языка, допускаемого магазинным  автоматом.   Согласно   первому  способу  считается,   что входная цепочка α Є V* принадлежит языку L₁ (M) тогда, когда после просмотра последнего символа,  входящего в эту цепочку,

в магазине автомата М будет находиться пустая цепочка ε. Другими словами,

L₁ (M) = { α | α: (q₀, z₀) ├ _* (q, ε)}

где q Є Q.

Согласно  второму способу считается, что входная цепочка принадлежит языку L₂ (M) тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М окажется в одном из своих заключительных состояний q_f Є F. Другими словами,

L₂ (M) = { α | α: (q₀, z₀) ├ _* (q_f, γ)}

где γ Є V^*_m, q_f Є F 

Доказано, что  множество языков, допускаемых произвольными  магазинными автоматами согласно первому  способу, совпадает с множеством языков, допускаемых согласно второму  способу.

Доказано  также, что если L (G₂) — бесконтекстный язык, порождаемый Грамматикой G₂ = (Vx, V_T, Р, S), являющейся нормальной формой Грейбах, произвольной бесконтекстной грамматики G, то существует недетерминированный магазинный автомат М такой, что L₁ (M) = L (G₂). При этом

M = (V, Q, V_m , δ, q₀, z₀, 0),

Где V=V_T; Q={q₀}; V_M=V_N; z₀=S

а для каждого  правила G₂ вида

A→aα, a Є V_T, a Є V^*_n

строится  команда отображения δ:

(q₀, a, A)→(q₀, a)

Apia логично для любого недетерминированного магазинного автомата М, допускающего язык L₁ (M), можно построить бесконтекстную грамматику G такую, что L (G) = L₁ (M).

Если для конечных автоматов  детерминированные и недетерминированные модели эквивалентны по отношению к классу допускаемых языков, то этого нельзя сказать для магазинных автоматов. Детерминированные автоматы с магазинной памятью допускают лишь некоторое подмножество бесконтекстных языков, которые называют детерминированными бесконтекстными языками.