This article does not have a corresponding language version
算法

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

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

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) # 开始状态集. 
  for c in str:
    S = ϵ-closure(move(S, c)) #经过字符c之后,可以看作是状态S发生了转移 (即: S因为c变化了)
  if (S ∩ F != ∅) 
  	return ACCEPT
	else
  	return REJECT

时间复杂度

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

代码第3行计算ϵ-closure(s0)的过程实际上是要遍历s0中的每一个状态s，再对于遍历的每一个s，去遍历所有的transition。找出所有的ϵ转移。假设一共有n个状态，m个可能的转移，那么ϵ-closure的时间复杂度就是O(nm)。

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

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

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

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

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

来看原算法第5行：

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

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

S_A = ϵ-closure(move(S_B, c))
S_B = S_A

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

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

S_A_NewStates += NEW_STATES_NOT_IN_S(ϵ-closure(move(S_B_OldStates, c)))

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

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

重申一下重要的事情：

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

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

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

观察一下伪代码sim_nfa第三行，我们要做的事情包括：

  • 计算S = ϵ-closure(s0)。把结果放到SB(Old States)，方便直接开启第五行的迭代（如果将结果放到SA(New States)，那么还需要做S_B = S_A步骤，将结果放到输入的位置，才能开启第五行循环）。
  • AlreadyOn[S] = TRUE, 标记这些节点S已知（已经在New States上了）。（为什么是在New States上？原因参见第一条：S = ϵ-closure(s0) 操作隐含S_A_NewStates=ϵ-closure(s0), S_B_OldStates=S_A_NewStates两个操作。）

那么伪代码sim_nfa第5行要做的事情包括：

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

具体实现：

OldStates = [] # Stack
NewStates = [] # Stack
AlreadyOn = {} # Array or Hashset
move = [] # 状态转移表，表中包含ϵ转移

# 计算ϵ-closure(s) (输入是单个状态s，不是集合)，结果保存到NewStates
def compute_ϵ_closure_and_addTo_NewStates(S):
    NewStates.push(s)
    AlreadyOn[s] = True
    for t in move[s, ϵ]: #查找对于节点s所有的ϵ转移，也即可以无条件转移到的节点
        if not AlreadyOn[t]:
            compute_ϵ_closure_and_addTo_NewStates(t)
            
# 计算ϵ-closure(s) (输入是单个状态s，不是集合)，但是结果保存到OldStates
def compute_ϵ_closure_and_addTo_OldStates(S):
    OldStates.push(s)
    AlreadyOn[s] = True
    for t in move[s, ϵ]: #查找对于节点s所有的ϵ转移，也即可以无条件转移到的节点
        if not AlreadyOn[t]:
            compute_ϵ_closure_and_addTo_OldStates(t)
            
def sim_nfa(nfa, str):
  (s0, F, move) = nfa # NFA的开始状态s0和终结状态F，状态转移表move
  # 计算流程1：S = ϵ-closure(s0) 计算开始
  for s in s0:
    compute_ϵ_closure_and_addTo_OldStates(s)
  # S = ϵ-closure(s0) 计算结束，此时计算结果在OldStates，方便直接进入下面的循环
  for c in str:
    # 计算流程2：S = ϵ-closure(move(S, c)) 计算开始
    for s in OldStates:
        for t in move[s, c]: # 我们从状态s经过字符c能抵达的状态t
            if not AlreadyOn[t]:
            	compute_ϵ_closure_and_addTo_NewStates(t)
    # 流程3：将本次计算输出赋给输入开启下一次循环
    OldStates = NewStates
    NewStates = {}
    # S = ϵ-closure(move(S, c)) 计算结束
  if (S ∩ F != ∅) 
  	return ACCEPT
	else
  	return REJECT

新算法时间复杂度分析

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

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

虽然我们不知道每一次循环迭代可能的转移有多少，但是我们知道转移一共就m条，状态节点一共就n个。那么我们针对于一个字符c而言，至多执行O(n+m)次转移。 （对于计算流程1、计算流程2都适用）

对于流程3，其时间复杂度至多为O(n)。其余的计算我们都可以看成是O(1)时间复杂度（比如说AlreadyOn可以用哈希表实现获得常数时间复杂度）

那么总体的时间复杂度是O(L(n+m))。

插个题外话：你还记得Ω(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～(∠・ω< )⌒★