1 Глава 5. Магазинные автоматы Теория формальных языков и трансляций

2 § 5.1. Неформальное описание В этой главе мы рассмотрим простое устройство магазинный автомат (pda pushdown automaton), которое адекватно классу КС-языков в том смысле, что любой КС-язык распознаётся каким-нибудь магазинным автоматом, и любой магазинный автомат распознаёт некоторый КС-язык. Вместо этого термина часто используется сокращение МП-автомат.

3 Магазинный автомат подобен конечному автомату, но в отличие от последнего имеет рабочую память магазин, в который записываются символы из ещё одного алфавита алфавита магазинных символов. Магазинные автоматы неформальное описание

4 Каждое движение магазинного автомата определяется в зависимости от: текущего состояния управления, входного символа или независимо от него так называемые -движения и верхнего символа магазина. Магазинные автоматы неформальное описание

5 Одно движение магазинного автомата состоит в замещении верхнего символа магазина некоторой магазинной цепочкой, в частности, пустой (стирание верхнего символа магазина), и переходе в новое состояние управления. При этом текущим входным символом становится следующий символ на входной ленте, если выполняется движение, зависящее от входного символа, либо текущий входной символ остаётся тем же самым, если выполняется -движение. Магазинные автоматы неформальное описание

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

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

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

9 В этой главе будет показано, что оба определения приёма эквивалентны в том смысле, что если язык распознаётся некоторым магазинным автоматом при пустом магазине, то он может быть распознан некоторым другим магазинным автоматом при конечном состоянии, и наоборот. Кроме того, будет доказана основная теорема о том, что язык принимается недетерминированным МП-автоматом тогда и только тогда, когда он является КС- языком. Магазинные автоматы неформальное описание

10 Известно, что класс языков, распознаваемых детерминированными МП-автоматами, является строгим под- классом языков, распознаваемых недетер- минированными МП-автоматами. Этим класс КС-языков отличается от класса регулярных языков, для которого недетерминированная и детерминирован- ная модели распознавателей эквивалентны. Магазинные автоматы неформальное описание

11 § 5.2. Формальное определение Определение 5.1. Недетерминированный магазинный автомат есть формальная система M = (Q,,,, q 0, Z 0, F), где Q конечное множество состояний; конечный входной алфавит; конечный магазинный алфавит; отображение типа Q ( { }) 2 Q *, причём область значений представлена конечными подмножествами пар из Q * ; q 0 Q начальное состояние; Z 0 начальный символ магазина; F Q множество конечных состояний.

12 Мы будем придерживаться следующей системы обозначений: строчные буквы из начала латинского алфавита отдельные входные символы; строчные буквы из конца латинского алфавита служат для обозначения цепочек входных символов; строчные греческие буквы цепочки магазинных символов; прописные латинские буквы отдельные магазинные символы.

13 Определение 5.2. Для описания движений МП-автомата будем использовать понятие конфигурации, под которой будем подразумевать тройку (q, x, ), где q Q текущее состояние управления; x * непросмотренная часть входной цепочки (от текущего символа до её конца); * магазинная цепочка, причём крайний левый её символ считается находящимся на вершине магазина. Недетерминированный pda формальное описание

14 Начальная конфигурация есть (q 0, x, Z 0 ), где x вся входная цепочка. Конечная конфигурация определяется по- разному в зависимости от того, какой признак приёма используется. (а) Если приём определяется при конечном состоянии, то конечная конфигурация есть (q,, ), где q F автомат достиг конеч- ного состояния; означает, что вся входная цепочка прочитана; * произвольная магазинная цепочка. Недетерминированный pda формальное описание

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

16 (б) Если приём характеризуется опусто- шением магазина, то конечная конфигура- ция есть (q,, ), где q Q любое состояние; во второй позиции означает, как и в предыдущем случае, что вся входная цепочка прочитана; в третьей позиции означает, что магазин пуст. При пустом магазине никакое дальнейшее движение не определено. Недетерминированный pda формальное описание

17 Недетерминированный pda формальное описание Запись (q, a, Z) = {( p 1, 1 ), ( p 2, 2 ),..., ( p m, m )}, где q, p i Q, a, Z, i * (i = 1, 2,..., m), означает, что магазинный автомат в состоянии q с символом a на входе и символом Z на вершине магазина может для любого i перейти в состояние p i, заменить Z на i и продвинуться на входе к следующей позиции.

18 Недетерминированный pda формальное описание Пусть текущая конфигурация имеет вид: (q, ax, Z ), где q Q, a, x *, Z, *. В терминах конфигураций одно из возможных движений представляется следующим образом: (q, ax, Z ) (p i, x, i ) для любого i, 1 i m.

