【摘 要】 在编译原理的学习中，从上下文无关文法的初步理解进阶到词法分析过程，是理解整个编译过程的关键一步;其中，确定性有限自动机（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 W.Appel.现代编译原理[M].赵克佳，等，译.北京：人民邮电出版社， 2006： 18-20

作者简介：刘杨（1999——）男，汉族，河南信阳人，单位：河南大学计算机与信息工程学院，本科，软件工程专业，软件工程：