软件理论基础

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

开设学校：清华大学；学科：计算机、

软件理论基础课程：前往报名学习

软件理论基础视频慕课课程简介：

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

前往报名学习

软件理论基础课程列表：

{{'上次学习:'+learn_list['THU08091000723']['last_leaf_name']}}

第一章基础知识

-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的构造实例

-第八章 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年在中国科学院数学与系统科学研究院获得博士学位。后加入清华大学数学科学系任教。现为清华大学软件学院教授。研究领域包括电路建模和测试，系统辩识，自适应控制与信号跟踪，智能建模，软件的形式化方法和形式化验证等。

也许你还感兴趣的课程:

© 柠檬大学-慕课导航课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。