19 Недетерминированный pda формальное описание Запись (q,, Z) = {( p 1, 1 ), ( p 2, 2 ),..., ( p m, m )} означает, что pda в состоянии q независимо от того, какой символ на входе, и с символом Z на вершине магазина может для любого i перейти в состояние p i, заменить Z на i, не изменяя текущей позиции на входе.

20 Недетерминированный pda формальное описание Пусть текущая конфигурация имеет вид (q, x, Z ), где q Q, x *, Z, *. Тогда в терминах конфигураций одно из возможных движений в рассматриваем случае представляется следующим образом: (q, x, Z ) (p i, x, i ) для любого i, 1 i m.

21 Если i =, то происходит стирание верхнего символа магазина вершина магазина опускается; если i = 1, то происходит замена верх- него символа магазина; если i > 1, то вершина магазина подни- мается. Недетерминированный pda формальное описание

22 Недетерминированный pda формальное описание Таким образом, мы ввели на множестве конфигураций pda отношение непосред- ственного следования одной конфигурации за другой, использовав для него символ. Степень, транзитивное замыкание и рефлексивно-транзитивное замыкание это- го отношения определяются обычным образом.

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

24 Язык, распознаваемый магазинным автоматом Определение 5.3. Язык, распознаваемый магазинным автоматом M = (Q,,,, q 0, Z 0, F) при конечном состоянии, определим как множество T(M) = {w * (q 0, w, Z 0 ) (q,, ), q F}.

25 Язык, распознаваемый магазинным автоматом Определение 5.4. Язык, распознаваемый магазинным автоматом M = (Q,,,, q 0, Z 0, F) при пустом магазине, определим как множество N(M) = {w * (q 0, w, Z 0 ) (q,, ), q Q}. В этом случае неважно, каким является множество конечных состояний, и часто оно просто считается пустым (F = ).

26 Пример 5.1. Пусть pda M = ({q 1, q 2 }, {0, 1}, {R, B, G},, q 1, R, ), где 1) (q 1, 0, R) = {( q 1, BR)}, 2) (q 1, 1, R) = {( q 1, GR)}, 3) (q 1, 0, B) = {( q 1, BB), ( q 2, )}, 4) (q 1, 1, B) = {( q 1, GB)}, 5) (q 1, 0, G) = {( q 1, BG)}, 6) (q 1, 1, G) = {(q 1, GG), ( q 2, )}, 7) (q 1,, R) = {( q 2, )}, 8) (q 2, 0, B) = {( q 2, )}, 9) (q 2, 1, G) = {( q 2, )}, 10) (q 2,, R) = {( q 2, )}.

27 M недетерминированный магазинный автомат, распознающий язык N(M) = {ww R w {0, 1} * }, где w R обозначает инвертированную цепочку w, при пустом магазине. Правила 1 – 6 позволяют pda M запомнить входной символ в магазинной памяти. При этом входной символ 0 отображается в магазине посредством символа B, а символ 1 отображается в магазине посредством символа G. Пример 5.1. pda M : N(M) = {ww R w {0, 1} * }

28 При этом правила 3 и 6 предоставляют автомату выбор движений между запоми- нанием очередного входного символа в магазине (в предположении, что середина входной цепочки не достигнута) и пере- ходом в режим сопоставления текущего входного символа с символом на вершине магазина и стиранием последнего в случае их соответствия (в предположении, что достигнута середина входной цепочки). Пример 5.1. pda M : N(M) = {ww R w {0, 1} * }

29 Если на входе находится цепочка вида ww R, то существует такая последователь- ность движений, которая опустошает магазин к моменту достижения конца цепочки. Например, если на вход поступает цепочка 0110, то автомат имеет выбор движений, представленный на рис. 5.1, где приведено дерево возможных переходов между конфигурациями. Пример 5.1. pda M : N(M) = {ww R w {0, 1} * }

30 (q 1, 0110, R) (q 1, 110, BR) (q 2, 0110, ) (q 1, 0, GGBR)(q 2, 0, BR) (q 1, 10, GBR) (q 1,, BGGBR) (q 2,, R) (q 2,, ) Рис Пример 5.1. pda M : N(M) = {ww R w {0, 1} * } Существующая среди них следующая последователь- ность движений: (q 1, 0110, R) (q 1, 110, BR) (q 1, 10, GBR) (q 2, 0, BR) (q 2,, R) (q 2,, ) дает основание заключить, что входная цепочка 0110 принимается.

