正规式与FA在线视频

同学们

正则表达式和有限状态自动机

都可以描述程序设计语言的单词结构

正则表达式便于描述和理解

有限自动机则便于实现

二者的描述功能是等价的

都是来描述正则语言

它们之间是可以相互转换的

转换的方法归根结底

还是要以正规集作为桥梁

首先我们来依据FA

构建正规式R

一种思路就是

先分析清楚 FA 识别的集合

它的结构特征

然后再设计这个集合的正规式

另外一种思路就是根据FA

直接的写出对应的正规表达式

在这个过程当中首先考查

FA它的状态转换图结构

和正规式运算之间的关系

以此来削减状态节点和有向边

从而得到综合的正规式

例如在FA当中

从同一状态S出发

存在多条边

例如说在这个例子当中

有两条边分别是a和b

在这种结构当中呢

对应的就是正规表达式当中的a|b

在FA当中

从同一状态S

它的入边是a

出边是b

这种结构当中呢

对应的正规式是a连接b

如果在FA当中出现了“环”

也就是说在S状态下

如果输入a

仍然停留在S状态下的这种结构

对应于正规表达式的a*

在之前的考查的基础之上呢

有限状态自动机M转换成

正规表达式的步骤是这样子的

第一步 在 M 上面增加两个结点S和Z

从S结点用ε弧连接M的所有的初态

再从M的所有终态用ε弧

连接到终态Z

这样就结成了与M等价的

另外一个有限状态自动机M’

M’只有一个初态S和一个终态Z

第二步就是逐步消去M’当中的结点

直至剩下S和Z这两个结点

在消结的过程当中

逐步用正规式来标记弧

规则是这样子的

第一条转换规则当中

R1和R2分别是状态2的入边和出边

你们就消去节点2

用R1连接R2这个正规式

来代替标记从状态1到状态3的弧

在第二条转换规则当中

用R1| R2这条正规式呢

来标记弧

代替从状态1到状态3的这两条弧

在第三条规则当中

用R1*来代替停留在

状态2上面的这个“环”

我们来看如何将这个

有限状态自动机M

转换成等价的正规式R

首先我们增加一个初态S结点

和一个终态Z结点

从S结点通过ε弧指向

M的初始状态0结点

M的终态2结点和4结点

通过ε弧指向新增的终态结点Z

接下来的任务就是消除M当中的

所有的状态结点

只留下我们刚才新增的S结点和Y结点

我们先看我们根据规则2

消去结点1和3

取而代之的是从状态0到状态4

标记为aa的这样的一条边

从状态0到状态2标记为

bb的这样一条边

同时根据规则1

消去多余的弧

用a|b来标记在状态0 2 4

这三个结点当中出现的

标记为a,b的弧

接着我们可以根据规则3

消去结点2和结点4

以及结点上面的“环”

分别用aa(a|b)*

和bb(a|b)*

这两个正规表达式来标记

从状态结点0到状态结点Z之间的两条弧

最后根据规则2

消去结点0

用(a|b)*(aa (a|b)*)|(bb(a|b)*)

来标记状态S到状态Z的弧

最后我们根据分配率

化简得到我们所要的正规式就是

(a|b)*(aa|bb)(a|b)*

那么反过来

我们根据正则表达式R

如何去构建FA

构建思路是这样子的

先是分解正则表达式

得到若干个规模适中的子正规表达式

为每一个子正规表达式

画出其最简的状态转换图

也就是状态转换子图

最后把所有的子图

组合在一起

就得到了完整的图

这个完整的图呢

就是我们要转换的有限状态自动机

它的状态转换图

接下来我们来看一下

从正则表达式到NFA转换的时候

所使用的Thompson算法

Thompson构造算法

其实是根据正规式的定义

按照正规式当中所含运算符的个数

递归给出的

假设x是等价的NFA它的初始状态结点

y是终止状态结点

我们来看下面的几个规则

规则1 如果正规式是空

那么对应的FA只有初态和终态

但是没有状态的转移

规则2 如果正规式是ε

那么对应的FA初态和终态之间

有一条标记为ε的弧

规则3 如果正规式是字母表上面的

