Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
1J Достаточно было бы S-vSl.— Прим. перев.
Формальные свойства грамматик
165
Условие 1 недостаточно сильно, чтобы позволить установить единообразный метод приписывания С-маркеров порождаемым предложениям, как это было бы желательно. Чтобы обеспечить эту возможность, мы, как было замечено в разд. 4 предыдущей главы, должны потребовать, чтобы на каждом шаге заменялся только один символ (вместе с некоторыми другими ограничениями, которые, как отмечено, ие влияют на порождающую способность). Эти соображения приводят нас к рассмотрению более строго ограничивающего условия.
Условие 2. Если есть правило, то существуют цепочки Xi, Хї< А, ш (где А — отдельный символ и <и Henycmd), такие, что T = X1AXa “ +=XituXa-
B грамматике типа 2 каждое правило (т.е. хИХа-*-
"vZi “&) может рассматриваться как утверждающее, что А может быть заменен иа м в контексте Xi—Хг> гДе> разумеется, Xi или Хз могут быть пусты. Мы будем говорить о грамматиках, удовлетворяющих этому условию, как о контекстных грамматиках. Правила этого вида весьма обычны в существующих грамматических описаниях. Они могут использоваться для указания контекстуальных ограничений на выбор определенных элементов или категорий, как об этом говорилось в предыдущей главе. Для контекстной грамматики можно определить класс Va нетерминальных символов как содержащий все (и только) такие элементы А, для которых G содержит правило ХіАхг~*ХітХг- В дальнейшем будем предполагать, что это условие всегда выполняется.
Из определения ясно, что каждая грамматика типа 2 является грамматикой типа 1, но не наоборот. Тем ие менее условие 2 не ограничивает порождающую способность грамматики.
Теорема 11. Если G есть грамматика типа 1, то существует грамматика G' типа 2, слабо эквивалентная G.
Прямое доказательство этого факта см. в работе [8].
Поскольку соответствие, указанное в теореме 11, эффективно, то сразу видно, что неразрешимые проблемы, касающиеся грамматик типа 1, остаются неразрешимыми, если ограничиться контекстными грамматиками.
Теорема 12. He существует алгоритма, определяющего по двум заданным контекстным грамматикам, являются ли эти грамматики эквивалентными, порождает ли какая-либо из них пустое, конечное или бесконечное множество цепочек, появляется ли некоторая произвольно выбранная цепочка как часть строки (MS \±)-вывода в какой-либо грамматике или как часть предложения порождаемого ею языка.
166
Н. Хомский
Здесь, как и прежде, мы находим, что мало что можно узнать путем систематического изучения правнл подобных систем.
Теорема 12 имеет важные последствия для теории грамматик непосредственных составляющих. Любая теория грамматик должна давать общий метод приписывания предложениям их структурных описаний заданной грамматикой, а в случае грамматик непосредственных составляющих это может быть сделано естественным образом лишь в том случае, если каждая грамматика удовлетворяет условию С, гласящему, что не существует символов А, В и цепочки ш, таких, что <рлВф и <?Аи>В$ являются последовательными строчками вывода терминальной цепочки (ср. сноску 3 к разд. 4 предыдущей главы). Поэтому разумно было бы потребовать от правильно построенной грамматики непосредственных составляющих в дополнение к уже наложенным ограничениям, чтобы она удовлетворяла условию С. Тогда из теоремы 12 непосредственно следует, что правильная построенность является неразрешимым свойством грамматик непосредственных составляющих. Этого уже достаточно, чтобы отвергнуть теорию грамматик непосредственных составляющих в ее настоящем виде как возможную теорию грамматик. Ясно, что общая теория грамматик должна давать рекурсивный класс правильно построенных грамматик как возможных кандидатов иа роль грамматик каких-либо естественных языков; другими словами, обязательно должен существовать алгоритм, определяющий, составляет ли данное множество правил правильно построенную грамматику в соответствии с этой теорией. Теория контекстных грамматик в ее современной форме не удовлетворяет этому требованию (хотя она может быть модифицирована так, чтобы ему удовлетворять, см. вышеуказанную сноску). Заметим, что теория трансформационных грамматик не вызывает этого затруднения, если, как предполагается в разд. 5 предыдущей главы, ее НС-компоиент порождает лишь конечное множество цепочек (аналогично, если он порождает бесконечное множество достаточно ограниченного вида; это ограничение может оказаться достаточным, если механизм трансформаций будет в достаточной мере усиливать эту порождающую способность).
В разд. 3 предыдущей главы мы использовали для примеров три искусственных языка L1, L1 и L3, все со словарем \а,Ь), и доказали, что L1 и L2 обладают грамматиками, которые сейчас мы называем контекстными. (В действительности оии обладают грамматиками,. удовлетворяющими условию 2 С пустыми Xl и Xa-) Однако для L3 была построена простая грамматика, которая вообще ие является (общей) системой подстановок. Мы зиаем, конечно, что грамматика типа общей системы подстановок должна существовать для языка L3, поскольку он, очевидно, представляет собой рекурсивно-перечислимое и даже рекурсивное множество. Инте-
