查看“︁上下文有关文法”︁的源代码

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

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

== 形式定义 ==

形式文法 ''G'' = (''N'', Σ, ''P'', ''S'') 如果在 ''P'' 中所有的规则都有如下形式，則我們說它是上下文有关的
: α''A''β → αγβ
这里的 ''A'' ∈ ''N''（就是 ''A'' 是单一[[非终结符]]），α,β ∈ (''N'' U Σ)*（就是 α 和 β 是非终结符和[[终结符]]的字符串）而 γ ∈ (''N'' U Σ)<sup>+</sup>（就是 γ 是非终结符和终结符的非空字符串）。 

上下文有關文法的某些定義只要求，對於任何形如 u → v 的產生式規則，u 的長度應當小於或等於 v 的長度。這個看起來要弱些的要求，被斷定為在實際上等價於上面的定義。<ref>{{cite book|authors=John E. Hopcroft, Jeffrey D. Ullman|title=Introduction to Automata Theory, Languages, and Computation|publisher=Addison-Wesley|year=1979'''</span>; p.223-224; Exercise 9, p.230. In the 2003 edition, the chapter on CSG has been omitted.</ref>

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

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

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

== 例子 ==

正规的非[[上下文无关语言]] <math> \{ a^n b^n c^n : n \ge 1 \} </math>可由以下上下文有關文法生成:
# ''S'' → ''aSBC''
# ''S'' → ''aBC''
# ''CB'' → ''HB''
# ''HB'' → ''HC''
# ''HC'' → ''BC''
# ''aB'' → ''ab''
# ''bB'' → ''bb''
# ''bC'' → ''bc''
# ''cC'' → ''cc''
規則1和2允許將 ''S'' 拆分為 ''a''<sup>''n''</sup>(''BC'')<sup>''n''</sup>；規則3到5允許隨後將每個 ''CB'' 對換位置為 ''BC''（需要用3個規則，因為1個 ''CB'' → ''BC'' 規則，不能適合 α''A''β → αγβ 模式，即產生式左手端只有1個非終結符能被替換）；規則6到9允許將在適當位置上的非終結符 ''B'' 或 ''C'' 分別替代為其對應的終結符 ''b'' 或 ''c''。

aaa bbb ccc 的产生链是：
: ''S''
: →<sub>1</sub> ''aSBC''
: →<sub>1</sub> ''a<span style="font-family:monospace">'''aSBC'''</span>BC''
: →<sub>2</sub> ''aa<span style="font-family:monospace">'''aBC'''</span>BCBC''（通過2次規則1和1次規則2，將 ''S'' 拆分為 ''a''<sup>''3''</sup>(''BC'')<sup>''3''</sup> 。）
: →<sub>3</sub> ''aaaB<span style="font-family:monospace">'''HB'''</span>CBC'' 
: →<sub>4</sub> ''aaaB<span style="font-family:monospace">'''HC'''</span>CBC''
: →<sub>5</sub> ''aaaB<span style="font-family:monospace">'''BC'''</span>CBC''
: →<sub>3</sub> ''aaaBBC<span style="font-family:monospace">'''HB'''</span>C''
: →<sub>4</sub> ''aaaBBC<span style="font-family:monospace">'''HC'''</span>C''
: →<sub>5</sub> ''aaaBBC<span style="font-family:monospace">'''BC'''</span>C''
: →<sub>3</sub> ''aaaBB<span style="font-family:monospace">'''HB'''</span>CC''
: →<sub>4</sub> ''aaaBB<span style="font-family:monospace">'''HC'''</span>CC''
: →<sub>5</sub> ''aaaBB<span style="font-family:monospace">'''BC'''</span>CC'' （通過3輪依次使用規則3、4、5，在''a''<sup>''3''</sup>(''BC'')<sup>''3''</sup> 中進行了3次 ''CB'' 對換位置為 ''BC''，形成''a''<sup>''3''</sup>''B''<sup>''3''</sup>''C''<sup>''3''</sup>。）
: →<sub>6</sub> ''aa<span style="font-family:monospace">'''ab'''</span>BBCCC''
: →<sub>7</sub> ''aaa<span style="font-family:monospace">'''bb'''</span>BCCC''
: →<sub>7</sub> ''aaab<span style="font-family:monospace">'''bb'''</span>CCC''
: →<sub>8</sub> ''aaabb<span style="font-family:monospace">'''bc'''</span>CC''
: →<sub>9</sub> ''aaabbb<span style="font-family:monospace">'''cc'''</span>C''
: →<sub>9</sub> ''aaabbbc<span style="font-family:monospace">'''cc'''</span>''
<math> \{ a^n b^n c^n d^n : n \ge 1 \} </math> 和其他有更多字母的语言可以使用更复杂的上下文有關文法解析。

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

== 范式 ==

不生成空串的所有上下文有关文法都可以被变换成等价的[[Kuroda范式]]的文法。这个“等价”意味着两个文法生成同样的语言。这种范式一般不是上下文有关的，但却是[[不收缩文法]]。

== 计算的性质和使用 ==

特定字符串 ''s'' 是否属于特定上下文有关文法 ''G'' 的语言的[[判定问题]]是 [[PSPACE#PSPACE - 完全|PSPACE-完全]]的。实际上，甚至有些上下文有关文法的固定文法识别问题也是 PSPACE-完全的。

上下文有关文法的空虚（emptiness）问题（给定上下文有关文法 G，<math>L(G)=\emptyset</math> 吗？）是[[不可判定性|不可判定]]的。 

已经证实几乎所有[[自然语言]]一般的都可以用上下文有关文法来刻画，但是整个 CSG 类好像比自然语言要大。更糟糕的是，因为上述 CSG 的判定问题是 PSPACE-完全的，这使得它们对于实际使用而言是完全不能运作的，因为一般算法将运行[[指数时间]]。关于[[计算语言学]]的当前进行中的研究关注于公式化是[[适度上下文有关语言]]的其他语言类，这种语言如[[树-邻接文法]]、[[组合范畴文法]]、[[连结上下文无关文法]]和[[线性上下文无关重写系统]]的判定问题是可行的。这些形式化所生成的语言适当的位于上下文无关和上下文有关语言之间。

== 参见 ==
* [[乔姆斯基谱系]]
* [[上下文有关文法]]
* [[形式文法]]
* [[分析表达式文法]]
* [[随机上下文无关文法]]

== 引用 ==
* Introduction to Languages and the Theory of Computation by John C. Martin McGraw Hill 1996 (2nd edition)
{{reflist}}

{{形式语言与形式文法}}

[[Category:形式语言|S]]