当前课程知识点:软件理论基础 >  第四章 正则表示 >  4.6 正则表示的代数定律 >  Video

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

Video在线视频

Video

下一节:Video

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

Video课程教案、知识点、字幕

欢迎同学们来到《软件理论基础》的MOOC课堂

现在介绍正则表示的第六节

也就是正则表示的代数定律

上一节里面我们介绍了正则表示

正则表示它是有一些符号

加一些运算构成的

这些运算里面有加这个符号

有连接符号 有*运算符号等等

那有了这些符号

它就有了运算的一些规律了

就是我们通常关心的

它的交换律怎么样

结合律怎么样等等

这些是我们要介绍的

正则表示的一些代数律

我们通过这些代数律也可以对正则表示

得到它们的一些化解

那下面我们看正则表示的

交换律和结合律

下面我们讨论字符

都是正则表示

也就是LMN等等 都是正则表示

大家不要看这是语言 这是正则表示

首先我们看加这个运算

假设L和M都是正则表示

它们做加之后 得到的是正则表示

这个正则表示 它就等于M+L

这是另外的一个正则表示

实际上它的L和M交换了

也就是说正则表示在加这个里面

它是对交换率是成立的

这个等号实际上是表示

这是两个不同的正则表示

它们只要是语言相同

就可以用等号写

实际上这个“等”是一个“等价”

这两个正则表示是等价的

那下面给的等号

都是等价这种意向 是相等的

那么我们再看LMN是三个正则表示

(L+M)再加N

它跟L加上(M+N)

这个正则表示 它们是相等的

那这说明加这个运算

它对正则表示来说是满足结合律的

我们再看连接运算

LM连接括号 再连接N

跟L连接M 连接N 括号

它们是相等的

这就说明正则表示

它对连接运算来说

它是满足结合律的

那要证明这些性质

我们说了这些相等

实际上是它们的语言相等

以及说要证明这个正则表示

和这个正则表示

它代表的语言 它们是相等的话

那它这个等号就相等

所以大家验证可以通过语言去验证的

这是交换律和结合律

我们看加是对

字母表示对加来说

它是满足交换律的

连接运算就没有了

连接运算L连接M

在一般情况下

它是不可能与M连接L是相等的

第二个是单位元和零元

空集加L这两个正则表示相加

它跟L是相等的

那这就说明这个空集

对正则表示加来说 它是单位元

空串连接L 跟L连接空串

它们是相等的 都等于L

这就说明空串

对连接运算来说是单位元

那空集对连接运算来说

空集连接L 跟L连接空集 都等于空集

这就说明这个空集这个正则表示

它在连接运算里面 它是个零元

这些性质也可以通过语言来验证

分配律

因为我们有连接运算 有加运算

这两个运算在一块

我们就可以讨论它们的分配律

下面我们有L连接(M+N)

它跟L连接M、L连接N

它们相加 这是相等的

这个也叫做结合律

因为正则表示它的连接运算

不满足结合律

所以它这里还有一个右结合律

这个分配律

我们要验证它 也是通过语言相等来验证

那通过分配律

我们可以对一些正则表示进行化解

等幂律

两个正则表示 相同的正则表示L+L

它就是等于L

这个通过语言很容易验证

关于闭包我们也有下面这些性质

任何一个正则表示

它的*闭包再做*闭包

跟它之前一样 是相等的

空集的*闭包是等于空串

空串的*闭包也等于空串

正则表示的正闭包

我们是这样定义的

它是至少含一个正则表示

也就是L连接L* 或者L*连接L

还有L*就等于L正加上空串

最后再介绍一个定义

这个定义是正则表示加一个问号

加一个问号

这个是表示0个或者1个正则表示

其他的我们都可以用语言来验证

在这一节里面

我们介绍了正则表示的

它的一些代数律或者是一些运算律

我们通过这些运算律

来对正则表示进行化解

那在这一章里面来看

我们介绍了正则语言的一些性质

特别是它的运算性质

我们得到了正则语言关于并

关于连接 反转 *运算 补运算

还有同态 逆同态等等

它都是封闭的

在这些关系下面

正则语言依然保持是正则语言

另外我们还介绍了正则表示

正则表示的定义

我们是通过文法和语义两方面定义的

而且我们定义是通过归纳的形式

这种新的定义方法

大家通过这里进行理解

我们以后还多次要利用这种定义方法

来定义其它的一些关系

因为这种定义非常简单明了

我们并且证明了正则表示

它表示的语言就是正则语言

今天的课就讲到这里

好 谢谢大家

软件理论基础课程列表:

第一章 基础知识

-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笔记与讨论

也许你还感兴趣的课程:

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