上下文有关文法

上下文有关文法（CSG，英語：context-sensitive grammar）是一種形式文法，其中任何产生式规则的左手端和右手端都可以被终结符和非终结符構成的上下文所围绕。上下文有关文法比上下文无关文法更一般性，但仍足够有秩序得可以被线性有界自动机所解析。

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

形式定义

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

αAβ → αγβ

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

上下文有關文法的某些定義只要求，對於任何形如 u → v 的產生式規則，u 的長度應當小於或等於 v 的長度。這個看起來要弱些的要求，被斷定為在實際上等價於上面的定義。^[1]

此外，還允許如下形式的规则

S → ε

这里的 ε 表示空串，而 S 不出现在任何规则的右手端。增加空串允许声明：上下文有关语言是上下文无关语言的真超集，而不是作出弱一些的声明：没有 →ε产生式的所有上下文无关文法也是上下文有关文法。

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

如果把向语言增加空串的可能性增加到由不收缩文法所识别的那些字符串（永不包括空串的）中，则在这两種定义下的語言是相同的。

例子

正规的非上下文无关语言 $\{a^{n}b^{n}c^{n}:n\geq 1\}$ 可由以下上下文有關文法生成:

S → aSBC
S → aBC
CB → HB
HB → HC
HC → BC
aB → ab
bB → bb
bC → bc
cC → cc

規則1和2允許將 S 拆分為 aⁿ(BC)ⁿ；規則3到5允許隨後將每個 CB 對換位置為 BC（需要用3個規則，因為1個 CB → BC 規則，不能適合 αAβ → αγβ 模式，即產生式左手端只有1個非終結符能被替換）；規則6到9允許將在適當位置上的非終結符 B 或 C 分別替代為其對應的終結符 b 或 c。

aaa bbb ccc 的产生链是：

S

→₁ aSBC

→₁ aaSBCBC

→₂ aaaBCBCBC（通過2次規則1和1次規則2，將 S 拆分為 a³(BC)³ 。）

→₃ aaaBHBCBC

→₄ aaaBHCCBC

→₅ aaaBBCCBC

→₃ aaaBBCHBC

→₄ aaaBBCHCC

→₅ aaaBBCBCC

→₃ aaaBBHBCC

→₄ aaaBBHCCC

→₅ aaaBBBCCC （通過3輪依次使用規則3、4、5，在a³(BC)³ 中進行了3次 CB 對換位置為 BC，形成a³B³C³。）

→₆ aaabBBCCC

→₇ aaabbBCCC

→₇ aaabbbCCC

→₈ aaabbbcCC

→₉ aaabbbccC

→₉ aaabbbccc

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

針對語言 $\{a^{2^{i}}:i\geq 1\}$ 也構造了上下文有關文法，可見於Hopcroft和Ullman在1979年書中例子 9.5 (p. 224)。

范式

不生成空串的所有上下文有关文法都可以被变换成等价的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)

^ {{cite book|authors=John E. Hopcroft, Jeffrey D. Ullman|title=Introduction to Automata Theory, Languages, and Computation|publisher=Addison-Wesley|year=1979; p.223-224; Exercise 9, p.230. In the 2003 edition, the chapter on CSG has been omitted.

[1] {{cite book|authors=John E. Hopcroft, Jeffrey D. Ullman|title=Introduction to Automata Theory, Languages, and Computation|publisher=Addison-Wesley|year=1979; p.223-224; Exercise 9, p.230. In the 2003 edition, the chapter on CSG has been omitted.

[1]