本课程介绍形式语言、自动机、文法、可判定性问题及计算复杂性，内容包括：基础知识；确定性有限自动机、非确定性有限自动机；正则表示与语言；正则语言与正则文法；正则语言的性质、Pumping引理及应用；上下文无关文法与语言；下推自动机、确定性下推自动机；上下文无关语言的性质、上下文无关语言的Pumping 引理及应用；图灵机；不可判定问题、NP问题等。
Overview
Syllabus
- 第一章 基础知识
- 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模型检测系统
- 期中考试
- 期末考试
Taught by
Guiming Luo
