基本介紹
- 中文名：上下文有關文法
- 外文名：Context-sensitive grammars
- 提出者：諾姆·喬姆斯基
- 類型：形式文法
形式定義,例子,範式,計算的性質和使用,
形式定義
形式文法 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-完全的，這使得它們對於實際使用而言是完全不能運做的，因為一般算法將運行指數時間。關於計算語言學的當前進行中的研究關注於公式化是適度上下文有關語言的其他語言類，這種語言如樹-鄰接文法、組合範疇文法、連結上下文無關文法和線性上下文無關重寫系統的判定問題是可行的。這些形式化所生成的語言適當的位於上下文無關和上下文有關語言之間。