31 Пример 5.2. Пусть pda M = ({q 1, q 2 }, {0, 1, c}, {R, B, G},, q 1, R, ), где Пример 5.2. pda M : N(M) = {wcw R w {0, 1} * } 1) (q 1, 0, R) = {(q 1, BR)}, 2) (q 1, 0, B) = {(q 1, BB)}, 3) (q 1, 0, G) = {(q 1, BG)}, 4) (q 1, 1, R) = {(q 1, GR)}, 5) (q 1, 1, B) = {(q 1, GB)}, 6) (q 1, 1, G) = {(q 1, GG)}, 7) (q 1, c, R) = {(q 2, R)}, 8) (q 1, c, B) = {(q 2, B)}, 9) (q 1, c, G) = {(q 2, G)}, 10) (q 2,, R) = {(q 2, )}, 11) (q 2, 0, B) = {(q 2, )}, 12) (q 2, 1, G) = {(q 2, )}.

32 Пример 5.2. pda M : N(M) = {wcw R w {0, 1} * } Легко сообразить, что N(M) = {wcw R w {0,1} * }, где w R обозначает инвертированную цепочку w. Рассмотрим движения pda M при наличии цепочки 01с10 на его входе: (q 1, 01с10, R) (q 1, 1с10, BR) (q 1, с10, GBR) (q 2, 10, GBR) (q 2, 0, BR) (q 2,, R) (q 2,, ). Следовательно, цепочка 01с10 принима- ется при пустом магазине.

33 Заметим, что равенство (q 2,, R) = {(q 2, )} означает движение, не зависящее от вход- ного символа, каким бы он ни был. В любом случае происходит стирание верхнего символа R магазина без продвижения по входной цепочке и переход в состояние q 2. Магазинный автомат из примера 5.2 является детерминированным в том смысле, что из любой конфигурации возможно не более одного движения. Пример 5.2. pda M : N(M) = {wcw R w {0, 1} * }

34 Определение 5.5. Магазинный автомат M = (Q,,,, q 0, Z 0, F) является детерминированным, если 1) для любых q Q, Z и a ( { }) значение # (q, a, Z) 1; 2) для любых q Q и Z всякий раз, как множество (q,,Z), множество (q, a, Z) = для всех a. Детерминированный магазинный автомат

35 Условие 1 означает, что если движение определено, то оно единственно. Условие 2 предотвращает выбор между - движением и движением, использующим входной символ. Для конечных автоматов детерминирован- ная и недетерминированная модели эквива- лентны по отношению к распознаваемым языкам (см. теорему 3.3).3.3 Для МП-автоматов это не так. Детерминированный магазинный автомат

36 Действительно, язык, состоящий из цепочек вида ww R, принимается недетерми- нированным pda, но не существует никакого детерминированного pda, который прини- мал бы такой язык. Детерминированный магазинный автомат

37 § 5.3. Недетерминированные магазинные автоматы и контекстно-свободные языки Теперь докажем фундаментальный результат: класс языков, принимаемых недетерминирован- ными МП-автоматами, есть в точности класс контекстно-свободных языков. Для этого сначала покажем, что языки, распознаваемые недетерминированными МП- автоматами при конечном состоянии, являются в точности языками, распознаваемые недетермини- рованными МП-автоматами при пустом магазине, а затем, что языки, принимаемые при пустом магазине, совпадают с классом КС-языков.

38 Теорема 5.1. Язык L = N(M 1 ) для некото- рого недетерминированного магазинного автомата M 1 тогда и только тогда, когда L = Т(M 2 ) для некоторого недетерминиро- ванного магазинного автомата M 2. Доказательство. I. Необходимость. Пусть M 1 = (Q,,,, q 0, Z 0, ) недетерминированный pda, такой, что L = N(M 1 ).

39 Положим M 2 = (Q {, q f },, {X},,, X, {q f }), где определяется следующим образом: 1) (,, X) = {(q 0, Z 0 X)}; 2) ( q, a, Z) = (q, a, Z) для всех q Q, a ( { }) и Z ; 3) ( q,, X) = {(q f, )} для всех q Q. L = N(M 1 ) L = Т(M 2 )

40 Правило 1 воспроизводит начальную конфигурацию автомата M 1. При этом начальный символ магазина X остается в качестве своеобразного маркера дна магазина до тех пор, пока он не будет удален последним движением автомата M 2. Выше этого маркера при последующих движениях, повторяющих движения pda M 1, всегда будут находиться только магазинные символы автомата M 1. Это обеспечивается правилом 2. L = N(M 1 ) L = Т(M 2 )

41 Когда же будет воспроизведено последнее движение pda M 1, опустошающее его магазин, на вершине магазина автомата M 2 появится маркер дна. В этот момент автомат M 2 посредством правила 3 переводится в конечное состояние, тем самым сигнали- зируя приём входной цепочки. Заметим, что движение по правилу 3 стирает символ магазина X, но могло бы записать вместо него любую магазинную цепочку. L = N(M 1 ) L = Т(M 2 )

