Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 44
Текст из файла (страница 44)
Аналогично можно потребовать, чтобы на каждом шаге заменялась крайняя справа переменная на одно из тел. В таком случае порождение называется ллааым (г(я!»гшоз!), и для его обозначения используются символы =» и =». Имя используемой грамматики также при необходимости записывается внизу. Пример 5.6. Порождение из примера 5.5 в действительности было левым, и его можно представить следующим образом. Е =» Е» Е =» ! * Е =» а» Е ~ 5.1. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ 191 а * (Е) =~ а " (Е+ Е) ~ а * (! + Е) ~ а * (а е Е) ~ ! ! ! ! а * (а ь У) =~ а * (а + !О) =~ а * (а + 100) =~ а * (а е ЪОО) ! ! ! Обозначения для порождений, заданных КС-грамматиками Существует немало соглашений, напоминающих о роли тех или иных символов, ис- пользуемых в КС-грамматиках.
Будем использовать следующие соглашения. П Строчные буквы из начала алфавита (а, Ь и т.д.) являются терминальными символами. Будем предполагать, что цифры и другие символы типа знака+ или круглых скобок — также терминалы. 2.
Прописные начальные буквы (А, В и т.д.) являются переменными. 3. Строчные буквы из конца алфавита, такие как !г или а, обозначают цепочки терминалов. Зто соглашение напоминает, что терминалы аналогичны входным снм- волам конечного автомата. 4. Прописные буквы из конца алфавита, вроде Хили У, могут обозначать как терми- палы, так и переменные.
5. Строчные греческие буквы (а, )5 и т.д.) обозначают цепочки, состоящие из терминалов и)или переменных. Для цепочек, состоящих только из переменных, специального обозначения нет, поскольку это понятие не имеет большого значения.
Вместе с тем, цепочка, обозначенная а или другой греческой буквой, возможно, состоит только из переменных. Можно резюмировать левое порождение в виде Е =ь а * (а+ ЬОО) или записать несколь! ко его шагов в виде выражений типа Е * Е =~ и ' (Е). ! Следующее правое порождение использует те же самые замены для каждой переменной, хотя и в другом порядке. Е =~ Е'Е =~ Е*(Е) =~Е*(Е+Е) =~ Е к (Е е !) => Е * (Е ~- Ю) =о Е " (Е ь )00) ~ Е * (Е + ЬОО) =~ ! П! Е *(!и ЬОО) =~ Е " (а+ ЬОО) =~ ! «(а+ ЬОО) =» а*(а+ ЬОО) Данное порождение также позволяет заключить, что Е =~ а * (а+ ЬОО).
Любое порождение имеет эквивалентные левое и правое порождения. Зто означает, что если н — терминальная цепочка, а А — переменная, то А ~ и тогда и только тогда когда А =~ зг, а также А =~ !г тогда и только тогда, когда А ~ и. Зги утверждения дока- в зываются также в разделе 5.2. ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 192 $.1,5, Язык, задаваемый грамматикой Если б=(1', Т, Р,б) — КС-грамматика, то язык, задаваемый грамматикой 6„или язык грамматики б, обозначается 1(б) и представляет собой множество терминальных цепочек, порождаемых из стартового символа.
Таким образом, Цб) = (и~ н 7 ) Я =» и~) . с Если язык Е задается некоторой КС-грамматикой, то он называется коптекстносеобсдпыи, или КС-языка,и. Например, мы утверждали, что грамматика, представленная на ряс. 5.1, определяет множество палиндромов в алфавите (О, 1). Таким образом, множество палиндромов является КС-языком. Можем доказать это утверждение слелуюшим образом. Теорема 5.7. Язык ЦСеы), где Оеы — грамматика из примера 5.1, является множеством палиндромов над (О, 1) . Доказательство. Докажем, что цепочка и в (О, 1) принадлежит Цап») тогда и только тогда, когда она является палиндромом, т.е. и = ге .
Достаточпасп1») Пусть и — палиндром. Докажем индукцией по (и (, что и е Цб м). Базис. Если Ое( = О илн )и ! = 1, то и представляет собой е, О или 1. Поскольку в грам- матике есть продукции Р— » е, Р— » О, Р » 1, то во всех случаях Р е и. Индукции. Пусть !и ~ > 2. Так как и = и, она должна начинаться и заканчиваться ода вим и тем же символом, т.е.
ге = Охб или зе = 1х1. Кроме того, х является палиндромом, т.е. х = хк. Заметим, что нам необходим факт ~и ~ > 2, чтобы обеспечить наличие двух различных нулей или единиц на обоих концах и . Если и = Охб, то по предположению индукции Р =-» х. Тогда существует порождение и из Р: Р =» ОРО ~ Охб = и. Если и = 1х1, то рассуждения аналогичны, но с использовавием продукции Р » 1Р! на первом шаге. В обоих случаях заключаем, что»г н ЦО„,~), тем самым завершая доказательство. (Оеобходимоспгь) Предположим, что и е Цб„„), т.е, Р =» и.
Докажем, что и — паливдром. Проведем доказательство индукцией по числу шагов в порождении и из Р. Базис. Если порождение имеет один шаг, то он использует одну из трех продукций, ве имеюших Р в теле, т.е. порождение представляет собой Р ~ е, Р ~ О или Р ~ 1. Так квк е, О и 1 — палиндромы, то базис доказан. Индукция. Предположим, что порождение состоит из и"; 1 шагов, где и > 1, и что утверждение индукции верно для всех порождений из п шагов. Таким образом, если Р =ь х за и шагов, то х является палиндромом. Рассмотрим (и + 1)-шаговое порождение, которое должно иметь вид Р =»ОРО =» Охб = ж 5.1, КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ 193 или Р ~ !Р! =» !х1 = н, поскольку и + 1 шаг — это как минимум два шага, н только использование продукций Р— > ОРО нли Р— » !Р! делает возможными дополнительные ша- ги порождения.
Заметим, что в обоих случаях Р ~ х за н шагов. По предположению индукции х является палиндромом, т.е. х = ха. Но тогда и Охб, и 1х1 — палиндромы. Например, (ОхО) = Ох О = ОхО, Делаем вывод, что н — палиндром и завершаем доказательство. П 5.1.б. Выводимые цепочки Порождения из стартового символа грамматики приводят к цепочкам, имеющим особое значение. Они называются "выводимыми цепочками*' ("зепгепг!а! Топи'*). Итак, если С = (1', Т, Р, 5) — КС-грамматика, то любая цепочка а из (Щ Т), для которой Е =» а, называется выводимой цепочкой.
Если Я ~ а, то а является левовыводимой цепочкой, а и если Е ~ а, то — нравовыводимой. Заметим, что язык 1(О) образуют выводимые цепочки из Т, состоящие исключительно нз терминалов. Пример 5.8. Рассмотрим грамматику выражений (см. рис. 5.2). Например, Е " (1+ Е) является выводимой цепочкой, поскольку существует следующее порождение. Е =» Е * Е » Е * (Е) =» Е * (Е + Е) ~ Е» (1 + Е) Однако это порождение не является ни левым, ни правым, так как на последнем шаге заменяется среднее Е.
Примером левовыводимой цепочки может служить а * Е со следующим левым порождением. Е ~ Е" Е=» 1»Е=» а»Е и /т и Аналогично, порождение Е =» Е * Е =» Е* (Е) =» Е* (Е"; Е) показывает, что Е * (Е+ Е) является правовыводимой цепочкой. П Способ доказательства теорем о грамматиках Теорема 5.7 типична для доказательств, показывающих, что та нли иная грамматика задает некоторый неформально определенный язык. Сначала строится предположение индукции, говорящее о свойствах цепочек, порождаемых из каждой переменной. В данном примере была только одна переменная Р, поэтому нам было достаточно доказать, что ее цепочки были палиндромами. ГЛАВА б. КОНТЕКСТНО-СВОВОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 194 Доказывается достаточность: если цепочка зг удовлетворяет неформальным утверждениям о цепочках переменной А, то А =~ н.
В нашем примере, поскольку Р явля- ется стартовым символом, мы утверждали "Р =~ ю", говоря, что н принадлежит языку грамматики. Обычно достаточность доказывается индукцией по длине слова н. Если в грамматике к переменных, то индуктивное утверждение имеет !г частей, которые доказываются с помощью взаимной индукции. Нужно доказать также необходимость, т.е. что если А =» и, то и удовлетворяет неформальным утверждениям о цепочках, порождаемых из переменной А.
Поскольку в нашем примере был только стартовый символ Р, предположение о том, что н а Е(бр„), было равносильно Р =ь н. Для доказательства этой части типична нндукдвя по числу шагов порождения. Если в грамматике есть продукции, позволяющие нескольким переменным появляться в порождаемых цепочках, то и-шаговое порождение нужно разбить на несколько частей, по одному порождению из каждой переменной. Эти порождения могут иметь менее п шагов, поэтому следует предполагать утверждение индукции верным для всех значений, которые не больше и, как это обсуждалось в разделе 1 А.2.
5.1.7. Упражнения к разделу 5,1 5,1.1. Построить КС-грамматики для следующих языков; а) (ь) множество (О" 1" ! и > 1) всех цепочек из одного и более символов О, за которыми следуют символы 1 в таком же количестве; б) (я!) множество (а'Ь'с" ! ! ~( или!'~Ц всех цепочек из символов а, за которыми следуют символы Ь и затем с так, что количества символов а и Ь или количества Ь и с различны; в) (!) множество всех цепочек из символов а и Ь, не имеющих вида ив, т.е.
не равных ни одной цепочке-повторению; г) (!!) множество всех цепочек, у которых символов 0 вдвое больше, чем символов 1. 5,1.2. Следуюшая грамматика порождает язык регулярного выражения 0 1(0+ 1) . Я вЂ” э А1В А — > ОА ) в В- ОВ~ !В!в Запишите левое и правое порождения следуюших цепочек: а) 00101; 5.1. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ б) !001; в) 000!!. 5.1.3. Докажите, что каждый регулярный язык является КС-языком. Указание. Постройте КС-грамматику с помощью индукции по числу операторов в регулярном выражении. 5.1.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
