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

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

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

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

На рис. 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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--