42 L = N(M 1 ) L = Т(M 2 ) I.1. Докажем, сначала, что если x N(M 1 ), то x T(M 2 ). Пусть x N(M 1 ), т. е. (q 0, x, Z 0 ) (q,, ). Посмотрим, какие движения будет совершать автомат M 2, имея на входе цепочку символов x. Согласно правилу 1 (, x, X) (q 0, x, Z 0 X).

43 L = N(M 1 ) L = Т(M 2 ) Далее согласно правилу 2 автомат M 2, повторяя движения автомата M 1, осуществ- ляет переход (q 0, x, Z 0 X) (q,, X). Наконец, по правилу 3 имеем последнее движение: (q,, X) (q f,, ). Таким образом, x T(M 2 ).

44 L = N(M 1 ) L = Т(M 2 ) I.2. Теперь докажем, что если x T(M 2 ), то x N(M 1 ). Пусть x T(M 2 ), т. е. (, x, X) (q f,, ) для некоторой цепочки ( {X}) *. Заметим, что автомат M 2 построен так, что =. Выделив здесь первый шаг явным образом, имеем (, x, X) (q 0, x, Z 0 X) (q f,, ).

45 L = N(M 1 ) L = Т(M 2 ) Заключительная конфигурация (q f,, ) достижима лишь посредством -движения благодаря правилу 3 и только в случае, когда на вершине магазина находится X. Следовательно, предпоследняя конфигу- рация должна иметь вид (q,, X). Итак, все движения выстраиваются в следующую последовательность конфигу- раций: (, x, X) (q 0, x, Z 0 X) (q,, X) (q f,, ).

46 L = N(M 1 ) L = Т(M 2 ) Но на главном участке (q 0, x, Z 0 X) (q,, X) автомат M 2 просто повторяет движения автомата M 1. Поэтому (q 0, x, Z 0 ) (q,, ) и x N(M 1 ). Из рассуждений, проведённых в пп.I.1 и I.2 следует, что T(M 2 ) = N(M 1 ).

47 II. Достаточность. Пусть M 2 = (Q,,,, q 0, Z 0, F) недетерминированный pda, такой, что L = T(M 2 ). Положим M 1 = (Q {, q e },, {X},,, X, ), где определяется следующим образом: 1) (,, X) = {(q 0, Z 0 X)}; 2) ( q, a, Z) = (q, a, Z) для всех q Q, a ( { }) и Z ; 3) ( q,, Z) = {(q e, )} для всех q F и Z {X}; 4) ( q e,, Z) = {(q e, )} для всех Z {X}. L = N(M 1 ) L = Т(M 2 ) Ret 52

48 Правило 1 воспроизводит начальную конфигурацию автомата M 2. При этом начальный символ магазина X остается в качестве своеобразного маркера дна магазина до тех пор, пока он не будет удален последним движением автомата M 1. Выше этого маркера при последующих движениях, повторяющих движения автомата M 2, всегда будут находиться только магазинные символы автомата M 2. Это обеспечивается правилом 2. L = N(M 1 ) L = Т(M 2 )

49 Если когда-либо pda M 2 входит в конечное состояние, то pda M 1 либо продолжает моделировать движения автомата M 2 по правилу 2, либо переходит по правилам 3 и 4 в состояние q e и, не продвигаясь по входу, очищает магазин, тем самым принимая входную цепочку. L = N(M 1 ) L = Т(M 2 )

50 Следует заметить, что автомат M 2 может на неправильном входе опустошить свой магазин, не заходя в конечное состояние и, следовательно, не принимая входную цепочку. Чтобы неправильные цепочки не принимались pda M 1, и введено его собственное особое дно в виде символа X, чтобы он, воспроизводя эти же движения, тоже не опустошил свой магазин и, таким образом, принял бы неправильную цепочку. Остаётся убедиться в том, что N(M 1 ) = T(M 2 ). L = N(M 1 ) L = Т(M 2 )

51 L = N(M 1 ) L = Т(M 2 ) II.1. Докажем, сначала, что если x N(M 1 ), то x T(M 2 ). Если x N(M 1 ), то по определению (, x, X) (q,, ) при некотором q Q {, q e }. Рассмотрим подробнее эти движения. Согласно правилу 1 имеем (, x, X) (q 0, x, Z 0 X).

52 L = N(M 1 ) L = Т(M 2 ) Далее (q 0, x, Z 0 X) (q,, ) при некотором q Q {, q e }. Удалить X из магазина согласно построению автомата M 1 возможно только посредством правил 3 или 4, причём правило 4 применимо только после того, как применено правило 3. В свою очередь, правило 3 применимо только в том случае, если автомат M 2 достиг одного из своих конечных состояний.правил

