软件理论基础

本课程介绍形式语言、自动机、文法、可判定性问题及计算复杂性。

播放:19975次,课程ID:4232189

软件理论基础课程简介:前往报名学习

软件理论基础课程简介:

本课程介绍形式语言、自动机、文法、可判定性问题及计算复杂性。

前往报名学习

软件理论基础课程目录:

第一章 基础知识

--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模型检测系统

考试一:期中

期末考试

软件理论基础授课教师:

罗贵明-教授-清华大学-软件学院

罗贵明于1988年在中国科学技术大学获得硕士学位,1992年在中国科学院数学与系统科学研究院获得博士学位。后加入清华大学数学科学系任教。现为清华大学软件学院教授。研究领域包括电路建模和测试,系统辩识,自适应控制与信号跟踪,智能建模,软件的形式化方法和形式化验证等。

© 柠檬大学 2020