НАУЧНАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Автоматы с магазинной памятью

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

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

Автоматы и преобразователи с магазинной памятью играют важную роль при

построении автоматно-лингвистических моделей различного назначения,

связанных с использованием бесконтекстных (контекстно-свободных) языков. В

частности, такие устройства используются в большинстве работающих программ

для синтаксического анализа программ, написанных на различных языках

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

бесконтекстные.

В отличие от конечных автоматов и преобразователей,

автоматы с магазинной памятью снабжены дополнительной магазинной памятью

(рабочей лентой).

На рис. 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) тогда, когда после просмотра последнего

символа, входящего в эту цепочку,

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

L1 (M) = ?: (q0, z0) + * (q, ?)

где q Є Q.

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

L2 (M) тогда, когда после просмотра последнего символа, входящего в эту

цепочку, автомат М окажется в одном из своих заключительных состояний qf Є

F. Другими словами,

L2 (M) = ?: (q0, z0) + * (qf, ?)

где ? Є V*m, qf Є 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 Є VT, a Є V*n

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

(q0, a, A)>(q0, a)

Apia логично для любого недетерминированного магазинного автомата М,

допускающего язык L1 (M), можно построить бесконтекстную грамматику G

такую, что L (G) = L1 (M).

Если для конечных автоматов детерминированные и недетерминированные модели

эквивалентны по отношению к классу допускаемых языков, то этого нельзя

сказать для магазинных автоматов. Детерминированные автоматы с магазинной

памятью допускают лишь некоторое подмножество бесконтекстных языков,

которые называют детерминированными бесконтекстными языками.

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

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

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

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

Р Е Ф Е Р А Т

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

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

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

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

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

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

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