证明CFG等价性问题的不可判定性和图灵可识别性质

本文档主要探讨了形式语言和自动机理论中的几个关键概念，特别是与判定性和识别性相关的证明。首先，章节5.1证明了等价上下文无关文法（EQCFG）问题是不可判定的，通过展示ALLCFG（所有上下文无关文法的集合）可以归约为EQCFG。由于ALLCFG已知是不可判定的，因此推导出EQCFG同样不可判定。 接着，在5.2节中，证明了EQCFG问题的补集是图灵可识别的。通过设计一个图灵机F，该机对输入的两个上下文无关文法G和H进行检查，如果G和H都能生成相同的字符串w或都不能生成w，机器F将接受输入。这表明EQCFG的补集是可以被识别的，但不是可判定的。 5.4节讨论了一个例子，说明即使语言A与正则语言B的并集（A∪B，用m表示并集操作）是可计算的，并不意味着A本身是正则的。举出了非正则语言A={0^n1^n|n>0}和正则语言B={0}，证明了A与B的并集A∪B是可计算的，但A仍然是非正则的。 5.5节通过反证法证明了自动机决定问题（ATM）不能映射规约到停机问题的等价形式（ETM）。如果可以，那么ETM的补集也将是图灵可识别的，与停机问题的补集不是图灵可识别的事实相矛盾。 5.7节指出，如果一个问题A是图灵可识别的，并且可以通过映射规约转化为某个图灵可判定问题B的补集，那么A本身也是可判定的。这是因为B的补集是图灵可识别的，而B也是图灵可识别的，所以A可以通过B判定。 最后，5.8节提出了解决方法，涉及如何在构建与图灵机M和输入w对应的骨牌系统时添加特定类型的骨牌，以解决与图灵可识别问题相关的映射规约问题。这部分内容没有给出具体的证明，但暗示了所有图灵可识别的问题都可以映射规约到自动机决定问题（ATM）。 这些内容深入探讨了形式语言理论中的复杂概念，包括判定性、识别性和规约性，以及它们在上下文无关文法、图灵可识别问题和自动机理论中的应用。这些理论基础对于理解计算理论和复杂性理论至关重要。