当前课程知识点:软件理论基础 >  第二章 确定有限自动机 >  2.5 DFA构造 >  Video

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

Video在线视频

Video

下一节:Video

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

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

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

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

在上一节里面 我们给出了自动机的语言

也就是正则语言

通过一个DFA

我们可以得到这个自动机的语言

这一部分对同学们来说应该比较简单

反过来 通过一个语言

怎么去构造一个自动机呢

通过前面的几个例子可以看出

这是具有一些强制性的问题

特别是我们做软件专业的同学

需要通过需求来写出相关的软件

我们的需求实际上就是一种语言

而语言怎么写成软件

这就是一个构造过程

那下面我们介绍几个实例

也就是DFA的构造

我们怎么通过语言去构造一些DFA

首先我们看

这个语言输入字母是0、1

要求它的输入串 倒数第二个字母

或者倒数第二个字符为1

因为我们语言是0、1串构成的

它可以串的长度为1

也可以串的长度为n

那前面我们语言的串是多少

我们不关心

只关心它倒数第二个

所以我们在构造我们的自动机的时候

我们特别注重它倒数第二个是1的

这样的串我们是被接受的

那我们构造自动机 我们看

在初始状态

用一个符号 也可以不用符号

那接下来我们要关心的是倒数第二个是1

也就是说只要是1出现了 我们特别关注

那对于0 前面是0

是多少个0 对我们这个串是没影响的

所以如果是0的话

那这个里面就有一个自环

如果是1 它就转到另外一个状态

这个状态我们就把它标为输入为1

因为我们只关注它的1的出现

那接下来再输入0和1的时候

我们这个时候就应该被接受了

所以我们首先要关注的是输入是0

这个时候输入的是0 那得到了它

假如这是最后一个的话

那这就是倒数第二个

所以这个时候

我们得到的这个串10就应该被接受

在10的时候

我们如果再输入1

它就要到达这个状态

因为我们始终关注倒数第二个是1

所以它再输入1

我们还是要

看它是不是倒数第二个是1

如果它到这里来 再回到0的话

它就是是被接受的

如果在这个状态输入0

我们就转移到另外一个状态

那我们再在这个状态里面

如果再输入0的时候

它的倒数第二个还不是1

还不被接受

那如果是在这里要输入1的时候

大家注意

只要是输入1

我们都关注它是不是倒数第二个

所以它就转移了

应该转移到这个

再来之后呢

如果再输入0它被接受

那如果在这个状态里面是输入1的时候

输入1大家注意

这个输入1 因为在之前有一个1

所以到这儿来 这里倒数第二个是1的

我们把这个状态就是1

这里依然是被接受的

那在这个状态里面

如果再输入1的话

那它永远是被接受的

因为这里倒数第二个都是1

如果输入0的时候

我们实际上关注它

因为它这里是输入1

再输入0 它倒数第二个应该是1的

所以它应该到这个状态

通过刚才的分析

就把这个语言的自动机就构造出来了

这个语言的自动机构造

我们这里有1、2、3、4、5个状态

把这个自动机的状态可以减少

那下面我们可以把

刚才这个状态减少之后

那得到这样的自动机

这个自动机接受的语言

也是倒数第二个是1的这个自动机

跟刚才的自动机的语言是一样的

也是一个等价的自动机

下面我们再看一个例子

这里给出的语言也是输入是0、1的串

这个串中1的个数被3整除

0的个数被2整除 这类语言

因为这个0、1串里面0的个数

和1的个数是任意多的

1的个数被3整除

0的个数被2整除

像这样的串才是被我们的语言所接受的

但是这样的串有无穷多个

那我们怎么样去

构造一个有限状态的自动机

来解释这类语言呢

观察这个语言的特点

因为这个串当中 虽然1的个数是有很多

但是要求它被3整除

那被3整除 它的余数

它只有0、1、2三种情况

同样这个串当中

0的个数可以是无穷多个

但是被2整除 它的余数只有0和1

我们就用这个串的余数 它的规律

来构造这个状态

状态用两个数来表示

第一个数 表示1的个数被3整除 它的余数

第二个数 是0的个数被2整除 它的余数

这样我们开始构造我们的状态

用两个数来表示

第一个数 表示1的个数被3整除 它的余数

第二个数 表示0的个数被2整除 它的余数

那一开始我们什么东西都没输入

那1的个数的余数和0的个数的余数都是0

那这里我们就说它是被接受的

那接下来输入一个1

大家看 这里面这个串就是一个1

1的个数被3整除 它是余1

所以我们这里

第一个数是表示1被3整除的余数

它表示1和0

