上下文无关语言

维基百科,自由的百科全书
跳转至: 导航搜索

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

例子[编辑]

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


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


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

闭包性质[编辑]

上下文无关语言闭合于下列运算下。就是说,如果 LP 是上下文无关语言而 D正则语言,下列语言也是上下文无关语言:

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

在交集下不闭包[编辑]

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

可判定性性质[编辑]

上下文无关语言的下列问题是不可判定的:

上下文无关语言的下列问题是可判定的:

  • L(A)=\emptyset 吗?
  • L(A) 是有限的吗?
  • 成员关系:给定任何字 w,w \in L(A) 吗?(成员关系问题甚至是多项式可判定的 - 参见CYK算法

上下文无关语言的性质[编辑]

引用[编辑]