Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 61
Текст из файла (страница 61)
215-227. ГЛАВА б. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯЧЪЮ 2бб 2. Р.С.Р)асЬег, "Оп согпрпгаЬ!11!гу Ьу сегга!п с1аааеь о( геагг)егере Тппп8 гпасЬ)пеа," Ргос. РоиггЬ Апп( Бутроз(ит оп Бабае(г(о8 С(гсиа ТЬеогу анг( (.офса! Реиягг (1963), рр. 23-32. 3. Р. Е. КппгЬ, "Оп гЬе ггапа1абоп ог" 1ап8па8еа агота!ей го г!8Ьг," 1п~огогог(оп апд Сонно! 8:6 (1965), рр. 607 — 639. (Кнут Д. О переводе (трансляции) языков слева направо.— Сб. "Языки и автоматы*'. — Мл Мир, 1975. — С. 9-42.) 4. А. Сг. Оегбп8ег, "Апгогпабс аупгасбс апа1уа)ь апд рпаЬдотгп агоге," Ргос.
5утрот(а он Арр((ег( л(аг)с 12 (1961), Аптег)сап МагЬегпабса1 Бес)егу, РгочЫепсе, й1. 5. М. Р. 5сЬпгаепЬегбег, "Оп сопгехпГгее!ап8па8еь апд рпаЫоюп апгогпага," 1п1огишг(оп анН Сонгго! 6: 3 (! 963), рр. 246-264. ЛИТБРАТУРА ГЛАВА 7 Свойства контеистно- свободных языков Наше изучение контекстно-свободных языков завершается знакомством с некоторыми из ях свойств. Вначале определяются ограничения на структуру продукций КС-грамматик и доказывается, что всякий КС-язык имеет грамматику специального вида. Этот факт облегчает доказательство утверждений о КС-языках.
Затем доказывается "лемма о накачке" для КС-языков. Эта теорема аналогична теореме 4.1 для регулярных языков, но может быть использована для доказательства того, что некоторые языки не являются контекстно-свободными. Далее рассматриваются шайства, изученные в главе 4 для регулярных языков, — свойства замкнутости и разрешяиости.
Показывается, что некоторые, но не все, свойства замкнутости регулярных языков сохраняются и у КС-языков. Часть задач, связанных с КС-языками, разрешается с помощью обобщения проверок, построенных для регулярных языков, но есть и ряд вопросов о КС-языках, на которые нельзя дать ответ. 7.1. Нормальные формы контекстно-свободных грамматик Цель зтого раздела — показать, что каждый КС-язык (без к) порождается грамматикой, ясе продукции которой имеют форму А — э ВС или А — > а, где А, В и С вЂ” переменные, а— терминал. Эта форма называется нормальной формой Хомского. Для ее получения нужно несколько предварительных преобразований, имеющих самостоятельное значение.
1. Удалить бесполезные символы, т.е. переменные или терминалы, которые не встречаются в порождениях терминальных цепочек из стартового символа. Удалить в-продукции, т.е, продукции вида А — т е для некоторой переменной А, 3. Удалить цепные продукции видаА — > В с переменнымиА и В. 7.1.1. Удаление бесполезных символов Символ Х называется полезным в грамматике 0 = (1; Т, Р, Я, если существует некоторое порождение вида Я =ь аХ1З ~ ш, где ш н T.
Отметим, что Х может быть как переиенной, так и терминалом, а выводимая цепочка аХД вЂ” первой или последней в по- рождении. Если символ Х не является полезным, то называется бесполезным. Очевидно, что исключение бесполезных символов из грамматики не изменяет порождаемого языка, поэтому все бесполезные символы можно обнаружить и удалить. Наш подход к удалению бесполезных символов начинается с определения двух свойств, присущих полезным символам. 1. Символ Х называется лорождакллим, если Х =э ж для некоторой терминальной цепочки н.
Заметим, что каждый терминал является порождающим, поскольку и' может быть этим терминалом, порождаемым за 0 шагов. Символ Х называется достижзгмым, если существует порождение 5 ~ аХ)3 для не которых а и )3. Естественно, что полезный символ является одновременно и порождающим, и дос тижимым. Если сначала удалить из грамматики непорождающие символы, а затем не достижимые, то, как будет доказано, останутся только полезные. Пример 7.1. Рассмотрим следующую грамматику.
5 — эАВ~ а А — >Ь Все символы, кроме В, являются порождающими; и и Ь порождают самих себя, 5 порождает и и А порождает Ь. Если удалить В, то придется удалить и продукцию 5 э АВ, что приводит к следующей грамматике. 5 — >и А — >Ь Теперь нетрудно обнаружить, что из 5 достижимы только а и 5. Удаление А и Ь оставляет лишь продукцию 5 — > а. Она образует грамматику с языком (а), как и у исходной грамматики. Заметим, что если начать с проверки достижимости, то все символы грамматики 5-чАВ~а А — эЬ оказываются достижимыми.
Если затем удалить В как непорождающий символ, то останется грамматика с бесполезными символами А и Ь. СЗ Теорема 7.2. Пусть 0 = (1; Т, Р, 5) — КС-грамматика, и Е(С) я Ы, т.е, б порождает хотя бы одну цепочку. Пусть й, = (Гь Т„Р„5) — грамматика, полученная с помощью следующих двух шагов.
!. Вначале удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть Сг = (гл Ть Рл 5) — полученная в результате грамматика. Заметим, что 5 должен быть порождающим, так как по предположению Ц6) содержит хотя бы одну цепочку, поэтому 5 не удаляется. 270 ГЛАВА 7.
СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ 2. Затем удаляются все символы, недостижимые в Сл Тогда Сс не имеет бесполезных символов, и ЦС,) = ЦС), Доказательство. Пусть Х вЂ” оставшийся символ, т.е. 'Хй Т, 0 Рь Нам известно, что Х ) в для некоторой цепочки и из 7 . Кроме того, каждый символ, использованный в порождении и изХ, также является порождающим. Таким образом, Х ~ и.
Поскольку Х не был удален на втором шаге, нам также известно, что существуют та- кие а и Д для которых 5 =з аХ)3. Кроме того, каждый символ, использованный в этом о, порождении, достижим, поэтому 5 ~ аХ 3. ц Нам известно, что каждый символ в цепочке аХ)3 достижим, и что все эти символы принадлежат Тз 0 7'ь поэтому каждый из них является порождающим в Сь Порождение некоторой терминальной цепочки, скажем, аХВ ~ хиу, содержит только символы, дос- тижимые из 5, поскольку они достижимы из символов в цепочке аХ3.
Таким образом, зто порождение есть также порождение в Сь т.е. Я =~ аХ)3 ~ хиу. ц ц Итак, Х полезен в Сь Ввиду произвольности Х в С, можно заключить, что С~ не имеет бесполезных символов. Нам осталось доказать, что ЦС,) = ЦС). Как обычно, покажем взаимное включение этих языков. Включение ЦС~) с ЦС) очевидно, поскольку при построении С, нз С символы и продукции только удаляются. Докажем, что ЦС) с ЦС,). Если и е ЦС), то 5 ~ и. Каждый символ в этом порождевии, очевидно, является как достижимым, так и порождающим, поэтому порождение в б~такжеегосодержит.
Таким образом, Я =~ ж, ив е ЦС~). Е) 7.1.2. Вычисление порождающих и достижимых символов Рассмотрим, каким образом вычисляются множества порождающих и достижимых символов грамматики. В алгоритме, используемом в обеих задачах, делается максимум возможного, чтобы обнаружить символы этих двух типов. Докажем, что если правильное индуктивное построение указанных множеств не позволяет обнаружить, что символ является, порождающим или достижимым, то он не является символом соот- ветствующего типа. Базис.
Каждый символ из Т, очевидно, является порождающим; ои порождает сам себя. 271 7.1. НОРМАЛЬНЫЕ ФОРМЫ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК Индукция. Предположим, есть продукция А -э а, и известно, что каждый символ в гг является порождающим. Тогда А — порождающий. Заметим, что это правило включает и случай, когда а = е; все переменные, имеюшие е в качестве тела продукции, являются порождающими. Пример 7.3.
Рассмотрим грамматику из примера 7.1. Согласно базису а и Ь вЂ” порождающие. По индукции используем продукции А — > Ь и В -+ а, чтобы заключить, что А и  — также порождаюшие. На этом индукция заканчивается. Продукцию 5 — э АВ использовать нельзя, поскольку не установлено, что  — порождающий. Таким образом, множеством порождающих символов является 1и, Ь, А, В1. П Теорема 7.4. Вышеприведенный алгоритм находит все порождающие символы грамматики С и только их.
Доказательство. В одну сторону, а именно, что каждый добавленный символ на са- мом деле является порождающим, доказать легко с помошью индукции по порядку, в котором символы добавляются к множеству порождаюших символов. Это оставляется в качестве упражнения. Для доказательства в другую сторону предположим, что Х вЂ” порождающий, и пусть Х =ь и. Докажем индукцией по длине порождения, что Х будет обнаружен как о порождающий.
Базис. Нуль шагов. Тогда Х вЂ” терминал и находится как порождающий согласно ба- зису алгоритма. Индукция. Если порождение имеет п шагов, где и > О, то Х вЂ” переменная. Пусть по- рождение имеет вид Х~ а ~ в, т.е. первой использована продукция Х вЂ” э ос Из с каждого символа цепочки а выводится некоторая терминальная цепочка, образующая часть и, и это порождение имеет менее, чем и шагов. По предположению индукции каждый символ цепочки а находится как порождаюший. Индуктивная часть алгоритма позволяет с помощью продукции Х вЂ” > а заключить, что Х вЂ” порождающий. П Теперь рассмотрим индуктивный алгоритм, с помощью которого находится множество достижимых символов грамматики б = (1; Т, Р, о).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
