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

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

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

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

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

На рис. 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 )→( q 1 , γ 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

q 1 = q , q 2 ,…, qn +1 = q ’ Є Q

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

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

L1 (M) = { α | α : (q0 , z0 ) ├ * (q, ε )}

где q Є Q .

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

L 2 ( M ) = { α | α: ( q 0 , z 0 ) ├ * ( qf , γ )}

где γ Є V * m , qf Є F

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

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

M = (V, Q, Vm , δ, q0 , z0 , 0),

ГдеV=VT ; Q={q0 }; VM =VN ; z0 =S

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

A→a α , a Є VT , a Є V* n

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

(q0 , a, A)→(q0 , a)

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

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

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

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

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

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

Р Е Ф Е Р А Т

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

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

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

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

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

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

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