Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 59
Текст из файла (страница 59)
Предыдущие рассуждения и теорема 7.5 должны были нас подготовить к этим неразрешимостям; поскольку проблема пустоты для пересечения КС-языков неразрешима, а дополнение связано с пересечением и тривиальными множествами У* и Я соотношениями де Моргана и 7.= У*'~,1., то кажется естественным, что неразрешимости для пересечения влекут за собой неразрешимости для дополнения (объединение, как мы видели, неприятностей в этом смысле не доставляет).
Кроме того, проблема тривиальности— частный случай проблемы эквивалентности, поэтому неразрешимость 4 следует из неразрешимости 3. Однако, например, неразрешимость пустоты дополнения нельзя доказывать «в лоб», опираясь только на указанные связи (т. е. рассуждая примерно так: для Ьь Ц и г'.107, проблема пустоты разрешима, а для (.ЯЬз — нет; но Ь~Д(.з=(.Д(.г, поэтому причиной неразрешимости является дополнение), поскольку дополнение не сохраняет тип языка и верхнее дополнение в правой части может относиться уже не к КС-языку. Поэтому доказательства утверждений теоремы 7.7 более сложны и опираются на построение специальных КС-языков вида Я(Х), позволяющих свести указанные проблемы к проблеме Поста.
Подробное доказательство содержится в [57). 7зн ОПЕРАЦИИ НАД ЯЗЫКАМИ Операции иад языками, связанные с подстановками. Один вид операций над языками — теоретико-множественный (объединение, пересечение, дополнение) — мы фактически уже рассмотрели. Выяснилось, что класс КС-языков не замкнут (в смысле гл. 2) относительно пересечения и дополнения, Это говорит о том, что теоретико-множественные операции, за исключением объединения, не имеют естественной синтаксической интерпретации. С этой точки зрения большой интерес представляют другие операции, которые связаны с подстановкой языка в язык. Пусть г'.0 — язык, задаваемый грамматикой бо — — ( Уо, )Уо, )го, 1о), аенУ,; Ь| — язык, задаваемый грамматикой 61 — — ( Уь В'ь Ип 11 ) .
Подстановка (,з(а-~-Ь1) языка (л в 1а вместо символа а — это операция, сопоставляющая языкам Е, и 1,~ язык 1=10(а-«Е,), состоящий из всех це- почек 1„в которых вместо каждого вхождения а подстав- лена некоторая цепочка 1~ (вместо различных вхождений а могут подставляться различные цепочки). Обобщением этой операции является подстановка 1,=1а(а,— «1ь...,ая-« -«1.~) нескольких языков 1.ь...,1.«в язык 1.м при которой вместо каждого вхождения а подставляется некоторая це- почка соответствующего языка 1„(1=),...Й). Пример 7.6.
Пусть 1,— язык арифметических выраже- ний (примеры 7.1, г и 1.5), 1,, — язык идентификаторов из примера 7.2. Замена в 1, переменных а, Ь, с произвольны- ми идентификаторами описывается подстановкой 10(а-«1.ь Ь вЂ” «1, с- Е,). Отметим, что а, Ь, с — пе только терминальные символы 1м но и однобуквенные цепочки, входящие как в 1.м так и в 1«Поэтому они содержатся в цепочках (т. е. арифметических выражениях) не только языка 1м но и 1..
Конкатенация Е,Ц языков 1,~ и 1з — это операция, со- поставляющая языкам 1,, и 1,, язык 1., содержащий все цепочки вида ай, где а~(.ь рен1,ь Любую цепочку можно рассматривать как конкатена- цию ее подцепочек и, в частности, как конкатенацию со- ставляющих ее букв. Как и обычно при мультипликативной записи операций (см. й 2.2), используются степенные обо- значения 11,=1', 1.1,1=1,' и т.
д. В дальнейшем нам так- же понадобятся степенные обозначения для повторений подстановки вместо одного и того же символа: (Ц,'=1„ (Ц~ =А(п — «Ц, (Ца=(1а)Р(а — «1) и т, д., а также вместо множества символов У= (аь ..., аь): (Цг =1,(а~ — «1..., а«- 2 -«1.), Итерация 1.* языка 1, определяется равенством 1,* =(с)01-й" 01-"() =(е)() () 1', где е — пустая цепочка. Важное замечание: не следует смешивать язык (е), со- стоящий из одной пустой цепочки е, с пустым языком ф, не содержащим нн одной цепочки.
Например, 1.(е)=(е)В=1,; 1.ф=-ф1=ф для любого 1.. Конкатенация и итерация, а также рассмотренное выше объединение легко выражаются через подстановку в неко- торые простые языки. Обозначим 1,м — — (аЬ), 1,0~ (а)*, Ааз~ (а, Ь). Тогда для любых 1 ь 1, 1 ~1,=1 м (а- 1 ь Ь-« -«1з), 1.з =1оз(п — «1з), 1.ьМз=Е оз(а-«1-ь Ь-~-(.а) Нетруд- ав4 но видеть, что из п+2 элементарных языков (аД,...,(а,), (а,аз), (а„аз) с помощью некоторой последовательности подстаповок можно получить любой конечный язык в алфавите (ао..., а,). Зацикливанием (7.з); по символу а (а-рекурсией, или а-итерацией) языка ).з будем называть операцию, сопоставляющую языку Т.з язык 7.=(7.0)„содержащий те и только те цепочки языка () (1.з),',, в которые не входит ~=! символ а.
Обобщением этой операции является зацикливание (7.з)г по множеству символов У, определение которого получается из предыдущего заменой (1.01',на (7.01г. ПРимеР 7.7. РассмотРим Язык сУмм ьз —— (а, (а+а), (а+ а+а)...) и язык произведений (термов) 1 г=(п, аа, ааа...). Подстановка 7.з(а- (.г) дает язык Иг сумм произведений, т. е.
язык многочленов, который содержит выражения глубины (2 (о глубине формул см. 5 ЗА) над переменной а. Язык (Иг~, — это язык выражений глубины 2а над переменной а. Однако язык (7зг~, — это не язык выражений произвольной глубины, как могло бы показаться на первый взгляд, а пустой язык, поскольку для любого п любая цепочка ().зг~". содержит а и поэтому не входит в (7.зг~' Если же в исходные языки 1.з и Ег ввести вторую переменную Ь, т. е. рассматривать языки Ез =(а, Ь, (а+а), (а+ +Ь)...), 1-г =(а, Ь, аа, аЬ...), то (7з г) — это язык выважений глубины е=2п над переменными а, Ь, а (7-з г ),— язык выражений произвольной глубины над переменной Ь.
Главное достоинство операции подстановки с точки зрения теории языков заключается в том, что она имеет тот же характер, что и правила КС-грамматик, поскольку применение любого правила КС-грамматики есть некоторая подстановка вместо символа. Точнее, если А — ~а,(аз!...~иь— множество всех правил КС-грамматики 6 с левой частью А, то при порождении 1,(6) происходит подстановка конечного языка (ао...,аД вместо символа А в язык, состоящий из всех цепочек, порождаемых и содержащих А. Наличие связи между подстановкой и КС-правилами позволяет весьма просто представить операцию подстановки над КС-языками 1., и 7., как операцию над порождающими их КС-грамматиками 6, и 6з. Пусть 6,= ( Уо В'ь )7ь 7, ), 6,=(Ум раем йм 7з) .
Тогда язык Т,=(., (а- И) порождается грамматикой 6= ( У, Ю', )г, 1 ), которая определяется через 6~ и 6з следующим образом; У=(ЩУз) 285 (а); Я7=)Р,()Ф',()(а); 1=1ц Ю=ЩР,Яа-э1э). Иначе говоря, символ а становится нетермииальным, и грамматика 6, «подставляетсяъ в грамматику 6~ посредством КС-правила а-~-1ь Правда, такое определение подстановки грамматики в грамматику корректно только при выполнении условий: !) аф($'д)гз); 2) )р'я)р, я. действительно, азиат приводит к противоречию: по определению подстановки языков в этом случае а~У, тогда как по приведенному только что определению грамматики 6, порождающей 1.
= 1,,(а- 1,з), а ф У; если Ч7ДВ'~ФЯ, то включение в Я правила а-э1~ приводит к подстановке в 1,, не языка 1.м а языка 7., который содержит язык 1,„ но не совпадает с ним; если же аенЯ~,, то к а можно применить не только специальное правило а-ь1„но и некоторые правила из 11з с а в левой части, в результате чего может оказаться, что 1.(6)Ф1.~(а-э(з). Кроме того, очевидна необходимость условий: 3) УДЫ~=Я; 4) Уз()В',=Я, поскольку при их нарушении Р())РФО. Поэтому, когда хотя бы одно из условий 1 — 4 не выполнено, перед подстановкой бз в 6, необходимо переименовать некоторые символы из Р~ и %'ь т.
е. заменить их другими символами так, чтобы эти условия выполнялись. С учетом этих оговорок подстановка КС-грамматики 6,= ( $гм Ю'м йм 1, ) в КС-грамматику 6~= ( Ь'о )э'ь )сь 1~ ) определяется как операция, которая грамматикам 6~ и 6м сопоставляет грамматику 6= ( У, )г", Р, 1), для которой Р=(К()$'з)' (а); %'= =)Р'~())Рэ()(п); 1=1б К=РЫйгМа — ~1з), где Уь )Р'ь 11ьа' — результат переименования Рь )Рь 11„а соответственно в случае, когда условии 1 — 4 не выполнены, и К =Кб )(г~ = Ф'б 11, =11,; а'=а, если условия 1 — 4 выполнены. Нетрудно убедиться, что независимо от того, производится переименование или нет, 1.
(6) =1. (6,) (а-э1.(6,)), Таким образом, подстановка КС-языка в КС-язык может быть представлена как подстановка КС-грамматики в КС-грамматику, дающая снова КС-грамматику. Отсюда следует, что класс КС-языков замкнут относительно подстановки, а следовательно, также относительно конкатенации и итерации (поскольку выше была показана представимость этих операций через подстановку в КС-языки). Зацикливание КС-языка также может быть представлено как операция над его грамматикой. Для языка 1ч с грамматикой 6,= ( Уь )Р'ь Йо 1~) грамматика 6= = ( У, '««т, Р, 1 ), порождающая язык (Е«)„определяется следующим образом: р= $';~(а); )р'= «к',0(а); 1=1,; Я= =Й«()(а- 1«), Доказательство того, что Е(6) =(Е«")„предоставляем читателю.
Очевидно, что 6 — КС-грамматика, и, следовательно, класс КС-языков замкнут относительно зацикливания. Порождающая способность зацикливания сильнее порождающей способности подстановки в следующем смысле: если Е, и Е, — копечныс языки, то Е«(а — «. — «-Ез) — конечный язык для любого а, тогда как язык Е('6)=(Е«), бесконечен, если в Е«имеется цепочка длины 2, содержащая а.
Действительно, если в 6 1=>с«ар, |«ха|)|) )2, то по определению 6 1=«-и1р, где либо и, либо 8 непусто, и, следовательно, для Е(6) выполнен критерий бесконечности КС-языка (описанный вслед за доказательством теоремы 7А). ««ример 7.8. Пусть языки Ез и Ег из примера 7.7 заданы соответственно грамматиками 6а с системой правил Йз= =(1,— а| (А+А),А-+а|А+А),и 6гссистемой правил Рг= (1, а|1«а). Подставим 6гв 6з вместо а.
Поскольку а~ гнРт (т. е. нарушено условие 1), та заменяем в 6з а на В, после чего получаем искомую грамматику 6зг с начальным символом 1, и системой правил (1«- В| (А+А), А-«. -«В|А+А, В- 1м 1 -а|1,а), которая порождает язык Езг= =Еа(а- Ег) из примера 7.7.
Устраним теперь из 6аг цепное правило В-«.1«и введем в язык Езг вторую переменную Ь (терминальный символ), добавив правила 1« — «Ь |1«Ь. Получим грамматику 6зт с правилами (1« — «-1«|(А+А), А — э1«|А+А, 1г — ~а|Ь|1«а|1«Ь), порождающую язык Езг арифметических многочлепов (без вычитания и деления) над двумя переменными. Зацикливание грамматики 6зг по символу а дает язык (Езт),' выражений произвольной глубины над переменной Ь. Его грамматика, полученная зацикливанием 6зг, имеет следующие правила (проведенное здесь переименование а в С необязательно и сделано только для того, чтобы сохранить традиционные обозначения нетермипалов): 1« — «.1,|(А+А); 1,-«-С|Ь! 1,6|1,Ь; А- 1.,|А+А; С-~1«.
Блочные грамматики и сети из языков. Идея использования подстановки языка в правилах грамматики вместо подстановки конечной цепочки, как это делается в прави- лах обычной КС-грамматики, приводит к понятию блочной грамматики, которая определяется как пятерка обьектов б= (,Ф, го, 2', Я, В' ), где .~Ф=(А» ..., Л,,) — система конечных (возможно, пересекающихся) алфавитов; Я'= =(Хь..., Х ) — система конечных алфавитов, таких, что Х,«-А»„,,Х ыЛ и для любых йуХсП(Л; Хс) ф; 2'= =(1.ь...,» ) — конечное множество языков в алфавитах Аь...,Л соответственно; Д вЂ” конечное множество блочных правил вида х- 1.» где хенХ; Х= 0 Хк, ТчяУ; Уен2'— к=с начальный язык.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
