Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
*) Это построение принадлежит Р. В. Фрейвалду.
104
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
1ГЛ, 3
Прежде всего легко построить неукорачивающую грамматику Ti, порождающую язык {пп'п\п = 1, 2, ...}, где Я— двоичная запись числа п и п' — тоже двоичная запись п, но состоящая из цифр 0' и 1' (чтобы можно было различить «зоны» цепочки); эта грамматика строится аналогично грамматике примера 11 из § 1.3, и, как в этом примере, Ti можно построить так, чтобы цепочка х = пп'п была выводима в Ti не более чем за с|х|2 шагов, где с — некоторая постоянная (ср. замечание *1) после теоремы 3.7). Поскольку | fin'n |<j3(log2tt + 1), число с|йгё'йр мажорируется линейной функцией от Зп = \апЬпсп\. Поэтому нам достаточно построить Неукорачивающую грамматику Гг, в которой для любого п = 1,2, ... из цепочки Я будет выводима не более чем за Citt шагов, где Ci — постоянная, цепочка ап, и не будет выводима никакая другая цепочка в словаре {а}.
Мы не будет выписывать схему, грамматики Г2 ввиду ее громоздкости; ограничимся описанием принципа ее работы — вполне достаточным, впрочем, для фактического построения схемы*).
Пусть n = isis-x ... /ji0, где ij — 0, 1 и ls=\. Вывод в Г2, начинающийся цепочкой Я, будет состоять из s + 1 «макрошагов». Цепочка, выведенная к началу &-го макрошага (6 = 0, ..., s), будет иметь вид is...ik+xikayaik-' г°, где /*_, ... г0 = • 2k~^ +...'+ /0 • 2° и <у =
<= Л0Л0ЛЛ0Л3Л0Л7 ... Л0Л2* 1_I. Макрошаг состоит в следующем:- а) Если 4 = 0, то ik превращается в Л0, каждое «старое» вхождение Л0 —в Л0Л и каждое вхождение Л — в АА. В результате__________получается цепочка
ls ... /А+1Л0Л0ЛЛ0Л3... Л0Л2*- ’a<ft г° (поскольку в этом
случае , ... i0 = ik • • • h)- б) Если ik = 1 и k < s, то ik превращается в Л0Л0Л, каждое «старое» вхождение Л0, кроме последнего, — в Л0Л3, каждое вхождение Л левее последнего вхождения Л0 — в Л4, а последнее вхождение Л0 и каждое вхождение Л правее него — в аа. В результате получается опять-таки це-
*) На самом деле для осуществления приводимой ниже конструкции первый и последний символы цепочки Л должны быть предварительно как-то помечены.
$ 3.5] НС-ГРАММАТИКИ С ОДНОСТОРОННИМ КОНТЕКСТОМ ю5
почка ls ... tk+lA0A0AA0A3 ... А0А2к-1а‘к'"1°. в) Если k = s, то ls и все вхождения символов Л0 и А заменяются на а. Получается цепочка a‘s'”4
Легко видеть, что схему описанной грамматики можно построить так, чтобы на каждом шаге, не входящем в последний макрошаг, цепочка удлинялась. Поэтому длина вывода цепочки ап из Я не будет превышать 2п шагов.
Построение примера закончено.
Заметим еще, что любой язык из j??(HC) распознается ДЭ-машиной с ограниченным растяжением (теорема 2.3,6), лемма 2.3, упражнение 3.14), так что его дополнение является НС-языком. В то же время даже дополнение к Б-языку, как и пересечение двух Б-язы-ков, может не принадлежать i??(HC) (упражнение 3.21).
§ 3.5. НС-грамматики с односторонним контекстом
В настоящем параграфе будет рассмотрен один специальный класс НС-грамматик, выделяемый с помощью некоторого на первый взгляд весьма сильного ограничения, но тем не менее оказывающийся эквивалентным по «порождающей силе» классу всех НС-грамматик.
Будем называть НС-грамматику левоконтекстной, соответственно правоконтекстной, если правые (левые) контексты всех ее правил пусты. Левоконтекстные и правоконтекстные НС-грамматики будем называть также НС-г р а м м а ти к а м и с односторонним контекстом.
Довольно долго стоял вопрос о существовании НС-грамматик с односторонним контекстом, порождающих не бесконтекстные языки (см. библиографические замечания). Тем не менее имеет место 'Теорема 3.8. Для любой НС-грамматики может быть построена эквивалентная ей левоконтекстная HG-грамматика.
Доказав эту теорему, мы, разумеется, будем вправе заключить о справедливости аналогичного факта для рравокрнтекстных грамматик..
106
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
Чтобы сделать основную идею доказательства теоремы 3.8 более ясной, рассмотрим сначала пример. Пусть Г — грамматика со следующей схемой (кото-
для удобства разделим на 4 группы):
• 1) 1->А1В III. 1) Ci —? Ei
2) I-> АВ 2) EtAt -? EiA
3) I -> atai 3) AAi -> AA
• 1) 4) ADt AFt
2) CiA —? CiAi 5) AFji AFj
3) AiA —> AiAi 6) FjFki-^FjFk
4) AiB —*? AtDi 7) F,Dt -> FjFi
5) AiF j —? AtF n IV. 1) Ei->ai
6) FtiFk-+F,iFu 2) Fi—>ai
7) FjiB ~> FjiDt
(Индексы i, /, k принимают значения 1, ..., п.)
Нетрудно видеть, что L(T) — {хх\хе{аь а„}+}. Именно, цепочка хх, где х — а, ...а, , s ^ 2, может
Ч ls
быть порождена так. Сначала по правилам группы I порождаем AJBS. Затем заменяем первое вхождение А на Ci, (правило строки II, 1)), с помощью 11,2) и II, 3) передаем информацию в начало правой половины цепочки и заменяем первое вхождение В на А, (11,4)). Это — первая половина первого цикла. Вторая половина начинается применением III, 1), после чего левая половина цепочки очищается от ненужной теперь информации (111,2), 111,3)) и Dit заменяется на Fj, (111,4)). Следующие циклы проводятся так же, только для передачи информации используются дополнительно 11,5) и 11,6), для уничтожения ее — 111,5) и 111,6), а вместо
