admin 管理员组文章数量: 1086019
2024年4月16日发(作者：swift入门基础知识)
龙源期刊网
NFA的确定化过程简析
作者：刘杨
来源：《大经贸·创业圈》2020年第06期
龙源期刊网
【摘 要】 在编译原理的学习中，从上下文无关文法的初步理解进阶到词法分析过程，是
理解整个编译过程的关键一步;其中，确定性有限自动机（DFA）和非确定性有限自动机
（NFA）的等价与转换，是这一部分的难点之一。本文将首先介绍DFA和NFA相关的几个基
本概念，然后着重介绍确定性有限自动机（DFA）和非确定性有限自动机（NFA）的等价变化
过程。
【关键词】 编译原理 词法分析 DFA NFA 有限自动机
龙源期刊网
一、基本概念
（一）正规集和正规式
所谓正规集，就是一个集合，是一个字符的集合。正规指的就是，该集合中的字符，对于
我们所研究的程序设计语言来说，是合法的。正规式则是正规集的另一种表示方式。或者说，
在研究编译原理的过程中，用正规式来表示正规集。二者的对应关系可以参考如下示例：设有
字母表Σ，则Σ上的字符a和b都是正规式，它们分别表示Σ上的正规集{a}和{b}。
词法分析中的等价关系判定的充要条件，就是：被研究的两个对象，其所表示的正規式是
否相同。
（二）DFA和NFA
首先，FA（finite automaton），有限自动机，本质上就是状态转换图（表示词法分析器逐
个识别输入字符并进行状态转换的过程）。一个有限自动机由一个五元式组成：
S：有穷状态集;Σ：有穷输入字母表;f：状态转换函数;S0：初始状态;F：终态
有限自动机中的状态转换函数是其精髓所在。状态转换函数将词法分析器的状态转换过程
抽象为一个双输入单输出的函数，而这样的函数很容易使用矩阵来表示，从而使词法分析器的
工作过程得以数字化，进而可以使用代码来实现。
DFA（deterministic finite automaton），确定的有限自动机;
NFA（Nondeterministic finite automaton），非确定的有限自动机。
二者的区别主要有三点：
DFA的初始状态是唯一的，但NFA的初始状态可以不唯一（注意，DFA和NFA的终态
结点都可以不唯一）;
DFA中，每个状态的输入只能是单个字符，且不包括ε（空字符）;但是在NFA中，可以
是一个字或者单个字符或者ε;
DFA中，每个状态接收输入后的转换关系是一定的，但是在这一转换关系NFA中不是确
定的。
二、DFA和NFA之间的等价转换过程
龙源期刊网
通过以上三点区别，不难看出，DFA是NFA的一种特例，或者说NFA可以确定化为
DFA。接下来我们讨论NFA的确定化过程。根据DFA和NFA的三点区别，确定化的过程也
分为三步：初态唯一化、拆分输入、转换关系确定化。
为了方便讨论，我们以图1（a）为NFA状态转换图的示例。首先，引进新的初态结点X
和终态结点Y（X、Y不属于原NFA的状态集），从X到NFA的原初态集合中的任意一个结
点连一条ε弧，从原终态集合中的任意一个结点连一条ε弧到Y，使X、Y成为新的初态和终
态结点，完成初态结点的确定化，如图1（b）所示。这样并没有改变原NFA的识别能力。接
着，将图中弧线上的多个字符拆分，方法是在有个u个字符的弧线上，添加u-1个状态结点，
多字符弧线分解为一个字符一条弧线，效果如图1（c）所示。状态函数确定化的关键是，要
将每个状态所连接的ε弧和其本身的非ε弧到达的状态统一起来。这里要用到子集法。讨论子
集法之前，要先了解两个概念。
1.设有状态S，状态集I是整个状态集的一个子集，则定义I的ε-闭包——ε-closure（I）
为：若S∈I，则S∈ε-closure（I）;
若S∈I，则从S出发经过任意条ε弧而能到达的任何状态S’都属于ε-closure（I）。
即集合形式： ε-closure（I）= I∪{S’|从某个S∈I出发经过任意条ε弧能到达S’}。
2.设a是Σ中的一个字符，定义 Ia=ε-closure（J） ：
J为I中所有状态经过一条a弧而到达的状态集合;
将ε-closure（I）的定义套用在集合J上。
由此而达到的效果是，从I中的某个状态出发经过一条a弧而可以达到的所有状态都在Ia
之中。从而使得状态之间的转换变成状态集之间的转换。
接下来，先准备一个大集合 I0，在图3的状态转换图中，经过如下步骤：
1）从初始状态开始，计算每一个状态的I集合，放入 I0中;
2）再从I出发，计算每一个I的Ja（状态经过一条a弧到达的状态集合），再计算 Ia;
3）检查 I0中是否有 Ia，如果没有，就将 Ia放入I0中，将 Ia看作新的集合I，再计算其
Ja和Ia;
4）循环步骤2、3，直至所有的都出现在 I0中。
龙源期刊网
（这里请注意，步骤中的a代指的是状态转换图中的所有非ε终结符;示例的具体计算步骤
比较繁琐，但是并不难理解，在此不再详述）
至此，NFA和DFA的三方面差别都被消除。之后还可以对DFA进行简化使结果更加直
观。以上既是NFA向DFA的转换过程，也可以间接证明二者的等价。
【参考文献】
[1] 陈火旺，等.程序设计语言编译原理（第3版）[M].北京：国防工业出版社，2006： 46-
53
[2] [美] Andrew .现代编译原理[M].赵克佳，等，译.北京：人民邮电出版社，
2006： 18-20
作者简介：刘杨（1999——）男，汉族，河南信阳人，单位：河南大学计算机与信息工程
学院，本科，软件工程专业，软件工程：
版权声明：本文标题：NFA的确定化过程简析 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713199683a623559.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论