Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 132
Текст из файла (страница 132)
Теперь применим грамматику для вывода арифметического выражения ((3 2) —: (5+ 7). Начнем с продукции Я- (А-:В). Затем применим продукции А- (А В) и В- (А+В), чтобы получить ((А В) оь (А+ В)). Продукции А- 3 и В+2 дают ((3" 2) оь (А + В)) . Наконец, применяя продукции А- 5 и В- 7, выводим ( (3 2) + (5 + 7)). ПРИМЕР 17.25. Аналогичным образом формируются арифметические выражения в постфиксной форме. Пусть множество Х = (Я,А,В) и Т = (+,—, х,/,,0,1,2,3,4,5,6,7,8,9), Нам потребуются следуюшие продукции: Я-чАВ+ А- АВ+ В- АВ+ А — ~0 Я- АВ- А- А — В- АВЯ- АВх А- АВх В- АВх А-~9 Я- АВоо А- АВсе В- АВ+ В- 0 Я- АВ А- АВ"  — АВ" В- 9 Рассмотрим выражение 32+47+ х. Поскольку все рассматриваемые целые числа меньше, чем 10, то 32+ представляет собой символ целого числа 3, за которым следует символ целого числа 2 и символ +. Для построения этого выражения начнем с продукции Я- АВх Затем воспользуемся продукциями А- А+В и В- А+В, РАЭДЕЛ 17.3.
Грамматоки 745 чтобы вывести АВ+АВ+ х. Продукции А — ~2 и  — ~3 дают 23+ АВ+ х . Наконец, применияя продукцию А- 4 и В- 7, выводим 3+47+ х. ПРИМЕР 17.26. Грамматику можно также использовать для вывода истинных выражений. Такие выражения истинны в том смысле, что они грамматически правильны, хотя даже лишены смысла. Предположим, что нужно построить грамматику, которая наряду с другими выводит следующие утверждения: Джо преследует Фреда.
Большой пес прыгает через старый забор. Том исчезал медленно за горизонт. Перед началом фактического построения грамматики выберем ее структуру. В каждом из рассматриваемых предложений имеется именная группа (им. гр.), глагольная группа (гл. гр.) и еще одна именная группа. Кроме того, два последних предложения содержат предлог (предл.).
Поэтому, пусть первой продукцией будет 5 - (им. гр.)(гл. гр.)(предл.)(им. гр.). В нашем примере наиболее общей формой именной группы является прилагательное (прил.), за которым следует существительное (сущ.). Следующим правилом будет (им. гр.) — ~ (прил.)(сущ.) . Наиболее общей глагольной формой является глагол (гл.), за которым следует наречие (нар.). Поэтому пусть следующей продукцией будет (гл. гр.) — (нар.) (гл.) . Заранее известно, что финальное множество имеет вид Т = (Джо, преследует, Фреда, большой, пес, прыгает, через, старый, забор, Том, исчезал, медленно, за, горизонт).
Нетерминальное множество имеет вид Х = (Я, (им. гр.), (гл. гр.), (прил.), (сущ.), (нар.), (гл.), (предл.)). Теперь понадобятся продукции, приписывающие значения для (прил.), (сущ.), (нар.), и (гл.). В некоторых из приведенных предложений не нужны (прил.), (предл.) и (нар.). Для решения этой задачи введем продукции (прил.) — Л (нар.) — Л (предл.) — Л.
746 ГЛАВА ~7. теория вычислений Поставив в соответствие этим символам пустое множество, мы можем вычерки- вать их за ненадобностью. Оставшаяся часть продукций включает следующее: (нар.) — медленно (гл.) — преследует (гл.) — прыгает (предл.) — за Для вывода предложения "Джо преследует Фреда" начнем с Я вЂ” (им. гр.)(гл.
гр.)(предл.)(им. гр.), чтобы вывести (им. гр.)(гл. гр.)(предл.)(им. гр.). Используя продукцию (им. гр.) — (прил.)(сущ.), (прил.) (сущ.) (гл, гр.) (предл.) (им. гр.) . выводим Применив (прил.) — Л, выводим (сущ.)(гл. гр.)(предл.)(им. гр.) . Повторяя процесс для второй именной группы (им, гр.), выводим (сущ.) (гл. гр.) (предл.) (сущ.) . Применив (гл. гр.) — (нар.)(гл.), (сущ.)(нар.)(гл,)(предл.)(сущ.). (предл.) — Л, (сущ.) (гл.) (сущ.) . выводим Применив выводим Воспользовавшись (сущ.) — Джо (сущ.) — Фред (гл.) — преследует, выводим Джо преследует Фреда.
(сущ.) — Фред (прил.) — большой (прил.) — старый (сущ.) — Джо (гл.) — исчезает (сущ. ) — забор (сущ.) — пес (сущ.) — Том (сущ.) — горизонт (предл.) — через РА37?ЕЛ 17.3. Грамматики 747 Я - (им. гр.)(гл. гр.)(предл.)(им. гр.), чтобы вывести (им. гр.)(гл. гр.)(предл.)(им. гр.) . Применив продукцию (им. гр.) — (прил.)(сущ.), выводим (прил.) (сущ.) (гл.
гр.) (предл.) (им. гр.) . Используя (прил.) — большой (сущ.) — пес, выводим Большой пес (гл. гр.)(предл.)(им, гр.) . Применив (гл. гр.) — (нар.) (гл.), Большой пес(нар.) (гл.) (предл.) (им. гр.) . (нар.) — Л (гл.) — прыгает, Большой пес прыгает(предл.)(им. гр.). выводим Используя выводим Применив (предл.) -~ через, выводим Большой пес прыгает через(им. гр.) . Используя продукцию (им. гр.) — (прил.)(сущ.), получаем Большой пес прыгает через(прил.)(сущ.). Применив (прил.) — старый (сущ.) — забор, выводим Большой пес прыгает через старый забор.
Вывод последнего предложения предоставляем читателю. ОПРЕДЕЛЕНИЕ 17.27. На рис. 1?.29 изображено соответствующее дерево для продукции Р— шгшзшз... и„. Выведем предложение: "Большой пес прыгает через старый забор". Как и в предыдущем случае, начнем с продукции 748 ГЛЯВЯ 17. Теория вычислений Я з"' ° Ри, 172о Таким образом, соответствующим деревом для  — А+ В является дерево, изображенное на рис.
17.30. + В Рис. 17.30 ОПРЕДЕЛЕНИЕ 17.28. Если соответствующие деревья продукций, использо- ванных для вывода данного выражения, связны, то они формируют дерево с корнем В, называемое деревом грамматического разбора или деревом выво- да. Листья дерева при чтении слева направо формируют выражение. а(Ы вЂ” ч А+ В, чтобы сформировать соответствующее дерево, изображеное на рис. 17.3!. А +В Рис. 17.31 А +В Рис. 17.32 Затем воспользуемся деревом, изображенным на рис. 17.32, которое соответствует продукции А- А+В, чтобы сформировать дерево, изображенное на рис. 17.33. Далее воспользуемся деревьями, соответствующими следующим продукциям А- 3, В- 2, В- 4, чтобы сформировать дерево грамматического разбора, изображенное на рис.
17.34. А+В Рис. 17.33 3 г Рис. 17.34 ПРИМЕР 17.29. В примере 17.23 продукции использовались для вывода 3+ 2+4. Для построения дерева начнем с первой использованной продукции РАЗДЕЛ 17.Э. Грамматики 749 ПРИМЕР 17.30. В примере 17.25 для вывода выражения ((2+3) х (4+5)) исполь- зовались продукции 5- (А х В), А- (А+В), А- 2, В- 3,  — ~(А+В), А- 4, В- 5. Поэтому дерево грамматического разбора — это дерево, изображенное на рис. 17.35.
(А+В) (А+В) ! ! Рис 7733 ПРИМЕР 17.31. В примере 17.26 для вывода выражения "Большой пес прыгает через старый забор" использовались продукции Я вЂ” ~ (им. гр.)(гл. гр.)(предл.)(им. гр.) (им. гр.) — (прил.)(сущ.) (им. гр.) — (прил.)(сущ.) (прил.) — ~большой (сущ,) — пес (гл. гр.) — (нар.) (гл.) (нар.) — Л (гл.) — прыгает (предл.) через (прил.) — старый (сущ.) — забор Соответствующее дерево грамматического разбора изображенно на рис. 17.36. (пм. гр) (гл. гр.) (преем.) (пм.
гр.) (прплаг) (сущ.) (пар) (гл) через (првлаг.) (сущ) стпарыв забоР Рис. (7.36 'Х прыгаегл Белыиеб пес Во всех грамматиках данного раздела продукции имели вид А — Иг, где А — нетерминальиый символ. Следовательно, эти продукции можно использовать всюду, где возникает А, невзирая на его расположение в выражении. Такие грамматики назывются контекстно-свободными грамматиками. Если грамматика содержит продукцию вида аАЬ вЂ” И', где А — нетерминальный символ, и а либо Ь не являются пустым словом, то эту продукцию можно использовать только тогда, когда а находится слева от А, а Ь вЂ” справа.
Поэтому такую продукцию нельзя применять непосредственно к А, и, следовательно, грамматика зависит от контекста, в котором находится А. Такая грамматика называется контекстнозависимой, или контекстной грамматикой. П 750 ГЛАВА З7. Теория вычислений В приведенных ниже примерах рассматриваются контекстно-свободные грамматики, порождающие более абстрактные языки. ПРИМЕР 17.32. Пусть Г = (Ю,Т, Я, Р) — грамматика, определенная с помощью )У = (Я,А,В), Т = (а,Ь) и множества продукций Р. Я- АВ, А- а,  — ~ВЬ,  — Л.
Применив продукцию Я вЂ” АВ, выводим АВ. Далее с помощью продукций А — а и  — Л выводим а. Если теперь последовательно использовать продукции Я- АВ, А- а, В- ВЬ, В- Л, то получим а6. Можно породить также аЬЬЬ, а66Ь6 и аЬЬЬЬЬ. Фактически, для любых неотрицательных чисел и можно породить аЬ". Следовательно, язык, порожденный грамматикой Г, задается выражением аЬ*. и ПРИМЕР 17.33.
Пусть Г' = ()Ь', Т, Я, Р) — грамматика, определенная с помощью Х = (Я, А), Т = (а, Ь) и множества продукций Р. Я- аА6, А- аАЬ, А — ~Л. Применив продукции Я вЂ” аАЬ и А — Л, выводим а6. Применяя последовательно продукции Я- аАЬ, А- аАЬ, А- Л, получаем ааЬЬ, или азЬз. Воспользовавшись последовательно продукциями Я вЂ” +аАЬ, А — ~аАЬ, А- аАЬ, А — ~аЬ, выводим аааЬЬ6, или азЬз. Легко показать, что язык, порожденный грамматикой Г', — это (а"Ь": и — положительное целое число ).
Отметим, что это не то же самое, что а'Ь', поскольку последнее может включать также а Ь", где числа т и и не обязательно равны. П ПРИМЕР 17.34. Пусть Гн = (Ю, Т, Я, Р) — грамматика, определенная с помощью Х = (В, А, В), Т = (а, Ь) и множества продукций Р. Я вЂ” АВАВАВА, А — ~ Аа, А — Л,  — Ь. Можно показать, что язык, порожденный грамматикой Г", задается выражением а'Ьа"Ьа"Ьа . Это язык, состоящий из всех слов, содержащих в точности три символа Ь. а В примере 17.33 порожден язык (а"Ь": п — положительное целое число).
Интуитивно понятно, что зто не регулярный язык, поскольку единственный способ построения бесконечного регулярного языка на основе конечного алфавита состоит в использовании звезды Кляни е. В данном случае единственной возможностью является а'Ь', но, как отмечалось ранее, зта возможность не реализуема, так как сюда включаются и слова а Ь", где числа т и и не обязательно равны. Возникает вопрос, существует ли такая грамматика, которая порождает только регулярные языки. Ответ положительный. РдзДЕл 17.3.
Грамматики 751 ~ ОПРЕДЕЛЕНИЕ 17.35. Контекстно-свободная грамматика Г = (Х,Т, В, Р) называется регулярной грамматикой, если каждая продукция р Е Р имеет вид и — са, где строка ш содержит не более одного нетерминального символа, который встречается только в конце строки. Следовательно, та может иметь вид аасА, аЬ или 6А, где а, 6 и с — терминальные символы, а символ А — нетерминальный. Однако, строка ш не может иметь вид аАЬ, аАВ или Аа. Продукцию и — абсА можно заменить продукцией и- аВ, В- ЬС, С- сА. Возможно также, что строка и не содержит ни одного терминального символа и один нетерминальный, поэтому имеем  — С, но если за этим следует С— сС, где С вЂ” терминальный символ, то можно скомбинировать две продукции и получить  — СС.
Поэтому нет необходимости вводить ограничение на то, чтобы каждая продукция имела одну из следующих форм: А- аВ, В- Ь, С- Л. где А, В и С вЂ” нетерминальные символы, а символы а и 6 — терминальные. Приведенная ниже теорема объединяет понятия регулярных грамматик, регулярных языков и автоматов. Теорема сформулирована без доказательства. ТЕОРЕМА 17.35. Язык является регулярным тогда и только тогда, когда он порожден регулярной грамматикой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
