从NFA到DFA
NFA是非确定性的状态机，DFA是确定性的状态机。确定性和非确定性的最大区别就是：从一个状态读入一个字符，确定性的状态机得到一个状态，而非确定性的状态机得到一个状态的集合。如果我们把NFA的起始状态S看成一个集合{S}的话，对于一个状态集合S’，给定一个输入，就可以用NFA计算出对应的状态集合T’。因此我们在构造DFA的时候，只需要把起始状态对应到S’，并且找到所有可能在NFA同时出现的状态集合，把这些集合都转换成DFA的一个状态，那么任务就完成了。因为NFA的状态是有限的，所以NFA所有状态的集合的幂集的元素个数也是有限的，因此使用这个方法构造DFA是完全可能的。
为了形象地表达出这个算法的过程，我们将构造一个正则表达式，然后给出该正则表达式转换成NFA的结果，并把构造DFA的算法应用在NFA上。假设一个字符串只有a、b和c三种字符，判断一个字符串是不是以abc开始并且以cba结束正则表达式如下：
abc(a|b|c)*cba
通过上文的算法，可以得出如下图所示的NFA：
图5.7
现在我们开始构造DFA，具体算法如下：
1：把{S}放进队列L和集合D中。其中S是NFA的起始状态。队列L放置的是未被处理的已经创建了的DFA状态，集合D放置的是已经存在的DFA状态。根据上文的讨论，DFA的每一个状态都对应着NFA的一些状态。
2：从队列L中取出一个状态，计算从这个状态输出的所有边所接受的字符集的并集，然后对该集合中的每一个字符寻找接受这个字符的边，把这些边的目标状态的并集T计算出来。如果T∈D则代表当前字符指向了一个已知的DFA状态。否则则代表当前字符指向了一个未创建的DFA状态，这个时候就把T放进L和D中。在这个步骤里有两层循环：第一层是遍历所有接受的字符的并集，第二层是对每一个可以接受的字符遍历所有输出的边计算目标DFA状态所包含的NFA状态的集合。
3：如果L非空则跳到2。
现在我们开始对图5.7的状态机应用DFA构造算法。
首先执行第一步，我们得到：
图5.8
从上到下分别是队列L、集合D和DFA的当前状态。就这样一直执行该算法直到状态3进入集合D，我们得到：
图5.9
现在从队列L中取出{3}，经过分析得到状态集合{3}接受的字符集合为{a b c}。{3}读入a到达{4}，读入b到达{5}，读入c到达{6 7}。因为{4}、{5}和{6 7}都不属于D，所以把它们都放入队列L和集合D：
图5.10
从队列中取出4进行计算，我们得到：
图5.11
显然，对于状态{4}的处理并没有发现新的DFA状态。于是处理{5}和{6 7}，我们可以得到：
图5.12
在处理状态{5}的时候没有发现新的DFA状态，处理{6 7}在输入{a c}之后的跳转也没有发现新的DFA状态，但是我们发现了{6 7}输入b却得到了新的DFA状态{5 8}。把算法执行完，我们得到一个DFA：
图5.13
至此，对图5.7的状态机应用DFA构造算法的流程就结束了，我们得到了图5.13的DFA，其功能与图5.7的NFA等价。在DFA中，起始状态是0，结束状态是4E。凡是包含了NFA的结束状态的DFA状态都必须是结束状态。