Главная Промышленная автоматика. гл. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Лемма 2.12. Пусть Saa, ,..,а„-вывод цепочки а„ аз S в КС-грамматике G-(N, 2, Р, S). Тогда в G можно построить дерево вывода D, для которого а,~крона, а а, а, .. a-i ~~ некоторые из крон сечений. Доказательство. Построим такую последовательность деревьев выводов (0<г</г), что а- -крона дерева D,-. Пусть £) дерево, состоящее из единственной вершины, помеченной S. Допустим, что а,- = р/Лу,- и после применения правила А-Х-Х ... Xf, к выделенному вхождению А получается - fcTr Тогда дерево D получается из D-добавлением к листу, помеченному выделенным вхождением Л (он является (IPH + O символом кроны дерева k прямых Xi л*! • • • Yfc Рис, 2.10. Построение деревьев выводов. потомков, которые помечаются Х, Х, Х соответственно. Очевидно, что кроной дерева D;., будет ct/+i. Построение D;.j по показано на рис. 2.10. Дерево D„ будет искомым деревом вывода D. □ Докажем обращение леммы 2.12, т. е. покажем, что для каждого дерева вывода в грамматике G существует хотя бы один соответствующий вывод. Лемма 2.13. Пусть D -дерево вывода в КС-грамматике G~ -=(N, S, Р, S) с кроной а. Тогда 5=Ф*а. Доказательство. Пусть Co,Cj, С, -такая после- довательность сечений дерева D, что (1) Сц содержит только корень дерева D, (2) С, + 1 для 0<г < /г получается из С,- заменой одной нетерминальной вершины ее прямыми потомками, (3) С„ -крона дерева D. Ясно, что хотя бы одна такая последовательность существует. Если -крона сечения С,-, то а, а, ..., «„ - вывод цепочки а„ из «о в G. □ Среди выводов, которые можно построить по данному дереву, два вывода нас особенно интересуют, 2.4. КОНТСКСТИО-СРОБОДНЫЕ ЯЗЫКИ Определение. Если в доказательстве леммы 2.13 сечение С,-+ получается из С/ заменой самой левой нетерминальной вершины в С{ ее прямыми потомками, то соответствующий вывод ccq, а,, ,.., а„ называется левым выводом цепочки а„ из в грамматике G. Правый вывод определяется аналогично, надо только в предыдущем предложении читать „самой правой" вместо „самой левой". Заметим, что левый (илн правый) вывод определяется по дереву вывода однозначно. Если 3-=а,а, а„ левый вывод терминальной цепочки то каждая цепочка (0<г<и) имеет вид xAfii, Рис. 2.П. Пример дерева. где л:/62*, А,.£ и P,-€(NUS)*. Каждая следующая цепочка cc/..j левого вывода получается из предыдущей к,- заменой самого левого нетерминала Л,- правой частью некоторого правила. В правом выводе заменяется самый правый нетерминал. Пример 2.21, Рассмотрим КС-грамматику Gq с правилами T~TF\F F-{E)\a Дерево вывода, показанное на рис. 2.11, служит представлением десяти эквивалентных выводов цепочки а+ G. Ее левый вывод - а правый вывод - Определение. Цепочку а будем называть левовыводимой (в грамматике G), если существует левый вывод 3 = а,а, ...,а„-а, и писать S=>OL (или 5=?>*а„, когда ясно, какая грамматика G имеется в виду). Аналогично а будем называть правовыводи-юй, если существует правый вывод 5 = а, ..., а„ - а, и писать S=Qa (или 5=:>*о). Один шаг левого вывода обозначим через =;, а шаг правого вывода - через Леммы 2,12 и 2.13 можно объединить в одну теорему: Теорема 2.11. Пусть G = , Р, 8)~КС-граммотика. 5=Ф*а тогда и только тогда, когда в G существует дерево вывода с кроной а. Доказательство. Это непосредственно следует из лемм 2.12 и 2.13. □ Заметим, что мы остерегались говорить, что если дан вывод 5=?>*а в КС-грамматике, то можно найти единственное дерево вывода в G с кроной а. Причина этого заключается в том, что есть КС-грамматики, у которых может быть несколько различных деревьев выводов с одной и той же кроной. Такова грамматика из примера 2.19. На рис. 2.8 показаны разные деревья выводов (в) н (г) с одной и той же кроной, Определение. КС-грамматику G называют неоднозначной, если существует хотя бы одна цепочка wL{G), которая является кроной двух или более различных деревьев выводов в G. Это равносильно тому, что некоторая цепочка wL{G) имеет два или более разных левых (правых) вывода (упр. 2.4.4). В противном случае КС-грамматика G называется однозначной. Неоднозначность будет подробнее рассмотрена в разд. 2.6.5. 2.4.2. Преобразования КС-грамматик Данную грамматику часто требуется модифицировать так, чтобы порождаемый ею язык приобрел нужную структуру. Рассмотрим, например, язык L{Gf,). Этот язык может порождаться грамматикой G с правилами £->£ + ££*£1(£)а Но грамматика G имеет два недостатка. Прежде всего она неоднозначна из-за наличия в ней правил Е-i-E-i-ElEE. Эту неоднозначность можно устранить, взяв вместо G грамматику Gj с правилами Т (£) I а Другой недостаток грамматики G, которым обладает также и Gj, заключается в том, что операции -- и * имеют один и тот же приоритет. Иначе говоря, структура выражений о4-й*а н asa + i, которую придает им грамматика G, подразумевает тот же порядок выполнения операций, что и в выражениях {а~а}<-а и (о«а)-fa соответственно. Чтобы получить обычный приоритет операций + и *, при которол! « предшествует + и выражение а~\-аиа понимается как о + (сг«(3). надо перейти к грамматике G. Общего алгоритмического метода, который придавал бы данному языку произвольную структуру, не существует. Но с помощью ряда преобразований можно видоизменить грамматику, не испортив порождаемого ею языка. В данном разделе и разд. 2.4.3-2.4.5 мы укажем несколько преобразований такого рода. Начнем с очевидных, но важных преобразований. В некоторых случаях КС-грамматика может содержать бесполезные символы и правила. Например, в грамматике G={{S,A], {а, Ь], Р, 5), где Р \S~a, А->Ь\, нетерминал А и терминал Ь не могут появиться ни в какой выводимой цепочке. Таким образом, эти символы не имеют отношения к языку L{G), и их можно устранить из определения грамматики G, не затронув языка L{G). Определение. Назовем символ X N (J S бесполезным в КС-грамматике G(N, S, Р, S), если в ней пет вывода вида Sr=*wXy ->* цЛу, где W, X, у принадлежат S*. Чтобы установить, бесполезен ли нетерминал А, построим сначала алгоритм, выясняющий, может ли нетерминал порождать какие-нибудь терминальные цепочки, т. е. решающий проблему пустоты множества {w\A*w, S*}. Из существования такого алгоритма следует разрешимость проблемы пустоты для КС-грам-матнк. Алгоритм 2,7. Непуст ли язык L(G)? Вход. КС-грамматика G-(N, 2, Р, S). Выход. „ДА", если 1{С)Ф0, „НЕТ" в противном случае. Метод. Строим множества N,, Nj, ... рекурсивно: (1) Положить N0 и i-1. (2) Положить aG и ct G (n,- i U 2)*} U Vj. (3) Если N,7N, i, положить \ и перейти к шагу (2). В противном случае положить NN. (4) Если s€Ng, выдать выход „ДА", в противном случае »НЕТ". □ Так как NN, то алгоритм 2.7 должен остановиться самое большее после /2 + 1 повторений шага (2), если N содержит п нетерминалов. Докажем корректность алгоритма 2.7. Доказательство простое и послужит в качестве модели для нескольких аналогичных доказательств. Теорема 2.12. Алгоритм 2.7 говорит ,да" тогда и только тогда, когда для некоторой цепочки w1f\ Доказательство. Сначала докажем индукцией по i, что (2.4.1) если 6N;, то A=*w для некоторой цепочки w£2*. Базис, 1 = 0, не нуждается в доказательстве, так как ]Ф0, Предположим, что утверждение (2.4.1) истинно для i, и возьмем GNi+i- Если Л принадлежит также и N,-, то шаг индукции тривиален. Если Л N-+£ - N, то существует правило Л->Xi...X,;, где каждый символ Х,- принадлежит либо 2, либо N,-. Таким образом, для каждого Ху можно найти такую цепочку Wj, что Xj*Wj: если Ху2, то Wj = Xj, в противном случае существование Wy следует нз (2.4.1). Легко видеть, что ЛгХ ... X„z*w,X,...X„z* ...z*w,...Wf, Случай k = 0 (т. е. правило Л->е) не составляет исключения. Шаг индукции окончен. Определение множеств гарантирует, что если Nj-N,- i, то N-N,-.j.i = ... . Мы должны показать, что если Azw для некоторой цепочки wI,*, то А. В силу сделанного выше замечания все, что нужно показать, это что ЛGNJ для некоторого i. Индукцией по п докажем, что (2.4.2) если Az"w, то ЛК,- для некоторого Базис, п=1, тривиален - в этом случае i-l. Допустим, что (2.4.2) истинно для п, н пусть Az"w. Тогда можно написать AzXi ... X/zw, где цепочка w = W- • • • такова, что XjzjWj для каждого / н tijti). Согласно (2.4.2), если XyN, то XyN-. для некоторого /у. Если XyG2, то lyO. Пусть i--l+raax(ii, ....г). Тогда по определению Л N-. Индукция завершена. Положив Л = 5 в (2.4.1) и (2.4.2), получим утверждение теоремы. □ Следствие. Для КС-грамматики G проблема пустоты языка L (G) разрешима. □ Определение. Символ X 6 N U 2 назовем недостижимым в КС-грамматике G = (N, 2, Р, 5), если X не появляется ни водной выводимой цепочке. Недостижимые символы, можно устранить из КС-грамматнки с помощью следующего алгоритма, который легко получить из алгоритма 0.3. 1) Это „очевидное" замечание требует тем не менее некоторого осмысле иия: представьте себе дерево вывода Az=>w, в нем ш-крона поддеоевя с корнем Xj. Алгоритм 2.8. Устранение недостижимых символов. Вход. КС-грамматика G--(N, 2, Р, S). Выход. КС-грамматика G=(N, 2, Р, 5), у которой (i) L(G) = L{G), (ii) для всех XN U2 существуют такие цепочки а и р из (NU2)*, что 5=ФоаХр. Метод. (1) Положить {5} и i=\. (2) Положить К;-{Х в Р есть Л-аХр и Л G ,--Л U К,. £. (3) Если 1/,-К,- 1, положить г = 1+ и перейти к шагу (2). В противном случае пусть N = l/,nN, 2К,П2, Р состоит из правил множества Р, содержащих только символы из Vi, G = {W, 2. Р, S). □ Алгоритмы 2.7 и 2.8 очень похожи. Заметим, что шаг (2) алгоритма 2.8 можно повторить только конечное число раз, так как K,-Nu2. Кроме того, прямое доказательство индукцией по i показывает, что 5=с>о/аХр тогда и только тогда, когда XVi для некоторого i. Теперь мы готовы устранить из КС-грамматики все бесполезные символы. Алгоритм 2.9. Устранение бесполезных символов. Вход. КС-грамматика G-(N, 2, Р, S), у которой 1{О)Ф0. Выход. КС-грамматика G-(N, 2, Р, S), у которой L{G) = L{G) н в NU2 нет бесполезных символов. Метод. (1) Применив к G алгоритм 2.7, получить N. Положить i(NnN, 2, Pj, 5), где Pj состоит из правил множества Р, содержащих только символы из NU2. (2) Применив к G алгоритм 2.8, получить G = (N\ 2, Р, 5). □ На шаге (1) алгоритма 2.9 из G устраняются все нетерминалы, Которые не могут порождать терминальных цепочек. Затем на шаге (2) устраняются все недостижимые символы. Каждый символ X результирующей грамматики должен появиться хотя бы в одном выводе вида S=*wXy=* wxy. Заметим, что если сначала применить алгоритм 2.8, а потом алгоритм 2.7, то не всегда результатом будет грамматика, не содержащая бесполезных символов. 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.0022 |