dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 61
Текст из файла (страница 61)
Если сначала удалить из грамматики непорождающие символы, а затем недостижимые, то, как будет доказано, останутся только полезные.Пример 7.1. Рассмотрим следующую грамматику.S → AB | aA→bВсе символы, кроме B, являются порождающими; a и b порождают самих себя, S порождает a и A порождает b. Если удалить B, то придется удалить и продукцию S → AB, чтоприводит к следующей грамматике.S→aA→bТеперь нетрудно обнаружить, что из S достижимы только a и S.
Удаление A и b оставляет лишь продукцию S → a. Она образует грамматику с языком {a}, как и у исходной грамматики.Заметим, что если начать с проверки достижимости, то все символы грамматикиS → AB | aA→bоказываются достижимыми. Если затем удалить B как непорождающий символ, то останется грамматика с бесполезными символами A и b. Теорема 7.2. Пусть G = (V, T, P, S) — КС-грамматика, и L(G) ≠ ∅, т.е. G порождаетхотя бы одну цепочку. Пусть G1 = (V1, T1, P1, S) — грамматика, полученная с помощьюследующих двух шагов.1.270Стр. 270Вначале удаляются непорождающие символы и все продукции, содержащие одинили несколько таких символов. Пусть G2 = (V2, T2, P2, S) — полученная в результатеграмматика.
Заметим, что S должен быть порождающим, так как по предположениюL(G) содержит хотя бы одну цепочку, поэтому S не удаляется.ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂЗатем удаляются все символы, недостижимые в G2.2.Тогда G1 не имеет бесполезных символов, и L(G1) = L(G).Доказательство. Пусть X — оставшийся символ, т.е. X ∈ T1 U V1. Нам известно, что*X ⇒ w для некоторой цепочки w из T*. Кроме того, каждый символ, использованный вG*порождении w из X, также является порождающим. Таким образом, X ⇒ w.G2Поскольку X не был удален на втором шаге, нам также известно, что существуют та*кие α и β, для которых S ⇒ αXβ. Кроме того, каждый символ, использованный в этомG2*порождении, достижим, поэтому S ⇒ αXβ.G1Нам известно, что каждый символ в цепочке αXβ достижим, и что все эти символыпринадлежат T2 U V2, поэтому каждый из них является порождающим в G2.
Порождение*некоторой терминальной цепочки, скажем, αXβ ⇒ xwy, содержит только символы, досG2тижимые из S, поскольку они достижимы из символов в цепочке αXβ. Таким образом,это порождение есть также порождение в G1, т.е.**G1G1S ⇒ αXβ ⇒ xwy.Итак, X полезен в G1. Ввиду произвольности X в G1 можно заключить, что G1 не имеетбесполезных символов.Нам осталось доказать, что L(G1) = L(G). Как обычно, покажем взаимное включениеэтих языков.Включение L(G1) ⊆ L(G) очевидно, поскольку при построении G1 из G символы ипродукции только удаляются.*Докажем, что L(G) ⊆ L(G1). Если w ∈ L(G), то S ⇒ w. Каждый символ в этом порожGдении, очевидно, является как достижимым, так и порождающим, поэтому порождение в*G1 также его содержит.
Таким образом, S ⇒ w, и w ∈ L(G1). G17.1.2. Âû÷èñëåíèå ïîðîæäàþùèõ è äîñòèæèìûõ ñèìâîëîâРассмотрим, каким образом вычисляются множества порождающих и достижимыхсимволов грамматики. В алгоритме, используемом в обеих задачах, делается максимум возможного, чтобы обнаружить символы этих двух типов.
Докажем, что если правильное индуктивное построение указанных множеств не позволяет обнаружить, чтосимвол является порождающим или достижимым, то он не является символом соответствующего типа.Базис. Каждый символ из T, очевидно, является порождающим; он порождает сам себя.7.1. ÍÎÐÌÀËÜÍÛÅ ÔÎÐÌÛ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 271271Индукция. Предположим, есть продукция A → α, и известно, что каждый символ в αявляется порождающим.
Тогда A — порождающий. Заметим, что это правило включаети случай, когда α = ε; все переменные, имеющие ε в качестве тела продукции, являютсяпорождающими.Пример 7.3. Рассмотрим грамматику из примера 7.1. Согласно базису a и b — порождающие. По индукции используем продукции A → b и S → a, чтобы заключить, что A иS — также порождающие. На этом индукция заканчивается. Продукцию S → AB использовать нельзя, поскольку не установлено, что B — порождающий. Таким образом, множеством порождающих символов является {a, b, A, S}.
Теорема 7.4. Вышеприведенный алгоритм находит все порождающие символы грамматики G и только их.Доказательство. В одну сторону, а именно, что каждый добавленный символ на самом деле является порождающим, доказать легко с помощью индукции по порядку, в котором символы добавляются к множеству порождающих символов.
Это оставляется вкачестве упражнения.Для доказательства в другую сторону предположим, что X — порождающий, и*пусть X ⇒ w. Докажем индукцией по длине порождения, что X будет обнаружен какGпорождающий.Базис. Нуль шагов. Тогда X — терминал и находится как порождающий согласно базису алгоритма.Индукция. Если порождение имеет n шагов, где n > 0, то X — переменная. Пусть по*рождение имеет вид X ⇒ α ⇒ w, т.е. первой использована продукция X → α. Из каждогоGсимвола цепочки α выводится некоторая терминальная цепочка, образующая часть w, иэто порождение имеет менее, чем n шагов. По предположению индукции каждый символцепочки α находится как порождающий.
Индуктивная часть алгоритма позволяет с помощью продукции X → α заключить, что X — порождающий. Теперь рассмотрим индуктивный алгоритм, с помощью которого находится множество достижимых символов грамматики G = (V, T, P, S). Можно доказать, что если символне добавляется к множеству достижимых символов путем максимально возможного обнаружения, то он не является достижимым.Базис. Очевидно, что S действительно достижим.Индукция. Пусть обнаружено, что некоторая переменная A достижима.
Тогда длявсех продукций с головой A все символы тел этих продукций также достижимы.Пример 7.5. Снова начнем с грамматики из примера 7.1. Согласно базису S достижим. Поскольку S имеет тела продукций AB и a, символы A, B и a также достижимы. У Bпродукций нет, но A имеет A → b. Делаем вывод, что b достижим. К множеству достижимых символов {S, A, B, a, b} добавить больше нечего. 272Стр.
272ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂТеорема 7.6. Вышеприведенный алгоритм находит все достижимые символы грамматики G, и только их.Доказательство. Это доказательство представляет собой еще одну пару простых индукций в духе теоремы 7.4 и оставляется в качестве упражнения.7.1.3. Óäàëåíèå ε-ïðîäóêöèéПокажем теперь, что ε-продукции, хотя и удобны в задачах построения грамматик, неявляются существенными.
Конечно же, без продукции с телом ε невозможно породитьпустую цепочку как элемент языка. Таким образом, в действительности доказывается,что если L задается КС-грамматикой, то L – {ε} имеет КС-грамматику без ε-продукций.Начнем с обнаружения “ε -порождающих” переменных.
Переменная A называется*ε-порождающей, если A ⇒ ε. Если A — ε-порождающая, то где бы в продукциях она нивстречалась, например в B → CAD, из нее можно (но не обязательно) вывести ε. Продукция с такой переменной имеет еще одну версию без этой переменной в теле (B → CD).Эта версия соответствует тому, что ε-порождающая переменная использована для вывода ε.
Используя версию B → CAD, мы не разрешаем из A выводить ε. Это не создает проблем, так как далее мы просто удалим все продукции с телом ε, предохраняя каждую переменную от порождения ε.Пусть G = (V, T, P, S) — КС-грамматика. Все ε-порождающие символы G можно найти с помощью следующего алгоритма.
Далее будет показано, что других ε-порождающихсимволов, кроме найденных алгоритмом, нет.Базис. Если A → ε — продукция в G, то A — ε-порождающая.Индукция. Если в G есть продукция B → C1C2…Ck, где каждый символ Ci являетсяε-порождающим, то B — ε-порождающая. Отметим, что для того, чтобы Ci был ε-порождающим, он должен быть переменной, поэтому нам нужно рассматривать продукции, тела которых содержат только переменные.Теорема 7.7. В любой грамматике ε-порождающими являются только переменные,найденные вышеприведенным алгоритмом.Доказательство. Переформулируем утверждение в виде “A является ε-порождающейтогда и только тогда, когда алгоритм идентифицирует A как ε-порождающую”. Для достаточности нетрудно показать индукцией по порядку, в котором обнаруживаются εпорождающие символы, что каждый такой символ действительно порождает ε.
Для не*обходимости используем индукцию по длине кратчайшего порождения A ⇒ ε.Базис. Один шаг. Тогда A → ε должно быть продукцией, и A обнаруживается согласно базису алгоритма.*Индукция. Пусть A ⇒ ε за n шагов, где n > 1. Первый шаг должен иметь вид*A ⇒ C1C2…Ck ⇒ ε , где каждый символ Ci порождает ε за число шагов, которое7.1. ÍÎÐÌÀËÜÍÛÅ ÔÎÐÌÛ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр.
273273меньше n. По предположению индукции каждый символ Ci обнаруживается как ε-порождающий. Тогда с помощью индуктивного шага A также обнаруживается как ε -порождающая на основе продукции A → C1C2…Ck. Пример 7.8. Рассмотрим следующую грамматику.S → ABA → aAA | εB → bBB | εСначала найдем ε-порождающие символы. A и B непосредственно ε-порождающие, таккак имеют продукции с ε в качестве тела. Тогда и S ε-порождающий, поскольку телопродукции S → AB состоит только из ε-порождающих символов. Таким образом, все трипеременные являются ε-порождающими.Построим теперь продукции грамматики G1. Сначала рассмотрим S → AB. Все символы тела являются ε-порождающими, поэтому есть 4 способа выбрать присутствие илиотсутствие A и B.
Однако нам нельзя удалять все символы одновременно, поэтому получаем следующие три продукции.S → AB | A | BДалее рассмотрим продукцию A → aAA. Вторую и третью позиции занимают ε-порождающие символы, поэтому снова есть 4 варианта их присутствия или отсутствия. Всеони допустимы, поскольку в любом из них остается терминал a. Два из них совпадают,поэтому в грамматике G1 будут следующие три продукции.A → aAA | aA | aАналогично, продукция для B приводит к следующим продукциям в G1.B → bBB | bB | bОбе ε-продукции из G не вносят в G1 ничего. Таким образом, следующие продукции образуют G1.S → AB | A | BA → aAA | aA | aB → bBB | bB | bЗавершим наше изучение удаления ε-продукций доказательством, что описанная конструкция не изменяет язык, за исключением того, что цепочки ε в нем больше нет, еслиона была в языке грамматики G. Поскольку конструкция, очевидно, удаляет ε-продукции, мы будем иметь полное доказательство утверждения о том, что для любой КС-грамматики G найдется такая КС-грамматика G1 без ε-продукций, для которойL(G1) = L(G) – {ε}.Теорема 7.9.
Если грамматика G1 построена по грамматике G с помощью описаннойвыше конструкции удаления ε-продукций, то L(G1) = L(G) – {ε}.274Стр. 274ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂДоказательство. Нужно доказать, что если w ≠ ε, то w ∈ L(G1) тогда и только тогда,когда w ∈ L(G). Как часто случается, проще доказать более общее утверждение. В данном случае будем говорить о терминальных цепочках, порождаемых каждой переменной, несмотря на то, что нас интересуют лишь порождаемые стартовым символом S.
Таким образом, докажем следующее утверждение.**G1G• A ⇒ w тогда и только тогда, когда A ⇒ w и w ≠ ε.В обе стороны доказательство проводится индукцией по длине порождения.*(Необходимость) Пусть A ⇒ w. Несомненно, w ≠ ε, поскольку G1 не имеет εG1*продукций. Докажем индукцией по длине порождения, что A ⇒ w.GБазис. Один шаг. В этом случае в G1 есть продукция A → w. Согласно конструкцииG1 в G есть продукция A → α, причем α — это w, символы которой, возможно, переме*жаются ε-порождающими переменными. Тогда в G есть порождение A ⇒ α ⇒ w, где наGGшагах после первого, если они есть, из всех переменных в цепочке α выводится ε.Индукция.
Пусть в порождении n шагов, n > 1. Тогда оно имеетвид*A ⇒ X1X2…Xk ⇒ w. Первая использованная продукция должна быть построена по проG1G1дукции A → Y1Y2…Ym, где цепочка Y1Y2…Ym совпадает с цепочкой X1X2…Xk, символы которой, возможно, перемежаются дополнительными ε-порождающими переменными. Це*почку w можно разбить на w1w2…wk, где Xi ⇒ wi для i = 1, 2, …, k. Если Xi есть термиG1*нал, то wi = Xi, а если переменная, то порождение Xi ⇒ wi содержит менее n шагов. ПоG1*предположению индукции Xi ⇒ wi.GТеперь построим соответствующее порождение в G.**GGA ⇒ Y1Y2…Ym ⇒ X1X2…Xk ⇒ w1w2…wk = wGНа первом шаге применяется продукция A → Y1Y2…Ym, которая, как мы знаем, есть в G.Следующая группа шагов представляет порождение ε из тех Yj, которые не являются ниодним из Xi. Последняя группа шагов представляет порождения wi из Xi, которые существуют по предположению индукции.*(Достаточность) Пусть A ⇒ w и w ≠ ε.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
