在编译原理中，正规式、NFA（非确定有穷自动机）、DFA、最简DFA的转换在词法分析中是十分重要的一个环节。

（正规式R到NFA的转化）

(2)状态集的a弧转换: 状态集I中的任何状态s经过一条a弧而能到达的所有状态的集合，定义为状态集I的a弧转换，表示为move(l,a)。

(3)状态集的a弧转换的闭包： la= ε-closure(move(l,a))。

对于输入字符集合∑={a1,a2…ak}，我们构造一张k+1列的表格（行数未做限制）。一般来来讲，步骤如下： （1）表格的第一行第一列的位置写的是从NFA的起始节点经过任意个ε所能到达的结点集合S0的ε-closure(S0)。 （2）接着填写该行剩余位置的信息，做法是在对应的位置上填写la= ε-closure(move(l,a))。Ia表示从该集合开始经过一个a所能到达的集合，经过一个a的意思是可以略过前后的ε。 （3）检查该行上的所有状态子集，如果未在第一列出现，则将该状态子集写到第一列。 （4）重复（2）（3）的步骤，直到所有状态子集均在第一列上出现即可。 （5）然后给状态子集重新编号，需要注意的是，包含原来终态的状态子集为新的终态，按照对应的转换函数f，构造对应的DFA即可。

预备知识 （1）无关状态 ①多余状态：对于一个状态Si ，若从开始状态出发，不可能到达该状态Si，则Si为多余（无用）状态。 ②死状态：对于一个状态Si，对任意输入符号a，若转到它本身后，不可能从它到达终止状态，则称为Si为死状态。S2为死状态。多余状态和死状态又称为无关状态。 （2）等价状态：若Si为自动机的一个状态，我们把从Si出发能导出的所有符号串集合记为L(Si)。设有两个状态Si和Sj，若有L(Si)=L(Sj)，则称Si和Sj是等价状态。 （3）可区别状态：Si，Sj不是等价状态即为可区别状态。一般有两种情况： ①终止状态和非终止状态是可区别状态。 ②状态Si，Sj对于∀a∈∑，必须转到等价的状态里面，否则称其实可区别的。

分割法求最简DFA的步骤

（1）首先将DFA的状态集进行初始划分，分成π=(S-Z,Z)。【其中Z为终态集合，S-Z为非终态，终态对于非终态是可以区分的】 （2）用下面的过程对π构造新的划分π new， 对π中每个组G，满足以下条件： ① 任意两个状态Si和Sj在同一组中 ② move(Si, a) 和move(Sj, a) 是到不同的组中 则说明Si和Sj是可区别的，可进行划分，在π new中用刚完成的对G的划分代替原来的G， 否则不可以进行划分。 （3）重复执行(2)的操作，直到π中每个状态集都不能再进一步划分为止。 （4）合并等价状态，在每个G中，取任意状态作为代表，删去其它状态。将删去的状态关系全部转到代表状态。 （5）删去无关状态，包括从其它状态到无关状态的转换弧都都删掉。