之前提到了经过通过NFA来构造DFA(http://www.jb51.cc/article/p-sihorzyw-sq.html),现在继续来忽悠下,直接从正则表达式构造DFA。嗯,还有个附加的DFA极小化。
直接构造DFA,大致分为3步:构造语法分析树、计算followpos函数(难点)、生成DFA。
以正则表达式(a|b)*abb为例:
1、构造语法分析树:
这个不多说,看图应该就能明白:
(给每一个标号赋予一个独有的整数)
2、计算followpos函数:
首先需要计算一些辅助函数:nullable(n),firstpos(n),lastpos(n)→followpos(n)
(截图流又来了……)
嗯,这三个函数应该还是比较好理解的,nullable辅助计算first和last的。而firstpos(n)表示的就是该子表达式可能出现的首字符的标号(之前独一无二的整数)集合,同样lastpos则是可能的最后面字符的标号集合。(lastpos可以同理得到)
然后就是我们的followpos函数了
这个函数的理解可能有点难度,就是求q的集合,而q则是符合上面那个条件的,其实可以理解为该子表达式可以接的字符(接了之后还属于该语言)
然后有2个规则来计算followpos:
嗯,针对cat节点(也就是与),左边节点c1的lastpos(c1)中的每个标号的followpos值都包含firstpos(c2)的标号;同样的,对于star节点,lastpos(n)中的每个标号的followpos值都包含firstpos(n)中的标号。(对于|节点,忽视掉……)
实际计算的过程中,建议可以先罗列出1、2、3……n,然后从语法分析树开始从根往下应用这2个规则,期间不断为各个标号的followpos添加值。
最后可以得到如下:
3、构造DFA:
这简单了,初始状态为firstpos(root),这里为A{1,2,3},然后分别找对应a为1和3,b为2。所以a的转换为B=Dtran[A,a]=followpos(1)Ufollowpos(3)={1,3,4}。有印象了吧,前面一篇讲到NFA到DFA也是有这么个类似的流程,一直下去直到没有没标记的状态即可。
嗯,差点忘了,终止状态是那些包含了和结束标记#对应的位置(给结束标志赋予的独一无二的整数)的状态。
这样就大功告成了!
接下里是DFA的最小化:
给算法如下:
看起来有点难懂,跟着一个实例走一般都有助于理解算法的。其实记住每次划分为更小的组的时候,要使得两个状态s和t在同一个小组中当且仅当对于所有的输入符号a,状态s和t在a上的转换都到达新的分组中的同一组。嗯,每次分组都满足这么个条件,知道再也分不了,就搞定了。
嗯,我打算偷懒不写了……