上下文有關文法

形式文法 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-完全的，這使得它們對於實際使用而言是完全不能運做的，因為一般算法將運行指數時間。關於計算語言學的當前進行中的研究關注於公式化是適度上下文有關語言的其他語言類，這種語言如樹-鄰接文法、組合範疇文法、連結上下文無關文法和線性上下文無關重寫系統的判定問題是可行的。這些形式化所生成的語言適當的位於上下文無關和上下文有關語言之間。 ^[1]