NFADFA

NFA是非确定性的状态机,DFA是确定性的状态机。确定性和非确定性的最大区别就是:从一个状态读入一个字符,确定性的状态机得到一个状态,而非确定性的状态机得到一个状态的集合。如果我们把NFA的起始状态S看成一个集合{S}的话,对于一个状态集合S’,给定一个输入,就可以用NFA计算出对应的状态集合T’。因此我们在构造DFA的时候,只需要把起始状态对应到S’,并且找到所有可能在NFA同时出现的状态集合,把这些集合都转换成DFA的一个状态,那么任务就完成了。因为NFA的状态是有限的,所以NFA所有状态的集合的幂集的元素个数也是有限的,因此使用这个方法构造DFA是完全可能的。

为了形象地表达出这个算法的过程,我们将构造一个正则表达式,然后给出该正则表达式转换成NFA的结果,并把构造DFA的算法应用在NFA上。假设一个字符串只有abc三种字符,判断一个字符串是不是以abc开始并且以cba结束正则表达式如下:

abc(a|b|c)*cba

通过上文的算法,可以得出如下图所示的NFA

5.7

现在我们开始构造DFA,具体算法如下:

1:把{S}放进队列L和集合D中。其中SNFA的起始状态。队列L放置的是未被处理的已经创建了的DFA状态,集合D放置的是已经存在的DFA状态。根据上文的讨论,DFA的每一个状态都对应着NFA的一些状态。

2:从队列L中取出一个状态,计算从这个状态输出的所有边所接受的字符集的并集,然后对该集合中的每一个字符寻找接受这个字符的边,把这些边的目标状态的并集T计算出来。如果TD则代表当前字符指向了一个已知的DFA状态。否则则代表当前字符指向了一个未创建的DFA状态,这个时候就把T放进LD中。在这个步骤里有两层循环:第一层是遍历所有接受的字符的并集,第二层是对每一个可以接受的字符遍历所有输出的边计算目标DFA状态所包含的NFA状态的集合。

3:如果L非空则跳到2

现在我们开始对图5.7的状态机应用DFA构造算法。

首先执行第一步,我们得到:

5.8

从上到下分别是队列L、集合DDFA的当前状态。就这样一直执行该算法直到状态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.13DFA,其功能与图5.7NFA等价。在DFA中,起始状态是0,结束状态是4E。凡是包含了NFA的结束状态的DFA状态都必须是结束状态。