那我们再输入一个1的时候

这个时候我们的串的1的个数

被3整除就余2了

0的个数没有任何增加

这是输入了两个1

如果再输入一个1

那这个时候 我们1的个数就是3个了

被3整除 它的余数就变成0

所以它这个转移就转移到这个状态

那在这里这是输入1过来的

如果在这个状态里面

我们在输入0的时候

这个串当中输入0

表示这个串当中有一个0了

有一个0被2整除 它的余数是为1

所以到1、0

在这个状态里面

我们再输入一个1

1被3整除的余数就为1

那前面也讲了这个状态里面

0的个数被2整除

余数也为1

所以它的余数是1、1

如果再在这里输入一个1的时候

我们看这个时候

1的个数被3整除 余数为2

0的个数被2整除 还是为1

如果在这里输入一个1的时候

被3整除就为0了

余数为0

就回到这个状态

那这还没有完

我们这里要对每一个状态

对每一个输入字母都要有转移

在这里0的个数被2整除是余1

再输入一个0 被2整除了

它的余数就为0

但是这里这个状态

如果再输入一个0的时候

0的个数被2整除就为1

那在这个状态

这是表示0和1

分别被3整除 被2整除 都是余1

再输入一个0的时候

那0的个数的余数就为0了

同样在这个状态里面

在这个状态里面

输入0 那0增加了一个

被2整除 余数为1

在这里再输入一个0的时候

0的个数被2整除就为0了

那这个自动机 就给出了1的个数被3整除

0的个数被2整除

它接受是在这个状态接受

其他的都是不接受的

看 我们用六个状态

就刻划了这个语言的自动机

下面我们再看一个例子

同样这个例子里面的输入字母是0和1

这个串是以0字串

它说这个串w是以1开始

转为整数时

也就是十进制整数时 它被3整除

这样的串是被接受的

实际上我们0、1的串

它的个数也是无穷多种

你转为十进制的时候

我们看如果前面是0

你就没法去转十进制

只有以1开始的时候

它才可以转成十进制

比方说输入一个1

转成十进制是1

输入一个10

那转成十进制是2

如果输入11

转成十进制就是3

输入的01的串

只要是转成十进制为3的时候 就被接受

那我们要做这样的一个自动机该怎么构造

在这个里面同样这个串是无穷多个

我们自动机的状态不可能是无穷多个

那我们就想在这一个串

转制十进制被3整除

我们关心的是3整除的它的余数

被3整除的余数 它只可能是0、1、2、3组

那我们就根据这个规律

来构造这个自动机

下面我们看 这是初始状态 是q0

q0如果输入1的时候

它转成十进制是1

也就是被3整除的时候

它的余数是为1

如果再输入一个1的时候

那这是11这个串

11这个串转成十进制的时候 它就等于3

它就被3整除了

被3整除 它的余数就是等于0

那在这里如果是你在后面增加0的时候

1、1、0就表示6

再加0 也就是在原来的3里面再乘2倍

所以这些都是被3整除的

所以它的余数都等于0

那如果是在这个状态里面

我们后面增加的是1

增加的是1

就表示原来0、1的数后面 增加了一个1

就是把原来的数乘上2倍再加1

原来的数乘上2倍 这个余数为0的

乘上2倍再加1

那这个时候 余数大家看

它应该是等于1的

大家看如果在这个状态里面

输入是0的时候

这相当于把原来这个数乘上了2倍

那这个时候被3整除 它应该是余2

在2这个地方

如果是再加一个1的话

就表示把原来的数乘上2再加1

那这个时候余数还是2

那在状态2这个地方 我输入的是0的话

就表示把原来的这个数乘了2倍

乘了2倍被三整除 它的余数就是1了

现在我们通过刚才的分析

把通过四个状态表现出这个语言

但是这个语言

还没有把这个自动机完全刻画出来

我们这个自动机要求在每一个状态

对每一个输入字母都必须要转移

那在q0这个状态

我们有1这个输入

但没有0这个输入

那我们必须要考虑给了0之后

也就是我们开始不是以1开始

以0开始的

那这样的输入串

当然不可能转成整数

也不在我们这个接受的语言里面

所以它转到另外一个状态

这个状态是不可能被接受的

在这里面再输入任何一个字符

也是不被接受的

所以这个自动机

我们用五个状态就把它描述出来了

下面我们再看一个例子

这里语言是这样的 输入串依然是0、1

但是它要求这个串中

长度不超过3的任意子串

最多只包含一个1

那这句话是什么意思呢

因为我们输入的串是0、1

这个长度是任意的

但是它里面的子串

只要是长度等于3的

