2.3 Finite automata在线视频

大家好

这节课我们继续来学习

词法分析的相应内容

我们首先来回顾

上节课讲的相关内容

对于词法分析器来说

我们知道它的工作原理

是通过扫描源代码进行相应的分析

得到一系列的记号流

那么在我们之前讲过的内容当中

我们知道在整个过程当中

最为重要的就是这种模式的描述

也就是规则的描述

这种规则的形式

我们一共学习了两种

第一种是非形式化的描述

也就是用语言上描述它有什么样的规则

进而我们学习了形式化的描述

也就是正规式

而在正规式里面

我们了解到正规式的名字

实际上就是我们最后想要得到的词法记号

那么在这节课当中

为了能够把正规式更贴近于计算机来实现

我们来学习

有限自动机的相应的内容

也就是说

从正规式到状态转换图

我们上节课看到了一些例子

但是如果一些复杂的正规式

怎么得到这个状态转换图

这样就一定的困难

也就是说

我们怎么样才能得到

正规式对应的编译程序

我们采取一种迂回的策略

也就是说在这节课里面

我们一共会介绍两种状态转换图

分别叫做不确定的有限状态自动机

和确定的有限状态自动机

而正规式和这种不确定的有限状态自动机的对应

是比较顺利的

因此我们可以通过

先把正规式转换成不确定的有限状态自动机

进而转换成确定的有限状态自动机

而这种和我们想要得到的状态转换图

就是等价的

那么这就是我们本章要讲的内容

有限状态自动机的定义

以及这种不确定的有限状态自动机的构造方法

首先我们先了解

第1种确定的有限状态自动机

也称为DFA 它的定义以及数学表达形式

那么整个确定的有限状态自动机

都是有一系列的状态集合为基础的

也就是我们上节课看到的状态转换图

这个圆圈里表示的东西

也就是圆圈本身实际上就是状态

那么这些状态结合到一起

就是状态集合

进而它需要有一系列的输入字母表

输入字母表

就是状态和状态之间箭头上的文字

这就是输字母表里面相应的内容

第3个就是转换函数

也就是说从一个状态

到另一个状态之间

如果有跳转的话

应该是怎么样的规则来转换

它表示的

比如说状态S通过识别字母表上的某一个字母

就可以达到另一个状态

这就是它转换函数的定义

最后两点

就是

它有唯一的一个初始状态

那么还有终态的一个集合

也就是接受状态可能不唯一

可能很多状态都可以表示

当前的串是正确的

那么比如我们看这样的一个例子

从开始状态开始

通过识别字母表上的一个字母a

就可以到达一个接受状态这样 1 来表示

这就表示的一个转换关系

也就是一个确定的有限状态自动机

进而我们来学习

不确定的有限状态自动机

也就是NFA 的相应内容

我们看不确定的有限状态自动机

对应它的数学形式

以及它的定义

同理

它也是由状态集合、输入字母表

以及转换函数这一系列构成的

那么不同在于它的转换函数

和确定的有限状态自动机有一些区别

那么它的转换函数

我们看从一个状态开始

可以识别字母表上的字母

也可以识别空串 也就是 ε

那么识别这两个东西之后

跳转到的不是一个目标状态

这里的 P(s) 表示一个状态集

也就是说

可以识别字母表上的一个符号

就跳转到好多个状态上去

这也是它不确定性的体现

第1个就是输入字符包括 ε

也就是我不通过扫描源程序的任何一个符号

就可以跳转到其他状态

第2个就是一个状态

对于某一个字符

可能有多条输出边

也就是它的跳转不是唯一的

这两个缺点

也是它不确定性的一个体现

接下来我们来看一下

DFA 和 NFA 的区别

我们以同样的一个正规式为例

我们来看一下

它们对应的状态转换图

有什么区别

对于 a 或 b 的闭包

连接一个 a 再连接一个 b 来说

那么我们首先看这里面

从状态零开始

表示闭包可以在自身循环

进而连接一个 a 连接一个 b

从这个图里

我们可以看出

这种NFA 的形式

从开始状态开始

它可以有

多条同样字母的输出边

我识别一个 a 既可以回到(状态) 0

又可以跳转到状态1

这就它不确定性的一个表示

而对于确定的有限状态自动机来说

识别这样一个正规式 是这样的一个图

我们可以看出

上面的图

和正规式的结合

更紧密 更直观

而下面的图

它的确定性比较好

不存在回溯

也就是跳转的状态1

