Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 62
Текст из файла (страница 62)
Можно доказать, что если символ не добавляется к множеству достижимых символов путем максимально возможного об- наружения, то он не является достижимым. Базис. Очевидно, что В действительно достижим. Индукция. Пусть обнаружено, что некоторая переменная А достижима. Тогда для всех продукций с головой А все символы тел этих продукций также достижимы. Пример 7.5. Снова начнем с грамматики из примера 7.1. Согласно базису В достижим. Поскольку В имеет тела продукций АВ и а, символы А, В и а также достижимы.
У В продукций нет, но А имеет А — э Ь. Делаем вывод, что Ь достижим, К множеству достижимых символов 1о, А, В, а, Ь1 добавить больше нечего. П ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ Теорема 7.6. Вышеприведенный алгоритм находит все достижимые символы грамматики б, и только их. Доказательство. Это доказательство представляет собой еще одну пару простых индукцнй в духе теоремы 7А и оставляется в качестве упражнения.
7,1.3. Удаление В-продукций Покажем теперь, что к-продукции, хотя и удобны в задачах построения грамматик, не являются существенными. Конечно же, без продукции с телом в невозможно породить пустую цепочку как элемент языка. Таким образом, в действительности доказывается, что если Е задается КС-грамматикой, то  — (в) имеет КС-грамматику без г-продукций. Начнем с обнаружения "в-порождающих" переменных. Переменная А называется елорождающей, если А =» н Если А — в-порождающая, то где бы в продукциях она ни встречалась, например в  — э САП, из нее можно ~но не обязательно) вывести ж Пролукдвя с такой переменной имеет еше одну версию без этой переменной в теле ( — > С»»). Эта версия соответствует тому, что г-порождающая переменная использована для вывода д Используя версию В -э СА»», мы не разрешаем из А выводить ц Это не создает проблем, так как далее мы просто удалим все продукции с телом г, предохраняя каждую переменную от порождения н Пусть 6 = (Г, Т, Р, 5) — КС-грамматика.
Все в-порождающие символы 6 можно найтя с помощью следующего алгоритма. Далее будет показано, что других г-порождающих свнволов, кроме найденных алгоритмом, нет. Базис. Если А э в — продукция в Сч то А — в-порождающая. Индукции. Если в С есть продукция  — » С»Сл ..Си где каждый символ С, является внорождающим, то  — в-порождающая. Отметим, что для того, чтобы С, бьш в-порождающим, он должен быть переменной, поэтому нам нужно рассматривать продукция, тела которых содержат только переменные.
Теорема 7.7. В любой грамматике в-порождающими являются только переменные, лайденнь»е вышеприведенным алгоритмом. Доказательство. Переформулируем утверждение в виде "А является в-порождающей тогда и только тогда, когда алгоритм идентифицирует А как в-порождающую".
Для достаточности нетрудно показать индукцией по порядку, в котором обнаруживаются в- порождающие символы, что каждый такой символ действительно порождает ц Для не- обходнмости используем индукцию по длине кратчайшего порождения А =» ц Базис. Один шаг. Тогда А — э в должно быть продукцией, и А обнаруживается согласно базису алгоритма., Индукция. Пусть А =» в за и шагов, где и > Е Первый шаг должен иметь вид А=» С~Сл..С» =» в, где каждый символ С, порождает в за число шагов, которое 7.1.
НОРМАЛЬНЫЕ ФОРМЫ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 273 меньше л. По предположению индукции каждый символ С, обнаруживается как е-порождающий. Тогда с помощью индуктивного шага А также обнаруживается как е-порождающая на основе продукции А -+ С~Сп..бь П Пример 7.8. Рассмотрим следующую грамматику.
 — +АВ А — эаАА ~ е В -+ ЬВВ(е Сначала найдем е-порождающие символы. А и В непосредственно е-порождающие, так как имеют продукции с к в качестве тела. Тогда и В г-порождающий, поскольку тело продукции  — > АВ состоит только из в-порождающих символов. Таким образом, все три переменные являются к-порождающими. Построим теперь продукции грамматики б,. Сначала рассмотрим 5 — э АВ. Все символы тела являются г-порождающими, поэтому есть 4 способа выбрать присутствие или отсутствие А и В.
Однако нам нельзя удалять все символы одновременно, поэтому получаем следующие три продукции. В-эАВ~А~В Далее рассмотрим продукцию А — э аАА. Вторую и третью позиции занимают в-порождающие символы, поэтому снова есть 4 варианта их присутствия или отсутствия. Все они допустимы, поскольку в любом из них остается терминал а.
Два из них совпадают, поэтому в грамматике б, будут следующие три продукции. А — э аАА ~ аА ~ а Аналогично, пролукция для В приводит к следующим продукциям в бп В -э ЬВВ(ЬВ(Ь Обе к-продукции из б не вносят в б, ничего. Таким образом, следующие пролукции образуют ба В-+АВ~А~В А — > аАА ! аА ( а В-+ ЬВВ)ЬВ(Ь П Завершим наше изучение удаления е-продукций доказательством, что описанная конструкция не изменяет язык, за исключением того, что цепочки л в нем больше нет, если она была в языке грамматики б.
Поскольку конструкция, очевидно, удаляет кьпродукции, мы будем иметь полное доказательство утверждения о том, что для любой КС-грамматики б найдется такая КС-грамматика б, без е-продукций, для которой Цб~) = Цб) — 1к). Теорема 7.9. Если грамматика б, построена по грамматике б с помощью описанной выше конструкции удаления в-продукций, то Цб,) = Цб) — (е). 274 ГЛАВА 7. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ Доказательство. Нужна доказать, что если»к И ц то и Н с»О») тогда и только тогда, когда и и )Аб). Как часто случается, проще доказать более общее утверждение, В данном случае будем говорить о терминальных цепочках, порождаемых каждой переменной, несмотря на то, чта нас интересуют лишь порождаемые стартовым символом 5.
Такни образом, докажем следующее утверждение. ° А =ь и тогда и только тогда, когда А =ь и и и и ц с, с В обе стороны доказательство проводится индукцией по длине порождения. (Необходимость) Пусть А ~ »и. Несомненно, »пи и, поскольку б» не имеет по, продукций. Докажем индукцией по длине порождения, что А =ь и. с Базис. Один шаг. В этом случае в О» есть продукция А — ь»г.
Согласно конструкции 6» в б есть продукция А -» а, причем а — это»о, символы которой, возможно, переме- каются с-порождающими переменными. Тогда в О есть порождение А =ь а =ь»г, где на о с шагах после первого, если они есть, из всех переменных в цепочке а выводится н Индукции. Пусть в порождении и шагов, и > 1. Тогда оно имеет вид А =» ХХь..Х» ~ и. Первая использованная продукция должна быть построена по прас, " с, лукини А — > У»Уь..1'„„где цепочка У»Уь,,у совладаете цепочкой Х,Хь,.Хь символы которой, возможно, перемежаются дополнительными и-порождающими переменными.
Це- почку»к можно разбить на»о»»гь..иь где Л; ~ и, для» = 1, 2, ..., 7». Если Л; есть терми- нщ то и, =Х, а если переменная, то порождение Х, ~ и; содержит менее и шагов. По с, предположению индукции Х, =ь в,, ' с Теперь построим соответствующее порождение в 6. А =ь У»Уз...у =ь ХХь..Х» ~ и»и»ь..и»= и с о с На первом шаге применяется продукция А — » У»Уь .. У„„которая, как мы знаем, есть в б. Следующая группа шагов представляет порождение и из тех Уо которые не являются ни одним из Х,. Последняя группа шагов представляет порождения и, из Х, которые суще- ствуют по предположению индукции. Достаточность) Пусть А ь ж и и и ш Докажем индукцией по длине и порождения, с чтпА =о ж.
с, 7.1. НОРМАЛЬНЫЕ ФОРМЫ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 275 Базис. Один шаг. А -+ ж является продукцией в О. Поскольку н л д эта же продукция есть и в Сь поэтому А =» и. с, Индукции. Пусть в порождении и шагов, и > 1. Тогда оно имеет вид А =7 ?;У»... У =» гв Цепочку и можно разбить на и»»ил..и» так, что У, =» и, для 1= 1, 2, с с с ..., л». ПУсть Хп Хл ..., Х» бУдУт теми из У» (в поРЯдке записи), дла котоРых и, и Е lг> 1, поскольку н ~ н Таким образом, А — > Х»Хл ..Х» является продукцией в С». Утверждаем, что Х»Х»...Х» ~ н, поскольку только 1Ь которых нет среди Х», Хл ..., Хь использованы для порождения л и не вносят ничего в порождение и.
Так как каждое из по- рождений 1; .=» и, содержит менее и шагов, к ним можно применить предположение инс дукции и заключить, что если и, м К то 1; ~ нг Таким образом, А ~ Х»Л> ..Х» ~ и, с, Завершим доказательство. Нам известно, что и е ь1й») тогда и только тогда, когда 5 =»»г. Полагая, что А = В в описанных выше рассуждениях, получаем, что»г е ЦО») тос, гда и только тогда, когда 5 ~ »г и ж и е Таким образом, и е Ь!6») тогда и только тогда, с когда»ге !АЙ») ив я е С) ТЛ.4. Удаление цепных продукций Цепная лрсдукнил — это продукция вида А — + В, где и А, и В являются переменными.
Эти продукции могут быть полезными; в примере 5.27 мы видели, как использование цепных продукций Š— » Т и Т вЂ” » Е позволило построить следуюшую однозначную грамматику лля простых арифметических выражений. ! -+ а ( Ь!!а ! 1Ь (!О ( П Е вЂ” » 7( (Е) Т -+ Е)ТŠŠ— » Т~Е+ Т Вместе с тем, цепные продукции могут усложнять некоторые доказательства и создавать излишние шаги в порождениях, которые по техническим соображениям там совсем не нужны. Например, в продукции Š— » Т переменную Т можно расширить обоими возможными способами, заменив эту продукцию двумя: Š— » Е~ Т» Е Это изменение все еще не избавляет от цепных продукций из-за появления Š— » Е. Дальнейшая замена Е дает Š— » ! ~ (Е) ~ 7' " Е, однако при этом остается Е » 1. Но если в этой продукции заменить ! всеми шестью возможными способами, то получим следуюшие продукции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
