当前课程知识点：软件理论基础 > 第四章 正则表示 > 4.1 单一终结状态的NFA > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
我是清华大学的教师 罗贵明
今天我们讲述的内容是正则表示
内容包括单一终态的NFA
正则语言的运算性质 正则表示和语言
正则表示和正则语言 正则语言的同态
最后我们介绍正则表示的代数律
首先我们介绍单一终态的NFA
我们在之前介绍了自动机DFA和NFA
它们都是一个五元组
你像NFA 它里面有状态
有输入字母 有状态转移函数
有初始状态
最后是终态的一个子集
终态它是一个集合
它可以有多个状态
也可以没有状态
任何一个NFA
现在它实际上
可以等价只有一个终态的NFA
我们看这样一个例子
这个NFA它有两个终态
得到了一个等价的NFA
这个NFA增加了一个终态
那就把原来的两个终态改为非终态
那增加了这么一个ε转移
这样得到了只有一个终态的NFA
跟两个终态的NFA来比
它们实际上是等价的
对一般的情形
这个NFA可能有多个终态
那我们只要增加一个新的状态
再把原来的终态改为非终态的时候
添加ε转移
这样得到的NFA只有一个终态
但是它们的语言
跟这个NFA的语言是相等的
所以这两个NFA它是等价的
但是这里只有一个终态
这个NFA它没有终态
我们强调是任何一个NFA都等价
只有一个终态的NFA
那它没有终态
那我们可以这样做
增添一个终态
增添一个终态 但是原来的自动机
到这里就没有路径
这个自动机跟原来的自动机
它还是等价的
但是它有一个终态
那这个情形说明任何一个NFA
都等价只有一个终态的NFA
这节内容就到此
谢谢大家
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试
