上下文有关文法的概念是诺姆·乔姆斯基在1950年代作为描述自然语言的语法的一种方式介入的，在自然语言中一个单词是否可以出现在特定位置上要依赖于上下文。可以被上下文有关文法描述的形式语言叫做上下文有关语言。
上下文有关文法的概念是诺姆·乔姆斯基在1950年代作为描述自然语言的语法的一种方式介入的，在自然语言中一个单词是否可以出现在特定位置上要依赖于上下文。可以被上下文有关文法描述的形式语言叫做上下文有关语言。
上下文有关文法(CSG)是其中任何产生规则的左手端和右手端都可以被终结符和非终结符的上下文所围绕的形式文法。上下文有关文法比上下文无关文法更一般性但仍足够有秩序得可以被线性有界自动机所解析。
形式文法 G = (N, Σ, P, S) 是上下文有关的，如果在 P 中所有的规则都有如下形式
αAβ → αγβ
这里的 A ∈ N (就是 A 是单一非终结符)，α,β ∈ (N U Σ)* (就是 α 和 β 是非终结符和终结符的字符串)而 γ ∈ (N U Σ)+ (就是 γ 是非终结符和终结符的非空字符串)。
此外还有如下形式的规则
S → ε 假定 S 不出现在任何规则的右手端
这里的 ε 表示空串是允许的。增加空串允许声明上下文有关语言是上下文无关语言的真子集，而无须作出没有 →ε产生式的所有上下文无关文法也是上下文有关文法这种弱一些的声明。
上下文有关这个名称来源自 α 和 β 形成了 A 的上下文并且决定 A 是否可以被 γ 所替代。这不同于不考虑非终结符上下文的上下文无关文法。
如果向语言增加空串的可能性被增加到由(永不包括空串的)不收缩文法所识别的那些字符串中，则这个语言在这两个定义中是同一的。
以下文法生成正规的非上下文无关语言
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
可以使用更复杂的文法解析 和其他有更多字母的语言。
aaa bbb ccc 的产生链是：
S
aRc
aaRTc
aaaRTTc
aaabTTc
aaabbUTc
aaabbUUc
aaabbVUc
aaabbVcc
aaabbbccc
aaaa bbbb cccc 的产生链是：
S
aRc
aaRTc
aaaRTTc
aaaaRTTTc
aaaabTTTc
aaaabbUTTc
aaaabbUUTc
aaaabbUUUc
aaaabbUVUc
aaaabbUVcc
aaaabbVVcc
aaaabbbWVcc
aaaabbbWWcc
aaaabbbTWcc
aaaabbbTccc
aaaabbbbcccc
不生成空串的所有上下文有关文法都可以被变换成等价的Kuroda范式的文法。这个“等价”意味着两个文法生成同样的语言。这种范式一般不是上下文有关的，但却是不收缩文法。
特定字符串 s 是否属于特定上下文有关文法 G 的语言的判定问题是 PSPACE-完全的。实际上，甚至有些上下文有关文法的固定文法识别问题也是 PSPACE-完全的。
上下文有关文法的空虚（emptiness）问题（给定上下文有关文法 G， 吗？）是不可判定的。
已经证实几乎所有自然语言一般的都可以用上下文有关文法来刻画，但是整个 CSG 类好像比自然语言要大。更糟糕的是，因为上述 CSG 的判定问题是 PSPACE-完全的，这使得它们对于实际使用而言是完全不能运做的，因为一般算法将运行指数时间。关于计算语言学的当前进行中的研究关注于公式化是适度上下文有关语言的其他语言类，这种语言如树-邻接文法、组合范畴文法、连结上下文无关文法和线性上下文无关重写系统的判定问题是可行的。这些形式化所生成的语言适当的位于上下文无关和上下文有关语言之间。
温馨提示：
