Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Ясно, что если хеЦГ) и г — длина некоторого нормального вывода х (в двоичной записи), то цепочка Vzxz может быть получена описанным только что способом из подходящей цепочки языка L0. Покажем, кроме того, что если х — цепочка в основном словаре Ti, то цепочка вида Slzxz, где ze{0, 1}*, может быть получена на первом этапе работы машины только тогда, когда х е L(T) и z — длина некоторого нормального вывода х. Для этого заметим, что если х не выводима в Ti из /oQ1*1-1, то цепочка вида Vvxw, v, ®е{0, 1}*, может появиться в результате первого этапа лишь в случае, когда некоторые циклы обрываются при прохождении средней зоны (например: вместо того, чтобы применить, скажем, правило A\Bi-*А2В2, заменяем Ai на Лг и после этого сразу переходим к следующему циклу). Поэтому нам, во всяком случае, достаточно установить, что при получении цепочки Vzxz никакой цикл не может оборваться после того, как начало изменяться содержимое левой зоны, но до того как закончилось изменение содержимого правой. Очевидно однако, что: а) при обрыве цикла в средней зоне (в частности, на границе с левой или правой) содержимое левой зоны успевает увеличиться на 1, в то время как содержимое правой не меняется; б) при обрыве внутри левой зоны после начала изменения ее содержимое увеличивается даже больше чем на 1 (например, из 101 = 5 вместо 110 = 6 получится 111 = 7); в) при обрыве внутри правой зоны до окончания изменения ее содержимое уменьшается (поскольку запись в этой зоне производится справа налево; например, из 1011 = 13 вместо 0111 = = 14 получится ООП = 12). Следовательно, если хоть один цикл оборвется в нежелательном месте, то цепочки вида Vzx& мы уже не получим.
110
Грамматики составляющих
[гл. з
Назначение второго этапа работы машины — проверить, совпадает ли содержимое правой зоны с обращенным содержимым левой. Это можно сделать аналогично тому, как порождалась цепочка хх в примере на стр. 106 (ясно, что этот пример нетрудно видоизменить так, чтобы получались цепочки вида хх). Формальные построения мы опускаем. Можно представлять себе ячейки правой зоны «двухэтажными»; в верхних этажах записан результат первого этапа, в нижних — копия содержимого левой зоны. В тех ячейках, в которых оба этажа оказываются заняты «тезками», двухэтажные вспомогательные символы заменяются основными; основные символы возникают и в левой зоне. Этим работа машины заканчивается.
В дальнейшем будем считать, что длины цепочек языка L(T) не меньше восьми. Если это не так, то для цепочек меньшей длины можно очевидным образом ввести специальные правила.
Заметим теперь, что для данной грамматики Г существует такая эффективно по ней вычисляемая постоянная с, что для каждой цепочки леЦГ) среди цепочек, принадлежащих Г2-образу L0, найдется хотя бы одна цепочка Vzxz, для которой |z|<;c|*|. (Это следует из того, что среди нормальных выводов цепочки х найдется хотя бы один бесповторный, длина которого мажорируется показательной функцией от |х|.)
Фиксируем натуральное число t ^ 2(2с-\-\). Сопоставим каждой цепочке г) длины, не большей 21, состоящей из символов, входящих в словари всех рассмотренных нами грамматик, новый символ а(т]). Определим понятие образа цепочки аналогично тому, как это было сделано в доказательстве теоремы 2.1, используя число t вместо фигурировавшего там I. С помощью того же метода «блочного кодирования», который был применен в указанном доказательстве, легко преобразовать грамматику Гг в грамматику Гг, обладающую свойством
1) грамматики Гг и сверх того следующим свойством:
2) ?2-образ языка {# HkGnHmGn \ k, т, п = 0, 1, ...} состоит из всевозможных цепочек вида #^&a(z)a(x)a(i), где x^L(T),$—двоичная запись длины некоторого нормального вывода х, R — некоторый специальный символ, k = 0, 1, ... и а(со) означает образ цепочки ш. В силу
УПРАЖНЕНИЯ
111
выбора числа t для каждой цепочки xeL(r) найдется такая цепочка х — Ф Rha(z)a{x)a(2), принадлежащая Гг-образу языка {ф HhGnHmGn\k, т, п = 0, 1, ...}, что
1x1 = W-
Теперь для завершения конструкции достаточно построить грамматику Гз, удовлетворяющую тому , же условию 1) и такую, что а) для всякой цепочки х е У* и всякой цепочки х = Ф Rhot(z)a(x)a(2), где ге{0, 1}* и |х1 = |*|, из х в Гз выводима х; б) цепочка x^V* выводима в Гз из цепочки вида ф Rsa{z)a(u)a{i), где «gV*, 2 е {0, 1}*, лишь тогда, когда это имеет место согласно пункту а). Принцип работы Гз может быть охарактеризован так. Пользуясь тем же представлением грамматики как машины, которое было использовано при построении Гг, будем считать ленту «четырехэтажной». Начальная информация записана в первом этаже. Работа начинается с того, что кусок первого эгажа, являющийся образом х, переписывается в правый конец второго этажа. Затем в третьем этаже записывается произвольная цепочка у е У*; после этого в правом конце четвертого этажа записывается (произвольный) образ у\ наконец, содержимое второго и четвертого этажей сравнивается, и в случае их совпадения уничтожаются все этажи, кроме третьего.
Доказательство теоремы закончено.
Упражнения
