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

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

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

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

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

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