Гладкий - Формальные грамматики и языки - 1973 (947381), страница 21
Текст из файла (страница 21)
Пусть à — грамматика со следующей схемой (которую мы для удобства разделим на 4 группы): 1. 1) 1-+А1В И1. 1) Сс- Ес 2) 1 — «АВ 2) ЕсАс — «Е[А 3) 1 -+ асас 3) ААс -+ АА И. 1) А — »С, 4) АЕ!с -+ АР, 2) СсА -+ С[А[ 5) ЛР[с -+ АР[ 3) АсА -+ Л[Ас 6) Р,Р„Р,Р, 4) А[В -+ Асяс 7) Р[Есс -' Р[Рс 5) А,Р[ — Л,Р[с 1Ч.
!) Е, — а, 6) Рс[РА -+ РНРи 2) Рс — ас 7) Р В Рс~в (Индексы с, 1, й принимают значения 1, ..., п.) Нетрудно видеть, что Е(Г) = (хх[хеи (а„..., а„)'). Именно, цепочка хх, где х = а ... а, з ) 2, может с, ' с, быть порождена так. Сначала по правилам группы ! порождаем А'В'. Затем заменяем первое вхождение А на Сс, (правило строки И, !)), с помощью И,2) и И, 3) передаем информацию в начало правой половины цепочки и заменяем первое вхождение В на Е[с, (И,4)). Это — первая половина первого цикла.
Вторая половина начинается применением И1, 1), после чего левая половина цепочки очищается от ненужной теперь информации (И1,2), И1,3)) и Вс, заменяется на Рс, (И!,4)). Следующие циклы проводятся так же, только для передачи информации используются дополнительно И,5) и И,б), для уничтожения ее — И1,5) и И1,6), а вместо И, 4) и И1, 4) применяются соответственно И, 7) и И1,7). После з циклов получаем цепочкуЕ,,...Ес Рс ... ... Рс, которая затем преобразуется в хх (1Ч, !), 2)).
Любой цикл можно в любой момент оборвать и перейти к следующему; однако если хоть один цикл не будет доведен до конца, то мы не сможем уничтожить все вхождения вспомогательных символов. Поэтому ника- кая цепочка в основном словаре, не имеющая вида хх, не выводима из 1 в Г. Перейдем к доказательству теоремы 3.8. Для произвольной грамматики Г = ( У,[У,!, Й) н произвольного языка Е ы(У 0 !У)' будем называть Г образом множество всех тех цепочек в У, которые выводимы в Г из цепочек, принадлежащих Е. Мы докажем предложение, несколько более сильное, чем теорема 3.8, а именно: для произвольной неукорачивающей грамматики Г с основ- Р ным словарем У можно построить грамматику Г с основным словарем У и вспомогательным словарем [[Г такую, что: 1) каждое правило Г' имеет вид аА -+ а[[ или А -+ р, где А я [[У, а, 5 еи У () [У; 2) 1.(Г) является Г'- образом КС-языка ЯН"6'"Н"О" !й, си, и = О, 1, ...), где К, б, Н вЂ” некоторые элементы [У.
Заметим прежде всего, что для данной неукорачивающей грамматики Г можно построить такую грамматику Г» что в каждом ее правиле длины левой и правой частей равны и Е(Г) есть Гиобраз языка (1Д [си = = 0„1, ...), где 1о и Я вЂ” некоторые вспомогательные символы Гс. Построение Гь весьма простое, предоставляется читателю. Любой вывод цепочки х ~ У' из цепочки 1юЯ в Гс (такой вывод существует тогда и только тогда, когда х еи Е(Г) и т = [х( — !) будем называть нормальным выводом х.
Построим теперь грамматику Гм обладающую свойством !) искомой грамматики Г', а также следующим свойством: 2') вспомогательный словарь Г' содержит такие символы Ч, Р, Я, что Гюобраз языка 1., = = (ЧР«с~ Р ~[си, и = О, 1, ...) состоит из всевозможных цепочек вида Чаха, где х еи Е(Г) и х — двоичная запись длины некоторого нормального вывода х. Мы не будем приводить формальное построение Гз и ограничимся описанием принципа ее работы. При этом нам удобно будет представлять себе Гз — поскольку она работает с цепочкой ЧР"Я Р" — как некоторую машину, снабженную конечной лентой, длина которой в процессе работы не изменяется; по ленте с л е в а н а п р аз о движутся головки, которые могут возникать и исчезать.
Прн этом можно потребовать, чтобы головки могли возникать только в крайней слева ячейке ГРАММАТИКИ СОСТАВЛЯЮЩИХ 108 «КЗ! НС-ГРАММАТИКИ С ОДНОСТОРОННИМ КОНТЕКСТОМ !99 !ГЛ, 3 (а исчезать — в любой) и чтобы в одной ячейке не могли одновременно находиться две головки. Можно даже потребовать, чтобы на ленте в каждый момент была только одна головка.) В начале работы нам удобно будет считать все ячейки пустыми. Символы Ч, Р и Я будет интерпретироваться как различные метки, стоящие в пустых ячейках; эти метки будут сохраняться н при заполнении ячеек, так что любая ячейка в любой момент несет информацию о том, является ли она крайней слева, и если нет, то какой из трех зон она принадлежит — левой (первые и ячеек, не считая крайней слева), средней (следующие и ячеек) или правой (последние и ячеек).
В левой и правой зонах будут записываться цепочки в словаре (О, 1), причем цепочка О, записанная в левой зоне, всегда будет двоичной записью натурального числа, а цепочка ш, записанная в правой зоне, — обращением двоичной записи натурального числа. Для простоты мы будем отождествлять О, соответственно в, с числом, двоичной записью которого служит б, соответственно Й; будем говорить, например: «прибавим к п единицу» ит.п. Работа машины распадается на два этапа; вплоть до конца второго этапа в левой и правой зонах вместо нулей и единиц стоят их двойники, являющиеся вспомогательными символами; мы, однако, будем для простоты пренебрегать этим.
Первый этап состоит в последовательном выполнении циклов, которые будут сейчас описаны. 1-й цикл. В последней ячейке левой зоны записывается О, в первой ячейке средней зоны записывается 7« и в первой ячейке правой зоны записывается О. з + 1-й ци к л (з ) 0). Содержимое левой зоны увеличивается на 1, затем в средней зоне имитируется применение некоторого правила грамматики Г1 (причем сначала первый слева символ выбранного вхождения левой части правила заменяется первым символом правой части, затем второй и т.
д,) и, наконец, увеличивается на 1 содержимое правой зоны. При этом прибавление единицы в правой зоне производится обычным способом: если в младшем (т. е. самом левом) разряде сгоит нуль, то он заменяется единицей, если единица, она заменяется нулем и делается перенос. В левой зоне единица прибавляется «наугад»: до какого-то места цепочка проходится слева направо без изменения, затем в некоторой ячейке нуль заменяется единицей (вариант — записывается единица в пустой ячейке); если следующая ячейка оказалась пустой, операция закончена, если нет, делается попытка истолковать произведенную замену нуля единицей как перенос при прибавлении единицы; если такое толкование невозможно, т. е.
где-то правее есть еще нуль, то машина «ломается». Ясно, что если х ~ 1.(Г) и г — длина некоторого нормального вывода х (в двоичной записи), то цепочка Чгхг может быть получена описанным только что способом из подходящей цепочки языка (ь Покажем, кроме того, что если х — цепочка в основном словаре Гь то цепочка вида Чгхг, где ген (О, 1)*, может быть получена на первом этапе работы машины только тогда, когда х ~ Ь(Г) и г — длина некоторого нормального вывода х. Для этогозаметим,чтоесли х не выводима в Г, из 1Д~'~ ', то цепочка вида Чохи, О, ш~(0, 1)", может появиться в результате первого этапа лишь в случае, когда некоторые циклы обрываются при прохождении средней зоны (например: вместо того, чтобы применить, скажем, правило А1В~- А«ВМ заменяем А, на А» и после этого сразу переходим к следующему циклу).
Поэтому нам, во всяком случае, достаточно установить, что при получении цепочки Чгхй никакой цикл не может оборваться после того, как начало изменяться содержимое левой зоны, но до того как закончилось изменение содержимого правой. Очевидно однако, что: а) при обрыве цикла в средней зоне (в частности, на границе с левой или правой) содержимое левой зоны успевает увеличиться на 1, в то время как содержимое правой не меняется; б) при обрыве внутри левой зоны после начала изменения ее содержимое увеличивается даже больше чем на 1 (например, из 101 = 5 вместо 110 = 6 получится 1! 1 = 7); в) при обрыве внутри правой зоны до окончания изменения ее содержимое уменьшается (поскольку запись в этой зоне производится справа налево; например, нз !011 = 13 вместо О!11 = = 14 получится 0011 = 12). Следовательно, если хоть один цикл оборвется в нежелательном месте, то цепочки вида Чгхг мы уже не получим. УПРАЖНВЫИЯ Нб гРАммАтики составляющих !гл.
з Назначение второго этапа работы машины — проверить, совпадает ли содержимое правой зоны с обращенным содержимым левой. Это можно сделать аналогично тому, как порождалась цепочка хх в примере на стр. 10б (ясно, что этот пример нетрудно видоизменить так, чтобы получались цепочки вида хХ). Формальные построения мы опускаем. Можно представлять себе ячейки правой зоны «двухэтажными»; в верхних этажах записан результат первого этапа, в нижних — копия содержимого левой зоны.
В тех ячейках, в которых оба этажа оказываются заняты «тезками», двухэтажные вспомогательные символы заменяются основными; основные символы возникают и в левой зоне. Этим работа машины заканчивается. В дальнейшем будем считать, что длины цепочек языка Т.(Г) не меньше восьми. Если это не так, то для цепочек меньшей длины можно очевидным образом ввести специальные правила.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
