dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 44
Текст из файла (страница 44)
Доказательство этого факта, однако, требует некоторых усилий, и мы отложим его до раздела 5.2. 5.1.4. Ëåâûå è ïðàâûå ïîðîæäåíèÿДля ограничения числа выборов в процессе порождения цепочки полезно потребовать, чтобы на каждом шаге мы заменяли крайнюю слева переменную одним из тел еепродукций. Такое порождение называется левым (leftmost), и для его указания использу*ются отношения ⇒ и ⇒ . Если используемая грамматика G не очевидна из контекста, тоlmlmее имя G также добавляется внизу.Аналогично можно потребовать, чтобы на каждом шаге заменялась крайняя справапеременная на одно из тел.
В таком случае порождение называется правым (rightmost), и*для его обозначения используются символы ⇒ и ⇒ . Имя используемой грамматикиrmrmтакже при необходимости записывается внизу.Пример 5.6. Порождение из примера 5.5 в действительности было левым, и его можно представить следующим образом.E ⇒ E*E ⇒ I*E ⇒ a*E ⇒lmlmlmlm5.1. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈСтр.
191191a * (E) ⇒ a * (E + E) ⇒ a * (I + E) ⇒ a * (a + E) ⇒lmlmlmlma * (a + I) ⇒ a * (a + I0) ⇒ a * (a + I00) ⇒ a * (a + b00)lmlmlmÎáîçíà÷åíèÿ äëÿ ïîðîæäåíèé, çàäàííûõ ÊÑ-ãðàììàòèêàìèСуществует немало соглашений, напоминающих о роли тех или иных символов, используемых в КС-грамматиках. Будем использовать следующие соглашения.1. Строчные буквы из начала алфавита (a, b и т.д.) являются терминальными символами.
Будем предполагать, что цифры и другие символы типа знака + или круглыхскобок — также терминалы.2. Прописные начальные буквы (A, B и т.д.) являются переменными.3. Строчные буквы из конца алфавита, такие как w или z, обозначают цепочки терминалов. Это соглашение напоминает, что терминалы аналогичны входным символам конечного автомата.4. Прописные буквы из конца алфавита, вроде X или Y, могут обозначать как терминалы, так и переменные.5. Строчные греческие буквы (α, β и т.д.) обозначают цепочки, состоящие из терминалов и/или переменных.Для цепочек, состоящих только из переменных, специального обозначения нет, поскольку это понятие не имеет большого значения.
Вместе с тем, цепочка, обозначенная α или другой греческой буквой, возможно, состоит только из переменных.*Можно резюмировать левое порождение в виде E ⇒ a * (a + b00) или записать нескольlm*ко его шагов в виде выражений типа E * E ⇒ a * (E).lmСледующее правое порождение использует те же самые замены для каждой переменной, хотя и в другом порядке.E ⇒ E * E ⇒ E * (E) ⇒ E * (E + E) ⇒rmrmrmrmE * (E + I) ⇒ E * (E + I0) ⇒ E * (E + I00) ⇒ E * (E + b00) ⇒rmrmrmrmE * (I + b00) ⇒ E * (a + b00) ⇒ I * (a + b00) ⇒ a*(a + b00)rmrmrm*Данное порождение также позволяет заключить, что E ⇒ a * (a + b00).rmЛюбое порождение имеет эквивалентные левое и правое порождения.
Это означает,*что если w — терминальная цепочка, а A — переменная, то A ⇒ w тогда и только тогда,***когда A ⇒ w, а также A ⇒ w тогда и только тогда, когда A ⇒ w. Эти утверждения докаlmrmзываются также в разделе 5.2.192Стр. 192ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ5.1.5. ßçûê, çàäàâàåìûé ãðàììàòèêîéЕсли G = (V, T, P, S) — КС-грамматика, то язык, задаваемый грамматикой G, илиязык грамматики G, обозначается L(G) и представляет собой множество терминальныхцепочек, порождаемых из стартового символа.
Таким образом,*L(G) = {w ∈ T* | S ⇒ w}.GЕсли язык L задается некоторой КС-грамматикой, то он называется контекстносвободным, или КС-языком. Например, мы утверждали, что грамматика, представленная нарис. 5.1, определяет множество палиндромов в алфавите {0, 1}. Таким образом, множествопалиндромов является КС-языком. Можем доказать это утверждение следующим образом.Теорема 5.7. Язык L(Gpal), где Gpal — грамматика из примера 5.1, является множеством палиндромов над {0, 1}.Доказательство. Докажем, что цепочка w в {0, 1}* принадлежит L(Gpal) тогда и только тогда, когда она является палиндромом, т.е. w = wR.(Достаточность) Пусть w — палиндром.
Докажем индукцией по |w|, что w ∈ L(Gpal).Базис. Если |w| = 0 или |w| = 1, то w представляет собой ε, 0 или 1. Поскольку в грам*матике есть продукции P → ε, P → 0, P → 1, то во всех случаях P⇒ w.Индукция. Пусть |w| ≥ 2. Так как w = wR, она должна начинаться и заканчиваться одним и тем же символом, т.е. w = 0x0 или w = 1x1. Кроме того, x является палиндромом,т.е. x = xR. Заметим, что нам необходим факт |w| ≥ 2, чтобы обеспечить наличие двух различных нулей или единиц на обоих концах w.*Если w = 0x0, то по предположению индукции P ⇒ x. Тогда существует порождение*w из P: P ⇒ 0P0 ⇒ 0x0 = w.
Если w = 1x1, то рассуждения аналогичны, но с использованием продукции P → 1P1 на первом шаге. В обоих случаях заключаем, что w ∈ L(Gpal),тем самым завершая доказательство.*(Необходимость) Предположим, что w ∈ L(Gpal), т.е. P ⇒ w. Докажем, что w — палиндром. Проведем доказательство индукцией по числу шагов в порождении w из P.Базис. Если порождение имеет один шаг, то он использует одну из трех продукций,не имеющих P в теле, т.е. порождение представляет собой P ⇒ ε, P ⇒ 0 или P ⇒ 1.
Таккак ε, 0 и 1 — палиндромы, то базис доказан.Индукция. Предположим, что порождение состоит из n + 1 шагов, где n ≥ 1, и чтоутверждение индукции верно для всех порождений из n шагов. Таким образом, если*P ⇒ x за n шагов, то x является палиндромом.Рассмотрим (n + 1)-шаговое порождение, которое должно иметь вид*P ⇒ 0P0 ⇒ 0x0 = w5.1. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈСтр.
193193*или P ⇒ 1P1 ⇒ 1x1 = w, поскольку n + 1 шаг — это как минимум два шага, и только использование продукций P → 0P0 или P → 1P1 делает возможными дополнительные ша*ги порождения. Заметим, что в обоих случаях P ⇒ x за n шагов.По предположению индукции x является палиндромом, т.е. x = xR. Но тогда и 0x0, и1x1 — палиндромы. Например, (0x0)R = 0xR0 = 0x0. Делаем вывод, что w — палиндром изавершаем доказательство. 5.1.6.
Âûâîäèìûå öåïî÷êèПорождения из стартового символа грамматики приводят к цепочкам, имеющим особое значение. Они называются “выводимыми цепочками” (“sentential form”). Итак, если*G = (V, T, P, S) — КС-грамматика, то любая цепочка α из (V U T)*, для которой S ⇒ α,*называется выводимой цепочкой. Если S ⇒ α, то α является левовыводимой цепочкой, аlm*если S ⇒ α, то — правовыводимой. Заметим, что язык L(G) образуют выводимые цеrmпочки из T*, состоящие исключительно из терминалов.Пример 5.8. Рассмотрим грамматику выражений (см. рис. 5.2). Например, E * (I + E)является выводимой цепочкой, поскольку существует следующее порождение.E ⇒ E * E ⇒ E * (E) ⇒ E * (E + E) ⇒ E * (I + E)Однако это порождение не является ни левым, ни правым, так как на последнем шаге заменяется среднее E.Примером левовыводимой цепочки может служить a * E со следующим левым порождением.E ⇒ E*E ⇒ I*E ⇒ a*ElmlmlmАналогично, порождениеE ⇒ E * E ⇒ E * (E) ⇒ E * (E + E)rmrmrmпоказывает, что E * (E + E) является правовыводимой цепочкой.
Ñïîñîá äîêàçàòåëüñòâà òåîðåì î ãðàììàòèêàõТеорема 5.7 типична для доказательств, показывающих, что та или иная грамматиказадает некоторый неформально определенный язык. Сначала строится предположение индукции, говорящее о свойствах цепочек, порождаемых из каждой переменной.В данном примере была только одна переменная P, поэтому нам было достаточно доказать, что ее цепочки были палиндромами.194Стр. 194ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈДоказывается достаточность: если цепочка w удовлетворяет неформальным утвер*ждениям о цепочках переменной A, то A ⇒ w. В нашем примере, поскольку P явля*ется стартовым символом, мы утверждали “P ⇒ w”, говоря, что w принадлежит языку грамматики.
Обычно достаточность доказывается индукцией по длине слова w.Если в грамматике k переменных, то индуктивное утверждение имеет k частей, которые доказываются с помощью взаимной индукции.*Нужно доказать также необходимость, т.е. что если A ⇒ w, то w удовлетворяет неформальным утверждениям о цепочках, порождаемых из переменной A. Поскольку внашем примере был только стартовый символ P, предположение о том, что*w ∈ L(Gpal), было равносильно P ⇒ w.
Для доказательства этой части типична индукция по числу шагов порождения. Если в грамматике есть продукции, позволяющиенескольким переменным появляться в порождаемых цепочках, то n-шаговое порождение нужно разбить на несколько частей, по одному порождению из каждой переменной. Эти порождения могут иметь менее n шагов, поэтому следует предполагатьутверждение индукции верным для всех значений, которые не больше n, как это обсуждалось в разделе 1.4.2.5.1.7. Óïðàæíåíèÿ ê ðàçäåëó 5.15.1.1.Построить КС-грамматики для следующих языков:а) (∗) множество {0n1n | n ≥ 1} всех цепочек из одного и более символов 0, закоторыми следуют символы 1 в таком же количестве;б) (∗!) множество {aibjck | i ≠ j или j ≠ k} всех цепочек из символов a, за которыми следуют символы b и затем c так, что количества символов a и b иликоличества b и c различны;в) (!) множество всех цепочек из символов a и b, не имеющих вида ww, т.е. неравных ни одной цепочке-повторению;г) (!!) множество всех цепочек, у которых символов 0 вдвое больше, чем символов 1.5.1.2.Следующая грамматика порождает язык регулярного выражения 0*1(0 + 1)*.S → A1BA → 0A | εB → 0B | 1B | εЗапишите левое и правое порождения следующих цепочек:а) 00101;5.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
