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