比较两个按下自动机

Question

我正在研究一个项目，要求我比较两个PDA来检查他们是否接受相同的语言。我已经将这些PDA转换为其相应的上下文无关语言，但我不知道如何进一步处理。

Answer 1

对于CFL而言，平等的问题是不可判定的 - 您可以通过将CFL的普遍性问题归结为HALT问题（通过图灵机定义的一般问题）来展示，而语言平等几乎只限于普遍性。

我不确定你在做什么样的项目，但考虑使用DCFL，如果它是一个“实际”问题，并且如果它是学术问题/家庭作业，你应该做我提到的更高的缩小。

编辑：我没有考虑过，你可能只是想比较两个特定的languanges作为一次性的事情。不幸的是，没有办法一概而论，因为问题可能仍然是不可判定的。