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

Недетерминированный магазинный автомат - это недетерминированный конечный автомат, вид функции перехода которого зависит от содержимого вершины некоторого стека. В недетерминированной конечном автомате набор возможных состояний определяется текущим состоянием, входным алфавитом и символом, который может быть извлечен из некоторого стека. При переходе недетерминированного магазинного автомата из одного состояния в другое, в стек может быть занесено произвольное конечное число некоторых символов.

Магазинным автоматом называется автомат:

M= (Q, U, Г, d, q₀, Z₀, F), где

Q - конечное множество символов состояний автомата,

U - конечный входной алфавит,

Г - конечный алфавит магазинных символов,

d - переходная функция d: Q´{VÈ{e}}´Г® Q´Г,

q₀ÎQ - начальное состояние,

Z₀ÎГ - начальный магазинный символ,

FÌQ - некоторое подмножество состояний автомата, которые называются заключительными состояниями.

Конфигурацией автомата называется множество троек

(q, w, a)Î Q´{VÈ{e}}´Г, где

q - текущее состояние автомата,

w - неиспользованная часть входной цепочки. Первый символ этой цепочки просматривается входной головкой автомата. Если w= {e}, значит входной символ прочитан,

a - содержимое магазина (стека). Если a= {e}, магазин пустой.

Конфигурация (q, aw, za) |- (q', w, ga), символ |- читается как «переходит в конфигурацию».

Если g= e, то верхний символ удаляется из магазина и магазинная цепочка сокращается.

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

Следующий такт работы невозможен, если магазин пуст: (q₀, w, z₀).

Заключительное состояние автомата (q, e, a), если qÎF.

Цепочка w допускается магазинным автоматом, если из начальной конфигурации за конечное число таков работы автомат перейдет в заключительное состояние: (q, w, z₀)|-*(q, e, a).

Если P - автомат, то L(P) - язык, определяемый P.

Пример: L={0ⁿ1ⁿ | n³0}

Определим автомат P= ({q₀, q₁, q₂}, {0,1}, {z, 0}, d, q, z, {q₀})

d(g_0, 0, z)= {(g₁, 0z)}

d(g_1, 0, 0)= {(g₁, 00)}

d(g_1, 1, 0)= {(g₂, e)} e означает, что символ просто снимается со стека

d(g_2, 1, 0)= {(g₂, e)}

d(g_1, e, z)= {(g₀, e)}

Пусть на вход поступила цепочка 0011. Как будет выглядеть работа автомата:

(g_0, 0011, z) |- (g_1, 011, 0z) |- (g_1, 11, 00z) |- (g_2, 1, 0z) |- (g_2, e, z) |-(g_2, e, e)

Вопросы и упражнения

1. Что понимают под конфигурацией автомата?