当前课程知识点:软件理论基础 > 第五章 正则文法和正则语言 > 5.4 自动机的积 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍第四节 自动机的积
那在前面我们介绍了DFA、NFA
还介绍了其它的正则表示 还有正则文法
现在我们介绍对两个DFA
它们之间做一个积
你看我们给了两个DFA
一个DFA是A
一个DFA是B
它们的状态分别为qA、qB
我们通过这两个DFA
怎么构造它的一个积呢
我们这个积是用笛卡儿积来表示
这个自动机用M表示
它的状态是A的状态和B的状态的笛卡儿积
当然这里输入字母都是一样的
状态转移我们等会儿再说
初始状态分别为
a的初始状态和b的初始状态
构成的这一个状态z
而接受状态是由
A的接受状态和B的接受状态的笛卡儿积
那它的状态转移δ就是
a当中的状态 b中的状态
构成的状态z
如果输入a 那它转移到哪呢
转移到我们就看 在a中的这个自动机qA
对输入字母a它转移到了哪
对B中的自动机状态qB
输入a它转移到哪
这两个转移
因为我们这是DFA 它的转移是唯一的
那整个这个状态z
就到了一个新的状态z
这就是我们的积自动机
这是有DFAA和DFAB
它的笛卡儿积得到的积自动机
下面我们看一个例子
这个图一当中给了这个自动机
这个自动机转移有自环 有p到q的转移
在这里有一个自环
得到的语言大家看
得到的语言这里面
只要是有一个0 它就到了q里面来
所以它的语言应该是
所有含0的串 只要含一个0 它都被接受
那我们再看另外的一个自动机
这个自动机状态是rs
它这里面大家看这也是一个DFA
它只要是输入一个1
它就到终态s里面来了
也就是说它的语言
只要含一个1就接受了
所以所有含1的这个串都被接受
那现在我们给了这两个DFA
怎么去构造这两个自动机的积自动机呢
那根据刚才的定义
我们通过这两个自动机
它的状态的笛卡儿积
也就是p和q跟r和s的笛卡儿积
我们就考虑它的状态
首先初态
初态是这个自动机
和这个自动机的初态构成的 你比如说pr
就作为积自动机的一个初态
当然我们这里可以表示成它的状态z
就用pr来表示
效果也是类似的
它分别对0和1都要求有转移
那我们首先看它对输入1的时候
输入1的时候
就看p输入1的时候
它转移到了p
而r这个时候 它输入1的时候
那r输入1的时候 是转移到s
所以pr输入1的时候是转移到ps
我们再看输入0
那p输入0 转移到q
所以p输入0 就转移到q
那r输入0 这是一个自环转移到r
那这里所以r输入0就转移到r
也就是pr这一个状态输入0 就转移到qr
那我们再看这个ps输入1的时候
ps输入1 首先看p
它输入1 它转移到是p
s输入1的时候 就是自环到s
所以ps输入1 还是到ps
所以这是一个自环
那看ps输入0
ps输入0
p输入0转移到q
s输入0的时候
s输入0的时候 转移到s
也就是ps输入0的时候 转移到qs
那同样我们可以推出这个qr输入0的时候
它肯定是转移到qr
那qr输入1的时候
根据刚才的这种推导方法
我们就得到qr输入1的时候 就转移到qs
那qs
q是第一个图当中的终态
s是第二个图当中的终态
那它们组成的状态qs
就是积自动机的终态
qs它输0和1
我们一看从图一和图二
我们得出了
它在01里面 它都是一个自环
你看这样我们就得到
自动机图一表示的自动机
和图二表示的自动机
它的积自动机就是这样的一个自动机
这个自动机我们很容易验证
这个自动机 它接受的语言
至少包含有一个0和一个1的字符串
从刚才给的例子看
积自动机是刚才两个DFA
它们构成的语言的交
我们从这里还可以把这个结论
推广到多个DFA它们的积
也就是多个DFA它们的迪卡尔积
得到的这个自动机
定义跟我们两个自动机积的定义是完全一样的
那我们也可以得到多个
这个正则语言它们的交
这个自动机的构造方法
那下面我们再介绍一些自动机的构造
我们看这个例子
构造一个输入字母是0到9
这个字母上面我们接受的字符串
是最后的一个字符串
在前面没有出现过的
只要是最后一个字符
在前面没有出现的
这样的字符串我们都已接受
那这个语言怎么构造它的自动机
那在这儿我们首先给出一个初始状态
初始状态我们就看最后一个字符
最后一个字符要么是0 要么是1
要么是2 一直等等 要么是9
那我们看最后一个字符假如是0
我要把它这个字符串接受的话
那前面是肯定是不能够出现0
那前面不能出现0
那我们在这里构成的状态就是q0
我们是这样的
这里是从1或者是2 或者是3
又或者是9到q0
那这里面是0没在这里出现过的
这里肯定是被接受
当然我们也可以
这些字符串 它到这里还可以多次出现
也就是1到9这里有个自环
那这样得到的一些字符串
直到最后一个是0的时候
我们这里就接受了
这个里面是表示最后一个除0
但是前面没除0的被接受
那最后一个是1
那前面这个字符串是不能出现1
这里是被接受的
当然还可以这里增加一个自环
这里也是可以被接受的
那等等 直到最后一个假如是9
那前面是不能够出现9
这里是被接受的
当然这个地方还可以出现一个自环
是1、2一直到8
这个字符串也是被接受的
这里表示的是最后出现的
前面肯定是没出现
但这个语言我们说
这个自动机是不是完全就是这个语言呢
我们再检查一下
如果这个字符串是两个或两个以上的
肯定是能够被这个自动机接受的
但如果是我们的语言是单个的字符的话
单个字符你比如说我是一个1
1这里可以看到最后一个是1
那前面肯定是没出现
那应该也在这个语言里面
但是这个自动机表示
没把这个表示出来
所以在这种情况下我还加一个路径
这个路径是只要输入0或者输入1
或者输入2等等 又或者输入9
它应该都是被接受的
都满足这个语言
下面我们再看一个例子
构造接受两个0之间的位置
为4的倍数的NFA
当然我们这里强调的是这个串当中
只要是有两个0
它中间 它改的有4的倍数
我们就说这个串被接受
我们不要求任何两个0都满足
只要是这个串当中有两个0满足这个性质
也就是这里面呢 有一个0
这里的0呢 这里面改的位置是4的倍数
4的倍数 当然0的倍数也算是4的倍数
所以这里面是给的一个*闭包
实际上我们要构造这样的语言的一个DFA
那构造这个DFA 我们怎么构造呢
首先 我们把它的初态写出来q0
q0这个地方
当然我们加一个自环就是01
任意的输入
我们要注意 只要是有两个0之间
有4的倍数就被接受
那我们假设这里面
输入一个0 我们得到q1
q1如果是直接输入一个0
那这两个0之间
实际上是0个4的倍数
这里当然是被接受的
这里面你再输入任何的字符
这个串都是在我们这个语言里面
这是对中间还要在00这个串
那中间里面如果含有其它的
你比如说我中间里面
我就在这个0之间
我还有其他字符
这里也可能是0也可能是1
在这里面我再插一个字符或者0和1
就插一个状态
在之间再还插0或者1到状态q4
实际上这里面它有三个位置了
那还不够
我们在这里面到它这里就四个位置了
到这里被接受了
这个肯定在这个语言里面
这个语言就是表示
只要有两个0中间有
这个位置是4的倍数
就是这个串是被接受的
下面我们把这个题稍稍修改一下
这个题里面是这个字符串里面
有两个0之间相差的位置是4的倍数
就可以了
那如果是我们对任何两个0正闭包里面
它都是相差4的倍数
也就是我们这个语言表示成的
是这里面0正0正
这里面是11
是四个1
当然这里面可以是 位数可以是0个
也可以是任意的倍数个
那其他这里面是1
这里表示的是
任何两个0正之间是4的倍数
那对这个语言
我们的这个自动机该怎么构造呢
你看我们首先在q0这个地方
那这里有一个自环 这个自环只能是1
再不能写0
如果输入一个0到q1
q1在这个里面如果是再输入0
我们这里看到的任何两个0之间
它们应该都是满足这个条件
是位置是4的倍数
那如果这里输入1的话 我们就到q2
再输入1到q3
再输入1到q4
再输入1到q1
那这里面就刚好位置是4的倍数
这里面如果再输入1
我们就说这里是就被接受了
这里我们就再输入1的话
也是一个被接受的串
这里就是任何两个0正之间
它们的位置就是4的倍数
我们得到了这个语言的自动机
下面我们再看另外一个例子
要构造一个接受这样的语言的NFA
这个语言是什么呢
是包含1个或多个重复的01的这个字符串
或者是包含1个或多个重复010的这个字符串
它这里的NFA
这个语言实际上
可以把它写成为这种形式
那要构造接受这个语言的自动机
我们看接受01 至少接受1个或多个01的
这个字符串的自动机
我们构造它应该不难
它就是用三个状态来构造
q1是初态
只要有一个01
它就被接受了
加一个ε转移 就是多个01
它也被接受
这是接受01
1个或多个重复的这个字符串
那下面我们再看接受010
1个或多个字符串
实际上也很简单
我们用这四个状态就可以了
这里面也是从这里加一个ε转移
这至少有1个再含多个
当然q4是初态
那求这两个语言的并
实际上我们原来讲自动机的性质的时候
我们就用了这个方法
我们只把这两个自动机
把它并起来就可以了
增加一个初态q0
增加两个ε转移
那这样得到了一个接受语言L的
它的NFA
那如果我们把这个题稍稍又改一下
语言还是这个语言
但是我们要求接受这个语言的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
-习题--作业
-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
-习题--作业
-期中考试