Распознающий автомат для кс- языков (автомат с магазинной памятью)

Для произвольной КС-грамматики может быть построен недетерминированный автомат с магазинной памятью, принимающий язык, порождаемый этой грамматикой.

Автоматы с магазинной памятью (МП-автоматы) представляют собой математическую модель синтаксических анализаторов КС-языков.

МП-автомат подобен КА, оснащенному дополнительным запоминающим устройством со стековой дисциплиной (последним пришел – первым ушел). Будем представлять магазин в виде цепочки символов, причем верхним элементом магазина будем считать самый левый символ цепочки. Модель автомата с магазинной памятью приведена на рисунке ниже:

Автоматом с магазинной памятью (МП-автоматом) называется семерка объектов P=(Q, S, Г, d, q₀, Z₀, F), где

Q – конечное множество состояний автомата

S - конечный алфавит входных символов

Г – конечный магазинный алфавит

d - функция переходов (магазинная функция), которая задает отображение множества Q´(S È {e})´Г в множество конечных подмножеств множества Q´Г*

q₀ ÎQ – начальное состояние автомата

Z₀ – начальный символ (дно) магазина, символ, который находится в магазине в начальный момент Z₀ Î Г

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

Конфигурацией МП-автомата Р называется тройка (q, x, a) Î (Q´ S* ´Г*), где

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

x – необработанная часть входной цепочки (первый символ цепочки х находится под входной головкой; если х=e, то считается что вся входная цепочка прочитана)

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

Такт работы МП-автомата будем описывать бинарным отношением (^), определенным на множестве конфигураций. Будем писать (q, aw, Z) ^(q’, w, ga), если

(q’, g) Î d(q, a, Z), где q, q’ ÎQ, a Î S È {e}, w Î S*, Z Î Г и a, g Î Г*

Если a¹e и входная цепочка прочитана на вся, то запись (q, aw, Aa)^(q’, w, ga) означает, что МП-автомат в состоянии q, обозревая символ входной цепочки a и имея символ A в верхушке магазина, может перейти в новое состояние q’, сдвинуть входную головку на один символ вправо и заменить символ магазина A цепочкой магазинных символов g. Если g=e, то верхний символ удаляется из магазина.

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

e-такты могут выполняться и в том случае, когда вся входная цепочка прочитана, но если магазин пуст, то очередной такт работы МП-автомата невозможен по определению.

Начальное конфигурацией МП-автомата называется конфигурация вида
(q0, w, Z₀), где устройство управления находится в начальном состоянии, на входной ленте записана цепочка w Î S*, которую необходимо распознать, а магазин содержит только начальный символ Z₀

Заключительной конфигурацией МП-автомата называется конфигурация вида (q, e, a), где q Î F – одно из заключительных состояний устройства управления, входная цепочка прочитана до конца, а в магазине записана некоторая, заранее определенная цепочка a Î Г*.

Говорят, что цепочка w Î S* допускается МП-автоматом Р=(Q, S, Г, d, q₀, Z₀, F), если (q0, w, Z₀) ^*(q, e, a) для некоторого q Î F и a Î Г*.

Языком, определяемым МП-автоматом Р, называется множество входных цепочек, допускаемых этим автоматом, т.е.

L(P)={w | w Î S* и (q0, w, Z₀) ^*(q, e, a) для некоторого q Î F и a Î Г*}

Пример. Определим МП-автомат Р, допускающий язык L={aⁿbⁿ | n³0 }

МП-автомат имеет следующий вид:

Р=({q0, q1, q2}, {a,b}, {Z,a}, d, q0, Z, {q2}),

в котором функция переходов определяется следующим образом:

1) d(q0, a, Z)={(q1,aZ)}	2) d(q1, a, a)={(q1,aa)}
3) d(q1, b, a)={(q2, e)}	4) d(q2, b, a)={(q2, e)}
5) d(q2, e, Z)={(q0, e)}

Работа МП-автомата состоит в том, что он сначала копирует префикс входной цепочки, состоящей из символов а, затем удаляет из магазина по одному символу а на каждый символ b, который читается с входной ленты. Например, для входной цепочки aaabbb МП-автомат выполнит следующую последовательность тактов:

(qo, aaabbb, Z) ├ ₍₂₎ (q1, aabbb, aZ) ├ ₍₂₎ (q1,aaabbb, aaZ) ├ ₍₂₎ (q1,bbb, aaaZ) ├ ₍₃₎
(q2, bb,aa Z) ├ ₍₄₎ (q2, b, aZ) ├ ₍₄₎ (q2, e, Z) ├ ₍₅₎ (q0, e, e )

Пример. Определим МП-автомат Р, допускающий язык L={ww^R | w Î{a, b}⁺}, где w^R – цепочка, реверсивная цепочке w.

МП-автомат имеет следующий вид:

Р=({q0, q1, q2}, {a,b}, {Z,a,b}, d, q0, Z, {q2}),

в котором функция переходов определяется следующим образом:

1) d(q0, a, Z)={(q0,aZ)}	2) d(q0, b, Z)={(q0, bZ)}
3) d(q0, a, a)={(q0, aa), (q1, e)}	4) d(q0, a, b)={(q0, ab)}
5) d(q0, b, a)={(q0, ba)}	6) d(q0, b, b)={(q0, bb), (q1, e)}
7) d(q1, a, a)={ (q1, e)}	8) d(q1, b, b)={ (q1, e)}
9) d(q1, e, Z)={ (q2, e)}

МП-автомат сначала копирует в магазине некоторую часть входной цепочки в соотвествии с функциями переходов (1), (2), (4) и (5) в зависимости от первых элементов множеств (3) и (6). Так как P – недетерминированный МП-автомат, то когда верхний символ магазина совпадает с текущим входным символом, он может в любой момент предположить, что в магазине записана цепочка w, перейти в состояние q1, используя вторые элементы множеств (3) и (6), и начать сравнивать цепочку в магазине с оставшейся частью входной цепочки (функции переходов (7) и (8)). Если МП-автомат обнаруживает несовпадение очередных символов, он осуществляет возврат в точку, где применялись функции перехода из альтернативного множества значений, и процесс анализа возобновляется. Если какой-либо выбор тактов приведет к тому, что символ Z окажется верхним и единственным символом магазина, то в соответствии с функцией перехода (9) этот символ удаляется из магазина и автомат переходит в заключительную конфигурацию (q2 e).

Таким образом, для любой конфигурации вида (q0, aw, aa) МП-автомат может сделать один из двух тактов: любо поместить в магазин еще один символ a, либо удалить из магазина верхний символ. Например, для входной цепочки abba МП-автомат Р может среди прочих выполнить следующие последовательности тактов:

(1) (q0, abba, Z) ├ (q0, bba, aZ) ├ (q0, ba, baZ) ├ (q0, a, bbaZ) ├ (q0, e, abbaZ) ├????

(2) (q0, abba, Z) ├ (q0, bba, aZ) ├ (q0, ba, baZ) ├ (q1, a, aZ) ├ (q1, e, Z) ├ (q2, e, e)

Поскольку последовательность тактов (2) заканчивается заключительной конфигурацией (q2, e, e), то МП-автомат Р допускает входную цепочку abba.

Дата добавления: 2014-01-03