当前课程知识点:软件理论基础 >  第二章 确定有限自动机 >  2.4 正则语言 >  Video

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

Video在线视频

Video

下一节:Video

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

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

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

今天我们继续介绍确定有限自动机

介绍确定有限自动机的正则语言

语言是我们这门课堂的重要的内容

DFA作为我们自动机当中的

十分重要的有限自动机

它的语言是怎么定义的

我们看看给了一个DFA

我们假设为M

我们把M所接受的字符串

都放在一个集合里面

这个集合就称为这个DFA的语言

把它记为L(M)

也就是我们用一个集合的表示

自动机M的语言

它就是从初态到终态这样集成的串

所有的字符串构成的集合

就是这个自动机的语言

那正则语言是什么呢

正则语言就是把所有的DFA接受的语言

都放在这个集合里面

这个集合就叫做正则语言

我们前面讲的这个自动机

这个自动机 它接受的串有ab 有abaa

还有abba

这些串构成的集合

就是这个自动机它的语言

前面我们给出了DFA语言的定义

但那种定义是描述化定义

比如一个自动机的语言

是被这个自动机接受的串构成的集合

这种说法如果是我们人与人的交流

这是可以理解的

但是如果说我们把这个定义告诉计算机

计算机它是不能理解的

那怎么样让一个计算机来理解的语言

这就是我们下面DFA语言的形式化定义

假设我们给了DFA是M

它接受的语言就是

从q0开始经过扩展的状态转移函数

如果把它转移到终态

我们把这个串就放在这个集合里面

这个集合就是自动机M的语言

这就是DFA语言的形式化定义

如果是这样定义的话

计算机它是能理解的

从这里看出扩展的状态转移函数

在语言的形式化定义当中

起着非常重要的作用

这个语言的表示

我们可以从下面这个图可以看出

一个串被接受 也就是从初态

由这个串标记的路径到一个终态

这样的串构成的集合就是这个语言集合

那给了一个自动机

不被它接受的语言是啥呢

这个定义我们可以看出

从q0开始

这个串经过扩展状态转移函数

最后转移到非终态

它构成的集合

就不是这个DFA它的语言的集合

下面我们看前面讲的这个例子

这个例子里面

被它接受的串有空串、11、01、0、1、101、001等等

这个自动机它接受的串应该是无穷多的

这是我们讲的从一个自动机

求它的语言一般的表示方法

就是把它的接受串 都把它找出来

它构成的集合就是这个自动机的语言

而我们讲这个问题的另外的一方面

如果给了一个语言

怎么样去把这个自动机构造出来呢

这个问题比刚才的问题来说

可能更有挑战性

如果你要构造一个自动机

你需要构造这个自动机的状态

这个自动机的状态转移 初态以及终态

最后它接受的语言就是你给的这个语言

下面我们看这个例子

给的语言是a的n次方b

我们要构造一个自动机M

来接受这么一个语言

这个语言首先a要出现n次

然后再出现b

那我们构造的话

首先我们要给一个初态

我们假设这个初态是q0

接下来我们再怎么去取它的状态

再怎么做它的转移

因为我们这个a的n次方

n是任意的

我们不可能把每一个a的转移

都用一个状态

你这样就不可能用一个有限自动机来表示

那下面呢 我们看这个n是任意的

我就可以在q0这个地方加一个自环

这个自环a可以在这里做任意的输入

然后如果在输入b的时候

到这里就算是被接受了

如果后面再输入a或者b

就不输入这种形式

那这样就不会是一个接受串

增加一个状态q2

从a和b转到q2

q2这个状态是非终态

它是不会被接受的

在q2里面我们这个自动机还没有接受

因为q2要在a和b都要有转移

q2是非终态

它是不被接受的

再输入任何字符a和b它都不会接受

所以我们这样得到了这个自动机

就是三个状态确定自动机

这个自动机就是这个语言的自动机

在这个自动机里面q1是接受状态

q2 看 我们在这里转移

只要是到了q2

它再也不会回到接受状态

因此这个q2这个状态

我们也把它叫做自动机的一个陷阱

好 我们现在看另外一个例子

在自动机的输入字符是a和b

它要求是前缀为ab

那我们构成这个自动机的时候

怎么将这个前缀ab表示出来

我们假定这是初态

我们要表示a和b

就必须要用两个状态 a输入a到q1

再输入b再到q2

这样得到的这个输入 前缀一定是ab

再在q2这个地方

因为它是前缀ab 它就是被接受的

再输入任何字符 这里都是被接受的

这得到的语言它一定是前缀ab

但是这个东西还不是我们要求的DFA

DFA要求在每一个状态

它对每一个输入字符都应该有转移

在q0输入a有转移

输入b它就会到另外一个状态q3

因为输入b之后呢

这个前缀就不可能是ab

所以这个状态肯定是不被接受的

在q1这个地方 是b转移到q2

那输入a 再得到的前缀也不会是ab

我们把它也转移到q3

也是不被接受的

在q3这个地方

它的前缀 都不具有ab这个性质

所以在这里再输入任何字符串

依然在q3不被接受

我们得到了这个语言对应的自动机

由四个状态构成的

下面我们再看一个例子

这个输入字符是01

w中不含字符串100

也就是说我们在01的字符串里面

只要不含100这个子串

那这个串就被接受

只要含有100这个子串

这个串就不被接受

那我们要构造这个自动机的时候

