This article does not have a corresponding language version
算法编译原理

EDIT1：更新原始算法的时间复杂度估计

EDIT2：更新优化后的算法实现

EDIT3: 重写了优化后的代码及代码分析。

EDIT4: 重写代码复杂度分析

EDIT5: 修改改进版本算法的分析，用Old/New替换B/A

NFA的基础

NFA的概念、构成要素可以参考这篇文章. 本文主要讨论如何模拟NFA.

模拟NFA的算法

ALGORITHM: NFA Simulation 的经典算法

算法

  • INPUT:

    1. 输入字符串str

    2. NFA nfa.

  • OUTPUT: ACCEPT / REJECT.

def sim_nfa(nfa, str):
  (s0, F) = nfa # NFA的开始状态s0和终结状态F
  S = ϵ-closure(s0) # 计算ϵ-closure(s), 即开始状态集. 
  for c in str:
    S = ϵ-closure(move(S, c)) #经过字符c之后,可以看作是状态S发生了转移 (即: S因为c变化了)
  if (S ∩ F != ∅) 
  	return ACCEPT
	else
  	return REJECT

时间复杂度

注：下面计算的是不带任何优化的情况下的算法最坏情况下时间复杂度。算法优化见下一节。

我们先来看ϵ-closure的计算流程：

def ε_closure(T):
  	closure = set(T) # 待计算的闭包,包含T中的所有状态.
    stack = list(T) # 使用栈进行深度优先遍历

    while stack:
        t = stack.pop()
        # 遍历所有从t出发的ε转移
        for all u in nfa.move(t, ϵ):
            if u is not in closure:
                closure.add(u)
                stack.push(u)
    return closure

上述代码的作用是计算ϵ闭包。也即，给定一个自动状态机的状态转移图，从指定的状态节点集合T出发，去找出所有沿着零条或者多条连续的ϵ边能抵达的所有节点。实际计算中给定的图极有可能存在ϵ环路，因此需要DFS/BFS配合visited标记来搜索。

这里的最坏情况就是前面所述的"找出零条或者多条连续的ϵ边能够抵达的所有节点的迭代“的迭代过程中迭代到了所有的transition（也即：每一条边都是ϵ）和所有的节点（路径不重复）。假设这里一共有n个状态，m个可能的转移，那么ϵ-closure的最坏时间复杂度就是O(nm)。

NFA Simulation 算法的代码第5行针对于长度为L的输入字符串，遍历其中的字符，对每一个字符都进行ϵ-closure计算。那么第4~5行的循环的时间复杂度是O(L*nm)

IMPLEMENT: NFA Simulation 的经典算法的改进实现

仔细观察上述伪代码不难发现，代码第3行和第5行做的事情是源源不断的将新发现的可达节点添加到S中。类似于BFS/DFS算法，我们可以用堆栈来模拟这个过程，不需要重复计算新的S并替换原来的集合。

《Compilers - Principles, Techniques, and Tools》这本书提到了这种思想，这里简单介绍一下这种思想的算法实现过程。

首先我们需要定义两个算法中用到的两个集合S_new、S_old，实际算法中我们将用栈(Stack)来存储这两个集合：

S_new = stack()
S_old = stack()

来看原算法第5行：

S = ϵ-closure(move(S, c))

我们将其改写为下面的摸样方便理解：

S_new = ϵ-closure(move(S_old, c))
S_old <== S_new

这里的S_old指的是新的循环迭代开始时的状态，也称为旧状态(Old States)。S_new是循环迭代完成之后的状态集合，也称为新状态(New States)，S_new实际上是下一次迭代开始前的S_old（可以理解在一次迭代中S_old是输入，S_new是输出，然后下一次循环迭代开始前将这次输出塞到输入里面方便开始下一次循环）。

这个状态S_old经过ϵ-closure(move(S_old, c))计算出经过字符c能够可达的所有节点。值得注意的是，这里计算出来的可达结点一定包含计算前集合S_new中的所有节点，因此我们可以理解这一行为：

S_new += NEW_STATES_OF_S(ϵ-closure(move(S_old, c)))

