символ, фигурирующий слева от стрелки подстановки, заменялся на «выходе» правила символом или цепочкой символов, стоящих справа от стрелки в формулировке правила. Так, например, следующее правило (ср. § 6.2.6)

N > N + and + N

интерпретировалось как инструкция «заменить» N на N + and + N (факультативно или обязательно) в любой цепочке символов, к которой это правило может быть применено. Другими словами, единственное условие действия правила заключается в появлении N на «входе» правила. Например, если на «входе» имеем альтернативные цепочки

(i) X + N + Y

(ii) W + N + Z,

то на «выходе», после действия рассматриваемого правила, будет в одном случае

X + N + and + N + Y

и в другом случае

W + N + and + N + Z.

Суть в том, что на действие правила не накладывается никаких контекстуальных ограничений.

Предположим, однако, что мы сформулировали это правило следующим образом:

N > N + and + N / в контексте X + ... + Y.

Можно было бы условиться, что это означает, что N следует «заменить» (факультативно или обязательно) только в том случае, если на «входе» непосредственно слева от него стоит X, а справа непосредственно от него — Y. В таком случае правило применялось бы к (i), но не к (И). Указание на контекстуальные условия, данное справа от наклонной черты в вышеприведенном правиле, превращает его в контекстно-связанное правило.

Могут быть сформулированы самые различные контекстно-связанные правила тех или иных типов и подтипов. Мы ограничим наше внимание теми, которые относятся к сфере грамматик непосредственных составляющих (формализуемых в виде набора упорядоченных или неупорядоченных, факультативных или обязательных, рекурсивных и нерекурсивных конкатенирующих правил). Любая такая грамматика, включающая одно или более контекстно-связанных правил, определяется как контекстно- связанная грамматика структуры непосредственных составляющих.

Внутри этого класса грамматик можно различать те, в которых X и Y, фигурируя в правилах только что приведенного типа, могут обозначать каждый только один символ; те, в которых или X, или Y, или тот и другой могут обозначать цепочку более чем из одного символа и т. д.

Мы будем считать, что занимающий нас здесь класс контекстно-связанных грамматик определяется тем условием, чтобы X и Y в правилах типа

А > В / в контексте X + ... + Y

могли обозначать независимо друг от друга любое конечное число конкатенированных символов, но чтобы А непременно было единичным символом. Кроме того, мы примем, что В не может быть тождественным с A и не может быть «нулевым» (ср. § 6.2.11). Эти условия допускают включение в систему в качестве «правильно построенных» следующие правила:

(a) Р > Q / в контексте Е + F + ... + G

(b) Р > Q + R / в контексте E+ ... + G+ H + K+L

(c) P > R + S + T / в контексте G + ... + Н

и т. д.

Они воспрепятствуют включению в грамматику правил, подобных следующим:

(d) Р > Р / в контексте Е + ... + F

(е) Р > O / в контексте Е +...+ Р.

Правило (d) «неправильно построено» потому, что оно заменяет Р само на себя (то есть нарушает условие, требующее, чтобы А и В не были тождественны). Правило (е) содержит «нулевой» символ (O) непосредственно справа от стрелки: это определяет правило (е) как правило элиминации («заменить Р на нуль» означает «элиминировать Р»; на «выходе» правила (е), если бы мы допустили его включение в систему, было бы E + F, выведенное посредством данного правила из E + P + F на «входе»).

Следует обратить внимание на то, что в вышеприведенных правилах одни символы напечатаны курсивом, другие — прямым шрифтом. Символы, напечатанные курсивом, являются постоянными, прочие — переменными[45]. Мы вернемся ниже к разграничению постоянных и переменных (см. § 6.6.6). Для целей настоящего раздела сведем различие к следующему: если символ появляется в какой-либо части правила в качестве постоянной, это означает, что правило относится к этому конкретному символу; если символ появляется в качестве переменной, это означает, что правило применяется к любой постоянной, которая определена как принадлежащая к классу, обозначенному посредством этой переменной.

Для настоящего изложения это различие существенно лишь постольку, поскольку оно разграничивает реальные правила грамматики (которые, как мы примем, не содержат никаких переменных) и отвлеченные характеристики формы этих правил. Другими словами,

А > В / в контексте X + ... + Y

не является правилом, но изображает целый класс правил, различающихся «значениями», которые определяются как допустимые для переменных А, В, X и У. Условия, которые ограничивают область допустимых значений переменных, были приведены выше.

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

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

А > В / в контексте X + ... + Y.

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

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

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