这是否意味着只有非确定性上下文无关语言才能在联合下关闭？那么为什么几乎所有的教科书和网站都提到 CFL 通常在 Union 下是关闭的？一个直观的解释就足够了。不需要详细的证明。
问问题
1698 次
1 回答
1
确定性上下文无关语言(DCFL)，定义为可被确定性下推自动机识别的语言，是 CFL 的真子集（更重要的是，DFCL 是具有明确语法的 CFL 的真子集）。换句话说，每个 DCFL 都承认一个明确的上下文无关文法。
这意味着两个 DFCL 的并集不一定是 DFCL；我的直觉是，当面对两个 DFCL 的联合时，确定性下推自动机变得无法在替代状态转换之间进行选择；也就是说，虽然两个 DCFL 承认一个明确的语法，但它们的联合不需要。
CFL 在联合下是封闭的，这源于一个强大的结果，称为替换定理，粗略地说，给定一个上下文无关语言 L，我们可以用整个上下文无关语言替换 L 的字符串的每个符号，并且最终得到一个上下文无关的语言。（参见John Hopcroft、Jeff Ullman 和已故的 Rajeev Motwani 所著的语言、自动机和计算理论导论的第 7 章。）
于 2016-04-05T09:17:51.427 回答