它的1的个数是不能超过1

只要是1的个数超过了1

这个串就不被接受

我们要构造这样的一个自动机

那对这个自动机的构造

我们就要关心

它任意一旦只要是长度等于3

或者长度不超过3的

我们都要求它的1的个数不能超过1

好 我们构造的时候

输入是空串

那它当空串 它里面是没1的

所以这个串是被接受

空串输入一个0的时候

那我们这个串只含一个0

因此它应该在这个语言当中 所以被接受

如果再输入一个0

这个串 就是0、0

同样它也是在这个语言里面

如果是再输入一个0 这个串0、0、0

长度为3 不包含1

所以也是被接受的

在这个串里面 你再任意输入0

只要是长度为3

它一个1都没有

所以这样只要输入0 它都是被接受的

那下面我们再看看这个串输入一个0

我们再输入1的时候

这个串就变成0、1

0、1长度为2

串当中只包含一个1

所以这个被接受

那我们再看看

这里再输入一个1的时候

这个串就变成001

串的长度为3

它只包含一个1

所以依然被接受

那我们再看看这个串

如果输入一个1

输入1这个串就变成了0001

那我们只关心它中间长度为3的

所以在前面一个0 我们就把它去掉了

我们就看后面的001

那它自然就转移到这个状态

这个状态也是被接受的

下面我们看这里面

这个状态输入0的时候

它就变成了010 也是被接受的

这个状态在输入0的时候

它变成了100 也是被接受的

这个状态001 再输入0的时候

后面的3个符号是010 也是被接受的

我们再看这个状态100 输入0的时候

它后面三个符号

就是000转到这个状态 也是被接受的

这个状态如果再输1的时候

后面三个数就变成001

这里也是被接受的

那我们再看这个001

这个状态输入1的时候

它后面三个符号变成011

这里三个符号里面含有两个1

因此不被接受

这个状态01输入1

也变成了011 也不被接受

这个状态010输入1

后面三个符号是101 也是不被接受的

101再输入0的时候

大家注意

好像101再输入0的时候 后面是010

应该转移到这个状态 好像被接受

但是我们前面这个状态

是到了是不可接受的

也就是说前面里面

其中有一个档里面

三个符号含有两个1

在这个情况下

是不能转到这个状态的

那它应该转移到另外一个新的状态

这个状态我们表示是不被接受的

只要前面有一个状态是不被接受的

它再输入什么都应该不被接受

下面我们再看这个状态

再输入任何一个符号

它都是不被接受的

101输入1的时候

变成01 也是不被接受的

这个状态输入0的时候

成了110 也是不被接受的

这个状态如果输入0的时候

它到时候后面是100 也变到这儿来

但是因为这是一个不被接受的状态

也就是说前面转到它是不能接受的

而到这儿来 转到这儿来

就成了被接受的

也就是这个串被接受

这里就是不会出现错误

所以我们要避免它

这里呢只要是不被接受的

那我们就把它转到这儿来

这里是不被接受状态

这里110就变成了101 也是不被接受的

再看空串输入1

串里面长度为1

只有一个1

也是在这个语言里面是被接受的

1输入0

10长度为2 只含一个1 也是被接受的

这个状态输入1的时候 是11

它长度为2

含两个1 不被接受

这个状态10再输入1的时候

变成了101也是不被接受的

这个状态11输入0变成110

也是不被接受的

在11这个状态 如果再输1的话

它变成了111 长度为3

它含两个1 还是三个1

那都是不被接受的

在这里11再输入1

它依然是不被接受的

还是在11这个状态

那这里111输入0

后面三位数是110 也是不被接受的

这个011输入1变成1 也是不被接受的

下面我们看10这个状态

那它输入0呢

它就到了这个状态100

这里是被接受的

根据上面的这个步骤

我们就画出了这个语言的它的自动机

这个自动机虽然我们画出来了

我们看这里的状态

还是比较复杂 比较多的

也就是说在这里面

这么多状态 实际上有些是冗余的

我们在后面要讲状态的优化的时候

可以得到一个跟它等价的

要求这个语言的自动机

但是状态的个数比它少

可以得到这样的一个自动机

这个自动机只有4个状态

这个四个状态实际上接受的语言

跟刚才描述的语言是一模一样的

那前面我们介绍了

给了一个语言

我们就可以构造一个DFA

那是不是任何一个语言

都可以构造DFA呢

这可不一定

我们下面看这样的语言

a的n次方 b的n次方

也就是a出现n个之后

b也出现n个

这个语言实际上是我们通常见到的

但这个语言的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笔记与讨论

也许你还感兴趣的课程:

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