上下文有关文法

上下文有关文法（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]