🗊Презентация Автоматы с магазинной памятью

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

Определение 14.21 Автомат с магазинной памятью – это односторонний недетерминированный распознаватель. Автомат с магазинной памятью является моделью синтаксического анализатора языка.

Q – конечное множество символов состояний, представляющих возможные состояния управляющего устройства; Q – конечное множество символов состояний, представляющих возможные состояния управляющего устройства;  - конечный входной алфавит (алфавит входной ленты); Г – конечный алфавит магазинных символов (алфавит рабочей памяти автомата);  - отображение множества Q  (  {})  Г в множество конечных подмножеств множества Q  Г* ( - функция переходов); q0  Q – начальное состояние управляющего устройства; z0  Г - символ, находящийся в магазине в начальный момент (начальный символ магазина); F  Q – множество заключительных состояний управляющего устройства.

В определении функции переходов запись (q, )  (q, a, Z) будет означать: В определении функции переходов запись (q, )  (q, a, Z) будет означать: если a  , то МП-автомат Р, находясь в состоянии q и имея a в качестве текущего входного символа, расположенного под входной головкой, а в качестве верхнего символа магазина - символ Z, может перейти в новое состояние q, сдвинуть входную головку на одну ячейку вправо и заменить верхний символ магазина цепочкой  магазинных символов; если а = , будем называть этот такт  –тактом; в  –такте текущий входной символ не принимается во внимание и входная головка не сдвигается, однако, состояние управляющего устройства и содержимое памяти могут измениться (заметим, что -такт может происходить и тогда, когда вся входная цепочка прочитана);

Определение 14.22 если  = , то верхний символ удаляется из магазина (магазинный список сокращается); следующий такт невозможен, если магазин пуст

 — неиспользованная часть входной цепочки; первый символ цепочки  находится под входной головкой; если =, то считается, что вся входная лента прочитана;  — неиспользованная часть входной цепочки; первый символ цепочки  находится под входной головкой; если =, то считается, что вся входная лента прочитана;  — содержимое магазина; самый левый символ цепочки  считается верхним символом магазина; если  = , то магазин считается пустым.

Определение 14.23 Начальной конфигурацией МП-автомата P называется конфигурация вида (q0, , Z0), где   *, (т. е. УУ находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в магазине есть только начальный символ Z0).

Определение 14.24 Заключительной конфигурацией МП-автомата P называется конфигурация вида: (q, , ), где q  F, .Г*.

Определение 14.26 Говорят, что цепочка  допускается МП –автоматом P, если (q0, , Z0)  Р* (q, , ) для некоторого q  F и   Г*.

Пример 14.3. Пример 14.3. Построим МП –автомат, определяющий язык L={0n1n | n0}. Пусть P=({q0, q1, q2}, {0, 1}, {Z, 0}, , q0, Z, {q0}), где (q0, 0, Z) = {(q1, 0Z)} (q1, 0, 0) = {(q1, 00)} (q1, 1, 0) = {(q2, )} (q2, 1, 0) = {(q2, )} (q2, , Z) = {(q0, )} Работа МП –автомата Р состоит в том, что он копирует в магазине начальную часть входной цепочки, состоящую из нулей, а затем устраняет из магазина по одному нулю на каждую единицу, которую он видит на входе. Кроме того, функция переходов гарантирует, что все нули предшествуют единицам.

Построим МП –автомат, определяющий язык L={wwR | w{0,1}+}. Построим МП –автомат, определяющий язык L={wwR | w{0,1}+}. Пусть P=({q0, q1, q2}, {0, 1}, {Z, 0,1}, , q0, Z, {q2}), где (q0, 0, Z) = {(q0, 0Z)} (q0, 1, Z) = {(q0, 1Z)} (q0, 0, 0) = {(q0, 00), (q1, )} (q0, 0, 1) = {(q0, 01)} (q0, 1, 0) = {(q0, 10)} (q0, 1, 1) = {(q0, 11), (q1, )} (q1, 0, 0) = {(q1, )} (q1, 1, 1) = {(q1, )} (q1, , Z) = {(q2, )} Работа МП –автомата Р состоит в том, что он копирует в магазине начальную часть входной цепочки, состоящую из нулей и единиц, и в какой-то момент начинает вычеркивать символы из магазина, если символ, находящийся в вершине магазина, совпадает с символом входной ленты.

