当前课程知识点:软件理论基础 > 第二章 确定有限自动机 > 2.5 DFA构造 > 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
-习题--作业
-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
-习题--作业
-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
-习题--作业
-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
-习题--作业
-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
-习题--作业
-期中考试