关于NFA的重要状态
我们将具有非ε出转移的NFA状态称为NFA的重要状态(Important state)。这里我直接贴定义原文了，这个好理解。
Importance State: We call a state of an NFA important if it has non-ϵ out-transition.
如何判定两NFA States相等
- 拥有完全相同的Importance states
- 要么都有Accept State，要么都没有。
相关算法的回顾
我们来回顾一下Regex-NFA的算法，看看如何跳过NFA直接到DFA。回顾一下McNaughton-Yamada-Thompson Algorithm(从Regex产生的语法树生成NFA的算法)，不难发现：NFA的Important State只有在Basis部分才会生成。其推导部分会产生带ϵ的节点—-根据定义，这个就不是Important State了。
先举个栗子
假设我们有正则表达式(a|b)*abb。我们首先需要将其转换到对应的语法树：
其中◯节点（操作符）代表的是cat-node (concatenation)， 是用于直接拼接两个字串的操作符。|(or-node),**(star-node)*节点对应于原正则表达式中的对应操作符，分别表示或和匹配零个或多个。
Regex可以拆分为操作数和操作符两部分。前面提到了操作符，剩下的a,b就是操作数。这个可以类比成数学表达式，a+b中的ab是操作数，+是操作符。
我们尝试将这个语法树转换到NFA，可以发现，非ϵ叶子节点其实就是所谓的Important State，因为叶子节点的NFA转换过程都是在Basis部分完成的，只有非叶子节点才涉及到了推导部分。也就是说，Regex产生的语法树中的叶子节点对应于原Regex的操作数。
最后我们给叶子节点上的操作数节点编上号，这个编号代表这个非ϵ叶子节点在语法树中的位置(Position)，1～5号分别对应于与原Regex的对应关系如下：
(a|b)*abb
1 2 345
最后面的6号叶子节点#是一个特殊的节点。这是一个伪节点。
Augmented RE
前面的图中的6号操作符是一个特殊的操作符。其对应的NFA状态节点其实是一个伪状态，由于Accept State实际上没有非ϵ out-transition，因此Accept State实际上不符合Important State的定义。我们可以引入一个伪状态来解决这个问题。这个伪状态代表Regex的结尾。这样5号节点就符合Important State的定义了。
用于语法树节点的几个函数
语法树节点定义有四个函数:nullable, firstpos, lastpos, followpos. 先解释这些函数是什么。
这四个函数是什么
-
nullable(n)代表以n为根节点的语法树对应的Regex的语言是否包含ϵ。说人话就是，以n为根节点的语法树对应的Regex能不能匹配上ϵ。对于正则来说，就是n对应的正则能不能匹配上空串。继续上图的例子。*节点的nullable = True。因为*表示匹配零个或多个。 -
firstpos(n)代表以n为根节点的语法树对应所有可能的派生语言中所有可能能匹配上首个符号的节点位置集合。这个定义稍微有些拗口，其实就是找这个语法树对应的正则表达式所有能匹配到的字符串，然后对于每一个字符串，去找哪个语法树n上的节点能匹配上字符串的第一个符号。再简化一些，就是给定语法树n，找哪些节点位置能匹配到字符串的第一个符号。对于上图的例子，*号节点的firstpos是{1,2},因为1号节点(a)和2号节点(b)都有可能出现在匹配到的字符串的第一个符号。 -
lastpos(n)与firstpos(n)类似，只不过这个是找哪些节点能匹配上字符串的最后一个符号。 -
followpos(n)比较麻烦，这个是已知当前匹配位置p能匹配上字串的某个符号，然后找哪些节点位置q能匹配上字串的下一个符号。继续拿上图举例，followpos(1)的下一个可能出现的符号有a(1), b(2), a(3),因此followpos(1) = {1,2,3}。
这四个函数怎么算
看完这四个函数的概念之后就要计算这四个函数了。第四个函数followpos比较麻烦，先看前三个：
nullable, firstpos, lastpos
| Node n | nullable | firstpos | lastpos |
|---|---|---|---|
| 叶子节点ϵ | True | ∅ | ∅ |
| 具有Position i的非ϵ叶子节点 | False | {i} | {i} |
| “或"节点 or-node $n = c_{1}\mid c_{2}$ | $nullable(c_{1}) \| nullable(c_{2})$ | $firstpos(c_{1}) \cup firstpos(c_{2})$ | $lastpos(c_{1}) \cup lastpos(c_{2})$ |
“拼接"节点 cat-node ◯ $n = c_{1}c_{2}$ |
$nullable(c_{1}) \&\& nullable(c_{2})$ | if $nullable(c_{1})$: $firstpos(c_{1}) \cup firstpos(c_{2})$else: $firstpos(c_{1})$; | if $nullable(c_{2})$: $lastpos(c_{1}) \cup lastpos(c_{2})$else: $lastpos(c_{2})$; |
* star-node $n = c_{1}^{*}$ |
true | $firstpos(c_{1})$ | $lastpos(c_{1})$ |
简单说一下“拼接”节点 (cat-node )◯ 的nullable, firstpos是怎么来的, lastpos与firstpos的情况类似：
nullable: $n = c_{1}c_{2}$，n可能为ϵ的条件就是$c_{1}c_{2}$同时为ϵ。
firstpos: $n = c_{1}c_{2}$，这个要分两种情况讨论：
- $c_{1}$不可能为ϵ，那么$firstpos(c_{1}c_{2})$其实就是等同于$firstpos(c_{1})$
- $c_{1}$可能为ϵ，那么就要将$c_{1}$为ϵ（$firstpos(c_{1}c_{2}) = firstpos(c_{2})$）和$c_{1}$不为ϵ（$firstpos(c_{1}c_{2}) = firstpos(c_{1})$）的情况都考虑进去。结果就是这两种情况的并集：$firstpos(c_{1}c_{2}) = firstpos(c_{1}) \cup firstpos(c_{1})$
followpos
followpos的计算分两种情况。
- 若
n是"拼接"节点 cat-node，那么n的左子树上的所有lastpos的followpos都是n的右子树上的所有firstpos。 - 若
n是*star-node，那么n的所有lastpos的followpos都是n的所有firstpos。
这两种情况可以参考下面两张图：
举个简单的栗子…
继续以之前的正则表达式regex为例举栗子：
-
1,2号节点的
followpos={1,2,3}（先看*节点，再看*节点上面的◯节点，分别应用followpos的两种情况来计算followpos） -
followpos(6) = ∅: 这是因为6号节点已经没有下一个节点了。
《关于闲的无聊把语法树节点用followpos串起来看看会发生什么这回事》
首先我们把所有的followpos计算出来：
| Position #n | followpos(n) |
|---|---|
| 1 | {1,2,3} |
| 2 | {1,2,3} |
| 3 | {4} |
| 4 | {5} |
| 5 | {6} |
| 6 | ∅ |
我们来把语法树节点用followpos串起来试试！
可以发现，1和2号节点实际上就是firstpos(root)的结果。这个图稍加改造，就变成了除了#节点之外，其他节点不包含ϵ的NFA：
这里我们把firstpos(root)的结果当成了NFA的起始状态(Start States)。因为firstpos(root)刚好就是原正则表达式匹配的起点。
将Regex直接转换到DFA
算法
这个算法其实就是把NFA转DFA的算法和上面介绍的构建NFA的方法结合起来。
注：在往下看之前最好回顾一下NFA转DFA的算法。
此算法分为三步：
- 将原正则表达式
r改写成(r)#，然后将其构造成语法树T。构造出的语法树根节点定为n0。 - 用计算T上各个节点的
nullable,firstpos,lastpos,followpos。 - 利用下面的方法构建Dstates,Dtrans:
Dstates = {unmarked firstpos(n0)}
while unmarked S in Dstates:
Mark S; # 避免重复处理
for all symbols a in Σ: # Σ就是Alphabet
# 对于S中symbol a对应的所有节点p,计算其并集，并将其赋给U.
U = U ∪ followpos(p) for p in S if p correspond to symbol a （*）
if U is not in Dstates:
Add unmarked U to DStates
Dtrans[S, a] = U
其中标(*)的一行可以改写成下面的公式方便理解：
继续举个栗子
假设我们需要转换正则表达式(a|b)*abb。
第一步，将原正则表达式改写成(a|b)*abb#，并构造出语法树,其根节点为n0：
第二步，计算nullable,firstpos,lastpos,followpos：
| Position #n | followpos(n) |
|---|---|
| 1 | {1,2,3} |
| 2 | {1,2,3} |
| 3 | {4} |
| 4 | {5} |
| 5 | {6} |
| 6 | ∅ |
第三步，构造DFA：
-
目标Alphabet为正则
[ab]对应的集合，也即{a,b} -
DFA的起始状态集合为firstpos(n0)，也就是 {1,2,3}，Dstates = {Unmarked{123}}
-
进入主循环, S={123}, Mark S{123}，
2a. a = ‘a’, S中与’a’对应的节点有{13}, 分别计算followpos并取并集, 结果是U = {1234}
2a. 将unmarked U加入集合Dstates, 此时Dstates = {marked{123}, unmarked {1234}}
2a. Dtrans[S={123}, ‘a’] = {1234}
2b. a = ‘b’, S中与’b’对应的节点有{2}, 分别计算followpos并取并集, 结果是U = {123}
2b. 由于U={123}已经在集合Dstates，因此忽略上一步2b计算出的结果
2c. Dtrans[S={123}, ‘b’] = {123}
2d. 本次循环结束，Dstates={marked{123}, unmarked {1234}}。
-
重复第2步，直到Dstates没有可用的unmarked状态集合为止。
其中0～2步骤构造的DFA如下图所示：
完整跑完整个算法最终构造出的DFA如下图所示：
DFA状态集合最小化
如果我们将正则表达式先转换为NFA,再从NFA转换到DFA,其最终结果会是下面这个样子：
画出其状态转移表：
| DFA STATE | a | b |
|---|---|---|
| A | B | C |
| B | B | D |
| C | B | C |
| D | B | E |
| E | B | C |
可以看到，DFA 状态A和C在转移函数上是一样一样的：在经过a和b能够到达的节点是一致的。为什么会造成这种情况？是因为我们在构造完成NFA之后，在将NFA转换到DFA的过程中，构造出的DFA节点A, C的来源NFA节点不一样。
这里有一个很重要，也很有意思的结论：
The matter of the names of states is minor.
这句话的意思是说，在Regex-NFA,NFA-DFA的过程中，我们生成的最终DFA状态转移表中的“名字”是可以忽略的。这里的名字是指的是该DFA节点对应哪些NFA节点，换句话说，我们可以忽略转移表上的DFA节点是从哪些NFA节点转换而来的，反正最终执行DFA匹配字串的时候我们又用不到这个NFA-DFA的“中间产物”，我们只需要用到最终的DFA状态转移表。
怎么区分DFA的状态
为了达成DFA集合最小化，我们需要一个方法能够将DFA的状态区分开。如果两个DFA状态不能够被区分开，那么我们就认为这两个状态是可以合并的。
先引入两段论述。
String
xdistinguishes statesfrom statetif exactly one of the states reached fromsandtby following the path with labelxis an accepting state.
State
sis distinguishable from statetif there is some string that distinguishes them.
这两段论述其实就已经把如何区分任意两个DFA状态讲的明明白白了：
如果：我们有一个字符串x, 状态s经过x的过程中能抵达Accepting State, 而状态t不行，那么我们就可以说：字符串x 区分了状态s和t；如果存在这么一个字符串x, 那么我们可以认为这两个两个状态能被互相区分
举个栗子
拿上面的DFA状态转移图举栗子。状态A和B是能够互相区分的，因为状态B经过支付串bb之后能抵达Accepting State(E)，而A不行。
状态A和C则完全不同：在经过同一任意字符串之后，A和C要么同时抵达Accepting State(E)（比如说abb），要么同时都抵达不了Accepting State节点，因此，我们认为状态A和C是不可相互区分开的。
最后一个栗子，任何非终结节点和终结节点都是可区分的。区分它们的是空字串ϵ。
DFA状态集合最小化算法
集合最小化的算法步骤有点像是数学归纳法。该算法通过不断的将原状态集合按照可区分性进行分区分组。最终将不可区分的状态放在一组，组与组之间是可区分的。
该算法的核心在于维护“组与组之间是可区分的”这个关键属性。算法的步骤如下：
- 将原DFA状态集合S分成两组, F 和 S - F。其中F是终结状态集合。S - F代表S内除了终结状态之外的所有状态。很明显，这一步产生的
F和S - F是可区分的。定义Π = {F, S - F}，也就是Π代表了我们的当前分区（我们当前分了F, S - F两区） - 循环应用下面的算法来产生新的分区，一直循环到没有新分区产生为止：
for group G in Π:
尝试将G分为subgroups, 使得两个状态s和t在于同一subgroup内 当且仅当这两状态在经过所有可能的输入符号对应的状态转移之后，其状态转移之后的节点也还在这个subgroup内。
将G替换为上面产生的新的groups // 最坏情况下，上面没有产生新的groups.我们就将G原封不动的塞回Π。
在每次循环迭代的过程中，我们不停的寻找当前分组内有没有继续可细分的分组。也就是说，每一次迭代，“组与组之间是可区分的”这个关键属性得以保持。
当我们达到了最坏（也是最终情况），细分操作没有继续产生新的subgroups，此时整个分组具有两个关键属性：
A. 每两个Groups之间都是可区分的
B. 每一个Group都不能继续拆成新的subgroups. 换句话说，我们再也不能通过继续细分Groups来达到区分同一Groups内节点的目的。换句话说，此时每一个Group内的节点都是不可区分的。
~~（怎么样？有没有数学归纳法那味了？）~~乐（
接下来的步骤就是将不可区分的Group内的节点归一化抽象成一个DFA节点就行了：
TBD。（等我写完啊Kora！，我可能会考虑搞一个动图来解释一下DFA节点分组的流程
E.O.F Ciallo～(∠・ω< )⌒★