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