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

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

Файл : ref avtomat.doc (размер : 46,592 байт)

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

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

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

На рис. 1

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

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

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) тогда, когда после просмотра последнего символа, входящего в эту цепочку,