Определение 14.28 Расширенный автомат с магазинной памятью (МП- автомат) – это семерка P = (Q, , Г, , q0, Z0, F), где 1) Q – конечное множество символов состояний, представляющих возможные состояния управляющего устройства; 2)  - конечный входной алфавит (алфавит входной ленты); 3) Г – конечный алфавит магазинных символов (алфавит рабочей памяти автомата);

4)  - отображение множества Q  (  {})  Г* в множество конечных подмножеств множества Q  Г* ( - функция переходов), т.е. расширенный автомат позволяет рассматривать не один символ магазина, а цепочку символов на каждом такте работы; 4)  - отображение множества Q  (  {})  Г* в множество конечных подмножеств множества Q  Г* ( - функция переходов), т.е. расширенный автомат позволяет рассматривать не один символ магазина, а цепочку символов на каждом такте работы; 5) q0  Q – начальное состояние управляющего устройства; 6) z0  Г - символ, находящийся в магазине в начальный момент (начальный символ магазина); 7) F  Q – множество заключительных состояний управляющего устройства.

В определении функции переходов запись (q, )  (q, a, Z) будет означать: В определении функции переходов запись (q, )  (q, a, Z) будет означать: если a  , то расширенный МП-автомат Р, находясь в состоянии q и имея a в качестве текущего входного символа, расположенного под входной головкой, а в качестве верхнего символа магазина - символ Z, может перейти в новое состояние q, сдвинуть входную головку на одну ячейку вправо и заменить верхний символ магазина цепочкой  магазинных символов; если а = , будем называть этот такт  –тактом; в  –такте текущий входной символ не принимается во внимание и входная головка не сдвигается, однако, состояние управляющего устройства и содержимое памяти могут измениться (заметим, что -такт может происходить и тогда, когда вся входная цепочка прочитана);

если  = , то верхний символ удаляется из магазина (магазинный список сокращается); если  = , то верхний символ удаляется из магазина (магазинный список сокращается); если Z = , то содержимое магазина не анализируется. Заметим, что в отличие от автомата с магазинной памятью, расширенный автомат с магазинной памятью может продолжить работу в случае, когда магазин пуст.

Пример 14.5. Пример 14.5. Построим расширенный МП –автомат, определяющий язык L={wwR | w{0,1}+}. Пусть P=({q, p}, {0, 1}, {S, Z, 0, 1}, , q, Z, {p}), где (q, 0, ) = {(q, 0)} (q, 1, ) = {(q, 1)} (q, , ) = {(q, S)} (q, , 0S0) = {(q, S)} (q, , 1S1) = {(q, S)} (q, , SZ) = {(p, )}

Определение 14.29 МП-автомат P = (Q, , Г, , q0, Z0, F) называется детерминированным (сокращенно ДМП-автоматом), если для каждых q  Q и Z  Г либо (q, a, Z) содержит не более одного элемента для каждого a и (q, , Z) = , либо (q, a, Z) =  для всех a   и (q, , Z) содержит не более одного элемента.

