context-free-grammar - 比较两个下推自动机

Question

我正在做一个项目，该项目需要我比较两个 PDA 以检查它们是否接受相同的语言。我已将这些 PDA 转换为相应的上下文无关语言，但我不知道如何进一步进行。

Answer 1

对于 CFL，相等性问题是不可判定的——您可以通过将 CFL 的普遍性问题简化为 HALT 问题（在图灵机上定义的一般问题）来证明，并且语言相等性几乎只是缩小了普遍性。

我不确定你在做什么类型的项目，但考虑使用 DCFL，如果它是一个“实际”问题，如果是学术问题/家庭作业，你应该做我上面提到的减少。

编辑：我不认为您可能只想将两种特定语言作为一次性事物进行比较。不幸的是，没有办法概括答案，因为问题可能仍然无法确定。