53 L = N(M 1 ) L = Т(M 2 ) C этого момента происходят только - движения, стирающие содержимое магази- на. С учётом этого имеем (, x, X) (q 0, x, Z 0 X) (q,, X) (q e,, ) (q e,, ). Здесь q F, *, ( {X}) *, причём если =, то перехода (q e,, ) фактически нет.

54 L = N(M 1 ) L = Т(M 2 ) Но мы знаем, что согласно правилу 2 автомат M 1 на главном участке просто повторяет движения автомата M 2 : (q 0, x, Z 0 X) (q,, X), т. е. имеет место переход (q 0, x, Z 0 ) (q,, ), где q F. Следовательно, x T(M 2 ).

55 L = N(M 1 ) L = Т(M 2 ) II.2. Теперь докажем, что если x T(M 2 ), то x N(M 1 ). Пусть x T(M 2 ), т. е. (q 0, x, Z 0 ) (q,, ), где q F, *. Посмотрим, как будет действовать автомат M 1 на том же входе. Согласно правилу 1 имеем (, x, X) (q 0, x, Z 0 X).

56 L = N(M 1 ) L = Т(M 2 ) Затем согласно правилу 2 воспроизводятся указанные ранее движения автомата M 2, т. е. имеем (, x, X) (q 0, x, Z 0 X) (q,, X), где q F, *. Далее согласно правилам 3 и 4 имеем (q,, X) ( q e,, ) (q e,, ), где ( {X}) *. Если =, то последнего перехода фактически нет.

57 L = N(M 1 ) L = Т(M 2 ) Итак, существует последовательность конфигураций: (, x, X) (q 0, x, Z 0 X) (q,, X) (q e,, ) (q e,, ), означающая, что x N (M 1 ). Из рассуждений. проведенных в пп.II.1 и II.2 следует, что N(M 1 ) = T(M 2 ). Заключение теоремы следует из доказанных утверждений I и II.

58 Определение 5.5. Пусть S x, где x V T *, причём = A, A V N,, либо =. Цепочка x называется закрытой, а открытой частью сентенциальной формы x.

59 Теорема 5.2. Если L КС-язык, то существует недетерминированный мага- зинный автомат M, такой, что L = N(M). Доказательство. Пусть G = (V N, V T, P, S) КС-грамматика в нормальной форме Грейбах, и L = L(G). Мы предполагаем, что L(G).

60 Построим недетерминированный pda M таким образом, чтобы в его магазине воспроизводились последовательности сен- тенциальных форм, составляющих лево- сторонние выводы в грамматике G, вернее, только открытые части таких форм. L cfl L = N(M) Для этого положим M = ({q}, V T, V N,, q, S, ), где (q, ) (q, a, A), если существует пра- вило A a P, где A V N, a V T, V N *.

61 Очевидно, что в магазине pda M, если он не пуст, всегда находится нетерминальная цепочка, причём на вершине символ, подлежащий замене на текущем шаге левостороннего вывода. Заметим, что pda M не совершает - движений. L cfl L = N(M)

62 L cfl L = N(M) Чтобы показать, что L(G) = N(M), доста- точно доказать, что A x тогда и только тогда, когда (q, x, A) (q,, ) для любых x V T +, A V N, V N *. Утверждение теоремы последует как частный случай этого вспомогательного утверждения при A = S, =.

63 L cfl L = N(M) I. Индукцией по длине вывода l покажем, что если A x, где x V T +, V N *, то (q, x, A) (q,, ). База. Пусть l = 1. Имеем A x. Это значит, что существует правило A x P, где x V T, V N *. Одновременно по построению автомата M мы имеем (q, ) (q, x, A), а тогда (q, x, A) (q,, ).

64 L cfl L = N(M) Индукционная гипотеза. Предположим, что для всех l n (n 1), если A x, то (q, x, A) (q,, ). Индукционный переход. Докажем это утверждение для l = n + 1. Пусть A yB ya = x левосторон- ний вывод длиной n + 1. В нём x = ya, = и B a P.

65 L cfl L = N(M) В соответствии с индукционной гипотезой из A yB следует (q, y, A) (q,, B ). С другой стороны, B a P, и по построению pda M имеем (q, ) (q, a, B). Учитывая эти два обстоятельства, можем написать: (q, x, A) = (q, ya, A) (q, a, B ) (q,, ) = = (q,, ). Утверждение I доказано.

