正则表达式

非确定有限状态机
我们可以将KMP算法看做一台由模式字符串构造的能够扫描文本的有限状态自动机，而对于正则表达式我们要将这个思想推广。
KMP的有限状态自动机会根据文本中的字符改变自身的状态。当且仅当自动机达到停止状态时它才找到了一个匹配。算法本身就是模拟这种自动机，这种自动机运行很容易模拟的原因是因为它是确定的：每种状态的转换都完全由文本中的字符所决定。
要处理正则表达式，就需要一种更加强大的抽象状态机。因为或操作的存在，自动机无法仅根据一个字符就判断模式是否出现；事实上，因为闭包的存在，自动机甚至无法知道检查多少个字符才会匹配失效。为了克服这些困难，我们需要非确定性的自动机：当面对匹配模式的多种可能时，自动机能够“猜出”正确的转换，也就是所谓的非确定有限状态自动机（NFA）。
Kleene定理是理论计算机科学中的一个重要结论，它证明了对于任意正则表达式都存在一个与之对应的非确定有限状态机（反之亦然）。
NFA中从一个状态转移到另一个状态规则与DFA有所不同：

• 如果当前状态和字母表中的一个字符相对应且文本中的当前字符和该字符相匹配，自动机可以烧过文本中的该字符并转换到下一个状态（匹配转换，具有唯一性）。
• 自动机可以通过红色的边转换到另一个状态而不扫描文本中的任何字符（可以转换至多种状态）。

以上充分说明了NFA和DFA之间的关键区别，NFA离开一个状态的转换有多种，因此从这种状态可能进行的转换是不确定的。但和DFA一样，列出所有状态的转换即可追踪NFA处理文本字符串的轨迹，而找到这一序列的方法就是系统的尝试所有的可能性。

判定一个长度为M的正则表达式所对应的NFA能否识别一段长度为N的文本所需的时间在最坏的情况下和MN成正比。

public boolean recognizes(String txt){
    Bag<Integer> pc = new Bag<Integer>();
    Directed dfs = new DirectedDFS(G,0);
    for(int v = 0; v<G.V(); v++)
        if(dfs.marked(v)) pc.add(v);

    for(int i = 0; i<txt.length(); i++){
        Bag<Integer> match = new Bag<Integer>();
        for(int v: pc)
            if( v<M)
                if(re[v] == txt.charAt(i) || re[v] == ".")
                    match.add(v+1）；
        pc = new Bag<integer>();
        dfs = new DirectedDFS(G,match);
        for(int v=0; v<G.V(); v++)
            if(dfs.marked(v)) pc.add(v);
    }
    for(int v: pc) if(v==M) return true;
    return false;
}

将正则表达式转化为NFA的过程在某种程度上类似于之前所说过的Dijkstra的双栈算法对表达式求值。

public class NFA{
    private char[] re;
    private Digraph G;
    private int M;

    public NFA(String regexp){
        Stack<Integer> ops = new Stack<Integer>();
        re = regexp.toCharArray();
        M = re.length;
        G = new Digraph(M+1);

        for(int i=0; i<M; i++){
            int lp = i;
            if(re[i] == '(' || re[i] == '|')
                ops.push(i);
            else if(re[i] == ')'){
                int or = ops.pop();
                if(re[or] == '|'){
                    lp = ops.pop();
                    G.addEdge(lp, or+1);
                    G.addEdge(or, i);
                }
                else  lp = or;
            }
            if( i<M-1 && re[i+1] == '*'){
                G.addEdge(lp, i+1);
                G.addEdge(i+1, lp);
            }
            if(re[i] == '(' || re[i] == '*' || re[i] == ')')
                G.addEdge(i, i+1);
        }
    }
    public boolean recognizes(String txt)
}