NFA(Nondeterministic finite-state automata)是一种在字符串中寻找正则表达式匹配的算法，优点是查找文本的指针不回退，适用于在网络传输的报文中寻找正则表达式描述的目标（因为网络传输中报文是被分段接收的，且分段的方式不确定），在Robert的"Algorithms"第5.4节"Regular Expressions"中有详细介绍。
NFA算法可以分为定义和执行两部分，定义阶段和执行阶段。
定义阶段是将要查找的正则表达式（String类型）转换为一个有向图（Digraph类型），该图中的边是所有可以进行的空转换（见p795倒数第2行），定义阶段在书中"Building an NFA corresponding to an RE"一节，图示见p803，代码见p802），在代码表现为以一个正则表达式字符串为参数的NFA构造函数；
执行阶段就是判断待处理的文本中是否含有目标正则表达式（见"Simulating an NFA"一节，图示见p798），整个过程是一个循环过程，每次循环待处理文本指针前进一个字符，这次循环由两步组成，首先根据当前正则表达式指针所处位置（最初位置都是0）算出所有空转换可达位置（借助深度优先算法DirectedDFS，可达位置保存在变量pc中），然后将所有可达位置上的字符与待处理文本指针处的字符比较，如果一样则把正则表达式指针的后一位保存在变量match中。然后以match为初始位置重新构造DirectedDFS对象，进而得到可达位置集合pc，然后从中筛选匹配上的位置，如此循环，直到待处理文本指针到达文本尾部，如果pc中有正则表达式长度的那个元素（代表匹配成功的位置，书中代码用类成员M表示），说明匹配正则表达式成功，否则失败。
需要说明的是，从所有可达状态pc中筛选匹配上位置并放入match中之前，需要先将值为M的元素去掉，以用"(AB|AC)D"匹配"AABDC"为例，当目标文本指针等于4时，即指向"AABDC"的最后一个字符C时，pc中已经包含了最终状态11（正则串"((AB|AC)D)"的长度），因为AABD符合"(AB|AC)D"，但最后的C导致整个文本不匹配"(AB|AC)D"，所以结果仍然是匹配失败。
测试代码如下：
String token = "(AB|AC)D"; String regexp = "(" + token + ")"; // when test if target string "contains" regex, regexp = "(." + token + ".*)" NFA nfa = new NFA(regexp); String target = "AABDC"; if (nfa.recognizes(target)) { System.out.println("match: " + target); } else { System.out.println("not match: " + target); }