КОНТЕКСТНО-СВЯЗАННЫЕ ГРАММАТИКИ ВКЛЮЧАЮТ В СЕБЯ КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ

Если мы добавим еще одно условие, мы сможем определить контекстно-свободные грамматики непосредственных составляющих как подклассы контекстно-связанных грамматик. Условие заклю­чается в том, что мы не ограничиваем «значения», принимаемые

X и У, в правилах вида

Л б / в контексте X +...+ У.

Сначала мы разграничим в целях чисто терминологического удобства нулевое значение (0) и положительные значения (любое допустимое «значение», отличное от 0, которое придается пере­менной). Итак, если указано, для некоторого конкретного пра­вила, что контекстуальные переменные X и У не ограничены по «значению» (каждое независимым образом может принимать или положительное, или нулевое «значение»), рассматриваемое правило является контекстно-свободным. Если «значения» X или У огра­ничены, то есть определяются либо как нулевое, либо как положи­тельное, правило является контекстно-связанным.

Рассмотрим ряд примеров. Следующие правила все являются контекстно-связанными:

(f) Р -> Q / в контексте 0 +•..+ 0

(g) Р -> Q / в контексте 0 + ...+ R + S

(h) Р -> Q / в контексте Т +...+ 0.

Правило (f), в действительности, говорит, что Р следует «заме­нить» на Q, если только слева и справа в цепочке на «входе» нет ни­каких других символов. (Обычно единственным символом, удовле­творяющим этому контекстуальному условию, является начальный символ 2.) Но можно представить себе систему правил, в которой начальный символ был бы «заменен» на Р. Правило (g) говорит, что Р следует «заменить» на Q только тогда, когда на «входе» имеем це­почку P+R+S, а правило (h), — что Р следует «заменять» толь­ко тогда, когда оно появляется в конце «входной» цепочки Т+Р. Эти правила можно также записать в другой форме (что часто де­лается в публикуемых грамматиках):

(f') 0+P+0+0+Q+0 (g') 0+P+R+S->0+Q+R+S (h') T+P+0+T+Q+0.

Обобщая эту форму (посредством использования переменных Л, б, X и У), мы можем сказать, что все правила контекстно-свя­занной грамматики имеют вид:

Х+Л + У->Х+б+У.

Тогда контекстно-свободное правило вида

Л->б

можно считать частным случаем контекстно-связанного правила, в котором «значения» X и У не ограничены.

Именно такого рода обобщения, проведенные внутри теории грамматик непосредственных составляющих, позволили сделать контекстно-свободные и контекстно-связанные правила формально однородными. Теперь мы можем перейти к более конкретному обсуждению сущности контекстной связанности в языке.

6.5.4.