W + N + and + N + Z.
Суть в том, что на действие правила не накладывается никаких контекстуальных ограничений.
Предположим, однако, что мы сформулировали это правило следующим образом:
N → N + and + N / в контексте X + ... + Y.
Можно было бы условиться, что это означает, что N следует «заменить» (факультативно или обязательно) только в том случае, если на «входе» непосредственно слева от него стоит X, а справа непосредственно от него — Y. В таком случае правило применялось бы к (i), но не к (И). Указание на контекстуальные условия, данное справа от наклонной черты в вышеприведенном правиле, превращает его в контекстно-связанное правило.
6.5.2. РАЗЛИЧНЫЕ ВИДЫ КОНТЕКСТНО-СВЯЗАННЫХ ГРАММАТИК
Могут быть сформулированы самые различные контекстно-связанные правила тех или иных типов и подтипов. Мы ограничим наше внимание теми, которые относятся к сфере грамматик непосредственных составляющих (формализуемых в виде набора упорядоченных или неупорядоченных, факультативных или обязательных, рекурсивных и нерекурсивных конкатенирующих правил). Любая такая грамматика, включающая одно или более контекстно-связанных правил, определяется как контекстно-связанная грамматика структуры непосредственных составляющих.
Внутри этого класса грамматик можно различать те, в которых 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
(е) Р → Ø / в контексте Е +...+ Р.
Правило (d) «неправильно построено» потому, что оно заменяет Р само на себя (то есть нарушает условие, требующее, чтобы А и В не были тождественны). Правило (е) содержит «нулевой» символ (Ø) непосредственно справа от стрелки: это определяет правило (е) как правило элиминации («заменить Р на нуль» означает «элиминировать Р»; на «выходе» правила (е), если бы мы допустили его включение в систему, было бы E + F, выведенное посредством данного правила из E + P + F на «входе»).
Следует обратить внимание на то, что в вышеприведенных правилах одни символы напечатаны курсивом, другие — прямым шрифтом. Символы, напечатанные курсивом, являются постоянными, прочие — переменными[45]. Мы вернемся ниже к разграничению постоянных и переменных (см. § 6.6.6). Для целей настоящего раздела сведем различие к следующему: если символ появляется в какой-либо части правила в качестве постоянной, это означает, что правило относится к этому конкретному символу; если символ появляется в качестве переменной, это означает, что правило применяется к любой постоянной, которая определена как принадлежащая к классу, обозначенному посредством этой переменной.
Для настоящего изложения это различие существенно лишь постольку, поскольку оно разграничивает реальные правила грамматики (которые, как мы примем, не содержат никаких переменных) и отвлеченные характеристики формы этих правил. Другими словами,
А → В / в контексте X + ... + Y
не является правилом, но изображает целый класс правил, различающихся «значениями», которые определяются как допустимые для переменных А, В, X и У. Условия, которые ограничивают область допустимых значений переменных, были приведены выше.
