Детерминированный магазинный автомат

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

Автомат с магазинной памятью (МПА)– это семерка

M = (Q, S, T, d, q ₀, Z ₀, F),

где Q = { q ₀, q ₂, …, q _n}– конечное множество состояний устройства управления (УУ);

= { a ₁, a ₂, …, a _k} – конечный входной алфавит;

T – конечный алфавит магазинных символов;

d – функция переходов, отображающая Q T во множество конечных подмножеств множества Q T^*;

q ₀ – начальное состояние устройства управления, q ₀ Î Q;

Z ₀ – начальный символ магазина, Z ₀ Î T;

F – множество заключительных состояний, F Í Q.

Автомат с магазинной памятью имеет две ленты: входную, которую можно только читать и которая содержит распознаваемую входную цепочку, и рабочую, содержащую магазинные символы, которые можно как читать, так и писать. Управляющее устройство находится в одном из состояний Q, устройство имеет две головки: одну для работы с входной лентой, другую – с рабочей, причем эта головка всегда указывает на верхнюю ячейку магазина. За один такт автомат может выполнить следующие действия над символами магазина:

q стереть символ из верхней ячейки магазина, при этом все символы магазина смещаются вверх на одну ячейку;

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

Ниже схематично изображен автоматс магазинной памятью

Рассмотрим интерпретацию функции d для автомата. Эта функция представляется совокупностью команд следующего вида:

d(q, a, Z) = {(q ₁, a₁), (q ₂, a₂), …,(q _n, a_n)},

где q, q₁, q₂, …, q_n Î Q, a ÎS, ZÎT, aÎ T^*.

При этом считается, что если на входе читающей головки автомата находится символ а, автомат находится в состоянии q, а верх­ний символ рабочей ленты Z, то автомат может перейти к состоянию q_i, записав при этом на рабочую ленту цепочку a_i(1 <i<n) вместо символа Z, передвинуть входную головку на один символ вправо. Крайний левый символ a_iдолжен при этом оказаться в верхней ячейке магазина. Команда

d(q, ε, Z) = {(q₁, a₁), (q₂, a₂), …,(q_n, a_n)}

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

перейдет в состояние q_i, заменив символ Z магазина на цепочку a_i(1 <i<n).

Конфигурацией МПА называется тройка (q, w, a)ÎQ S^* T^*,

где q Î Q – текущее состояние устройства управления;

w Î S^* – неиспользованная часть входной цепочки, первый символ которой находится под входной головкой; если w = ε, то считается, что вся входная лента прочитана;

a – содержимое магазина; самый левый символ цепочки a считается верхним символом магазина, если a= ε, то магазин считается пустым.

Такт работы автомата будем представлять в виде бинарного отношения ├, определенного на конфигурациях. Например, если d(q ₁, a, Z) содержит (q ₂, g), то, выполнив такт, автомат перейдет от конфигурации (q ₁, aw, Z a) к конфигурации (q ₂, w, ga), здесь q ₁, q ₂ Î Q, w Î S^*, a Î S, Z Î T, a, g Î T^*. Если а не пустой символ (a ¹ ε), то запись

(q ₁, aw, Z a) ├ (q ₂, w, ga)

говорит о том, что автомат, на­ходясь в состоянии q ₁ и имея а в качестве текущего входного символа, расположенного под входной головкой, a Z – в каче­стве верхнего символа магазина, может перейти в новое состоя­ние q ₂, сдвинуть входную головку на одну ячейку вправо и за­менить верхний символ магазина цепочкой gмагазинных символов. Если g = ε, то верхний символ удаляется из магазина, и тем самым магазинный список сокращается.

Если а = ε, будем называть этот такт ε - тактом. В ε-такте текущий входной символ не принимается во внимание и вход­ная головка не сдвигается. Однако состояние управляющего устройства и содержимое памяти могут измениться. Заметим, что ε-такт может происходить и тогда, когда вся входная цепочка прочитана. Если же магазин пуст, то следующий такт невозможен.

Начальной конфигурациейМПА называется конфи­гурация вида (q₀, w, Z ₀), где w Î S^*, т. е. управляющее устрой­ство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в магазине есть только начальный символ Z ₀. Заключительная конфигурация – это кон­фигурация вида (q, ε, a), где q ₂ Î Q, aÎ T^*.

