55. 下推自动机与文法的等价性 - 1

计算理论是关于计算知识的有系统的整体，本是数学的一个研究领域，诞生于数理逻辑学家对计算本质的探索。这里的计算 (Computation) 并不是指纯粹的算术 (Calculation)，而是指一种以 “机械而有效的” 方式获取问题答案的过程。随着计算理论的发展最终促使了计算机的发明，计算理论的重心也从数学转到了计算机科学，而计算理论关心的核心问题是：计算（机）的基本能力和限制究竟是什么?这个问题中包含了两个内容，分别对应计算理论的两个研究方向：可计算性理论和计算复杂性理论, 而形式语言与自动机理论正是这两个重要的研究方向的理论基础。为了能够严谨的研究这种机械而有效的计算过程，我们需要严格定义的概念去描述它，需要严谨的计算模型去分析它。这个概念，其实就是已经被我们大家所熟知的“算法”(Algorithm)；而这些模型呢，就是我们将要在课程中主要学习的自动机理论，包括有穷自动机、下推自动机和图灵机等几种自动机装置，还包括一些与自动机形式上不相似但能力上却完全相同的模型，如正则表达式和文法等。