Главная Промышленная автоматика. должать ли моделирование Р или перейти в специальное состояние которое опустошит магазин. Но есть одно осложнение. Для некоторой входной цепочки w автомат Р может сделать последовательность тактов, приводящую к опустошению магазина, а управляющее устройство окажется при этом не в заключительном состоянии. Тогда для того, чтобы помешать Р допустить в этом случае цепочку w, добавим к Р специальный маркер, отмечающий дно магазина, который автомат Р может устранить только в состоянии д. Формально положим Р = (QU{9„9}, 2, Ги{Г}, б, 9, 0)1), где б определяется так: (1) если 6{g,a,Z) содержит (/-, у), то Ь[д, а, Z) содержит (г, V) для всех gQ, a£2\j{e} и ZV; (2) б((?, е, Z) {(Q, Z(,Z)}, т. е. на первом такте автомат Р записывает в дмагазиц Z(,Z и переходит в начальное состояние автомата Р (Z играет роль маркера, отмечающего дно магазина); (3) для всех gF и Z£V[j{Z} множество бе, Z) содержит е); (4) Ь (д, е, Z) = {{q, е)} для всех Z£V\J{Z}. Легко видеть, (g\w,Z)[~P(g,,w,Z,Z) \ ЪЛде, К,...К,) где YrZ\ тогда и только тогда, когда (g,,w, Z,) \--р(д, е,Г,...У, ,) для gF я Vi...Vr-ieT\ Следовательно, L,{P) = L{P), □ Справедливо также и обращение леммы 2.22. Лемма 2.23. Пусть P = (Q, S, Г, б, д,, Z„ 0) -МП-автомат. Можно построить такой МП-автомат Р\ что L(P) - L{P). Доказательство. Р будет моделировать Я, используя в надлежащий момент специальный символ Z находящийся на дне магазина. В тот момент, когда автомат Р может прочесть Z, он будет переходить в новое заключительное состояние у. Формальное построение оставляем в качестве упражнения. □ 1) Для МП-автомата, допускающего язык опустошением магазина, множество заключительных состояний обычно берется пустым. Его, очевидно, можно сделать каким угодно. 2.5.3. Эквиввлентность МП-автоматов и КС-грамматик С помощью полученных результатов можно теперь показать, что языки, определяемые МП-автоматами - это в точности КС-языки. Начнем с построения естественного (недетерминированного) „нисходящего" распознавателя, эквивалентного данной КС-грамматике. Лемма 2.24. Пусть G = (N, S, Я, S) -КС-грамматика. По грамматике G можно построить такой МП-автомат что L,{R)=L{G). Доказательство. Построим R так, чтобы он моделировал все левые выводы в G. Пусть R = {{g}, 2, NUS, б, д, 5, 0), где б определяется следующим образом: (1) если Л~*-а принадлежит Я, то Ь{д, е, Л) содержит {д, а); (2) б ((?, а, а) = {(д, е)} для всех az. Мы хотим показать, что (2.5.2) A"w тогда и только тогда, когда ((?, Л)\-" {д,еуе) для некоторых т, п> I Необходимость условия докажем индукцией по т. Допустим, что Aw. Если m=I и w = а.. .a,(kO), то (д, а...а„, А)}~(д, ау...а, а,. .а) И(9. е) Теперь предположим, что A"w для некоторого т>1. Первый шаг этого вывода должен иметь вид Л гф-ХХд.. .Х, где X,-="X/ для некоторого/п-< т, \ik, я хх., .Xiw. Тогда (9, Л)Н(9, X,X,...Xft) Если XN, то по предположению индукции {q> Xi)\-*{g, е, е) Если X,- = x,-S, то (д, Xi, Х,-)[-(?, е, е) Объединяя вместе эти последовательности тактов, видим, что {д, W, А)[- [д, е, е). Для доказательства достаточности покажем индукцией по п, что если [д, Л) " {д, е, е), то Л w. Если п=\, то w = e и Л-е принадлежит Я. Предположим, Что утверждение верно для всех п < п. Тогда первый такт, сделанный МП-автоматом R, должен иметь вид iq, W, A)\-{q, w, Х,...Х) причем {q, XI, Х,-)[-"(9, е, е) для \ik н w = XiX..,Xf, (лемма 2.20). Тогда Л->Х.. .Х-правило из Я, и по предположению индукции Xi Xi для Xi 6N. Если X/ 2, то X,-Таким образом, =>* xjxa. . Xk-iXk W - вывод цепочки из Л в грамматике G. Из (2.5.2), в частности, вытекает, что 5 г+И) тогда и только тогда, когда (q, w, 5)1-+ {q, е, е). Следовательно, Le(R) = L(G),[2 Примера 2.34. Построим МП-автомат Р, для которого (Р) = - L (Go), где Gq-наша обычная грамматика, определяющая арифметические выражения. Пусть P==({q], 2, Г, б, q, Е, 0), где 6 определяется так; (1) 6(7, е, £) = {(?, £ + Т), (9, Г)}; (2) 6(9, Г)-{(9, Г.Р), (9, Р)}; (3) 6(9, Р)-{(9, ()), (?,«)}; (4) 6(9, г, Ь)-{(9, )} для всех Ь{а, +, (,)}• При входе аа it а для Р возможна среди других последовательность тактов (9, a + £)1-(9, a + .+7) Н(, а + й*а, Г+Г) 1-(9, G + a*Q, РЧ-Г) Ь(?, Q + flwQ, а + Г) Ь(?, +Г) а--а, Т) l~iq, аа, TF) \-{q, а-а, Р*Р) \-{q, аа, aF) f-(9, *а, *Р) f~(9, а, F) \~(q, а, й) » ) Заметим, что вычисление МП-автомата Р соответствует левому выводу цепочки а-аа из £ в КС-грамматике Go. □ 2.5. автоматы с МАГАЗИЫ1ЮЙ ПАМЯТЬЮ Тип синтаксического анализа, проводимого для КС-грамматики МП-автоматом, построенным в лемме 2.24, называется „нисходящим анализом" („анализом сверху вниз") или „предсказывающим анализом", потому что при этом дерево вывода строится по существу сверху (от корня) вниз, а каждый такт вида (1) можно трактовать как предсказание очередного шага левого вывода. Подробно нисходящий синтаксический анализ будет обсуждаться в гл. 3-5. Можно построить расширенный МП-автомат, который работает „снизу вверх" как „восходящий анализатор", моделируя в обратном порядке правые выводы в КС-грамматике. Рассмотрим цепочку q; + g*q;jL(G„) и ее правый вывод из £ в грамматике Gq. EE-yTET-F ETaEFa Предположим, что мы записываем этот вывод в обратном порядке. Если считать, что переход от цепочки а + (3*(3 к цепочке P + g*a происходит по правилу F-a, примененному „в обратном направлении", то можно сказать, что цепочка g -[- в а „свертывается слева" к цепочке Р + * Более того, это единственно возможная левая свертка. Подобным же способом можно правовыводимую цепочку Р+а*а свернуть слева к цепочке P + fi*g с помощью правила Г-j-P и т. д. Определим формально левую свертку. Определение. Пусть G = (N, 2, Р, S) -КС-грамматика и S гаЛи) r.cфи) rXW -правый вывод в ней. Будем говорить, что правовыводимую цепочку aw можно свернуть слева (или что она левосвертывается) к правовыводимой цепочке aAw с помощью правила Л-г-р. Указанное вхождение цепочки р в цепочку aw назовем основой цепочки ари). Таким образом, основа правовыводимой цепочки - это ее любая подцепочка, которая является правой частью некоторого правила, причем после замены ее левой частью этого правила тоже получается правовьшодимая цепочка. Пример 2,35, Рассмотрим грамматику с правилами S->Ac\Bd А ~aAb\ab B-aBbb\abb Она порождает язык U {a"b"d\n Ц. Рассмотрим правовыводимую цепочку aabbbbd. Единственная ее основа - подцепочка abb, так как aBbbd-правовыводимая цепочка. Заметим, что хотя а? -правая часть правила Л~аЬ, она не будет основой цепочки aabbbbd, так как aAbbbd-не правовыводимая цепочка. □ Основу правовыводимой цепочки можно было бы определить другим способом, сказав, что основа - это крона самого левого поддерева глубины 1 некоторого дерева вывода этой правовыводимой цепочки. (Дерево глубины I, состоящее нз вершины и ее прямых потомков, которые являются листьями, называют кустом или ееером.) I I Рис. 2.16. Отсечение основ. Дерево вывода цепочки q; + o*q в грамматике С,, показано на рнс. 2Л6,а. Самый левый куст состоит из самой левой вершины, помеченной F, которая является его корнем, и кроны а. Если удалить единственный лист самого левого куста, то останется дерево, показанное на рис. 2.16,6. Крона + этого дерева и есть результат левой свертки цепочки а-\-аа, а его основа - крона F поддерева с корнем, помеченным Т. Опять удалив основу, получим дерево на рис. 2.16,е. Описанный процесс свертки деревьев назовем отсечением основ. По КС-грамматике G можно построить эквивалентный расширенный МП-автомат Я, работа которого заключается в отсечении основ. Здесь удобно представлять себе магазин в виде цепочки, верхним символом которой является самый правый, а не самый левый символ. В силу этого соглашения конфигурации (расширенного) МП-автомата P = {Q, S, Г, б, (/о, Z, F) определяются точно так же, как раньше, а отношение j- несколько иначе. Если 6{q, а, а) содержит (/?, р), то будем писать {q, aw, уа)\-{р, w, ур) для всех wI,* и у€Г*. Таким образом, утверждение „6 [q, а, YZ) содержит (р, VWX)" имеет разные смыслы в зависимости от того, справа или слева расположена верхняя часть магазина. Если слева, то верхними символами до и после этого такта будут К и 1, а если справа, то верхними символами будут Z и X. По данному МП-автомату, верхний символ которого расположен слева, можно построить МП-автомат, делающий то же самое, но с верхним символом, расположенным справа, просто записывая в обратном порядке все цепочки из Г*. Например, если было {р, VWX) 6 б {q, а, YZ), то станет [р, XWV)£b{q, а, ZY). Разумеется, нужно оговорить тот факт, что верх магазина находится теперь справа. Обратно, МП-автомат с верхним символом, расположенным справа, легко превратить в МП-автомат с верхним символом слева. Мы видим, что обозначение МП-автомата в виде семерки можно интерпретировать как два разных МП-автомата в зависимости от того, какой из символов - правый или левый-считается верхним. Нам кажется, что удобство обозначений, создаваемое этими двумя соглашениями, перевешивает возможность путаницы в исходных понятиях. В дальнейшем, если не оговорено противное, будем считать, что у обычного МП-автомата верх магазина расположен слева, а у расширенного - справа. Лемма 2.25. Пусть G - (N, S, Я, S)~-¥JZ-epaMMamuKa. По G можно построить такой расширенный Ш\-автомат R, что L{R)L(G)). Работу автомата R „разумно" рассматривать как процесс отсечения основ. Доказательство. Пусть R = {{q, г}, S, NuSu{S}, б, q, $, {г}) -расширенный МП-автомат 2), в котором б определяется следующим образом: ) Лемма 2.25 очевидно следует из лемм 2.23 и 2.24, ио здесь интересна сама конструкция. ) По нашему соглашению верх его магазина расположен справа 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 [33] 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 0.0018 |