Входная цепочка w допускается МПА, если найдется последовательность тактов, переводящая автомат из начальной конфигурации (q ₀, w, Z ₀) в заключительную (q_f, e, a), здесь q_f – некоторое заключительное состояние q _f Î F, a Î T^*, e - пустая цепочка, или по-другому:

(q₀, w, Z ₀) ├^*(q_f, ε, a).

Языком, определяемым (или допускаемым) автоматом Р (обозначается L (Р)), называют множество цепочек, допускаемых автоматом Р.

Рассмотрим детерминированный автомат c магазинной памятью М1, определяющий множество цепочек вида {0ⁿ1ⁿ | n ³ 0 }.

M1=({ q₀, q₁, q₂ }, {0, 1}, { Z, 0}, d, q₀, Z, { q₀ }),

где d имеет вид

d(q₀, 0, Z) = {(q₁, 0Z)}

d(q₁, 0, 0) = {(q₁, 00)}

d(q₁, 1, 0) = {(q₂, ε)}

d(q₂, 1, 0) = {(q₂, ε)}

d(q₂, , Z) = {(q₀, ε)}

Автомат сохраняет в магазине подцепочку, состоящую из нулей, затем выталкивает из магазина по одному нулю на каждую единицу, считанную с входной ленты. Пока автомат читает нули, он находится в состоянии q ₁, как только автомат сосчитает первую единицу, он попадает в состояние q ₂, появление нулей в этом состоянии запрещено автоматом.

Теперь мы слегка расширим определение МПА, по­зволив ему заменять за один такт цепочку символов ограничен­ной длины, расположенную в верхней части магазина, другой цепочкой конечной длины. Напомним, что МПА в перво­начальной версии мог на данном такте заменять лишь один верх­ний символ магазина.

Расширенным МПА назовем семерку

Р = (Q, S, T, d, q ₀, Z ₀, F),

где d - отображение конечного подмно­жества множества Q (S È {ε}) ´T^* во множество конечных подмножеств множества Q T^*, а все другие символы имеют тот же смысл, что и раньше.

Конфигурация определяется так же, как прежде, и мы пи­шем

(q ₁, aw, ag) ├ (q ₂, w, βg)

если d(q ₁, a, a) содержит (q ₂, β), где q ₁, q ₂ Î Q, w Î S^*, a Î S È {ε}, Z Î T, a, β, g Î T^*. В этом такте цепочка a, расположен­ная в верхней части магазина, заменяется цепочкой β. Как и прежде, языком L(P), определяемым автоматом Р, называется множество

{ w | (q₀, w, Z ₀) ├*(q_f, ε, a) для некоторых q _f Î F, a Î T^*}

Заметим, что в отличие от обычного МПА расширен­ный МПА обладает способностью продолжать работу и тогда, когда магазин пуст.

Пусть P = (Q, S, T, d, q ₀, Z ₀, F) -МПА или расширенный МПА. Будем говорить, что Р допускает цепочку w Î S^* опустошением магазина, если (q₀, w, Z ₀) ├⁺(q, ε, ε) для некоторого q Î Q. Пусть L_e(P) - множество цепочек, допус­каемых автоматом Р опустошением магазина.

Доказано, что если L (G2) - бесконтекстный язык, по­рождаемый грамматикой G2 = (N, S, P, S), находящейся в нормаль­ной форме Грейбах, то существует недетерминированный магазинный автомат М такой, что L_e(M) = L (G2). При этом

M = (Q, S, T, d, q ₀, Z ₀, Æ),

где алфавиты S в грамматике и автомате совпадают; Q ={ q ₀}, Z ₀ = S, T = N,

а d определяется следующим образом:

если A ® aa принадлежит множеству правил P грамматики G2, то d(q ₀, a, A) = (q ₀, a)

если A ® a принадлежит множеству правил P грамматики G2, то d(q ₀, a, A) = (q ₀, ε)

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

L_e(М).

Пример. Грамматика в нормальной форме Грейбах, порождающая язык L={0ⁿ1ⁿ| n 1} задается следующим образом: множество N = {S, A }, множество S = {0, 1},а множество продукций:

S 0SA

S 0A

A 1

Для этой грамматики построим соответствующий ей МПА M = (Q, S, T, d, q ₀, Z ₀, Æ),

где алфавит S={0, 1}, Q ={ q ₀}, T = {S, A }, Z ₀ = S,

d(q ₀, 0, S) = (q ₀, SA)

d(q ₀, 0, S) = (q ₀, A)

d(q ₀, 1, A) = (q ₀, ε)