任意终结符a

对应的FA初态和终态之间

有一条标记为a的弧

规则4 如果正规式是A

那么A是一个正规表达式

我们先为A构造一个不确定的

有限状态自动机

记作NFA(A)

初态和终态的结点分别是x和y

规则5 如果正规表达式是A|B

A和B都是正则表达式

那么先为A和B分别构造

两个不确定的有限状态自动机

NFA(A)和NFA(B)

初态x结点通过ε弧分别指向

这两个NFA的初始状态结点

两个NFA的终态结点分别通过ε弧

指向y结点

规则6 如果正规表达式是AB

那么先为A和B构造两个不确定的

有限状态自动机

NFA(A)和NFA(B)

NFA(A)它的终态通过ε弧指向

NFA(B)的初态

规则7 如果正规表达式是A*

那么先为正规表达式A

来构造有限状态自动机NFA(A)

接下来来构造NFA(A)上面的环

先用ε弧标记从NFA(A)终态

到初态的有向边

接着初态x结点通过ε弧分别指向

终态结点y和NFA(A)的

初始状态结点s1

最后NFA(A)的终止状态结点f1

通过ε弧再指向终止状态结点y

接下来我们为正规表达式(a|b)*ab

构造等价的NFA N

我们先按照这个Thompson算法

先来构建正规表达式a

正规表达式b

对应的NFA

那么接下来我们再来构建a|b的NFA

我们构造了正规式a|b它的

有限状态自动机

接下来就来构建正规式(a|b)*的

有限状态自动机

最后我们就用a弧连接节点8

再用b弧连接终态结点9

这样我们就得到了

(a|b)*ab对应的有限状态自动机

我们再给大家介绍一种

比较灵活的转换方法

在这种方法当中呢

首先 我们用正规式R构造一个如下

仅有两个结点的状态转换图

那么在这个状态转换图当中

x是初态

y是终态

我们按照所引入的

3条正规式的分裂规则

来分裂我们刚才的这个正规式R

接下来就是重复步骤2

直到每个弧上的标记

是只是Σ上面的一个字符

或者是ε为止

那么将所得到的NFA M

因为它包含ε弧

我们再进行确定化

就可以得到对应的DFA了

假设A和B都是正规式

我们来看针对正规式的运算

所引入的三条分裂规则

首先将正规式先放在仅有两个结点

x和y的状态转换图上

接下来就是分裂的方法了

规则1 对于正规式AB

在x和y结点中间增加一个x1结点

用A来标记从初态x到x1的弧

用B来标记从x1到终态结点y的弧

规则2 对于正规式A|B

将x和y节点之间

它的弧分裂成两条弧

分别用A和B来标记

规则3 对于正规式A B* C

在x和y结点中间增加x1结点

然后构建在x1上面标记为B的环

然后用A去来标记

从状态x节点到x1节点的弧

用C来标记从x1节点到终态结点y的弧

那么接下来我们就用

刚才我们所讨论的分裂方法

来构建 (a|b)*ab的这个状态转化图

首先我们把正规表达式(a|b)*ab

放在仅有两个结点x和y的

这个状态转换图上

接下来根据分裂规则1

将标记为正规式(a|b)*ab的弧

给它通过增加一个新的结点i

分裂成标记为正则式(a|b)*

和ab这两个正规式的两条弧

接下来利用规则3

在结点x和i之间增加一个结点j

构建结点j上面标记为a|b的环

接下来再利用规则2

将标记为a|b的弧分裂成从j状态

回到j状态节点的两条弧

分别用a和b来标记

最后我们利用规则1

在结点j和y之间增加一个k节点

将正规式ab分裂成

从节点j到节点k标记为a的弧

从节点k到节点y标记为b的弧

这样的话我们就得到了

那么这个正规式所对应的

有限状态自动机它的状态转换图

同学们

在一般情况之下

我们设计词法分析程序的步骤

是这样子的

先用RE来定义单词的结构

然后将RE转化成NFA

再将NFA转化成DFA

那么DFA化简

并且实现就可以得到

我们的词法分析程序了

关于词法分析的内容

我们就讨论到这里

谢谢大家