Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 38

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 32 33 34 35 36 37 < 38 > 39 40 41 42 43 44 .. 136 >> Следующая

II, 4) и III, 4) применяются соответственно 11,7) и
III, 7). После s циклов получаем цепочкуEit.. .EisFi ... ... Fis, которая затем преобразуется в хх (IV, 1), 2)). Любой цикл можно в любой момент оборвать и перейти к следующему; однако если хоть один цикл не будет доведен до конца, то мы не сможем уничтожить все вхождения вспомогательных символов. Поэтому ника-
§ 3.5] НС-ГРАММАТИКИ С ОДНОСТОРОННИМ КОНТЕКСТОМ 107
кая цепочка в основном словаре, не имеющая вида хх, не выводима из / в Г.
Перейдем к доказательству теоремы 3.8. Для произвольной грамматики Г = ( V, W, /, R) и произвольного языка /.^(KUR7)* будем называть Г-образом L множество всех тех цепочек в V, которые выводимы в Г из цепочек, принадлежащих L. Мы докажем предложение, несколько более сильное, чем теорема 3.8, а именно: для произвольной неукорачивающей грамматики Г с основным словарем V можно построить грамматику Г' с основным словарем V и вспомогательным словарем W такую, что: 1) каждое правило Г' имеет вид а А -* ар или А р, где АеУ, а, р е V U W\ 2) L(T) является Г'-образом КС-языка {фHhGnHmGn\k, т, п = 0, 1, ...}, где #, G, Н — некоторые элементы W.
Заметим прежде всего, что для данной неукорачивающей грамматики Г можно построить такую грамматику Гь что в каждом ее правиле длины левой и правой частей равны и Ь(Г) есть Ггобраз языка {IoQm\m = = 0, 1, ...}, где /о и Q — некоторые вспомогательные символы П. Построение Ti, весьма простое, предоставляется читателю.
Любой вывод цепочки х е V* из цепочки IoQm в Ti (такой вывод существует тогда и только тогда, когда ^еЬ(Г) и т = \х\—1) будем называть нормальным выводом X.
Построим теперь грамматику Гг, обладающую свойством 1) искомой грамматики Г', а также следующим свойством: 2') вспомогательный словарь Г7 содержит такие символы V, Р, Q, что Гг-образ языка L0 = = {VPnQmPn\m, п = 0, 1, ...} состоит из всевозможных цепочек вида Wzx?, где ^еЦГ) и z — двоичная запись длины некоторого нормального вывода х.
Мы не будем приводить формальное построение Гг и ограничимся описанием принципа ее работы. При этом нам удобно будет представлять себе Гг — поскольку она работает с цепочкой ?PnQmPn — как некоторую машину, снабженную конечной лентой, длина которой в процессе работы не изменяется; по ленте слева напра-в о движутся головки, которые могут возникать и исчезать. При этом можно потребовать, чтобы головки могли возникать только в крайней слева ячейке
108
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
(а исчезать1—в любой) и чтобы в одной ячейке не могли одновременно находиться две головки. Можно даже потребовать, чтобы на ленте в каждый момент была только одна головка.)
В начале работы нам удобно будет считать все ячейки пустыми. Символы V, Р и Q будет интерпретироваться как различные метки, стоящие в пустых ячейках; эти метки будут сохраняться и при заполнении ячеек, так что любая ячейка в любой момент несет информацию о том, является ли она крайней слева, и если нет, то какой из трех зон она принадлежит — левой (первые п ячеек, не считая крайней слева), средней (следующие т ячеек) или правой (последние п ячеек).
В левой и правой зонах будут записываться цепочки в словаре {0, 1}, причем цепочка v, записанная в левой зоне, всегда будет двоичной записью натурального числа, а цепочка w, записанная в правой зоне, — обращением двоичной записи натурального числа. Для простоты мы будем отождествлять и, соответственно ш, с числом, двоичной записью которого служит 0, соответственно да; будем говорить, например: «прибавим к v единицу» и т. п.
Работа машины распадается на два этапа; вплоть до конца второго этапа в левой и правой зонах вместо нулей и единиц стоят их двойники, являющиеся вспомогательными символами; мы, однако, будем для простоты пренебрегать этим.
Первый этап состоит в последовательном выполнении циклов, которые будут сейчас описаны.
1-й цикл. В последней ячейке левой зоны записывается 0, в первой ячейке средней зоны записывается /о и в первой ячейке правой зоны записывается 0.
s + 1-й цикл (s ^ 0). Содержимое левой зоны увеличивается на 1, затем в средней зоне имитируется применение некоторого правила грамматики Ti (причем сначала первый слева символ выбранного вхождения левой части правила заменяется первым символом правой части, затем второй и т. д,) и, наконец, увеличивается на 1 содержимое правой зоны. При этом прибавление единицы в правой зоне производится обычным способом: если в младшем (т. е. самом левом) разряде сгоит нуль, то он заменяется единицей, если единица, она заменяется нулем и делается перенос. В левой
§ 3.5] НС-ГРАММАТИКИ С ОДНОСТОРОННИМ КОНТЕКСТОМ 109
зоне единица прибавляется «наугад»: до какого-то места цепочка проходится слева направо без изменения, затем в некоторой ячейке нуль заменяется единицей (вариант — записывается единица в пустой ячейке); если следующая ячейка оказалась пустой, операция закончена, если нет, делается попытка истолковать произведенную замену нуля единицей как перенос при прибавлении единицы; если такое толкование невозможно, т. е. где-то правее есть еще нуль, то машина «ломается».
Предыдущая << 1 .. 32 33 34 35 36 37 < 38 > 39 40 41 42 43 44 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed