上下文有关文法

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

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

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

αAβ → αγβ

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

此外还有如下形式的规则

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

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

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

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

其描述能力相当于线性有界自动机，、

例：

xSy -> xAy

也就是说，S推导出A是和上下文x, y相关的，即S只有在上下文x, y的环境中才能推导出A