课程简介
本课程介绍形式语言、自动机、文法、可判定性问题及计算复杂性，内容包括：基础知识；确定性有限自动机、非确定性有限自动机；正则表示与语言；正则语言与正则文法；正则语言的性质、Pumping引理及应用；上下文无关文法与语言；下推自动机、确定性下推自动机；上下文无关语言的性质、上下文无关语言的Pumping 引理及应用；图灵机；不可判定问题、NP问题等。
课程大纲
第一章 基础知识
1.1 概要
1.2 数学基础
1.3 图
1.4 证明方法
1.5 语言基础
1.6 语言运算
第二章 确定有限自动机
2.1 确定有限自动机的概念
2.2 确定有限自动机的定义
2.3 扩展转移函数
2.4 正则语言
2.5 DFA构造
第三章 非确定有限自动机
3.1 非确定有限自动机的概念
3.2 e转移
3.3 非确定有限自动机的定义
3.4 扩展转移函数
3.5 等价性证明
3.6 文本搜索
第四章 正则表示
4.1 单一终结状态的NFA
4.2 正则语言的运算性质
4.3 正则表示和语言
4.4 正则表示和正则语言
4.5 正则语言的同态
4.6 正则表示的代数定律
第五章 正则文法和正则语言
5.1 文法
5.2 线性文法
5.3 正则文法与正则语言
5.4 自动机的积
第六章 正则语言的性质与DFA优化
6.1 基本问题
6.2 泵引理
6.3 非正则语言的判定 1
6.4 非正则语言的判定 2
6.5 DFA的优化 1
6.6 DFA的优化 2
第七章 上下文无关文法和推导
7.1 上下文无关文法
7.2 规约和推导
7.3 语法分析树
7.4 规约、推导和语法分析树之间的关系
7.5 上下文无关语言
第八章 CFG的应用与文法的二义性
8.1 CFG的应用
8.2 CFG的转化
8.3 文法二义性
8.4 二义性的消除方法
8.5 CFG的构造方法
8.6 CFG的构造实例
第九章 下推自动机
9.1 PDA介绍
9.2 PDA的定义
9.3 PDA的即时描述
9.4 PDA的语言
9.5 PDA与CFG的关系
第十章 下推自动机与CFG化简规范
10.1 确定下推自动机
10.2 DPDA与其他语言的关系
10.3 终态型DPDA和空栈型DPDA
10.4 消除无用符号
10.5 消除e产生式
10.6 消除单一产生式
10.7 CFG的化简与Chomsky范式
第十一章 上下文无关语言的性质
11.1 CFL的必要条件
11.2 CFL的Pumping引理
11.3 CFL的闭运算性质
11.4 CFL的同态性质
11.5 CFL的交运算
11.6 CFL的判定性质
第十二章 Turing机
12.1 图灵机的介绍
12.2 图灵机的定义
12.3 图灵机的即时描述
12.4 图灵机的计算
12.5 图灵机的编程技术
第十三章 图灵机的扩展
13.1 Turing理论
13.2 图灵机带的扩展
13.3 图灵机移动的扩展
13.4 受限图灵机
13.5 图灵机与其他自动机
第十四章 不可判定问题
14.1 图灵机编码
14.2 对角线语言与通用语言
14.3 图灵机语言的性质
14.4 判定问题和语言
14.5 计算复杂性问题
第十五章 自动机及应用
15.1 时间自动机
15.2 Buchi自动机
15.3 软件形式化验证
15.4 模型检测方法
15.5 M3C模型检测系统
期中考试
期末考试
1.1 概要
1.2 数学基础
1.3 图
1.4 证明方法
1.5 语言基础
1.6 语言运算
第二章 确定有限自动机
2.1 确定有限自动机的概念
2.2 确定有限自动机的定义
2.3 扩展转移函数
2.4 正则语言
2.5 DFA构造
第三章 非确定有限自动机
3.1 非确定有限自动机的概念
3.2 e转移
3.3 非确定有限自动机的定义
3.4 扩展转移函数
3.5 等价性证明
3.6 文本搜索
第四章 正则表示
4.1 单一终结状态的NFA
4.2 正则语言的运算性质
4.3 正则表示和语言
4.4 正则表示和正则语言
4.5 正则语言的同态
4.6 正则表示的代数定律
第五章 正则文法和正则语言
5.1 文法
5.2 线性文法
5.3 正则文法与正则语言
5.4 自动机的积
第六章 正则语言的性质与DFA优化
6.1 基本问题
6.2 泵引理
6.3 非正则语言的判定 1
6.4 非正则语言的判定 2
6.5 DFA的优化 1
6.6 DFA的优化 2
第七章 上下文无关文法和推导
7.1 上下文无关文法
7.2 规约和推导
7.3 语法分析树
7.4 规约、推导和语法分析树之间的关系
7.5 上下文无关语言
第八章 CFG的应用与文法的二义性
8.1 CFG的应用
8.2 CFG的转化
8.3 文法二义性
8.4 二义性的消除方法
8.5 CFG的构造方法
8.6 CFG的构造实例
第九章 下推自动机
9.1 PDA介绍
9.2 PDA的定义
9.3 PDA的即时描述
9.4 PDA的语言
9.5 PDA与CFG的关系
第十章 下推自动机与CFG化简规范
10.1 确定下推自动机
10.2 DPDA与其他语言的关系
10.3 终态型DPDA和空栈型DPDA
10.4 消除无用符号
10.5 消除e产生式
10.6 消除单一产生式
10.7 CFG的化简与Chomsky范式
第十一章 上下文无关语言的性质
11.1 CFL的必要条件
11.2 CFL的Pumping引理
11.3 CFL的闭运算性质
11.4 CFL的同态性质
11.5 CFL的交运算
11.6 CFL的判定性质
第十二章 Turing机
12.1 图灵机的介绍
12.2 图灵机的定义
12.3 图灵机的即时描述
12.4 图灵机的计算
12.5 图灵机的编程技术
第十三章 图灵机的扩展
13.1 Turing理论
13.2 图灵机带的扩展
13.3 图灵机移动的扩展
13.4 受限图灵机
13.5 图灵机与其他自动机
第十四章 不可判定问题
14.1 图灵机编码
14.2 对角线语言与通用语言
14.3 图灵机语言的性质
14.4 判定问题和语言
14.5 计算复杂性问题
第十五章 自动机及应用
15.1 时间自动机
15.2 Buchi自动机
15.3 软件形式化验证
15.4 模型检测方法
15.5 M3C模型检测系统
期中考试
期末考试