Контекстно-связанная грамматика

ТЕРМИН «КОНТЕКСТНАЯ СВЯЗАННОСТЬ»

Мы должны теперь ввести разграничение между контекстно-связанными и контекстно-свободными правилами. (В качестве синонимов термина «контекстно-связанный» в литературе употребляются также термины «конктекстно-ограниченный» и «контекстно-зависимый».)

Все правила, приведенные до сих пор, были контекстно-свободными в том смысле, что символ, фигурирующий слева от стрелки подстановки, заменялся на «выходе» правила символом или цепочкой символов, стоящих справа от стрелки в формулировке правила. Так, например, следующее правило (ср. § 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), но не к (И). Указание на контекстуальные условия, данное справа от наклонной черты в вышеприведенном правиле, превращает его в контекстно-связанное правило.