如果有问题

我可能还要回来

重新跳回到状态里

而DFA不存在这样的问题

也就是说它们的区别在于

NFA 当中允许有 ε 的转换边

而 DFA 不允许

NFA 当中的跳转可能同时跳转到好多个状态去

而DFA只能跳转到唯一的一个状态

对于状态转换表来说

我们可以对比一下两种

前面的是 NFA 的状态转换表

我们看这里面有很多的空集

那么对于 DFA 的状态转换

我们看是比较确定的

因此我们看对于DFA来说

它的优点就是可以快速的定位

那么缺点就是字母表可能过大

大部分转换可能存在于有空的 这样的形式

因此我们如果想让正规式转换成

计算机能够更容易编程实现的状态转换图的话

我们很显然

应该选择DFA这样的一种实现方式

然而DFA直接想给它表示出来、画出来

是有一定难度的

也就是NFA它更贴近于人们的认识

而DFA转换比较确定

希望通过它来进行编程序

我们可以看NFA和正规式的表示是比较贴近的

因此我们采取一种迂回的策略

来达到我们最后获取DFA的

这样的一个目的

这个过程就是

我们可以先构建NFA

然后通过NFA 转换成DFA

得到我们想要的确定跳转的方式

最后我们还可以通过DFA化简

得到一个最精简的状态转换图

这样就可以使你的编译的程序

更加的有效

更加的迅速

那么这节课

我们就来学习NFA的构建方法

对于NFA的构建

和正规式的表示很类似

都是先从简单的规则构建起

然后再一点点扩展起来

具体来说

一般分成这样的几个简单的规则

第1个就是有单个符号的

然后从单个符号

再到选择关系、连接关系、再到闭包关系

或者是有括号的

分别是怎么来画

我们依次来看一下

这个规则里

第一个如果识别 ε

或者是识别一个符号的话

那么它的画法比较简单

就是从开始状态开始

识别一个 ε 到接受状态

或者识别一个字母 a 到达一个接受状态

进而我们看选择关系

那就是两条路都正确

那么从开始状态开始识别一个 ε

我们看 ε 表示的

就是我可以走这条路

也可以走这条路

那么选择的东西是什么

就可以在椭圆的部分来体现

这就是选择关系

接下来是连接关系

所谓连接关系

如果走这条路了

那么连接项里的第1个走完

就要走第2个

因此我们可以把椭圆表示

需要连接的第1部分

N(t) 表示需要连接的第2部分

把它们结合到一起就可以了

最后是比较复杂的闭包的形式

闭包我们了解到

它是可以自身循环多次的

也可以不存在

闭包可以直接过去

我这一项就不做任何操作了

因此我们看

画闭包可以画一个开始状态

再画一个接受状态

然后开始状态和接受状态之间

可以直接是一条 ε 边

这样我们就可以

当前闭包直接略过了

那也可以自身循环多次 用这样一种形式来表示

遇到一个 ε 到这个状态

然后走一遍之后

想自身连接一次 从 ε 再回来

再连接一次 好 再回来

连接够了 好 出来

这样就是一个闭包的形式

我们整体看这个图

大家如果记忆的时候

可以看成

它有点类似像一个平顶

像一个锅一样

上面是锅盖

是吧

下面这是锅的底儿

那么可以这样记它的这种形式

它是一种对称的这样的结构

那么对于NFA的

这样的构建方式

我们来看一个复杂的例子

a 或 b 的闭包 再连接一个a 再连接一个 b

它是怎样的一种形式

我们来看一下

a 或 b 的闭包连接 a 连接 b

先从简单的这样的开始

我们看

正规式最基本的就是字母a 和字母b

因此我们可以先把

字母a 和字母b a 或b

这样画出来

那么这是识别 a 的状态转换图

这是识别 b 的

进而我们画它们的选择

那么选择

我们刚才说过了

可以走这条路

也可以这条路

用 ε 边

给它们连接起来就可以了

进而在选择的基础上

也就是整体

我们可以想象成

是刚才讲的椭圆里的内容

进而就可以画闭包

就是我说的锅的 类似锅的 这样的形式

那么前面加上一个状态

后面加上一个状态

一个闭包这样给连接起来

整个闭包画完之后

最后连接一个a 连接一个b 这样

就比较简单了

通过连接一个 a 到达 8 状态

在连接一个 b 到达 9 状态

整个正规式的

对应的状态转换图

我们就画完了

以上就是我们这节课讲的内容

谢谢大家