Различные виды контекстно-связанных грамматик

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

Внутри этого класса грамматик можно различать те, в которых 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 и У. Условия, которые ограничивают область допустимых значений переменных, были приведены выше.