慕课-英华学堂

软件理论基础

课程类型：选修课

主讲教师：罗贵明

课程来源：清华大学

建议学分：3.00分

课程编码：xtzx0481

课程介绍

课程目录

教师团队

第一章基础知识

s 1.1 概要（6分钟）

s 1.2 数学基础（14分钟）

s 1.3 图（6分钟）

s 1.4 证明方法（15分钟）

s 1.5 语言基础（12分钟）

s 1.6 语言运算（10分钟）

第二章确定有限自动机

s 2.1 确定有限自动机的概念（7分钟）

s 2.2 确定有限自动机的定义（8分钟）

s 2.3 扩展转移函数（10分钟）

s 2.4 正则语言（21分钟）

s 2.5 DFA构造（26分钟）

第三章非确定有限自动机

s 3.1 非确定有限自动机的概念（8分钟）

s 3.2 e转移（8分钟）

s 3.3 非确定有限自动机的定义（13分钟）

s 3.4 扩展转移函数（8分钟）

s 3.5 等价性证明（27分钟）

s 3.6 文本搜索（17分钟）

第四章正则表示

s 4.1 单一终结状态的NFA （3分钟）

s 4.2 正则语言的运算性质（13分钟）

s 4.3 正则表示和语言（20分钟）

s 4.4 正则表示和正则语言（20分钟）

s 4.5 正则语言的同态（16分钟）

s 4.6 正则表示的代数定律（9分钟）

第五章正则文法和正则语言

s 5.1 文法（31分钟）

s 5.2 线性文法（7分钟）

s 5.3 正则文法与正则语言（20分钟）

s 5.4 自动机的积（20分钟）

第六章正则语言的性质与DFA优化

s 6.1 基本问题（12分钟）

s 6.2 泵引理（11分钟）

s 6.3 非正则语言的判定 1 （15分钟）

s 6.4 非正则语言的判定 2 （15分钟）

s 6.5 DFA的优化 1 （20分钟）

s 6.6 DFA的优化 2 （14分钟）

第七章上下文无关文法和推导

s 7.1 上下文无关文法（6分钟）

s 7.2 规约和推导（16分钟）

s 7.3 语法分析树（10分钟）

s 7.4 规约、推导和语法分析树之间的关系（10分钟）

s 7.5 上下文无关语言（6分钟）

第八章 CFG的应用与文法的二义性

s 8.1 CFG的应用（9分钟）

s 8.2 CFG的转化（10分钟）

s 8.3 文法二义性（7分钟）

s 8.4 二义性的消除方法（11分钟）

s 8.5 CFG的构造方法（10分钟）

s 8.6 CFG的构造实例（18分钟）

第九章下推自动机

s 9.1 PDA介绍（13分钟）

s 9.2 PDA的定义（26分钟）

s 9.3 PDA的即时描述（9分钟）

s 9.4 PDA的语言（14分钟）

s 9.5 PDA与CFG的关系（24分钟）

第十章下推自动机与CFG化简规范

s 10.1 确定下推自动机（9分钟）

s 10.2 DPDA与其他语言的关系（6分钟）

s 10.3 终态型DPDA和空栈型DPDA （21分钟）

s 10.4 消除无用符号（17分钟）

s 10.5 消除e产生式（6分钟）

s 10.6 消除单一产生式（6分钟）

s 10.7 CFG的化简与Chomsky范式（10分钟）

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

s 11.1 CFL的必要条件（12分钟）

s 11.2 CFL的Pumping引理（15分钟）

s 11.3 CFL的闭运算性质（11分钟）

s 11.4 CFL的同态性质（12分钟）

s 11.5 CFL的交运算（14分钟）

s 11.6 CFL的判定性质（14分钟）

第十二章 Turing机

s 12.1 图灵机的介绍（16分钟）

s 12.2 图灵机的定义（14分钟）

s 12.3 图灵机的即时描述（13分钟）

s 12.4 图灵机的计算（9分钟）

s 12.5 图灵机的编程技术（7分钟）

第十三章图灵机的扩展

s 13.1 Turing理论（8分钟）

s 13.2 图灵机带的扩展（12分钟）

s 13.3 图灵机移动的扩展（14分钟）

s 13.4 受限图灵机（10分钟）

s 13.5 图灵机与其他自动机（12分钟）

第十四章不可判定问题

s 14.1 图灵机编码（11分钟）

s 14.2 对角线语言与通用语言（10分钟）

s 14.3 图灵机语言的性质（10分钟）

s 14.4 判定问题和语言（17分钟）

s 14.5 计算复杂性问题（9分钟）

第十五章自动机及应用

s 15.1 时间自动机（15分钟）

s 15.2 Buchi自动机（6分钟）

s 15.3 软件形式化验证（7分钟）

s 15.4 模型检测方法（11分钟）

s 15.5 M3C模型检测系统（7分钟）