Регулярные выражения и языки (стр. 23 )

Теорема 5.7 типична для доказательств, показывающих, что та или иная грамматика задает некоторый неформально определенный язык. Сначала строится предположе­ние индукции, говорящее о свойствах цепочек, порождаемых из каждой переменной. В данном примере была только одна переменная Р, поэтому нам было достаточно до­казать, что ее цепочки были палиндромами.

Доказывается достаточность: если цепочка w удовлетворяет неформальным утвер­ждениям о цепочках переменной А, то А => w. В нашем примере, поскольку Р явля-

*

ется стартовым символом, мы утверждали "Р => w", говоря, что w принадлежит язы­ку грамматики. Обычно достаточность доказывается индукцией по длине слова w. Если в грамматике к переменных, то индуктивное утверждение имеет к частей, кото­рые доказываются с помощью взаимной индукции.

*

Нужно доказать также необходимость, т. е. что если А => w, то w удовлетворяет не­формальным утверждениям о цепочках, порождаемых из переменной А. Поскольку в

нашем примере был только стартовый символ Р, предположение о том, что

*

w б L(Gpai), было равносильно Р => w. Для доказательства этой части типична индук­ция по числу шагов порождения. Если в грамматике есть продукции, позволяющие нескольким переменным появляться в порождаемых цепочках, то «-шаговое порож­дение нужно разбить на несколько частей, по одному порождению из каждой пере­менной. Эти порождения могут иметь менее п шагов, поэтому следует предполагать утверждение индукции верным для всех значений, которые не больше п, как это об­суждалось в разделе 1.4.2.

5.1.7. Упражнения к разделу 5.1

Построить КС-грамматики для следующих языков:

а)        (*) множество {0"1п|/7> 1} всех цепочек из одного и более символов 0, за которыми следуют символы 1 в таком же количестве;

б)        (*!) множество {аУск | i или j # к) всех цепочек из символов а, за кото­рыми следуют символы Ъ и затем с так, что количества символов а и Ъ или количества Ьис различны;

в)        (!) множество всех цепочек из символов а и Ь, не имеющих вида тс, т. е. не равных ни одной цепочке-повторению;

г)        (!!) множество всех цепочек, у которых символов 0 вдвое больше, чем сим­волов 1.

Следующая грамматика порождает язык регулярного выражения 0*1(0 + 1)*.

S-M1B

А—>0А\е

В->0В\ \В\е

Запишите левое и правое порождения следующих цепочек:

а) 00101;

б) 1001; в) 00011.

Докажите, что каждый регулярный язык является КС-языком. Указание. По­стройте КС-грамматику с помощью индукции по числу операторов в регуляр­ном выражении. КС-грамматика называется праволинейной, если тело каждой продукции имеет не более одной переменной, причем она находится на правом краю тела. Таким образом, продукции праволинейной грамматики имеют вид А —> wB или A —>w, где А и В — переменные, aw — терминальная цепочка, возможно, пустая:

а)        докажите, что каждая праволинейная грамматика порождает регулярный язык. Указание. Постройте е-НКА, который имитирует левые порождения, представляя своим состоянием единственную переменную в текущей лево - выводимой цепочке;

б)        докажите, что каждый регулярный язык имеет праволинейную грамматику. Указание. Начните с ДКА, состояния которого представляются переменными грамматики.

(*!) Пусть Т= {0, 1, (,),+,*, 0, е}. Т можно рассматривать как множество символов, используемых в регулярных выражениях над алфавитом {0, 1}. Единственная разница состоит в том, что во избежание возможной путаницы вместо символа е используется символ е. Постройте КС-грамматику со мно­жеством терминалов Т, которая порождает в точности регулярные выражения в алфавите {0, 1}. Отношение => было определено с базисом "а=>а" и индукцией, утверждав-

* * ♦

шей: "из а => Р и /3 => /следует а => Есть несколько других способов опре­деления отношения =>, также равнозначных фразе: "=> есть нуль или несколь­ко шагов отношения =>". Докажите следующие утверждения:

а)        а Р тогда и только тогда, когда существует последовательность из одной или нескольких цепочек у,, у2, ..., у„ где а= yh /3 = у„ и для /'= 1, 2, ..., п - 1 имеет место у, => уьГ,

б)        если а => Р и /3 у, то а => у. Указание. Воспользуйтесь индукцией по

числу шагов в порождении Р => у.

(!) Рассмотрим КС-грамматику G, определяемую следующими продукциями: S->aS|S6|a|6

а)        докажите индукцией по длине цепочки, что ни одна цепочка в 1(G) не со­держит Ьа как подцепочку;

