hi,小慕
课程

中国大学MOOC,为你提供一流的大学教育

认证学习
为你提供认证成绩和证书,以及AI高效学习服务
查看详情
大学

国家精品

认证学习

智慧课程

理学工学农学

计算机

经济管理

外语

音乐与艺术

心理学

文史哲法

医学与保健

教育教学

大学生竞赛

软件实训

人工智能

升学/择业

考研

期末突击

专升本

四六级

保研及论文

求职就业

专四专八

大学应试英语

期末资料

终身学习

有声课堂

兴趣技能

hi,小mooc
期末不挂科
形式语言与自动机理论
第12次开课
开课时间: 2025年03月03日 ~ 2025年06月14日
学时安排: 每周3-5小时
进行至第5周,共15周 已有 194 人参加
认证学习
认证成绩和证书
智能问答和解析
视频学习辅助
立即参加
课程详情
课程评价(75)
spContent=为了探索“计算”的本质,需要使用和构造什么样的计算模型,就是计算理论入门课程“形式语言与自动机理论”的主要内容。这些模型都是高度抽象化的计算装置,简单明确但功能强大,不但便于在理论分析中进行推导和证明,在很多实际问题中也有非常直接的应用。
为了探索“计算”的本质,需要使用和构造什么样的计算模型,就是计算理论入门课程“形式语言与自动机理论”的主要内容。这些模型都是高度抽象化的计算装置,简单明确但功能强大,不但便于在理论分析中进行推导和证明,在很多实际问题中也有非常直接的应用。
—— 课程团队
课程概述

计算理论是关于计算知识的有系统的整体,本是数学的一个研究领域,诞生于数理逻辑学家对计算本质的探索。这里的计算 (Computation) 并不是指纯粹的算术 (Calculation),而是指一种以 “机械而有效的” 方式获取问题答案的过程。随着计算理论的发展最终促使了计算机的发明,计算理论的重心也从数学转到了计算机科学,而计算理论关心的核心问题是:


计算(机)的基本能力和限制究竟是什么?


这个问题中包含了两个内容,分别对应计算理论的两个研究方向:可计算性理论计算复杂性理论, 而形式语言与自动机理论正是这两个重要的研究方向的理论基础。


为了能够严谨的研究这种机械而有效的计算过程,我们需要严格定义的概念去描述它,需要严谨的计算模型去分析它。这个概念,其实就是已经被我们大家所熟知的“算法”(Algorithm);而这些模型呢,就是我们将要在课程中主要学习的自动机理论,包括有穷自动机下推自动机图灵机等几种自动机装置,还包括一些与自动机形式上不相似但能力上却完全相同的模型,如正则表达式文法等。

授课目标

形式语言与自动机理论是计算机科学与技术领域基本的思想和方法,它不仅是编译技术的基础,在诸如计算机网络协议、文件搜索、数字电路设计和验证等诸多领域也发挥着重要作用。本课程旨在培养学生形式化描述和抽象思维能力,掌握“问题——形式化描述——自动化(计算机求解)”的思想和方法,并用于解决实际问题。


课程目标1:掌握正则语言与上下文无关语言等语言的形式化描述方法和识别方法,能够设计与之相应的文法和自动机,培养学生的抽象思维能力和逻辑思维能力。


课程目标2:分类研究语言的性质,培养针对不同语言的模型描述能力和模型计算能力(包括模型的等价变换、推理等),能够在更高的抽象层面处理复杂工程问题,进而尝试探讨问题的可计算性及其计算的复杂性。


课程目标3:掌握由问题到形式化描述、再到计算机化的问题求解方法,能够对实际问题进行抽象、形式化,构建计算模型,进而用计算机予以解决。

课程大纲

第1章 课程简介和基础知识

1.1 课程简介

1.2 基础知识

第1章 测试 基础知识

第2章 有穷自动机

2.1 确定的有穷自动机

2.2 非确定有穷自动机

2.3 带有空转移的非确定有穷自动机

第2章 测试 有穷自动机

第3章 正则表达式

3.1 正则表达式

3.2 自动机和正则表达式

3.3 正则表达式的代数定律

第3章 测试 正则表达式

第4章 正则语言的性质

4.1 正则语言的泵引理

4.2 正则语言的封闭性

4.3 - 4.4 正则语言的判定性质&自动机最小化

作业1

第4章 测试 正则语言的性质

第5章 上下文无关文法

5.1 上下文无关文法

5.2 - 5.3 语法分析树&文法和语言的歧义性

5.4 文法的化简和范式

第5章 上下文无关语言

第6章 下推自动机

6.1 下推自动机

6.2 下推自动机的语言

6.3 下推自动机与文法的等价性

6.4 确定型下推自动机

第6章 测试 下推自动机

第7章 上下文无关语言的性质

7.1 上下文无关语言的泵引理

7.2 上下文无关语言的封闭性

7.3 上下文无关语言的判定性质

第7章 测试 上下文无关语言的性质

第8章 图灵机与不可判定性

8.1 图灵机

8.2 不可判定性

第8章 测试 图灵机与不可判定性

展开全部
预备知识

集合论与图论

参考资料
  1. Introduction to Automata Theory, Languages, and Computation - 3rd Edition
  2. 作者 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
  3. 国内影印版
  4. 《自动机理论、语言和计算导论》(英文版·第3版)
  5. 机械工业出版社,ISBN: 9787111223924
  6. Introduction to the Theory of Computation
  7. 作者 Michael Sipser
  8. 中文译版《计算理论导引》机械工业出版社
  9. An Introduction to Formal Languages and Automata
  10. 作者 Peter Linz & Susan H. Rodger
哈尔滨工业大学
1 位授课老师
王春宇

王春宇

教授、博士生导师

推荐课程

【DeepSeek适用】小白玩转AI大模型应用开发

林粒粒

195人参加

小白玩转 Python 数据分析

林粒粒

75人参加
下载
下载

下载App