《有限自动机理论》教学大纲

一、教学目的

计算理论是研究使用计算机解决计算问题的数学理论，是计算机科学与技术学科的核心理论。

计算理论包括自动机理论、可计算性理论和计算的复杂性理论。研究生阶段，有三门课程与之分别对应：《有限自动机理论》、《可计算理论》和《算法分析与设计》。

《有限自动机理论》论述计算的数学模型的定义和性质，这些模型在计算机科学的若干应用领域中起着重要作用，其应用范围已被扩展到生物工程、自动控制系统、图像处理与模式识别等许多领域。

《有限自动机理论》是学习计算理论的良好起点，不仅能提高学生的感知能力，同时也能提高学生思维的敏捷性，使学生考虑问题仔细、严谨、周密、有理有据；可以使学生由具体形象思维逐渐向抽象思维过渡，从而促进逻辑思维和创造力的发展；可以使学生的逻辑思维过程清晰化、条理化、整体化，有利于培养学生的计算表达能力，提高推理、判断、分析问题和解决问题的能力。

通过本课程的学习，使学生了解有限自动机理论的发展历程、文法的定义、有限状态自动机的定义、下推自动机的定义、图灵机的定义；掌握推导的方法、语言的产生方法、语言封闭性的证明方法、构造有限状态自动机的方法、下推自动机的构造方法、图灵机的构造技术、图灵机的计算能力。

《有限自动机理论》课程是培养计算思维能力的重要环节，不仅能提高学生的感知能力，同时也能提高学生思维的敏捷性，使学生考虑问题仔细、严谨、周密、有理有据；可以使学生由具体形象思维逐渐向抽象思维过渡，从而促进逻辑思维和创造力的发展；可以使学生的逻辑思维过程清晰化、条理化、整体化，有利于培养学生的计算表达能力，提高推理、判断、分析问题和解决问题的能力。

二、教学内容与要求

总学时：40学时

第一章 基础知识（3学时）

1. 本章教学内容

1.1 集合及其运算（0.5学时）

1.2 关系（0.5学时）

1.3 证明和证明的方法（0.5学时）

1.4 图与树（0.5学时）

1.5 语言（0.5学时）

1.6 常用术语（0.5学时）

1.7 形式语言与自动机的发展（自学）

2. 本章教学要求

通过本章课程的学习，要求学生理解集合及其运算、关系、证明和证明的方法以及图与树的概念；掌握形式语言与自动机理论中的相关术语；了解形式语言与自动机的发展。

3. 本章教学重点

形式语言与自动机理论中的相关术语。

4. 本章教学难点：

语言的形式化描述方法。

本章计划作业1次：语言的形式化描述。

第二章 形式语言简介（10学时）

1. 本章教学内容

2.1 例子语言（1学时）

2.2 文法和语言的关系（1学时）

2.3 Chomsky对文法的分类（0.5学时）

2.4 文法产生语言（1.5学时）

2.5 推导树（0.5学时）

2.6 空串定理（0.5学时）

2.7 消除左递归（0.5学时）

2.8 上下文无关文法的另一种表示（0.5学时）

2.9 语言之间的运算及运算的封闭性（3学时）

2.10 正则表达式和正则集（1学时）

2. 本章教学要求

通过本章课程的学习，要求掌握文法的定义、分类的原则，重点掌握文法的构造方法，语言运算的有效封闭性。 本章内容可以应用到高级程序设计语言语法单位的形式化描述。

3. 本章教学重点

文法的构造方法。

4. 本章教学难点

语言运算的有效封闭性的证明。

计划作业2次：文法的构造。

第三章 有限状态自动机（10学时）

1. 本章教学内容

3.1 有限状态自动机（0.5学时）

3.2 确定的有限状态自动机接收的语言（1.5学时）

3.3 确定的有限状态自动机接收语言的例子（2.5学时）

3.4 不确定的有限状态自动机（2.5学时）

3.5 带有ε动作的有限状态自动机（1.5学时）

3.6 有限状态自动机的一些变形（0.5学时）

3.7 有限状态接收机的存储技术（0.5学时）

3.8 有限状态自动机应用实例（0.5学时）

2. 本章教学要求

通过本章课程的学习，要求学生掌握有限状态自动机的定义、分类；重点掌握有限状态自动机的构造方法；DFA与NFA的转化。本章内容可以应用到各种系统的状态（转换）图，如词法分析状态图、操作系统进程间状态图、电路状态图等。

3. 本章教学重点

有限状态自动机的构造方法；

4. 本章教学难点

带有ε动作的有限状态自动机与一般有限状态自动机的转化。

计划课堂作业1次：简单DFA和NFA的构造。

计划课后作业1次：复杂DFA和NFA的构造。

本章内容可以应用到各种系统的状态（转换）图，如词法分析状态图、操作系统进程间状态图、电路状态图等。

第四章 正则语言（0学时，自学）

1. 本章内容

4.1 正则语言与有限状态自动机

4.2 正则语言的泵浦引理

4.3 正则语言对运算的封闭性

4.4 正则语言类中的判定算法

4.5 正则语言应用实例

第五章 下推自动机（7学时）

1. 本章教学内容

5.1 下推自动机（3学时）

5.2 上下文无关文法和范式（1.5学时）

5.3 下推自动机与上下文无关语言（2学时）

5.4 下推自动机应用实例（0.5学时）

2. 本章教学要求

通过本章课程的学习，要求学生掌握下推自动机的定义、分类。重点掌握下推自动机的构造方法和上下文无关文法的转换方法。本章内容可以应用到表驱动的系统，如复杂算术表达式的计算等。

3. 本章教学重点

下推自动机的构造方法

4. 本章教学难点

各类下推自动机的转化方法。

计划课后作业1次：下推自动机的构造。

第六章 图灵机（10学时）

1. 本章教学内容

6.1 图灵机的基本模型（0.5学时）

6.2 图灵机作为非负整数函数计算模型（3学时）

6.3 图灵机的构造技术（4学时）

6.4 图灵机变形（0.5学时）

6.5 通用图灵机（0.5学时）

6.6 图灵机与短语结构语言（0.5学时）

6.7 线性有界的图灵机与上下文相关语言（0.5学时）

6.8 图灵机应用实例（0.5学时）

2. 本章教学要求

通过本章课程的学习，要求学生掌握图灵机的定义、分类。重点掌握图灵机的构造技术，包括移动技术、子程序技术和多道技术。

3. 本章教学重点

图灵机的构造技术。

4. 本章教学难点

图灵机的子程序技术和多道技术。

计划课后作业1次：子程序技术、多道技术构造图灵机。

第七章 量子自动机（0学时，自学）

1. 本章内容

7.1 量子有限自动机

7.2 量子下推自动机

7.3 量子图灵机

撰写人：陈文宇

审核人：杨国武