NFA的确定化过程简析
发布时间：2023-04-07 09:03:12 来源：文档文库
小
中
大
字号：
龙源期刊网 http://www.qikan.com.cn NFA的确定化过程简析
作者：刘杨
来源：《大经贸·创业圈》2020年第06期
龙源期刊网 http://www.qikan.com.cn
【摘 要】 在编译原理的学习中，从上下文无关文法的初步理解进阶到词法分析过程，是理解整个编译过程的关键一步;其中，确定性有限自动机（DFA）和非确定性有限自动机（NFA）的等价与转换，是这一部分的难点之一。本文将首先介绍DFA和NFA相关的几个基本概念，然后着重介绍确定性有限自动机（DFA）和非确定性有限自动机（NFA）的等价变化过程。
【关键词】 编译原理 词法分析 DFA NFA 有限自动机
龙源期刊网 http://www.qikan.com.cn 一、基本概念 （一）正规集和正规式
所谓正规集，就是一个集合，是一个字符的集合。正规指的就是，该集合中的字符，对于我们所研究的程序设计语言来说，是合法的。正规式则是正规集的另一种表示方式。或者说，在研究编译原理的过程中，用正规式来表示正规集。二者的对应关系可以参考如下示例：设有字母表Σ，则Σ上的字符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之间的等价转换过程
龙源期刊网 http://www.qikan.com.cn 通过以上三点区别，不难看出，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 