Лемма 14.5 Пусть P = (Q, , Г, , q0, Z0, F) – некоторый МП-автомат. Если (q, w, A)  Рn (q', , ), то (q, w, A)  Рn (q', , ) для всех A  Г и   *. Доказательство. База индукции. При n = 1 доказательство очевидно (в этом случае длина цепочи w не превосходит 1). Так как выполнено (q, w, A)  Р1 (q', , ), то очевидно, что при наличии в магазине символов под символом А получим (q, w, A)  Р1 (q', , ). Шаг индукции. Допустим, что утверждение леммы верно для всех n, таких, что n' > n 1. Покажем, что если выполнено (q, w, A)  Рn' (q', , ), то (q, w, A)  Р n' (q', , ).

Так как выполнено (q, w, A)  Рn' (q', , ), то соответствующая последовательность тактов должна иметь вид: Так как выполнено (q, w, A)  Рn' (q', , ), то соответствующая последовательность тактов должна иметь вид: (q, w, A)  (q1, w1, X1,X2,…,Xk )  n1 (q2, w2, X2,…,Xk )  n2 (q3, w3, X3,…,Xk ) …  nk-1 (qk, wk, Xk )  nk (q', , ), причем все ni < n'.

Тогда для любых  возможна последовательность Тогда для любых  возможна последовательность (q, w, A)  (q1, w1, X1,X2,…,Xk )  n1 (q2, w2, X2,…,Xk )  n2 (q3, w3, X3,…,Xk ) …  nk-1 (qk, wk, Xk )  nk (q', , ), т.е. выполнено (q, w, A)  Р n' (q', , ). Лемма доказана.

Определение 14.30 Пусть P = (Q, , Г, , q0, Z0, F) – некоторый МП-автомат или расширенный МП-автомат. Будем говорить, что P допускает цепочку w * опустошением магазина, если (q, w, Z0) Р* (q', , ) для некоторого q  Q. Обозначим L(P) – множество цепочек, допускаемых автоматом P опустошением магазина.

Лемма 14.6 Пусть L = L(P) для некоторого МП-автомата P = (Q, , Г, , q0, Z0, F). Тогда можно построить такой МП-автомат P', что L(P') = L. Доказательство. Построим МП-автомат P' = (Q  {q, q'}, , Г  {Z'}, ', q', Z',). Определим функцию переходов следующим образом: 1. если (r,)  (q, a, z), то (r,)  '(q, a, z) для любых q  Q, a  {}, zГ; 2. '(q', , Z') = {(q0, Z0Z')}, т.е. на первом такте автомат P' записывает в магазин Z0Z' и переходит в состояние q0 – начальное для автомата P;

3. для любых q  F, z  Г  {Z'} элемент (q, )  '(q, , z); 3. для любых q  F, z  Г  {Z'} элемент (q, )  '(q, , z); 4. '(q, , z) = {(q, )} для всех z  Г  {Z'}. Очевидно, что (q', w, Z') Р' (q0, w, Z0Z') пункт (2) определения ' Р'n (q, , Y1Y2…Yr) пункт (1) определения ' Р' (q, , Y1Y2…Yr) пункт (3) определения ' Р'r-1 (q, , ) пункт (4) определения ' где Yr = Z' тогда и только тогда, когда (q0, w, Z0) Р'n (q, , Y1Y2…Yr-1) для q  F и Y1Y2…Yr-1  Г*. Следовательно, L(P') = L.

Лемма 14.7 Пусть P = (Q, , Г, , q0, Z0, ) – МП- автомат. Можно построить такой МП-автомат P', что L(P') = L(P).

1. если правило вида A    P, то (q, )  (q, , A); 1. если правило вида A    P, то (q, )  (q, , A); 2. для всех a   построим (q, a, a) = {(q, )}. Докажем, что A  m w, где w  *  (q, w, A) n (q, , ) для некоторых m  1 и n 1. Необходимость. Пусть имеет место A  m w при некотором m 1. Покажем (индукцией по m), что тогда существует n 1 такое, что выполнено (q,w, A) n (q, , ). База индукции. Если m = 1, A  1 w и w = a1a2…ak  *, т.е. k  0, то правило A  w  P и (q, a1a2…ak, A)  (q, a1a2…ak, a1a2…ak) пункт (1) определения  k (q, , ) пункт (2) определения , т.е. n = w+1 = k+1.

Предположим, что при всех m', таких, что 1 < m' < m, если A  m w, то существует n  1 такое, что выполнено (q,w, A) n (q, , ). Предположим, что при всех m', таких, что 1 < m' < m, если A  m w, то существует n  1 такое, что выполнено (q,w, A) n (q, , ). Докажем справедливость утверждения при m. Так как A  m w, то первый шаг вывода имеет вид A  X1X2… X k, причем правило A  X1X2… X k P и для всех i, 1 ik имеет место Xi mi xi, где mi < m. Но тогда по предположению индукции (q, xi, Xi)ni (q, , ), причем, в случае, когда Xi = xi   имеет место (q,xi,xi) (q,, ), т.е. ni = 1 . Следовательно, если A  m w, то (q, w, A)  (q, w, X1X2… Xk) n1 (q, w, X2… Xk) n2 …nk (q,,). Достаточность. Пусть имеет место (q, w, A) n (q, , ) при некотором n 1. Покажем (индукцией по n), что тогда существует m  1 такое, что выполнено Amw.

База индукции. Если n =1 и (q, w, A) 1 (q, , ), то w =  и правило AP (см. определение функции переходов), т.е. A1w. База индукции. Если n =1 и (q, w, A) 1 (q, , ), то w =  и правило AP (см. определение функции переходов), т.е. A1w. Предположим, что утверждение верно при всех n', таких, что n'<n. Докажем, что оно верно при n, т.е. докажем, что если (q, w, A) n (q, , ), то существует m1 такое, что выполнено A m w. Первый шаг, сделанный автоматом, должен иметь вид (q, w, A)  (q, w, X1X2… Xk), причем правило A  X1X2… Xk P. Пусть w = x1x2… xk, где xk  * и (q, xi, Xi) ni (q, , ), причем ni < n, но тогда по предположению Xi mi xi, причем mi = 0, если Xi  . Таким образом, имеет место вывод цепочки w в грамматике G:

A  X1X2… Xk A  X1X2… Xk * x1X2… Xk * x1x2X3… Xk * x1x2x3… xk = w Из условия леммы в частности следует, что S + w  (q, w, S) + (q, , ), следовательно L(R) = L(G).

Пример 14.6. Пример 14.6. Построим МП –автомат P, для которого L(P) = L(G), где G – КС-грамматика примера 7.5, определяющая арифметические выражения. Пусть P=({q}, , Г, , q, E, ), где  = {a, +, *, (, )} где (q, , E) = {(q, E+T), (q, E)} (q, , T) = {(q, T*F), (q, T)} (q, , F) = {(q, (E)), (q, a)} (q, b, b) = {(q, )} для всех b  .

Определение 14.31 Пусть G = (N, , P, S) – КС-грамматика и S r* Aw r w r*xw – правый вывод в G. Будем говорить, что правовыводимую цепочку w можно свернуть слева (или что она левосвертывается) к правовыводимой цепочке Aw с помощью правила A  . Вхождение цепочки  в цепочку w назовем основой цепочки w. Основа правовыводимой цепочки – это любая ее подцепочка, которая является правой частью какого–либо правила, причем после ее замены левой частью правила получается также правовыводимая цепочка.

Лемма 14.9 Пусть G = (N, , P, S) – КС-грамматика. По грамматике G можно построить такой расширенный МП-автомат R, что L(R) = L(G). Доказательство. Пусть R = ({q, r}, ,   N  {#}, , q, #, {r}) – расширенный МП–автомат (верхушка магазина располагается справа), в котором функция переходов  определяется следующим образом: (1) для всех a   определим (q, a, ) ={(q, a)} (выполняется перенос входного символа в магазин); (2) если правило A    P, то (q, A)  (q, , ) (выполняется свертка, т.е. основа заменяется нетерминальным символом грамматики); (3) (q, , #S) = {(r, )}.

Докажем, что справедливо L(G) = L(R). Докажем, что справедливо L(G) = L(R). 1. Докажем вначале справедливость L(G)  L(R), т.е. покажем, что если w = xy  L(G), то w  L(R). Для этого индукцией по n докажем, что (*) если имеет место S r* Ay rn xy, то также (q, ху, #) m (q, y, #A) Базис. При n = 1 имеем Ay r1 xy. В этом случае xy = y и правило А    Р. Тогда имеет место (q, ху, #) * (q, y, #) 1(q, y, #A) (т.е. выполняем перенос входных символов до тех пор, пока в магазине не появится основа , а затем заменяем основу нетерминальным символом A). Предположим, что (*) верно для всех значений n' < n. Докажем, что (*) верно для n. Вывод Ay rn xy можно представить в виде Ay r y rn–1 xy.

Допустим, что цепочка  состоит только из терминалов. Тогда =х и (q,ху, #) * (q, у, #)  (q, y, # A). Допустим, что цепочка  состоит только из терминалов. Тогда =х и (q,ху, #) * (q, у, #)  (q, y, # A). Если   *, т.е.  содержит нетерминальные символы, то можно представить  = Bz, где В—самый правый нетерминал. По (*) из S r* Bzy rn–1 xy следует (q, ху, #)* (q, zy, #B). Кроме того, (q, zy, #B) * (q, у, #Bz)  (q, у, #A) – тоже возможная последовательность тактов (согласно предположения индукции). Следовательно, (*) верно для всех n. Так как (q, , #S)  (r, , ), то L(G) L(R).

2. Теперь докажем обратное включение L(R)  L(G), т.е. покажем, что если w = xy  L(R), то w  L(G). Для этого индукцией по n покажем, что 2. Теперь докажем обратное включение L(R)  L(G), т.е. покажем, что если w = xy  L(R), то w  L(G). Для этого индукцией по n покажем, что (**) если имеет место (q, xy, #) n (q, y, #A), то выполнено Ау * ху Базис. При n = 1 имеем (q, xy, #) 1 (q, y, #A). В этом случае xy = y и правило А    Р, тогда Ау 1 ху = y. Предположим, что (**) верно для всех n < m. Докажем, что (**) верно для m, т.е. покажем, что если имеет место (q,xy,#)m (q, y, #A), то выполнено Ау * ху Если верхний символ магазина автомата R нетерминальный, то последний такт был сделан по правилу (2) определения функции . Поэтому можно записать

(q, ху, #) m–1 (q, y, #)  (q, y, # A), где правило А    Р. (q, ху, #) m–1 (q, y, #)  (q, y, # A), где правило А    Р. Если цепочка  содержит нетерминал, то по предположению индукции y * ху. Отсюда Aу  y * ху, что и утверждалось. В качестве частного случая утверждения (**) получаем, что если выполнено (q, w, #)* (q, , #S), то также S * w. Так как R допускает w только тогда, когда (q, w, #) * (q, , #S)  (r•, , ), то отсюда следует, что L(R)  L (G). Таким образом, L(R) = L(G)). Заметим, что сразу после свертки правовыводимая цепочка вида Ax представлена в R так, что А находится в магазине, а x занимает непрочитанную часть входной ленты. После этого R может продолжать переносить символы цепочки х в магазин до тех пор пока в его верхней части не образуется основа. Тогда R может сделать следующую свертку. Синтаксический анализатор этого типа называют „восходящим анализом" („анализом снизу вверх").

Пример 14.7. Построим восходящий анализатор R для грамматики G примера 7.5. Пусть R – расширенный МП-автомат R = ({q, r}, , Г, , q, #, {r}), где  = {a, +, *, (, )}, а функция переходов  определяется так: Пример 14.7. Построим восходящий анализатор R для грамматики G примера 7.5. Пусть R – расширенный МП-автомат R = ({q, r}, , Г, , q, #, {r}), где  = {a, +, *, (, )}, а функция переходов  определяется так: (q, b, ) = {(q, b)} для всех b  ; (q, , E+T) = {(q, E)} (q, , T) = {(q, E)} (q, , T * F) = {(q, T)} (q, , F) = {(q, T)} (q, , (E)) = {(q, F)} (q, , a) = {(q, F)} (q, , #E) = {(r, )}

Теорема 14.3 Язык L является КС-языком тогда и только тогда, когда L определяется некоторым МП-автоматом.