也即我们需要计算出ϵ-closure(move(S_old, c))计算出的新节点(NEW_STATES_OF_S负责判断哪些是计算出的新节点)，然后添加到集合S_new中。

再来观察伪代码sim_nfa，我们实际需要搞定第3行和第5行做的事情（这两行做的事情最耗时），整个算法就实现完毕了。

重申一下重要的事情：

  • S_new(New States)对于一次循环迭代来说是输出
  • S_old(Old States)对于一次循环迭代来说是输入

为了方便追踪某个节点是否在S_new（New States）上，我们需要一个数组或哈希表（或者其他的数据结构）：

AlreadyOn[S] == TRUE # S已经在New States上
AlreadyOn[S] == FALSE # S目前不在New States上

观察一下伪代码sim_nfa第三行S = ϵ-closure(s0)，我们要做的事情包括：

  • 计算S = ϵ-closure(s0)，并交换OldStates和NewStates（迭代完结果在S_new，在下一次迭代之前需要将其转移到S_old）。也可以将把结果直接放到S_old，方便直接开启第五行的迭代。
  • AlreadyOn[S] = TRUE, 标记这些节点S已知（已经在New States上了）。（为什么是在New States上？原因参见第一条：S = ϵ-closure(s0) 操作隐含S_new=ϵ-closure(s0), S_old=S_new两个操作。）

那么伪代码sim_nfa第5行S = ϵ-closure(move(S, c))要做的事情包括：

  • 计算ϵ-closure(move(S, c))。
  • 检查计算结果，结果中的节点如果没在New States上，那就添加上去。
  • 将本次循环迭代的输出（S_new）赋给输入（S_old）。方便开启下一轮循环。

算法伪代码

首先，我们需要定义公共函数，以及公共数据结构。

OldStates = [] # Stack
NewStates = [] # Stack
AlreadyOn = {} # Array or HashSet, to track whatever state s is in NewStates.
move = [] # 状态转移表，表中包含ϵ转移, 由sim_nfa函数负责填充

def addState(s):
	pass
	
def sim_nfa(nfa, str):
	pass

其中，函数addState的作用是根据给定的状态s，计算ϵ-closure(s)，并将其放置在NewStates里。

move数组是状态转移表。其中包含ϵ转移以及非ϵ转移，这是一个二重数组，move[s, i]表示当前状态s在经过字符或ϵ之后可以抵达的新状态节点，i可以是字符c（非ϵ转移）或者ϵ（ϵ转移）

addState函数

addState的实现特别简单，唯一值得注意的是代码中的去重操作，该操作保证了对于任意一个节点s而言，只会被添加到NewState一次。其实现伪代码如下：

# Add s into NewStates.
def addState(s):
	NewStates.push(s) #由于计算出来的ϵ-closure(s)结果必定包含s本身，因此这里直接将s推入NewStates栈。（因为我们允许0次转移，也即s呆在原地不动，s本身必定可以由s经过0次转移抵达）
	AlreadyOn[s] = TRUE
	for t in move[s, ϵ]:#遍历所有的ϵ转移
		if not AlreadyOn[t]: #给NewState去重
			addState(t)

sim_nfa函数

该算法接受一个nfa，一个字符串str。这个算法的目的是使用nfa去匹配字符串str，算法的运行结果要么匹配成功(ACCEPT), 要么匹配失败(REJECT).

算法的第一步，便是要计算起始状态s0，并将计算结果塞入OldStates里，方便开启算法循环。

def sim_nfa(nfa, str):
	# 从输入的NFA中取出起始状态集合S, 终结状态集合F，以及状态转移表move
	(s0, F, move) = nfa
	# 计算ϵ-closure(s)，
	addState(s)
	OldStates = NewStates
	NewStates = {}
	...

注意在计算完成之后，计算结果在NewStates(迭代输出)里，为了开启下一轮迭代，需要将NewStates的节点挪到OldStates里(迭代输入)。

或者，上述四行代码可以这样改写：新增一个addState函数的变体，其函数内部直接添加节点到OldStates而不是NewStates。这里就不展开实现了。

