|
9.3.3 上下文有关语法(1型语法)
上下文有关语法是一种满足以下约束的短语结构语法：对于每一条形式为
x→y
的产生式，y的长度(即符号串y中的符号个数)总是大于或等于x的长度，而且x，y∈V*。因此，
AB→CDE
是上下文有关语法中一条合法的产生式，但
ABC→DE
不是。这一约束已足以保证上下文有关语言是递归的。
有时也用另一种标记法来表示上下文有关语法。在这种标记法中，每一条产生式都采用如下形式
A→y/x_z
其中A∈N，y∈V+，x，z∈V*。这条产生式的意思是：如果A出现在上下文"x_z"中，即前面紧挨着符号串X，后面紧挨着符号串Z，则A可以重写为y。这等价于产生式
xAz→xyz。
第二种标记法强调了这样一个概念，即一个符号的重写依赖于其上下文，这也就是"上下文有关"这个名称的来由。你也许会注意到，这种标记法对于语法所施加的约束比我们为上下文有关语法所下的第一个定义更紧些。例如，形为
AB→BA
的产生式不能用第二种标记法重写。但是可以证明，能够被第一种形式的语法所定义的任何语言也可用第二种形式的语法定义。
9.3.4 无约束短语结构语法(0型语法)
如前所述，对于短语结构语法的重写规则如果没有附加任何限制，那么它就成为乔姆斯基体系中生成能力最强的一种形式体系，即O型语法。被这种无约束短语结构语法所定义的语言叫做O型语言，后者是可递归枚举的，但不一定是递归的。
由于不可能设计一部程序来判别一个输入的符号串是否是0型语言中的一个句子，所以O型语法很少被用来处理自然语言。
总而言之，在乔姆斯基体系中，如果一种语言可以被一部i型语法所生成，我们就称它为i型语言。
由于在乔姆斯基体系中，语法的型号愈高，对重写规则所附加的限制也愈多，所以3型语言是2型语言的一个子集，2型语言又是1型语言的一个子集，依此类推，有
O型语言
1型语言2型语言3型语言从语法的生成能力看，O型语法最强，依次递减，3型语法最弱。