РАСПОЗНАЮЩИЙ АВТОМАТ ДЛЯ КС- ЯЗЫКОВ (АВТОМАТ С МАГАЗИННОЙ ПАМЯТЬЮ)
Для произвольной КС-грамматики может быть построен недетерминированный автомат с магазинной памятью, принимающий язык, порождаемый этой грамматикой.
Автоматы с магазинной памятью (МП-автоматы) представляют собой математическую модель синтаксических анализаторов КС-языков.
МП-автомат подобен КА, оснащенному дополнительным запоминающим устройством со стековой дисциплиной (последним пришел – первым ушел). Будем представлять магазин в виде цепочки символов, причем верхним элементом магазина будем считать самый левый символ цепочки. Модель автомата с магазинной памятью приведена на рисунке ниже:
Автоматом с магазинной памятью (МП-автоматом) называется семерка объектов P=(Q, S, Г, d, q0, Z0, F), где
Q – конечное множество состояний автомата
S - конечный алфавит входных символов
Г – конечный магазинный алфавит
d - функция переходов (магазинная функция), которая задает отображение множества Q´( S È {e})´Г в множество конечных подмножеств множества Q´Г*
q0 ÎQ – начальное состояние автомата
Z0 – начальный символ (дно) магазина, символ, который находится в магазине в начальный момент Z0 Î Г
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, Z0), где устройство управления находится в начальном состоянии, на входной ленте записана цепочка w Î S*, которую необходимо распознать, а магазин содержит только начальный символ Z0
Заключительной конфигурацией МП-автомата называется конфигурация вида (q, e, a), где q Î F – одно из заключительных состояний устройства управления, входная цепочка прочитана до конца, а в магазине записана некоторая, заранее определенная цепочка a Î Г*.
Говорят, что цепочка w Î S* допускается МП-автоматом Р=(Q, S, Г, d, q0, Z0, F), если (q0, w, Z0) ^*(q, e, a) для некоторого q Î F и a Î Г*.
Языком, определяемым МП-автоматом Р, называется множество входных цепочек, допускаемых этим автоматом, т.е.
L(P)={w | w Î S* и (q0, w, Z0) ^*(q, e, a) для некоторого q Î F и a Î Г*}
Пример.Определим МП-автомат Р, допускающий язык L={anbn | 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) ├ (2) (q1, aabbb, aZ) ├ (2) (q1,aaabbb, aaZ) ├ (2) (q1,bbb, aaaZ) ├ (3)
(q2, bb,aa Z) ├ (4) (q2, b, aZ) ├ (4) (q2, e , Z) ├ (5) (q0, e , e )
Пример.Определим МП-автомат Р, допускающий язык L={wwR | w Î{a, b}+}, где wR – цепочка, реверсивная цепочке 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.