上下文无关语言_可以用上下文无关文法定义的形式语言

上下文无关语言

可以用上下文无关文法定义的形式语言

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

例子

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

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

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

可判定性性质

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

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

吗？

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

吗？

L(A) 是有限的吗？

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

上下文无关语言的性质

参考资料

最新修订时间：2022-10-27 14:22

条目作者

概述

例子

可判定性性质

参考资料