XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 76
Текст из файла (страница 76)
Заметим также, что, согласно определению 7.8, нетерминзлы не содержатся в цепочках языка, порождаемого грамматикой. Это совсем не значит, что нетерминалы „не нужны", напротив, с их помощью мы организуем вывод и можем получить требуемые терминальные цепочки. Когда мы решаем математическую расчетную задачу и должны в результате получить число, то это не значит, что мы не должны пользоваться формулами. Но все буквенные обозначения в окончательном результате должны исчезнуть, хотя без них этот результат получить невозможно. Определение 7.9.
Две грамматики называются зкваваленшкыми, если они порождают один и тот же язык. Примем соглашение о следующей сокращенной записи правил с одинаковой левой частью: вместо записи А-+ам А-+аз, ..., А-+ов 479 7.2. Порождающие грамматики будем использовать запись А-+ се1!ссг!...!ссо, разделял разные правые части вертикальной чертой. Кроме того, рассматривая примеры грамматик, мы зачастую будем записывать только их множества правил вывода, избеган скрупулезной записи всего кортежа, определяющего грамматику.
С учетом введенных вьппе соглашений об обозначениях зто не должно приводить к недоразумениям. Пример 7.4. Рассматриваемая ниже грамматика моделирует простейший фрагмент естественного (русского) языка: ее терминалы — это некоторые слова русского языка', нетерминалами являются „грамматические категории ", а именно понятия „предложение", „подлежащее" и „сказуемое" (они даны как слова, заключенные в угловые скобки): 01 = Цкот, пес, крокодил, мяукает, лает, плачет), ((предложение), (подлежащее), (сказуемое)), (предложение), Р|).
Множество правил Р1 имеет вид (предложение) -+ (подлежащее) (сказуемое), (подлежащее) -+ кот ! пес ! крокодил, (сказуемое) -+ мяукает ! лает ! плачет. Каждое правило вывода грамматики 01 можно трактовать как определение той или иной грамматической категории: например, первое правило есть запись такого определения: „предложение — зто подлежащее, за которым идет сказуемое". Так как нас интересует только синжиссис языка, то это определение, *Эти слова рассматрнваютсл как неделимые символы, а именно буквы данного термннального алфавита. Нас никак не должно ато смущать, ибо алфавит — это любое непустое конечное множество.
480 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ касающееся исключительно записи предложения, есть требование, согласно которому, записывая предложение, сначала нужно поставить подлежащее, а после него — сказуемое. Другие правила грамматики определяют подобным образом „подлежащее" и „сказуемое". Но тут новых грамматических категорий не возникает — просто перечисляются те слова, которые могут быть подлежащим и скаэуемым. Построим какой-нибудь вывод в грамматике 01.
(предложение) ~- (подлежащее) (скээуемое) 1- ~- кот (сказуемое) 1- кот лает. Заметим, что „смысл" (семавиьпка) выводимой цепочки нас никак не интересует. Мы вообще пока не знаем, что такое „смысл". Так что кот может лаять, крокодил мяукать и т.д. Приведенный пример, несмотря на его простоту, позволяет нам дать еще одну содержательную интерпретацию понятия грамматики. Грамматику можно рассматривать как „систему определений" некоторых „терминов", „понятий".
Выделяется самое общее понятие (в данном примере понятие „предложение"), оно сводится к менее общим „понятиям" до тех пор, пока мы не придем к „конкретным объектам" (в данном случае к цепочкам в каком-то алфавите), подпадающим под определяемые „понятия". Самое общее „понятие" — это аксиома, другие „понятия" — нетерминалы, „конкретные объекты"— терминальные цепочки. В подобном духе строится определение синтаксиса языков программирования с помощью так называемых форм Бэкуса — Наура.
Пример такого описания приведен ниже (см. Д.8.2). За другими примерами следует также обратиться к литературе по языкам программирования. Пример 7.5. а. Грамматика 481 7.2. Пороидающие грамматвки имеет множество правил Рз. 1 — ~ аР)ЬР~а~Ь, Р -~ аР~ЬР)ОР~1Р~а)Ь)0)1. Нетрудно видеть, что данная грамматика порождает простейшие „идентификаторы" в алфавите, состоящем из двух „букв" и двух „цифр", т.е.
цепочки, начинающиеся обязательно с „буквы". Примеры выводов в грамматике 02.. 1 ~ аР с- аЬР г- аЬОР 1- аЬОЬР 'г. аЬОЬ1, 1 1- а, 1 ~- Ь. б. Грамматика порождает множество так называемых „правильных скобочных структур "*, например Я 1- ЯЯ ~- (Я) Я ~- (())Я 1- (()) (). Полезно сопоставить с этой грамматикой индуктивное определение множества правильных скобочных структур: цепочка () есть правильная скобочная структура; если известно, что цепочки х и у — правильные скобочные структуры, то цепочку ху также считаем правильной скобочной структурой; если известно, что х — правильная скобочная структура, то и цепочка (х) есть правильная скобочная структура; никаких правильных скобочных структур, кроме определенных выше, не существует.
Видно, что грамматика Сз есть не что иное, как форма записи сформулированного только что индуктивного определения: „правильная скобочная структура" (понятие, обозначенное аксиомой Я) есть либо цепочка (), либо „правильная 'Мы заключилн четверку, задающую грамматику Сз, в угловые, а не в круглые скобкн, чтобы не смешввата ик со скобками, лвллющимисл термикалами данной грамматики. и — 1еое1 482 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ скобочная структура" в скобках — (Б), либо две „правильные скобочные структуры", записанные одна после другой, — ББ. в. Рассмотрим грамматику 04 = ((а, Ь,с), (Б,А, В,С), Б, Р4) с множеством правил вывода Р4. Б -+ аБВС~абС, (1) Н2) СВ -+ ВС, (3) ЬВ -+ 66, (4) 6С -+ Ьс, (5) сС -1 сс.
(б) Разберем некоторые примеры выводов: под символом 1- будем указывать номер применяемого на данном шаге правила, а над символом — количество повторений этого правила: Б 1-з абС 1-з аЬс; Б 1-1 аБВС 1-з аабСВС 1-з аабВСС 1-4 1-4 аабЬСС >-з ааЬбсС 1-з ааббсс; Б ~-1 аБВС ~-1 ааБВСВС Рз аааЬСВСВС ~-з >з аааЬВССВС >з аааЬВСВСС ~-з аааЬВВССС ~-4 ~-4 ааабЬВССС 1-4 ааабЬЬССС 1-з аааЬббсСС >-е~ аааЬ6Ьссс. Представим теперь вывод произвольной цепочки а"Ь"с": Б1-1аБВС1-1 ааБВСВС1-1 ... 1-1а" 1Б(ВС)" 1~-з чс~~Вс...Вс~ чВссдс,Вс~ л 1 е — 2 ~ а"ЬВ" 'С" 1- "66В" С" >.4 ...
1 4 авбвСа1 з авбвсСа-1 ) и — 1 авбвс™ (72) 483 7.2. Поромдааащио грамматики Можно заметить, что посредством многократного применения правила (3) в выводе (7.2) происходит „перегонка" всех бу В бу С, б "6СВСВС,ВС в — 1 выводится цепочка авЬВв 1С".
Если считать, что правило (3) на каждом шаге соответствующего вывода применяется так, что происходит замена первого вхождения цепочки СВ цепочкой ВС, то первый (самый левый) символ В в цепочке ВСВСВС,ВС„у б у *б С, бу й в-1 у В а б~ "6ВССВС., сс уу у*" у . в-2 два символа С и т.д. Отсюда следует, что правило (3) в указанном фрагменте вывода (7.2) применяется 1+ 2+... + (и — 1) = раз. п(п — 1) 2 Тогда последовательность номеров применяемых правил (протокол вывода) может быть записана так: (1)в 1(2)(3) В (4)в 1(5)(6)в 1, и ~ )1. Гораздо труднее доказать, что данная грамматика порождает только цепочки указанного вида.
Проанализируем другие варианты проведения вывода после применения правила (2) в выводе (7.2). 1. После применения правила (2) применяем правило (5) н после многократного применения правила (3) получаем авЬС(ВС)в 11 авЬс(ВС)в 1 авЬСВСВС ВС 1-+ евЬсВв-1Св-1 (7 3) Цепочка, записанная последней, такова, что, во-первых, она не является терминальной, а во-вторых, к ней не применимо ни 16' 484 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ одно правило грамматики. Любая такая цепочка называется н1униноеоб. 2.
Вывод (7.2) можно модифицировать, прервав на определенном шаге применение правила (3) и применив правило (4): авьВв'Св'+1(ВС)" 1 =авЬВ™С +1ВС...ВС~-,авЬЬВ 'С "+'(ВС)"-'=, где ти(н — 1. Далее, если посредством применения правила (3) мы „перегоним" все символы В влево, то получим цепочку а"Ь6В" ~св, из которой легко получается цепочка а" Ь"с". Таким образом, мы получили другой вариант вывода этой цепочки. Но если мы будем применять правило (4), начиная с цепочки вьВй~с~в+1 до тех пор, пока это возможно, то получим цепочку авув+1Ст+1 (ВС)в-1-т Из нее, если не применять сразу правило (5), снова получится цепочка а" Ьвсв. Применение же правила (5) приведет к тупиковой цепочке.
По аналогии можно рассмотреть произвольное чередование применения правил (3) и (4). Все варианты вывода терминальной цепочки тем самым разобраны. В общем же случае строгое доказательство того, что какая- либо предъявленная нам грамматика не порождает никаких других цепочек, кроме цепочек определенного вида, может быть весьма нетривиальным. 485 Ч.Ъ. Порождающие гранматвкя г. Зададим грамматику а = ((в), (и, А, С, П, Е, Р~), Е, )Ъ), множеством Рз правил Я-+ аСА, А -+ а2ЕА ~ Р, ЕР-~ ВР, ЕП ~ Пв'Е, Еа -+ аЕ, Са -+ аС, СЮ-+Со, СР-+ Л. Можно доказать, что данная грамматика порождает язык (а": и > 1), т.е. все квадраты натуральных чисел, закодированных в однобуквенном алфавите.
ф При доказательстве утверждений о грамматиках нам будет удобно испольэовать одну процедуру, которую мы назовем переименованием нетерминвлов араммапьини. Пусть дана какая-то грамматика 6 = (У, Ф, Я, Р). Введем новый алфавит Ф', не пересекающийся с У 0 Ж, так, что между алфавитами Ф и Ф' установлено взаимно однозначное соответствие, при котором каждый символ А е Ж переходит в символ А' Е Ж'. Построим новую грамматику 6' = (К Ф', У, Р'), заменив каждое правило в исходной грамматике новым, в котором на месте каждого вхождения каждого нетерминала А е Ф поставлен нетерминал А' е Ф'. Нетрудно доказать, что построенная таким образом грамматика С' эквивалентна исходной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
