模拟NFA
现在已经有NFA了，接下去我们需要模拟运行它，模拟的过程需要遍历状态集合，也就是状态链表：
struct List
{
State **s;
int n;
};
模拟过程需要两个链表：clist是当前的状态集合，nlist是下一步可能转移的状态集合。循环体首先将clist初始化为只包含开始状态，然后每次循环向前走一步。（C语言没有集合的概念，因此只能使用链表来表示集合）
int
match(State *start, char *s)
{
List *clist, *nlist, *t;
/* l1 and l2 are preallocated globals */
clist = startlist(start, &l1);
nlist = &l2;
for(; *s; s++){
step(clist, *s, nlist);
t = clist; clist = nlist; nlist = t; /* swap clist, nlist */
}
return ismatch(clist);
}
为了避免每次循环都要重新分配一个链表，match函数在每次循环结束前会交换clist和nlist，并在下一次执行前将nlist初始化。
最后，如果clist中包含终结状态，则说明输入字符串匹配。
int
ismatch(List *l)
{
int i;
for(i=0; i<l->n; i++)
if(l->s[i] == matchstate)
return 1;
return 0;
}
addstate函数将一个状态加入到链表中，如果这个状态已经存在于链表中，那么不做任何操作。从头到尾扫描一遍链表是很低效的，取而代之，我们使用一个变量listid表示链表的迭代数。当addstate函数将状态s添加到链表中，它同时将s->lastlist赋值为listid。如果s->lastlist和listid之前已经相同，那么说明状态s早就已经被添加入当前链表中。如果s是一个split状态（`|?*+`操作符都会产生一个split状态，参见上一节），那么addstate会同时将s指向的两个状态加入到当前链表中，而不加入s状态（可以将split状态理解为一个空的状态）。
void
addstate(List *l, State *s)
{
if(s == NULL || s->lastlist == listid)
return;
s->lastlist = listid;
if(s->c == Split){
/* follow unlabeled arrows */
addstate(l, s->out);
addstate(l, s->out1);
return;
}
l->s[l->n++] = s;
}
startlist函数创建一个初始化状态链表，其中只包含开始状态：
List*
startlist(State *s, List *l)
{
listid++;
l->n = 0;
addstate(l, s);
return l;
}
最后，step函数在接受一个字符后递进，并使用clist来计算nlist：
void
step(List *clist, int c, List *nlist)
{
int i;
State *s;
listid++;
nlist->n = 0;
for(i=0; i<clist->n; i++){
s = clist->s[i];
if(s->c == c)
addstate(nlist, s->out);
}
}
性能表现
尽管我们在编写C语言版本的过程中，并没有考虑任何的性能优化，但是即便如此，我们的算法性能也依旧比那些流行的指数级算法要快得多。通过测试一些主流的语言可以更好的证明这一点。
考虑我们在开篇提出的正则表达式a?nan，对于一个使用回溯进行匹配的算法来说，在处理？操作符时有两种选择，对于a?n则一共有2^n种可能，时间复杂度为O(2^n)。
相比之下，Thompson算法中的状态链表长度至多为n，若输入字符串的长度为m，则时间复杂度为O(mn)。（这个时间复杂度十分接近线性复杂度，因为如果我们把正则表达式的n保持为一个常数，比如25，则对于任意长度为m的字符串，其匹配时间为O(25m)）
下图为不同算法的匹配时间对比：（注意到y轴的间隔不是等距离间隔，而是对数间隔，用对数划分能够更好地比较他们的区别）
从图中我们可以看出，Perl, PCRE, Python和Ruby全都使用递归回溯算法。尽管这里没有评估
Java，但是
Java使用的也是递归回溯算法，而PHP使用的也是PCRE库。
优化：NFA转为DFA
DFA的效率比NFA更高，因为DFA中，在任意时刻你只能处于一个状态，只有一种选择，绝不可能有第二种选择。任何一个NFA都可以转化为与之相对应的DFA，每个DFA中的状态是原来NFA的一组状态集合。
例如，如下是abab|abbb的NFA：
