dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 57
Текст из файла (страница 57)
P2 допускает по заключительному состоянию то, что P допускает по пустому магазину.6.2.7.250Стр. 250(!) Покажите, что если P — МП-автомат, то существует МП-автомат P2, у которого только два магазинных символа и L(P2) = L(P). Указание. Рассмотрите двоичное представление магазинных символов P.ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞ6.2.8.(∗!) МП-автомат называется ограниченным, если при любом переходе он можетувеличивать высоту магазина не более, чем на один символ. Таким образом, если (p, γ) содержится в функции переходов, то |γ| ≤ 2.
Докажите, что если P —МП-автомат, то существует ограниченный МП-автомат P3, для которогоL(P3) = L(P).6.3. Ýêâèâàëåíòíîñòü ÌÏ-àâòîìàòîâ è ÊÑ-ãðàììàòèêВ этом разделе мы покажем, что МП-автоматы определяют КС-языки. План доказательства изображен на рис. 6.8. Цель состоит в том, чтобы доказать равенство следующих классов языков.1.Класс КС-языков, определяемых КС-грамматиками.2.Класс языков, допускаемых МП-автоматами по заключительному состоянию.3.Класс языков, допускаемых МП-автоматами по пустому магазину.Мы уже показали, что классы 2 и 3 равны.
После этого достаточно доказать, что совпадают классы 1 и 2.ГрамматикаМП!автоматпо пустомумагазинуМП!автоматпо заключительномусостояниюРис. 6.8. Организация конструкций, показывающих эквивалентность трехспособов определения КС-языков6.3.1. Îò ãðàììàòèê ê ÌÏ-àâòîìàòàìПо данной грамматике G строится МП-автомат, имитирующий ее левые порождения.Любую левовыводимую цепочку, которая не является терминальной, можно записать ввиде xAα, где A — крайняя слева переменная, x — цепочка терминалов слева от A, α —цепочка терминалов и переменных справа.
Aα называется остатком (tail) этой левовыводимой цепочки. У терминальной левовыводимой цепочки остатком является ε.Идея построения МП-автомата по грамматике состоит в том, чтобы МП-автомат имитировал последовательность левовыводимых цепочек, используемых в грамматике дляпорождения данной терминальной цепочки w. Остаток каждой цепочки Aα появляется вмагазине с переменной A на вершине. При этом x “представлен” прочитанными на входесимволами, а суффикс цепочки w после x считается непрочитанным.Предположим, что МП-автомат находится в конфигурации (q, y, Aα), представляющей левовыводимую цепочку xAα.
Он угадывает продукцию, используемую для расши6.3. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ ÌÏ-ÀÂÒÎÌÀÒÎÂ È ÊÑ-ÃÐÀÌÌÀÒÈÊСтр. 251251рения A, скажем, A → β. Переход автомата состоит в том, что A на вершине магазина заменяется цепочкой β, и достигается МО (q, y, βα). Заметим, что у этого МП-автоматаесть всего одно состояние, q.Теперь (q, y, βα) может не быть представлением следующей левовыводимой цепочки,поскольку β может иметь терминальный префикс. В действительности, β может вообщене иметь переменных, а у α может быть терминальный префикс. Все терминалы в началецепочки βα нужно удалить до появления следующей переменной на вершине магазина.Эти терминалы сравниваются со следующими входными символами для того, чтобыубедиться, что наши предположения о левом порождении входной цепочки w правильны;в противном случае данная ветвь вычислений МП-автомата отбрасывается.Если таким способом нам удается угадать левое порождение w, то в конце концов мыдойдем до левовыводимой цепочки w.
В этот момент все символы в магазине или расширены (если это переменные), или совпали с входными (если это терминалы). Магазинпуст, и мы допускаем по пустому магазину.Уточним приведенное неформальное описание. Пусть G = (V, T, Q, S) — КСграмматика. Построим МП-автомат P = ({q}, T, V U T, δ, q, S), который допускает L(G)по пустому магазину. Функция переходов δ определена таким образом:1.δ(q, ε, A) = {(q, β) | A → β — продукция G} для каждой переменной A.2.δ(q, a, a) = {(q, ε)} для каждого терминала a.Пример 6.12. Преобразуем грамматику выражений (см. рис. 5.2) в МП-автомат.
Напомним эту грамматику.I → a | b | Ia | Ib | I0 | I1E → I | E * E | E + E | (E)Множеством входных символов для МП-автомата является {a, b, 0, 1, (, ), +, *}. Эти восемь символов вместе с переменными I и E образуют магазинный алфавит. Функция переходов определена следующим образом:а) δ(q, ε, I) = {(q, a), (q, b), (q, Ia), (q, Ib), (q, I0), (q, I1)};б) δ(q, ε, E) = {(q, I), (q, E + E), (q, E * E), (q, (E))};в) δ(q, a, a) = {(q, ε)}; δ(q, b, b) = {(q, ε)}; δ(q, 0, 0) = {(q, ε)}; δ(q, 1, 1) ={(q, ε)}; δ(q, (, () = {(q, ε)}; δ(q, ), )) = {(q, ε)}; δ(q, +, +) = {(q, ε)}; δ(q, *, *) ={(q, ε)}.Заметим, что пункты (а) и (б) появились по правилу 1, а восемь переходов (в) — по правилу 2.
Других переходов у МП-автомата нет.Теорема 6.13. Если МП-автомат P построен по грамматике G в соответствии с описанной выше конструкцией, то N(P) = L(G).Доказательство. Докажем, что w ∈ N(P) тогда и только тогда, когда w ∈ L(G).(Достаточность) Пусть w ∈ L(G). Тогда w имеет следующее левое порождение.252Стр. 252ÃËÀÂÀ 6.
ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞS = γ1 ⇒ γ2 ⇒ … ⇒ γn = wlmlmlm*Покажем индукцией по i, что (q, w, S) |− (q, yi, αi), где yi и αi представляют левовыводиPмую цепочку γi. Точнее, пусть αi является остатком γi, и γi = xiαi. Тогда yi — это такая цепочка, что xiyi = w, т.е. то, что остается на входе после чтения xi.*Базис. γ1 = S при i = 1. Таким образом, x1 = ε, и y1 = w. Поскольку (q, w, S) |− (q, w, S)через 0 переходов, базис доказан.Индукция.
Теперь рассмотрим вторую и последующие левовыводимые цепочки.Предположим, что*(q, w, S) |− (q, yi, αi)*и докажем, что (q, w, S) |− (q, yi+1, αi+1). Поскольку αi является остатком, он начинаетсяпеременной A. Кроме того, шаг порождения γi ⇒ γi+1 включает замену переменной A одlmним из тел ее продукций, скажем, β. Правило 1 построения P позволяет нам заменить Aна вершине магазина цепочкой β, а правило 2 — сравнить затем любые терминалы навершине магазина со следующими входными символами. В результате достигается МО(q, yi+1, αi+1), которое представляет следующую левовыводимую цепочку γi+1.Для завершения доказательства заметим, что αn = ε, так как остаток цепочки γn (а она*представляет собой w) пуст. Таким образом, (q, w, S) |− (q, ε, ε), т.е.
P допускает w попустому магазину.(Необходимость) Нам нужно доказать нечто более общее, а именно: если P выполняет последовательность переходов, в результате которой переменная A удаляется из вершины магазина, причем магазин под ней не обрабатывается, то из A в грамматике G порождается любая цепочка, прочитанная на входе в этом процессе. Формально:**PG• если (q, x, A) |− (q, ε, ε), то A ⇒ x.Доказательство проведем индукцией по числу переходов, совершенных P.Базис. Один переход.
Единственной возможностью является то, что A → ε — продукция грамматики G, и эта продукция использована в правиле типа 1 МП-автоматом P.В этом случае x = ε, и A ⇒ ε.Индукция. Предположим, что P совершает n переходов, где n > 1. Первый переходдолжен быть типа 1, где переменная A на вершине магазина заменяется одним из тел еепродукций. Причина в том, что правило типа 2 может быть использовано, когда на вершине магазина находится терминал.
Пусть использована продукция A → Y1Y2…Yk, гдекаждый Yi есть либо терминал, либо переменная.В процессе следующих n – 1 переходов P должен прочитать x на входе и вытолкнутьY1, Y2, …, Yk из магазина по очереди. Цепочку x можно разбить на подцепочки x1x2…xk,6.3. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ ÌÏ-ÀÂÒÎÌÀÒÎÂ È ÊÑ-ÃÐÀÌÌÀÒÈÊСтр. 253253где x1 — порция входа, прочитанная до выталкивания Y1 из магазина, т.е. когда длинамагазина впервые уменьшается до k – 1. Тогда x2 является следующей порцией входа,читаемой до выталкивания Y2, и т.д.На рис. 6.9 представлены разбиение входа x и соответствующая обработка магазина.Предполагается, что β имеет вид BaC, поэтому x разбивается на три части x1x2x3, гдеx2 = a.
Заметим, что вообще, если Yi — терминал, то xi также должен быть терминалом.Рис. 6.9. МП-автомат A прочитывает x и удаляет BaC из своего магазина*Формально мы можем заключить, что (q, xixi+1…xk, Yi) |− (q, xi+1…xk, ε) для всех i = 1,2, …, k. Кроме того, длина ни одной из этих последовательностей переходов не превышает n – 1, поэтому применимо предположение индукции в случае, если Yi — перемен*ная.
Таким образом, можно заключить, что Yi ⇒ xi.Если Yi — терминал, то должен совершаться только один переход, в котором прове*ряется совпадение xi и Yi. Опять-таки, можно сделать вывод, что Yi ⇒ xi; на этот раз порождение пустое. Теперь у нас есть порождение***A ⇒ Y1Y2…Yk ⇒ x1Y2…Yk ⇒ … ⇒ x1x2…xk.*Таким образом, A ⇒ x.Для завершения доказательства положим A = S и x = w. Поскольку нам дано, что**w ∈ N(P), то (q, w, S) |− (q, ε, ε). По доказанному индукцией имеем S ⇒ w, т.е. w ∈ L(G). 254Стр. 254ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞ6.3.2. Îò ÌÏ-àâòîìàòîâ ê ãðàììàòèêàìЗавершим доказательство эквивалентности, показав, что для любого МП-автомата Pнайдется КС-грамматика G, язык которой совпадает с языком, допускаемым P по пустому магазину.
Идея доказательства основана на том, что выталкивание одного символа измагазина вместе с прочтением некоторого входа является основным событием в процессе работы МП-автомата. При выталкивании из магазина МП-автомат может изменятьсвое состояние, поэтому нам следует учитывать состояние, достигаемое автоматом, когда он полностью освобождает свой магазин.pYpYpYpxxxРис. 6.10. МП-автомат совершает последовательность переходов, в результатекоторых символы по одному удаляются из магазинаНа рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
