当前课程知识点:软件理论基础 >  第六章 正则语言的性质与DFA优化 >  6.1 基本问题 >  Video

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

Video在线视频

Video

下一节:Video

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

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

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

我是清华大学的教师罗贵明

今天讲述第六章

正则语言的判定性质

内容包括

基本问题 泵引理 非正则语言的判定

首先我们讲第一节 基本问题

那这里面我们介绍的

是字符串与语言之间的关系

首先 我们给了一个语言

就是正则语言和一个字符串W

那如何判定W∈L

因为这个语言L是正则语言

那它就有一个DFA来解释它

那么假设这个DFA是M

那也就是说判定这个W

是不是被这个自动机M接受

如果在这个自动机里面

从初态到终态有一条路径W

那这时候W就是这个L

如果在这个自动机里面没有这条路径

那这个W就不是这个L

那如何去实现这类算法呢

这跟我们的正则语言的表示形式有关系

首先我们假设这个正则语言是DFA表示的

那我们判定算法从初态开始

输入这个字符串

如果从初态到达某一个终态

那这个语言就接受

这个字符串W

否则这个W就不被接受了

这个算法的复杂度

假设W字符串它的长度为n

那上述这个判定算法的复杂度就是O(n)的

也就是现已复杂度

如果这个语言是用NFA表示的

那我们就要讲这个NFA转化为等价的DFA

然后再执行上面的步骤

或者也可以直接来模拟这个字符串W

那这个算法的复杂度

那跟刚才就有些不一样

因为它有一个转化的问题

那如果这个自动机NFA的状态数是s

那这个算法的复杂度是O(ns2)

如果这个正则语言

是由正则表示来给出的

那我们需要把这个正则表示

转化为等价的NFA

然后再按上面的步骤再来执行

这是我们判定一个字符串

属不属于一个语言

下面我们再看第二个问题

就是正则语言是不是空的

也就是给了一个正则语言L

怎样判定这个L它是空语言

我们的方法就是给了这个语言的DFA M

我们判定这个自动机

是不是由初态到终态的一个路径

如果这个自动机有这样的路径

这个语言肯定是不为空的

那如果是这个自动机没有这样的路径

那这个语言它肯定为空的

如果这个自动机是DFA来表示的

那就看

这个自动机的某一个终态是不是可达的

如果这个自动机有某一个终态是可达的

那这个自动机的语言肯定是不为空的

判定算法

我们可以用递归的方法来实现

首先初态是可达的

然后再看状态q

如果状态q是可达的

则对某一个输入字母

如果q是可以转化为p的

则p也是可达的

我们可以根据这种算法

一直从初态慢慢的书写

到最后能不能找到一个终态

如果能够找到一个终态

那这个语言它就是不是空的

这个算法的复杂度就是一个O(n2)

如果刚才的语言是用正则表示来给的

那我们就用这个递归的方式

来判定这个语言是不是空的

这个算法我们根据正则表示

因为正则表示它是递归定义

它有空集 空串和单个字母a

是我们正则表示的基础

那我们首先看这三个正则表示

它们对应的语言

空集对应的语言它是为空的

另外两个表示的语言它是不为空的

所以我们看

对这种情况它是空语言

下面的归纳的情况

加的情况

如果一个正则表示

可以表示为R1加R2

那R这个语言为空

当且仅当R1和R2它对应的语言

全部都为空的

如果这个正则表示R是R1连接R2

那R这个语言为空

它当且仅当R1或者R2

至少有一个是为空的

那如果这个语言是为R*表示的

这个正则表示的语言它肯定是不为空的

那对R等于(R1)

R它对应的语言为空

当且仅当R1它对应的语言是为空的

这个算法的复杂度更简单

大家可以看

它的实际上就是我们正则表示的

它的符号度

这个复杂度也是O(n)

下面我们再看第三个问题

就是正则语言它们之间的相等

也就是给了两个正则语言L1和L2

如何判定L1等于L2

那我们这个判定算法你可以检验

按集合里面那个检验方法

看这个集合是不是为空的

或者也可以看L1是不是包含L2

L2是不是包含L1

那我们也可以采用这样的判定方法

我们把两个正则语言可以转化为DFA

然后证明这两个DFA是不是等价的

那这个转化的方法可以这样做

首先 对两个DFA

看它们命名有没有重名的

如果有重名的 我们就修改一下

这个对我们DFA没有任何影响的

再然后把两个DFA做并

构造一个新的自动机

对这个新的自动机M用填表算法

证明这原来两个自动机的初态

是不是不可区分的

如果是不可区分的话

那这两个语言是等价的

这种方法在我们下一次课

我们还介绍

也就是在我们的DFA的优化里面

我们要采用这种方法来做DFA的优化

这个算法的复杂度 它是O(n4)

我们可以适当的设计

这个算法的数据结构

将它的复杂度降为n的平方

下面我们还是补充说说这个

两个语言的等价问题

实际上在我们语言的设计里面

或者是在工程的设计里面应用了很多

我们工程的需求和我们设计的这个语言

是不是两个完全是一致的

实际上这就是我们的语言的等价问题

也就是我们的一致性问题

下面我们再看无限的正则语言

也就是给了一个正则语言L

我们判定这个L是不是无限的

那我们的方法就是看

接受这个语言L的DFA

判定它这个自动机初态到终态之间

是不是有一个环路

如果这个自动机

从初态到终态这个路径当中

有这么一个环路

那它这个语言肯定是无限的

那如果是这个自动机从初态

任何初态到终态这个路径当中

是没有这个环路的

那这个语言它就不是无限的

那就肯定是有限的

下面我们还有一个问题

就是怎么判定一个语言不是正则的

因为前面我们都是讲的正则语言

好像所有的语言都是正则的

这倒不是

因为在前面

我们判定一个语言是不是正则的

我们就看这个语言

要么它有没有对应的DFA

有没有对应的NFA

或者有没有正则表示

有没有正则文法等等

如果有这些来描述这个语言

那这个语言就是正则的

那我们怎么去证明这个语言不是正则的呢

那一般是不是我们证明

就是对这个语言来说

没有DFA来接受它呢

因为我们前面讲的

要证明一个语言是正则语言

只要有一个DFA接受它 它就是正则的

那我们要证明它不是正则语言

要证明没有DFA来接受它

这个是不可能的

那对于这个问题

我们下节课 我们再来解决

好 这节到此

谢谢大家

软件理论基础课程列表:

第一章 基础知识

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

也许你还感兴趣的课程:

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