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

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) # 开始状态集. 这个运算请参见附1.
  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 的经典算法的改进实现

TBD.