66 L cfl L = N(M) II. Теперь индукцией по числу l движений автомата M покажем, что если (q, x, A) (q,, ), где x V T +, V N *, то A x. База. Пусть l = 1. Имеем (q, x, A) (q,, ), где x V T +, V N *. Это движение определятся тем, что (q, ) (q,x,A),где x V T (pda M не совершает -движений). Оно обусловлено тем, что существует правило A x P, с помощью которого получаем требуемый вывод A x.

67 L cfl L = N(M) Индукционная гипотеза. Предположим, что утверждение выполняется для всех l n (n 1). Индукционный переход. Докажем это утверждение для l = n + 1. Пусть (q, x, A) = (q, ya, A) (q, a, B ) (q,, ) = = (q,, ), где x = ya, =. Последнее из этих движений подразуме- вает, что (q, ) (q, a, B), где a V T, а это обусловлено существованием правила B a P.

68 L cfl L = N(M) Учитывая следствие индукционной гипо- тезы из перехода (q, ya, A) (q, a, B ) и упомянутое правило, мы можем написать: A yB ya = x. Утверждение II доказано. Из рассуждений, проведённых в пп. I и II, при A = S и = получаем утверждение теоремы. Что и требовалось доказать. x

69 Теорема 5.3. Если M недетерминиро- ванный магазинный автомат, и L = N(M), то L контекстно-свободный язык. Доказательство. Пусть M = (Q,,,, q 0, Z 0, ) недетерминированный pda, такой, что L = N(M). L = N(M) L cfl

70 Построим cfg G, левосторонние выводы в которой моделируют движения pda M. В частности, нетерминалы, которые появляются в сентенциальных формах на любом шаге левостороннего вывода в грамматике G, соответствуют символам в магазине автомата M в момент, когда он уже просмотрел такую же часть входной цепочки, какую грамматика уже породила. L = N(M) L cfl

71 Положим G = (V N, V T, P, S), где V N = {S} {[qAp] q, p Q; A }; V T = ; P ={(1) S [q 0 Z 0 q] q Q} {(2) [qAp] a[q 1 B 1 q 2 ][q 2 B 2 q 3 ]...[q m B m q m + 1 ] q, q i Q (i = 1, 2,..., m + 1); p = q m + 1 ; a { }; A, B j (j = 1, 2,..., m); если (q 1, B 1 B 2...B m ) (q, a, A)}. Отметим, что если (q 1, ) (q, a, A), то m = 0, q 1 = p и правило вида 2 имеет вид [qAp] a. L = N(M) L cfl

72 L = N(M) L cfl Чтобы показать, что L(G) = N(M), мы сначала докажем вспомогательное утверж- дение: [qAp] x тогда и только тогда, когда (q, x, A) (p,, ). I. Индукцией по числу l движений pda M покажем, что если (q, x, A) (p,, ), то [qAp] x.

73 L = N(M) L cfl База. Пусть l = 1. Имеем (q, x, A) (p,, ). Это движение обусловлено тем, что (p, ) (q, x, A), где x { }. Соответственно по способу построения грамматики G существует правило [qAp] x, при помощи которого [qAp] x. Индукционная гипотеза. Предположим, что утверждение выполняется для всех значений l n (n 1).

74 L = N(M) L cfl Индукционный переход. Докажем, что утверждение выполняется для l = n + 1. Пусть (q, x, A) = (q, ax 1 x 2... x m, A) (q 1, x 1 x 2... x m, B 1 B 2...B m ) (p,, ). Здесь x = ax 1 x 2... x m, a { }, x i *, причём (q i, x i, B i ) (q i + 1,, ), l i n, i = 1, 2,..., m, q m + 1 = p. Ret 76

75 Поясним, что в этой последовательности переходов явно показано первое движение, которое может использовать входной символ a, с которого начинается входная цепочка x, либо оно может быть - движением. Каждая из подцепочек x i есть та часть цепочки x, которую автомат просматривает с момента, когда он оказывается в состоянии q i с символом B i на вершине магазина, до того момента, когда вершина магазина впервые опустится на один символ ниже этой позиции B i. L = N(M) L cfl

76 Очевидно, что первое движение обуслов- лено тем, что (q 1, B 1 B 2...B m ) (q, a, A), и, как следствие этого, существует правило грамматики вида (*) [qAp] a[q 1 B 1 q 2 ][q 2 B 2 q 3 ]...[q m B m q m + 1 ], где q m + 1 = p, с нетерминалами, связанными с состояниями и магазинными символами, участвующими в конфигурациях, упоми- навшихся выше.выше L = N(M) L cfl Ret 77

