查看“︁上下文无关语言”︁的源代码

'''上下文无关语言'''是可以用[[上下文无关文法]]定义的[[形式语言]]。所有上下文无关语言的集合同一于[[下推自动机]]所接受的语言的集合。

== 例子 ==

一个原型上下文无关语言是 <math>L = \{a^nb^n:n\geq1\}</math>，它是所有非空、偶数长度字符串的语言，字符串的整个前半部分都是 <math>a</math>，整个后半部分都是 <math>b</math>。<math>L</math> 由文法 <math>S\to aSb ~|~ ab</math> 生成，并被下推自动机 <math>M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, \{q_f\})</math> 接受，这里的 <math>\delta</math> 定义如下：


:<math>\delta(q_0, a, z) = (q_0, a)</math><br />
:<math>\delta(q_0, a, a) = (q_0, a)</math><br />
:<math>\delta(q_0, b, a) = (q_1, x)</math><br />
:<math>\delta(q_1, b, a) = (q_1, x)</math><br />
:<math>\delta(q_1, b, z) = (q_f, z)</math><br />
:这里的 z 是初始栈符号而 x 意味着弹出动作。


上下文无关语言在[[编程语言]]中有很多应用。大多数算术表达式可用上下文无关文法生成。

== 闭包性质 ==

上下文无关语言[[闭包 (数学)|闭合]]于下列运算下。就是说，如果 ''L'' 和 ''P'' 是上下文无关语言而 ''D'' 是[[正则语言]]，下列语言也是上下文无关语言：

* ''L'' 的 [[Kleene星号]] <math>L^*</math> 
* ''L'' 在[[字符串同态]] φ 下的像 φ(L)
* ''L'' 和 ''P'' 的[[串接]] <math>L \circ P</math>
* ''L'' 和 ''P'' 的[[并集]] <math>L \cup P</math>
* ''L'' 和（正则语言）''D'' 的[[交集]] <math>L \cap D</math> 

上下文无关语言不闭合于[[补集]]，[[交集]]或[[差集]]下。

=== 在交集下不闭包 ===

上下文无关语言不闭合于[[交集]]下。其证明在 Sipser 97 中被作为习题给出。选用语言 <math>A = \{a^m b^n c^n \mid m, n \geq 0 \}</math> 和 <math>B = \{a^n b^n c^m \mid m,n \geq 0\}</math>，它们都是上下文无关的。它们的交集是 <math>A \cap B = \{ a^n b^n c^n \mid n \geq 0\}</math>，它可以用[[泵引理|上下文无关语言的泵引理]]证实为非上下文无关的。

== 可判定性性质 ==

上下文无关语言的下列问题是[[判定问题|不可判定]]的：
*等价：给定两个[[上下文无关文法]] A 和 B，<math>L(A)=L(B)</math> 吗？
*<math>L(A) \cap L(B) = \emptyset </math> 吗？
*<math>L(A)=\Sigma^*</math> 吗？
*<math>L(A) \subseteq L(B)</math> 吗？

上下文无关语言的下列问题是可判定的：
*<math>L(A)=\emptyset</math> 吗？
*L(A) 是有限的吗？
*成员关系：给定任何字 w，<math>w \in L(A)</math> 吗？（成员关系问题甚至是多项式可判定的 - 参见[[CYK算法]]）

== 上下文无关语言的性质 ==

* 上下文无关语言的反转（reverse）也是上下文无关的，但是补（complement）不必须是。
* 所有[[正则语言]]都是上下文无关的，因为它们可以用[[正则文法]]描述。 
* 存在不是上下文无关的[[上下文有关语言]]。
* 要证明给定语言不是上下无关的，可以采用[[泵引理|上下文无关语言的泵引理]]。

== 引用 ==
* {{cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Chapter 2: Context-Free Languages, pp.91–122.

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

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