[科普中国]-上下文无关语言

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

例子一个原型上下文无关语言是 ，它是所有非空、偶数长度字符串的语言，字符串的整个前半部分都是a，整个后半部分都是b。L由文法 生成，并被下推自动机 接受，这里的 定义如下：

这里的 z 是初始栈符号而 x 意味着弹出动作。

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

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

等价：给定两个上下文无关文法A 和 B，吗？

吗？

吗？

吗？

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

吗？

L(A) 是有限的吗？

成员关系：给定任何字 w，吗？（成员关系问题甚至是多项式可判定的 - 参见CYK算法）

上下文无关语言的性质上下文无关语言的反转（reverse）也是上下文无关的，但是补（complement）不必须是。

所有正则语言都是上下文无关的，因为它们可以用正则文法描述。

存在不是上下文无关的上下文有关语言。

要证明给定语言不是上下无关的，可以采用上下文无关语言的泵引理。1

本词条内容贡献者为:

黎明 - 副教授 - 西南大学