77 L = N(M) L cfl С другой стороны, применение индук- ционной гипотезы к переходу (q i, x i, B i ) (q i + 1,, ), где l i n, дает основание заключить, что (**) [q i B i q i + 1 ] x i, i = 1, 2,..., m, q m + 1 = p. С помощью упомянутых правила (*) и частичных выводов (**) можно выстроить требуемый вывод:правила [qAp] a[q 1 B 1 q 2 ][q 2 B 2 q 3 ]... [q m B m q m + 1 ] ax 1 [q 2 B 2 q 3 ]...[q m B m q m + 1 ]... … ax 1 x 2... x m = x.

78 L = N(M) L cfl II. Индукцией по длине вывода l покажем, что если [qAp] x, то (q, x, A) (p,, ). База. Пусть l = 1. Имеем [qAp] x. Очевидно, что на этом единственном шаге применено правило [qAp] x. По способу построения cfg G: x { }. Такое правило существует, если только (p, ) (q, x, A). А тогда (q, x, A) (p,, ).

79 L = N(M) L cfl Индукционная гипотеза. Предположим, что утверждение выполняется для всех значений l n (n 1). Индукционный переход. Докажем, что утверждение выполняется для l = n + 1. Пусть [qAp] a[q 1 B 1 q 2 ][q 2 B 2 q 3 ]...[q m B m q m+1 ] ax 1 x 2...x m = x.

80 L = N(M) L cfl Следовательно, существует правило [qAp] a[q 1 B 1 q 2 ][q 2 B 2 q 3 ]...[q m B m q m+1 ] P, использованное на первом шаге вывода, в котором q m + 1 = p, и частичные выводы [q i B i q i + 1 ] x i, где l i n, i = 1, 2,..., m. Такое правило существует благодаря тому, что. Из частичных выводов в соответствии с индукционной гипотезой вытекает, что (q i, x i, B i ) (q i + 1,, ), i = 1, 2,..., m, q m + 1 = p. (q 1, B 1 B 2... B m ) (q, a, A)

81 L = N(M) L cfl Следовательно, существует последова- тельность конфигураций: (q, x, A) = (q, ax 1 x 2...x m, A) (q 1, x 1 x 2...x m, B 1 B 2... B m ) (q 2, x 2... x m, B 2...B m )... (p,, ). Итак, из рассуждений, проведенных в пп. I и II, следует справедливость вспомогатель- ного утверждения: [qAp] x (q, x, A) (p,, ). В частности, при q = q 0 и A = Z 0, имеем [q 0 Z 0 p] x (q 0, x, Z 0 ) (p,, ).

82 L = N(M) L cfl Остается вспомнить, что существуют правила вида S [q 0 Z 0 q] для любых q Q, в частности, для q = p. Тогда, пристраивая новое начало к имеющемуся выводу [q 0 Z 0 p] x: S [q 0 Z 0 p] x, заключаем, что S x тогда и только тогда, когда (q 0, x, Z 0 ) (p,, ), или, что то же самое, L(G) = N(M). Что и требовалось доказать.

83 Теоремы 5.1, 5.2 и 5.3 можно подытожить: следующие три высказывания являются эквивалентными: 1) L cfl; 2) L = N(M 1 ) для некоторого pda M 1 ; 3) L = T(M 2 ) для некоторого pda M 2. L = N(M) L cfl

84 Пример 5.3. Пусть pda M = ({q 0, q 1 }, {0, 1}, {X, Z},, q 0, Z, ), где : {(1) (q 0, 0, Z) = {(q 0, XZ)} (2) (q 0, 0, X) = {(q 0, XX)} (3) (q 0, 1, X) = {(q 1, )} (4) (q 1, 1, X) = {(q 1, )} (5) (q 1,, X) = {(q 1, )} (6) (q 1,, Z) = {(q 1, )}} Нетрудно сообразить, что N(M) = {0 n 1 m 1 n; 1 m n} Отображение в магазине 0 X Стирающие -движения Стирающие 1-движения

85 (q 0, 001, Z) (q 0, 01, XZ) (q 0, 1, XXZ) (q 1,, XZ) (q 1,, Z) (q 1,, ) n = 2, m = 1, n m. Пример 5.3.

86 Пример 5.3. Построим cfg G = (V N, V T, P, S), порож- дающую язык N(M), положив V N = {S, [q 0 Zq 0 ], [q 0 Zq 1 ], [q 1 Zq 0 ], [q 1 Zq 1 ], [q 0 Xq 0 ], [q 0 Xq 1 ], [q 1 Xq 0 ], [q 1 Xq 1 ]}, V T ={0, 1}. Для экономии времени при построении правил грамматики начнём с движений (3 6).3 6 Именно они дают начало продуктивным правилам.

