当前课程知识点:软件理论基础 > 第四章 正则表示 > 4.4 正则表示和正则语言 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍第四章正则表示的第四节
正则表示和正则语言
上一节我们介绍了正则表示
正则表示里面
我们是用语文法和语义来定义的
正则表示它可以表示语言
从上一节里面可以看出
它表示的那些语言
实际上都是正则语言
那正则表示跟正则语言有什么关系呢
下面我们就可以有这么一个定理
正则表示的语言实际上就是正则语言
也就是说我们把正则表示的语言
放在一个集合里面
把正则语言放在一个集合里面
这两个集合它是相等的
它相等这是两个集合相等
实际上定理它分两个部分
第一个部分就是正则表示的语言这个集合
它是包含在正则语言这个集合
也就是说给了一个正则表示
它的语言L(r)一定是正则语言
那定理第二部分就是正则语言
它一定包含在正则表示的语言里面
也就是说你给了一个语言
是正则语言的话
那我一定能够找到一个正则表示
这个正则表示它的语言
就是你原来给定的正则语言
下面我们给出这个定理的证明
首先证明定理的第一部分
就是对任何的正则表示
它的语言一定是正则的
因为正则表示
我们前面的定义是归纳定义的
那我们要证明
这个正则表示的语言是正则语言的话
也是通过归纳来证明
对正则表示它的长度来做归纳
长度也就是最开始是基本的正则表示
就是空集、空串和单个字母
它们是不是正则表示呢
我们就看这三个正则表示
它对应的语言它的自动机NFA
是不是能画得出来
那对于空集来说它的NFA就是这种形式
它的语言就是空集
那对于空串它的NFA它的语言
所以空串也是正则语言
单个输入字母
这个正则表示
它的语言 它也是正则语言
那对于基本的正则表示的语言
我们证明了它是正则语言
接下来我们就对一般的来证明
假设r1、r2
它的语言L(r1)、L(r2)是正则语言
这是我们的归纳假设
那我们要证明什么呢
要证明r1+r2
r1连接r2
r1的*闭包
r1的括号
这些语言也要是正则的
那这些语言是不是正则的呢
那我们从正则表示的语义定义 我们知道
加连接 *闭包 这个括号
它的语言是这种形式
那这样表示的它的右边
是不是正则语言呢
这个就根据我们前面第二节里面的知识
如果是r1的语言 r2的语言是正则的话
那它对于余下这些运算
并运算 连接运算 *运算
它们都是正则的
那关于带括号的 跟不带括号的语言是一样的
也是正则的
到此我们这个定理的第一部分就证明了
下面证明定理的第二部分
也就是对用户的一个正则语言
一定存在一个正则表示
它对应的语言就是你给的正则语言
那既然是存在一个r正则表示
我们就相当于要把这个r要去找出来
你给定一个正则语言去找一个r
那这就是一个构造
这个构造我们有两种方法
一种是叫路径叠代法
另外一种是状态消除法
我们下面介绍路径叠代法的
它的构造事项
也就是假定给了一个正则语言
它对应一个DFA
那这个DFA的状态
我们用数字1、2到n来表示这些状态
并且假设它的初态是1
下面我们构造它的正则表示
正则表示由Rij(k)这样来表示正则表示
这个正则表示实际上
它是表示的从状态i到状态j
有一个标记为W的这里的路径
这个属于正则表示它的语言里面
并且这个路径上面
除了状态i、状态j两头的状态以外
中间状态的编号是都不大于k的
那然后我们对所有的i、j、k
它从1到n
我们经过下面这个公式叠加
进行计算这个Rij(k)
可以以此计算到Rij(n)
得到了Rij(n)
i,j是从1到n的
那我们就对每一个终态j
因为1是初态
我们就计算R1j(n)
对每一个终态j我们都得到R1j(n)
然后把它们进行加
这样得到的一个正则表示
就是我们需要的正则语言的
它的正则表示
也就是这个正则表示它得到的语言
就是你给定的正则语言
当然我们这个路径叠代法
是只做一个参考
有兴趣的同学
你们可以去看我们的参考书
我们下面着重介绍另外一种构造方法
叫状态消除法
状态消除法的思想是这样的
给了一个正则语言
我们假定它对应的就是NFA了
那对于NFA
我们第一步就是扩展这个NFA自动机
因为NFA这个自动机
它的变迁上面都是输入字母
我们现在扩展的
就把它的边上面的输入字母
改成为正则表示
这是第一步做自动机的扩展
第二步就是消除中间的一些状态
那我们消除中间的状态之后
那状态相连接的一些弧那也同时消除了
当我们消除了这些弧
这些弧上面它需要的一些信息
我们就把它修改到
这些状态的前驱的状态上面去
或者是它的后继状态上面去
以弥补消除的弧转移
下面我们通过一个例子来看看
这是我们给的一个通常的一个NFA
这里NFA它的输入字母abc是输入字母
我们现在要扩展为边上面都是正则表示
那得到的跟它等价的一个自动机
就是这个边上面
我们单个的a可以写成为
带黑体的一个a
这是它对应的a的正则表示
因为我是为了区分它
就是把它写黑一点
这个就是表示a的正则表示
这个边上面原来是
输入a 可以到的这个状态
输入b 可以到的这个状态
那我们现在改为a和b两个正则表示
它们做并之后得到的这么一个转移
c这一个边上转移
我就改为c这个正则表示它的转移
那这个自动机就是这个自动机的扩展
实际上它们的功能都是相同的
我们再看另外一个例子
这里输入字母有ab
我们现在把这个自动机进行扩展
把它的边改为正则表示
那分别为这是b 这是a加b
这是正则表示了
这是b加ε 这是a 这是a
这个自动机是这个自动机的扩展
它们的功能实际上都是一样的
那现在我们假如要对这个自动机
要消除状态q1
消除状态q1的时候
因为q1它作为桥梁 它有q0到qf
还有qf 它自己到qf这个转移
那像这些转移上面的信息
我们必须把它放在前期状态
和后继状态里面去
可以得到它转移的信息
我们就补到这个边上面
或后面这个边上面来
虽然刚才q1那个状态消除了
那它得到的这个自动机
跟原来表示的自动机
实际上信息完全是一样的
那对于这样表示的NFA
我们要给出它的正则表示 那就很简单了
b是一个自环
从q0到这里 通过这个路径连接
这里有一个自环
因此 我们就得出了
这个自动机表示的正则表示
就是可以写成这种形式了
根据我们这个构造过程
从原来的扩展自动机
然后消除状态 信息跟原来完全等同
所以我们得到的语言
是跟原来的语言完全相同的
也就是说这样给出的正则表示
它的语言跟我们之前表示的自动机的语言
完全是一样的
下面我们再看另外一个例子
这里给出的NFA
这个NFA它是一个扩展的NFA
每个边上面分别都表示的是正则表示
像abcde都是正则表示了
q是介入到qi和qj中间的一个状态
q它就可以作为一个桥梁
如果我们要消除状态q
这个边上面这些信息
就必须放在它的前驱状态
和它的后继状态上面来
那我们消除了这个状态q之后
大家看怎么经过q到qi呢
是首先输入a
然后有一个1的自环
再通过d到qi
那我们也就得到a1*d
再看qi怎么跟qj联系呢
是qi输入a1有一个自环
再然后经过b这个转移到qj
也就是a1*b
就是a1*b到qj
那其他的这个边标的
跟这完全是类似的
通过刚才介绍的
我们怎么消除中间状态
那对于一个NFA来说
我们除了初态 除了终态
最后消除得到的
这样形式的NFA
那对于这种形式的NFA
它的正则表示该怎么写呢
那首先对于qf终态而言
它应该有两个自环
一个是r4正则表示 是个自环
还有一个自环是r3、r1有一个自环
再然后变成了整个r2到qf
这是另外的一个自环
那我们就可以把这样的正则表示
就表示成为r4
这样的自环进行相加
然后r1它是一个自环到r2
进行连接得到了(10)
这样的一个正则表示
这就是我们得到的这种形式的自动机
它的正则表示
当然还有另外一种形式就是q0
也有两个自环
一个是r1 一个是r2、r4自环
然后r3
所以我们可以给出
另外一种形式的正则表示是它
因为我们这个通过状态消除
整个这个过程
实际上只是一些符号进行了一些修改
但是我们所有的
它的表示的形式是没有变化的
所以我们得到的语言
应该是跟原来的自动机
表示的语言是相同的
那这样我们通过状态消除法
也可以通过自动机得到正则表示
我们可以把状态消除法这一些过程
总结为这样的步骤
第一个步骤是我们消除
除了初态和终态以外的其它值状态
这是第一步
那如果初态不等于终态的时候
那实际上我们消除了
是剩下两个状态这样的自动机
对于这个自动机 它表示的正则表示
就有这种形式和这种形式
我们刚才介绍了
那如果是我们的终态和初态是相同的
实际上我们最后消除的
是这种形式的这个自动机
这个自动机它的正则表示就是R*
然后对每一个终态我们都这样做的话
我们得到的正则表示
把这些正则表示 把它进行相加
也就是求它们的并
这就得到我们这个自动机的
它对应的正则表示
下面我们看一个例子
这是一个NFA
它有四个状态
ab是输入字母
我们现在要把这个自动机
它对应的正则表示把它写出来
第一步就是扩展这个自动机
也就是把它的边上的输入字母
改成为正则表示
那我们现在把它的
这些每一个边上面对应的正则表示
都表示出来
它的终态有两个
一个是q2 一个是q3
我们现在要对每一个终态
消除 除掉初态以外的其它的状态
那下面对终态q2
我们就要要消除q1、q3
这样得到的自动机
就是为这种形式的NFA
那对于终态q3
我们消除q1、q2状态
得到的这个自动机 就是等于这个
那对于这两个自动机
我们现在写它们的正则表示
对这个正则表示 就很简单了
就可以表示r1
这个正则表示就可以用r2
这个写出来 这也不难
然后把这两个正则表示求它们的并
也就是两个正则表示相加
这样得到的r
r就是我们给的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
-习题--作业
-期中考试