我们在写它的状态

或者是它的表示的时候

我们一定要瞅准这个100这个字符串

那我们在表示的时候

我们下面用另外的一种状态表示法

也就是状态命名

我们可以用其他的形式

反正状态的名字只是一个命名而已

我们就用输入的它的字符

来表示它的名字

首先我们没有输入任何字符的时候

我们有空串

在下面我们看

如果输入100这个子串的时候

它的表示是输入1到状态1

输入0 它表示为10

再输入0 它到100

也就是从在开始状态输了100之后

这个串里面就含有100这个子串

那再在100这个状态里面输入任何字符

那它都不受这个语言里面

那也就是说在100里面 再输入任何字符

这里都不被接受

在开始状态这个地方

我们输入1有转移

那输入0

因为这个里面 它是不包含100的

所以输入0 它肯定是被接受的

在1这个状态里面 输入0到这儿来

那输入1 它依然在状态1这个地方自环

因为这个地方是不含100的

那这个状态是被接受的

这里输入0之后

到了10

10它也是不含100的子串

所以这个状态也是被接受的

10输入0已经有了

那它输入1 这个状态大家看

应该转入哪呢

因为输入1 它这个状态

得到的串 它也不含100

而且输入1 我们注意 后面有可能输入两个0

所以我们输入1的时候

只能够转移到这个状态

那我们输入1 就回到状态1

然后它再输入00

这个就不被接受了

输入1这里是被接受的

那这个自动机

就是描述了这个语言的一个自动机

好 下面我们再讲一个例子

在自动机输入字符是ab

它接受的串是前缀有一个a

后缀有一个a

中间就是任意的w

这个自动机很有意思

但对w来说它是任意的串

只要是前面加一个a 后面加一个a

我们就可以把DFA构成串

那下面我们看

怎么利用它的前缀和后缀

来构造这样一个DFA

首先给的初态是q0

那输入a 它就到q2

就是有前缀我才考虑它是怎么走

到了q2之后

它取任意的串不一定被接受

只有它的后缀为a的时候才被接受

那中间的任意串怎么写呢

如果中间输入b的时候

我们就用一个自环来表示

如果输入a

这个时候 就表示它的后缀就是a

就能够被接受了

但这儿并没接受

因为q3这个状态

依然要对a和b要有输入

如果q3是b 那它应该回到q2

回到q2之后

再输入a的话 它可以到q3

再输入b 它就在这个地方自环

在q3 如果输入a的时候

那表示它的后缀都是a

所以都被接受

就得到一个自环

这个自动机是否好像已经换完了

好像是接受这个语言

但是这个自动机

还不是我们要求的一个DFA

因为在q2上有ab这个输入

在q3有ab这个输入

但是q0只有a这个输入 没有b

那么我们当q0是b的时候

那表示这个串它的前缀就不是a了

所以到q4

q4就是不是一个接受状态

在q4这个地方

再输入任何一个字符的时候

它的前缀都不可能是a

所以得到的都是被拒绝的

所以我们用一个自环ab来表示

这样我们得到了这个语言awa

它对应的自动机是用四个状态表示的

在前面在讲这些例子里面

我们给了一个语言去画一个自动机

但有的同学会提这个问题

你给了这个语言

你画的这个自动机

你这个语言 是不是自动机它接受的语言

这里也就是我们面临着

如何说明你给的这个自动机就是所求的

下面我们看这个例子

假设这个输入字符是01

我们要求这个串当中

01的数目的奇偶性相同

那就接受这个串

也就是说这个串0的个数和1的个数

它们虽然次序上面我们不管

但是0如果是奇数 那1的个数也是奇数

那就被接受

0的个数是偶数

1的个数也是偶数 也被接受

那除此以外 它们就不被接受

这样的语言实际上

我们用一个非常简单的表示

它也可以表示成这种语言

也就是这个串的长度为偶数

只要是串的长度为偶数

大家知道 0的个数和1的个数的奇偶性

必然是相同的

那我们对这个语言

怎么样去把它的自动机画出来

实际上这个语言

是我们之前见过的自动机的语言

这个自动机是这样的一个自动机

它是由四个状态刻划的

这个自动机它接受的语言

就是串的长度为偶数

或者0的个数和1的个数

的奇偶性是相同的

那虽然在得到了是它的自动机

或者这个语言是它的语言

但我们要严格证明

就应该用互归纳来证明

你这个自动机接受的语言

一定是0、1数目奇偶性相同

反过来0、1数目的奇偶性相同的串

一定被这个自动机接受

这样才说明这个自动机

是这个语言的自动机

当然在本课程当中

我们重要的是强调同学们掌握

自动机的构造

但只要是自动机构造是正确的

我们认为你的做法是OK的

对于它的严格证明

同学们感兴趣 可以课后做一些练习

今天我们介绍了自动机的语言 正则语言

从给了一个自动机

怎么去得到它的语言

到给了一个语言 怎么构造自动机

这就是我们这门课当中

需要同学们掌握的

特别是我们给了一个语言

怎么去构造一个自动机

这个构造对大家来说是有难度的

而且有挑战的

也就是说 你怎么样去构造自动机的状态

怎么构造它的状态转移

怎么构造它的终态和初态等等

由于这方面的内容十分重要

这方面的内容也具有挑战性

我们在下一节课当中

专门要讲到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笔记与讨论

也许你还感兴趣的课程:

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