87 Пример 5.3. Движение (4) (q 1, 1, X) = {(q 1, )} даёт: [q 1 X q 1 ] 1 Движение (5) (q 1,, X) = {(q 1, )} даёт: [q 1 X q 1 ] Движение (6) (q 1,, Z) = {(q 1, )} даёт: [q 1 Z q 1 ] Движение (3) (q 0, 1, X) = {(q 1, )} даёт: [q 0 X q 1 ] 1 Итак, в множество продуктивных нетерминалов R включены: [q 0 X q 1 ], [q 1 X q 1 ], [q 1 Z q 1 ].

88 Далее мы построим правила для S: (0.1) S [q 0 Zq 0 ] и (0.2) S [q 0 Zq 1 ]. Затем, исходя из движения (1), мы добавим правила для нетерминала [q 0 Zq 0 ]:1 {(1) (q 0, 0, Z) = {(q 0, XZ)}} (1.1) [q 0 Zq 0 ] 0[q 0 Xq 0 ][q 0 Zq 0 ], (1.2) [q 0 Zq 0 ] 0[q 0 Xq 1 ][q 1 Zq 0 ]. Поскольку только [q 0 Xq 1 ], [q 1 Xq 1 ], [q 1 Zq 1 ] продуктивные, то оба правила ( ), а также (0.1), излишни. Пример 5.3.

89 Теперь определим правило для нетерминала [q 0 Zq 1 ] из правой части (0.2) по движению (1) (q 0, 0, Z) = {(q 0, XZ)}: (1.3) [q 0 Zq 1 ] 0[q 0 Xq 0 ][q 0 Zq 1 ] (1.4) [q 0 Zq 1 ] 0[q 0 Xq 1 ][q 1 Zq 1 ] Правило (1.3) излишне, так как нетерминалы в правой части этого правила непродуктивные. Правила (0.2) и (1.4) дают основание считать R множеством нетерминалов не только продуктив- ных, но и достижимых, и включить [q 0 Zq 1 ] в R: R = {[q 0 Xq 1 ], [q 1 Xq 1 ], [q 1 Zq 1 ] }. Пример 5.3., [ q 0 Zq 1 ]

90 Добавим правила для нетерминала [q 0 Xq 1 ] из правой части (1.4), исходя из движения (2) (q 0, 0, X) = {(q 0, XX)} (2.1) [q 0 Xq 1 ] 0[q 0 Xq 0 ][q 0 Xq 1 ], (2.2) [q 0 Xq 1 ] 0[q 0 Xq 1 ][q 1 Xq 1 ]. Так как [q 0 Xq 0 ] R, R = {[q 0 Xq 1 ], [q 1 Xq 1 ], [q 1 Zq 1 ], [q 0 Zq 1 ]},то правило (2.1) излишне. Правило (2.2) не даёт ничего для пополне- ния множества R всё нетерминалы в правой части уже находится в R. Пример 5.3.

91 Теперь определим правило для нетерминала [q 1 Xq 1 ] из правой части (2.2) по движению (2) (q 1, 0, X) = {(q 1, XX)}: (2.3) [q 1 Xq 1 ] 0[q 1 Xq 0 ][q 0 Xq 1 ] (2.4) [q 1 Xq 1 ] 0[q 1 Xq 1 ][q 1 Xq 1 ] Правило (2.3) излишне, так как нетерминал [q 1 Xq 0 ] в правой части этого правила непродуктивный, ибо R = {[q 0 Xq 1 ], [q 1 Xq 1 ], [q 1 Zq 1 ], [q 0 Zq 1 ] }. Пример 5.3.

92 Окончательно получаем следующее мно- жество правил приведённой грамматики: (0.2) S [q 0 Zq 1 ], (1.4) [q 0 Zq 1 ] 0[q 0 Xq 1 ][q 1 Zq 1 ], (2.2) [q 0 Xq 1 ] 0[q 0 Xq 1 ][q 1 Xq 1 ], (2.4) [q 1 Xq 1 ] 0[q 1 Xq 1 ][q 1 Xq 1 ], (3) [q 0 Xq 1 ] 1, (4) [q 1 Xq 1 ] 1, (5) [q 1 Xq 1 ], (6) [q 1 Zq 1 ]. Заметим, что первый индекс, не равный 0, в номерах правил грамматики соответствует номеру равенства в определении. Пример 5.3.

93 Пример 5.3. Обозначим [q 0 Zq 1 ] = A, [q 1 Zq 1 ] = B, [q 0 Xq 1 ] = C, [q 1 Xq 1 ] = D. В новых обозначениях нетерминалов имеем следующие правила грамматики: (1) S A, (2) A 0CB, (3) B (4) C 0CD (5) C 1, (6) D 0DD, (7) D 1, (8) D. S A 0CB 00CDB 001DB 001B 001. Next