形式语言中的几个算法问题

　　摘要：引导学生关注学科前沿，培养学生理论研究兴趣是高校教学的重要任务之一。笔者尝试在编译原理的教学中，引导学生思考关于计算的基本问题：如何描述问题，是否有问题没有算法，等等。文章从编译原理课程中形式语言与自动机部分内容中，引出字符串匹配、自动机等价测试、上下文无关文法等价测试等问题，证明有不可计算的问题，介绍和分析相关算法，引导学生理论研究兴趣，拓展课程学习深度和广度。
　　关键词：问题；语言；算法；不可计算
　　
　　当今世界，计算机技术日新月异，渗透到日常生活中的每个领域。但是就目前技术而言，计算机的能力有没有极限？有没有计算机解决不了的问题？
　　在编译原理中，学习了形式语言、有限自动机(FA)、上下文无关文法(CFG)。这些知识只是形式语言与自动机理论的基础部分。然而，这些理论是富有启发性的，仅仅利用这些知识，我们就可以理解为什么有很多问题是没有算法的，也可以给出相关的没有算法的问题举例。
　　自动机理论是计算理论的一部分。其内容主要包括有限自动机、下推自动机(等价于上下文无关文法)、图灵机。前两者可以视为图灵机的简化，图灵机就是算法的定义。目前计算机能做到的事情，图灵机都能做到。我们知道有限自动机的能力弱于下推自动机，下推自动机的能力弱于图灵机。事实上，图灵机的能力也是有限的。
　　基础的自动机理论虽然简单，但它无论是在计算机领域还是在其它诸多领域都有很重要的应用，而且目前也还有很多学者在从事自动机的理论研究。
　　自动机理论是由应用数学一代宗师——冯•诺伊曼等人创立起来的。利用自动机理论，人们设计了很多强有力的算法。例如，对于字符串匹配问题[1-2] (设有两个字