当前课程知识点:软件理论基础 >  第四章 正则表示 >  4.4 正则表示和正则语言 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

Video

下一节:Video

返回《软件理论基础》慕课在线视频列表

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

-习题--作业

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

-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

-习题--作业

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

-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

-习题--作业

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

-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

-习题--作业

第十二章 Turing机

-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

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

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