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

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

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

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

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

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

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

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

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

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

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

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

Правило (d) «неправильно построено» потому, что оно заменяет Р само на себя (то есть нарушает условие, требующее, чтобы А и В не были тождественны). Правило (е) содержит «нулевой» символ

(0) непосредственно справа от стрелки: это определяет правило (е) как правило элиминации («заменить Р на нуль» означает «элими­нировать Р»; на «выходе» правила (е), если бы мы допустили его включение в систему, было бы Е + F, выведенное посредством данного правила из Е + Р + F на «входе»).

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

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

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

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

6.5.3.