б)        дайте неформальное описание L(G). Уточните ответ, используя часть (а). 5.1.8. (!!) Рассмотрим КС-грамматику G, определяемую следующими продукциями.

S-> aSbS | bSaS \ e

Докажите, что L(G) представляет собой множество всех цепочек, в которых по­ровну символов а и Ь.

5.2. Деревья разбора

Для порождений существует чрезвычайно полезное представление в виде дерева. Это дерево наглядно показывает, каким образом символы цепочки группируются в подце­почки, каждая из которых принадлежит языку одной из переменных грамматики. Воз­можно, более важно то, что дерево, известное в компиляции как "дерево разбора", явля­ется основной структурой данных для представления исходной программы. В компиля­торе древовидная структура исходной программы облегчает ее трансляцию в исполняе­мый код за счет того, что допускает естественные рекурсивные функции для выполнения этой трансляции.

В данном разделе представлено понятие дерева разбора и показано, что существова­ние дерева разбора тесно связано с существованием порождений и рекурсивных выво­дов. Далее изучается сущность неоднозначности в грамматиках и языках, являющейся важным свойством деревьев разбора. Некоторые грамматики допускают, что терминаль­ная цепочка имеет несколько деревьев разбора. Такое свойство делает грамматику не­пригодной для описания языков программирования, поскольку в этом случае компилятор не мог бы распознать структуру некоторых исходных программ, и, как следствие, не мог бы однозначно определить исполняемый код, соответствующий программе.

5.2.1. Построение деревьев разбора

Будем рассматривать грамматику G = (V, Т, Р, S). Деревья разбора для G — это дере­вья со следующими свойствами.

Каждый внутренний узел отмечен переменной из V. Каждый лист отмечен либо переменной, либо терминалом, либо е. При этом, если лист отмечен Ј, он должен быть единственным сыном своего родителя. Если внутренний узел отмечен А, и его сыновья отмечены слева направо Xh Х2, ..., Хк, соответственно, то А —>Х, Х2 — Хк является продукцией в Р. Отметим, что Смо­жет быть Ј лишь в одном случае— если он отмечает единственного сына, и А Ј — продукция грамматики G.

Обзор терминов, связанных с деревьями

Мы предполагаем, что читатель знаком с понятием дерева и основными определе­ниями для деревьев. Тем не менее, напомним их вкратце.

Деревья представляют собой множества узлов с отношением родитель-сын. Узел имеет не более одного родителя, изображаемого над узлом, и нуль или несколько сыновей, изображаемых под ним. Родителей и их сыновей соединяют линии. Примеры деревьев представлены на рис. 5.4-5.6. Один узел, корень, не имеет родителя; он появляется на вершине дерева. Узлы без сыновей называются листьями. Узлы, не являющиеся листьями, называются внутренними узлами. Сын сына и так далее узла называется его потомком', соответственно, роди­тель родителя и так далее — предком. Узлы считаются потомками и предками самих себя. Сыновья узла упорядочиваются слева направо и изображаются в этом порядке. Если узел N находится слева от узла М, то считается, что все потомки узла N на­ходятся слева от всех потомков М.

Пример 5.9. На рис. 5.4 показано дерево разбора, которое использует грамматику выражений (см. рис. 5.2). Корень отменен переменной Ј. В корне применена продук­ция Ј—»Ј + Ј, поскольку три сына корня отмечены слева направо как Ј, +, Ј. В левом сыне корня применена продукция Ј —» /, так как у этого узла один сын, отмеченный переменной /. □

Пример 5.10. На рис. 5.5 показано дерево разбора для грамматики палиндромов (см. рис. 5.1). В корне применена продукция Р —» 0/>0, а в среднем сыне корня — Р —> \Р\. Отметим, что внизу использована продукция Р —> е. Это использование, при котором у узла есть сын с отметкой е, является единственным случаем, когда в дереве может быть узел, отмеченный е. □

Р

Е

О

О

Е

Е

+

Р

Р

е

I

Рис. 5.4. Дерево разбора, показы - Рис. 5.5. Дерево разбора, показы­вающее порождение 1 + ЕизЕ        .

'        '        Ч/У/У        М        Ч III III

вающее порождение Р => 0110

5.2.2. Крона дерева разбора

Если мы посмотрим на листья любого дерева разбора и выпишем их отметки слева направо, то получим цепочку, которая называется кроной дерева и всегда является це­почкой, выводимой из переменной, отмечающей корень. Утверждение о том, что крона выводима из отметки корня, будет доказано далее. Особый интерес представляют дере­вья разбора со следующими свойствами.

Крона является терминальной цепочкой, т. е. все листья отмечены терминалами или е. Корень отмечен стартовым символом.

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