上下文有关文法

维基百科，自由的百科全书

跳转到: 导航, 搜索

上下文有关文法(CSG)是其中任何产生规则的左手端和右手端都可以被终结符和非终结符的上下文所围绕的形式文法。上下文有关文法比上下文无关文法更一般性但仍足够有秩序得可以被线性有界自动机所解析。

上下文有关文法的概念是诺姆·乔姆斯基在1950年代作为描述自然语言的语法的一种方式介入的，在自然语言中一个单词是否可以出现在特定位置上要依赖于上下文。可以被上下文有关文法描述的形式语言叫做上下文有关语言。

[编辑] 形式定义

形式文法 G = (N, Σ, P, S) 是上下文有关的，如果在 P 中所有的规则都有如下形式

αAβ → αγβ

这里的 A ∈ N (就是 A 是单一非终结符)，α,β ∈ (N U Σ)* (就是 α 和 β 是非终结符和终结符的字符串)而 γ ∈ (N U Σ)⁺ (就是 γ 是非终结符和终结符的非空字符串)。

此外还有如下形式的规则

S → ε 假定 S 不出现在任何规则的右手端

这里的 ε 表示空串是允许的。增加空串允许声明上下文有关语言是上下文无关语言的真子集，而无须作出没有 →ε产生式的所有上下文无关文法也是上下文有关文法这种弱一些的声明。

上下文有关这个名称来源自 α 和 β 形成了 A 的上下文并且决定 A 是否可以被 γ 所替代。这不同于不考虑非终结符上下文的上下文无关文法。

如果向语言增加空串的可能性被增加到由(永不包括空串的)不收缩文法所识别的那些字符串中，则这个语言在这两个定义中是同一的。

[编辑] 例子

下面文法生成正规的非上下文无关语言 $\{ a^n b^n c^n : n \ge 1 \}$ :

S → aRc

R → aRT | b

bTc → bbcc

bTT → bbUT

UT → UU

UUc → VUc → Vcc

UV → VV

bVc → bbcc

bVV → bbWV

WV → WW

WWc → TWc → Tcc

WT → TT

可以使用更复杂的文法解析 $\{ a^n b^n c^n d^n : n \ge 1 \}$ 和其他有更多字母的语言。

aaa bbb ccc 的产生链是:

aRc

aaRTc

aaaRTTc

aaabTTc

aaabbUTc

aaabbUUc

aaabbVUc

aaabbVcc

aaabbbccc

aaaa bbbb cccc 的产生链是:

aRc

aaRTc

aaaRTTc

aaaaRTTTc

aaaabTTTc

aaaabbUTTc

aaaabbUUTc

aaaabbUUUc

aaaabbUVUc

aaaabbUVcc

aaaabbVVcc

aaaabbbWVcc

aaaabbbWWcc

aaaabbbTWcc

aaaabbbTccc

aaaabbbbcccc

[编辑] 范式

不生成空串的所有上下文有关文法都可以被变换成等价的Kuroda范式的文法。这个“等价”意味着两个文法生成同样的语言。这种范式一般不是上下文有关的，但却是不收缩文法。

[编辑] 计算的性质和使用

特定字符串 s 是否属于特定上下文有关文法 G 的语言的判定问题是 PSPACE-完全的。实际上，甚至有些上下文有关文法的固定文法识别问题也是 PSPACE-完全的。

上下文无关文法的空虚(emptiness)问题(给定上下文有关文法 G， $L(G)=\emptyset$ 吗?) 是不可判定的。

已经证实几乎所有自然语言一般的都可以用上下文有关文法来刻画，但是整个 CSG 类好象比自然语言要大。更糟糕的是，因为上述 CSG 的判定问题是 PSPACE-完全的，这使得它们对于实际使用而言是完全不能运做的，因为一般算法将运行指数时间。关于计算语言学的当前进行中的研究关注于公式化是适度上下文有关语言的其他语言类，这种语言如树-邻接文法、组合范畴文法、连结上下文无关文法和线性上下文无关重写系统的判定问题是可行的。这些形式化所生成的语言适当的位于上下文无关和上下文有关语言之间。

[编辑] 参见

乔姆斯基谱系

[编辑] 引用

Introduction to Languages and the Theory of Computation by John C. Martin McGraw Hill 1996 (2nd edition)

自动机理论: 形式语言和形式文法
乔姆斯基层级	文法	语言	极小自动机
类型 0	无限制	递归可枚举	图灵机
n/a	(无公用名)	递归	判定器
类型 1	上下文有关	上下文有关	线性有界
n/a	附标	附标	嵌套堆栈
n/a	树-邻接	适度上下文有关	嵌入下推
类型 2	上下文无关	上下文无关	非确定下推
n/a	确定上下文无关	确定上下文无关	确定下推
类型 3	正则	正则	有限
每个语言或文法范畴都是其直接上面的范畴的真子集。