接下来便是算法的主循环。主循环迭代每一个输入字符来匹配目标NFA。

def sim_nfa(nfa, str):
	...
	for c in str:
		# 尝试计算S = ϵ-closure(move(S, c))，实现状态转移
		for s in OldStates: # OldStates: 输入的(右边的)状态集合S
			for t in move[s, c]: #遍历所有s节点沿着字符c的边能抵达的状态节点t
				if not AlreadyOn[t]: # 实际上节点只会被添加到NewStates一次，去个重
					addState(t)
			OldStates.pop(s)
		# 计算结束，结果在NewStates里(迭代输出)。
		# 在下一次迭代开始之前，需要将其挪动到输入的位置。
		# 下述代码实际执行的操作是OldStates += NewStates; NewStates.Clear()
		for s in newStates:
			NewStates.pop(s)
			OldStates.push(s)
			AlreadyOn[s] = FALSE
		...

值得注意是AlreadyOn[s]的语义实际上是本轮迭代中s是否已经在这一轮的NewStates中。因此在迭代的末尾完成NewStates和OldStates的元素交换之后需要将对应位置的AlreadyOn标志清空。

算法的最后，在所有迭代完成之后，需要判断一下结果状态节点集合S是否包含终结状态F，如果S于F相交则返回ACCEPT：

...
	S = NewStates
  return S ∩ F != ∅ ? ACCEPT : REJECT

新算法时间复杂度分析

假设一共有n个状态，m个可能的转移, 输入的字符串长度为L。

别看新算法中间计算S = ϵ-closure(move(S, c))套了三层循环，实际上整个算法流程就是，在每一次迭代，我们都是在发现新的未知转移，并添加新的未知节点到NewStates里。（为什么每一次都是走的是未知转移：假设我们从s经过h转移走到t节点：s—h–>t，当我们走到t之后，会将t添加到AlreadyOn上，也就是说，我们后面不会再从s出发走h到t了。）

我们来看sim_nfa中的循环：

for s in OldStates:
    for t in move[s, c]:
        if not AlreadyOn[t]:
            addState(t)
    OldStates.pop(s)

为了分析方便起见，我们假设addState的时间复杂度是O(1)。该代码片段的第2、3行实际上就是在发现新的未知非ϵ转移，也就是说，这段代码会从OldStates出发，遍历所有的非ϵ转移，并对转移过后的节点调用addStates。也就是说，假设addState的时间复杂度是O(1)，NFA中含有r个非ϵ转移，那么这个嵌套循环调用addState的时间时间度是O(r)。

再看上述代码片段的最后一行，OldStates.pop(s)，该操作的单次执行时间复杂度是O(1)，由于去重操作的存在，该操作至多会被执行n次，因此该操作的时间复杂度是O(n)。

再来看addState函数。

def addState(s):
	NewStates.push(s)        # O(1)
	AlreadyOn[s] = TRUE      # O(1)
	for t in move[s, ϵ]:     #遍历所有的ϵ转移
		if not AlreadyOn[t]: #去重
			addState(t)

addState函数的前两行操作的时间复杂度是O(1)。其中的循环会去遍历剩余未遍历所有的ϵ转移，针对每一个ϵ转移，会再次调用addState。由于去重操作的存在，这个递归调用不会去重复计算相同的节点和转移，通过sim_nfa循环调用addState，因为addState内递归调用addState去遍历剩余未遍历所有的ϵ转移的时间复杂度是O(m - r)。

考虑上for c in str的循环，总体时间复杂度就是O(L(r + m - r + n)) = O(L(m + n))

插个题外话：你还记得Ω(N) ,ω(N) ,Θ (N),o(N),O(N)的区别吗？

Ω(N) ,ω(N)是算法复杂度下界，是最佳情况；ω(N):渐近严格大于(复杂度必须大于N), Ω(N)非严格大于(复杂度可以是N)

Θ (N)是复杂度确切界，是准确情况

o(N),O(N)是复杂度上界，是最坏情况; o(N):渐近严格小于(复杂度必须小于N), O(N)非严格小于(复杂度可以是N)

E.O.F Ciallo～(∠・ω< )⌒★