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

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

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

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

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

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

Список использованной литературы

КУЗИН Л.Т «Основы кибернетики» Т.2

УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ

ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

Р Е Ф Е Р А Т

По дискретной математике на тему:

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

Подготовил студент гр. 1киб-30

Кирчатов Роман Романович

Преподаватель

Бразинская Светлана Викторовна

ДНЕПРОПЕТРОВСК, 2002