当前课程知识点:软件理论基础 >  第五章 正则文法和正则语言 >  5.4 自动机的积 >  Video

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

Video在线视频

Video

下一节:Video

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

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

-习题--作业

第六章 正则语言的性质与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笔记与讨论

也许你还感兴趣的课程:

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