public void NFATests()
        {
            var a = new NFA<char>();

            // "a" automaton
            a.AddTransition(a.Start, new State { Final = true }, 'a');
            a.Initial();

            a.Trigger('a');
            Assert.That(a.Current.Contains(a.LastAdded), Is.True);

            a.Initial();
            Assert.That(() => a.Trigger('b'), Throws.TypeOf<StateNotFoundException>());

            // "abcd" automaton
            a = new NFA<char>();
            a.AddTransition(a.Start, new State(), 'a');
            a.AddTransition(a.LastAdded, new State(), 'b');
            a.AddTransition(a.LastAdded, new State(), 'c');
            a.AddTransition(a.LastAdded, new State { Final = true }, 'd');
            a.Initial();

            foreach (char c in "abcd") {
                Assert.That(a.Current.Contains(a.LastAdded), Is.False);
                a.Trigger(c);
            }
            Assert.That(a.Current.Contains(a.LastAdded), Is.True);
            Assert.That(() => a.Trigger('b'), Throws.TypeOf<StateNotFoundException>());
        }

        public void AddExpression(string name, string regex)
        {
            using (var stream = new StringReader(InfixToPostfix.Convert(regex)))
            {
                while (stream.Peek() != -1)
                {
                    var c = (char) stream.Read();
                    switch (c)
                    {
                        case '.': _stack.Concatenate(); break;
                        case '|': _stack.Unite(); break;
                        case '*': _stack.Iterate(); break;
                        case '+': _stack.AtLeast(); break;
                        case '?': _stack.Maybe(); break;
                        default:
                            var a = new NFA<char>();
                            a.AddTransition(a.Start, new State(), c == '\\' ? Escape((char) stream.Read()) : c);
                            _stack.Push(a);
                            break;
                    }
                }

                var top = _stack.Peek();
                top.LastAdded.Final = true;
                top.SetName(top.LastAdded, name);
            }
        }

        public void AddStates(IDictionary<Mode, State> modeMap, CodePointEquivalenceClasses equivalenceClasses, NFA<LexerAction> nfa, int priority, Channel defaultChannel)
        {
            var states = Expression.AddTo(nfa, equivalenceClasses);

            foreach(var mode in Modes)
                nfa.AddEpsilonTransition(modeMap[mode], states.Start);

            nfa.SetFinal(states.End);

            // Set Action
            nfa.SetData(states.End, new LexerAction(priority, GetValueAction(), GetModeActions(), GetEmitAction(defaultChannel), GetCodeAction()));
        }

        public LTLMonitor(ITLFormula formula)
        {
            var tpositiveNFA = translator.GetBuchiAutomaton (formula).ToNFA();
            var tnegativeNFA = translator.GetBuchiAutomaton (formula.Negate ()).ToNFA();

            positiveNFA = tpositiveNFA.Determinize ();
            negativeNFA = tnegativeNFA.Determinize ();

            currentNegative = negativeNFA.InitialNode;
            currentPositive = positiveNFA.InitialNode;

            UpdateStatus ();
        }

        private static NFA RepeatOnceOrMore(NFA nfa)
        {
            // Add an epsilon transition from the accept state back to the start state
            NFA.State oldAcceptState = nfa.States.First(f => f.AcceptState);
            nfa.Transitions.Add(new Transition<NFA.State>(oldAcceptState, nfa.StartState));

            // Add a new accept state, since we cannot have edges exiting the accept state
            var newAcceptState = new NFA.State { AcceptState = true };
            nfa.Transitions.Add(new Transition<NFA.State>(oldAcceptState, newAcceptState));
            nfa.States.Add(newAcceptState);

            // Clear the accept flag of the old accept state 
            oldAcceptState.AcceptState = false;

            return nfa;
        }

        private static NFA Accept(CharSet acceptCharacters)
        {
            // Generate a NFA with a simple path with one state transitioning into an accept state.
            var nfa = new NFA();
            var state = new NFA.State();
            nfa.States.Add(state);

            var acceptState = new NFA.State { AcceptState = true };
            nfa.States.Add(acceptState);

            nfa.Transitions.Add(new Transition<NFA.State>(state, acceptState, acceptCharacters));

            nfa.StartState = state;

            return nfa;
        }

 public void AddExpression(string name, string regex)
 {
     var stream = new StringReader(InfixToPostfix.Convert(regex));
     while (stream.Peek() != -1)
     {
         var c = (char) stream.Read();
         NFA<char> a;
         switch (c)
         {
             case '.':
                 _stack.Concatenate();
                 break;
             case '|':
                 _stack.Unite();
                 break;
             case '*':
                 _stack.Iterate();
                 break;
             case '+':
                 _stack.AtLeast();
                 break;
             case '?':
                 _stack.Maybe();
                 break;
             case '\\':
                 char n = (char) stream.Read();
                 a = new NFA<char>();
                 a.AddTransition(a.Start, new State(), Escape(n));
                 _stack.Push(a);
                 break;
             default:
                 a = new NFA<char>();
                 a.AddTransition(a.Start, new State(), c);
                 _stack.Push(a);
                 break;
         }
     }
     var automaton = _stack.Peek();
     automaton.LastAdded.Final = true;
     automaton.SetName(automaton.LastAdded, name);
 }

 public override void ToNFA(NFA pad, int from, int to)
 {
     throw new InvalidOperationException();
 }

 public override LAD Reify(NFA pad)
 {
     return this;
 }

    public LexerState Next(NFA nf, int ch)
    {
        LexerState l;
        if (dfc.TryGetValue(ch, out l))
            return l;
        l = new LexerState(nf);
        for (int i = 0; i < nstates.Length; i++) {
            int bm = nstates[i];
            for (int j = 0; j < 32; j++) {
                if ((bm & (1 << j)) == 0)
                    continue;
                foreach (NFA.Edge e in nf.nodes[32*i + j].edges) {
                    if (e.when != null && e.when.Accepts(ch))
                        l.Add(e.to);
                }
            }
        }

        nf.Close(l);
        LexerState cl;

        if (!nf.dfashare.TryGetValue(l, out cl)) {
            nf.dfashare[l] = cl = l;
        }
        dfc[ch] = cl;
        return cl;
    }

    public static Lexer GetLexer(Frame fromf, STable kl, LAD[] lads, string title)
    {
        LexerCache lc = kl.GetLexerCache();
        Lexer ret;
        if (lc.nfas.TryGetValue(lads, out ret))
            return ret;
        if (lc.parent != null && lc.parent.mo.name != "Cursor" && lc.parent.mo.name != "Any") {
            ret = GetLexer(fromf, lc.parent.mo, lads, title);
            foreach (string u in ret.pad.used_methods) {
                if (lc.repl_methods.Contains(u))
                    goto anew;
            }
            if (LtmTrace)
                Console.WriteLine("Reused {0} alternation lexer for {1} in {2}",
                        title, lc.parent.mo.name, kl.name);
            return lc.nfas[lads] = ret;
        }
        anew:
        if (LtmTrace) {
            Console.WriteLine("Need new alternation lexer for {0} in {1}",
                    title, kl.name);
        }
        NFA pad = new NFA();
        pad.cursor_class = kl;
        LAD[] lads_p = new LAD[lads.Length];
        pad.outer_stack.Add(fromf);
        pad.info_stack.Add(fromf.info);
        for (int i = 0; i < lads_p.Length; i++)
            lads_p[i] = lads[i].Reify(pad);

        ret = new Lexer(pad, title, lads_p);
        lc.nfas[lads] = ret;
        return ret;
    }

        public static NFA And(NFA first, NFA second)
        {
            // Create a new NFA and use the first NFAs start state as the starting point
            var nfa = new NFA { StartState = first.StartState };

            // Change all links in to first acceptstate to go to seconds 
            // start state
            foreach (var edge in first.Transitions.Where(f => f.To.AcceptState))
            {
                edge.To = second.StartState;
            }

            // Remove acceptstate from first
            first.States.Remove(first.States.First(f => f.AcceptState));

            // Add all states and edges in both NFAs
            // Second NFA already has an accept state, there is no need to create another one
            nfa.AddAll(first);
            nfa.AddAll(second);

            return nfa;
        }

 private static NFA RepeatZeroOrOnce(NFA nfa)
 {
     // Easy enough, add an epsilon transition from the start state
     // to the end state. Done
     nfa.Transitions.Add(new Transition<NFA.State>(nfa.StartState, nfa.States.First(f => f.AcceptState)));
     return nfa;
 }

 public virtual void QueryLiteral(NFA pad, out int len, out bool cont)
 {
     len = 0; cont = false;
 }

    public Frame list_common(bool eval, Frame th, Variable var)
    {
        VarDeque iter = Builtins.start_iter(var);
        List<object> toks = new List<object>();
        List<LAD> lads = new List<LAD>();

        NFA pad = new NFA();
        pad.cursor_class = st.ns.klass;

        while (Kernel.IterHasFlat(iter, true)) {
            Variable svar = iter.Shift();
            P6any sobj = svar.Fetch();

        retry:
            if (sobj.Isa(Kernel.RegexMO)) {
                toks.Add(sobj);

                pad.outer_stack.Add(Kernel.GetOuter(sobj));
                pad.info_stack.Add(Kernel.GetInfo(sobj));
                lads.Add(pad.info_stack[0].ltm.Reify(pad));
                pad.outer_stack.Clear();
                pad.info_stack.Clear();
            } else if (eval) {
                sobj = Builtins.compile_bind_regex(th,
                        sobj.mo.mro_raw_Str.Get(svar));
                svar = Kernel.NewROScalar(sobj);
                goto retry;
            } else {
                string str = sobj.mo.mro_raw_Str.Get(svar);
                toks.Add(str);
                lads.Add(new LADStr(str));
            }
        }

        int[] cases = (new Lexer(pad, "array_var", lads.ToArray())).
            Run(global.orig_s, st.pos);

        Frame nth = th.MakeChild(null, ArrayHelperSI, Kernel.AnyP);
        nth.lex0 = MakeCursor();
        nth.lex1 = toks;
        nth.lex2 = cases;

        return nth;
    }

        public static NFA Or(NFA a, NFA b)
        {
            var nfa = new NFA();

            // Composite NFA contains all the and all edges in both NFAs
            nfa.AddAll(a);
            nfa.AddAll(b);

            // Add a start state, link to both NFAs old start state with
            // epsilon links
            nfa.StartState = new NFA.State();
            nfa.States.Add(nfa.StartState);

            nfa.Transitions.Add(new Transition<NFA.State>(nfa.StartState, a.StartState));
            nfa.Transitions.Add(new Transition<NFA.State>(nfa.StartState, b.StartState));

            // Add a new accept state, link all old accept states to the new accept
            // state with an epsilon link and remove the accept flag
            var newAcceptState = new NFA.State { AcceptState = true };
            foreach (var oldAcceptState in nfa.States.Where(f => f.AcceptState))
            {
                oldAcceptState.AcceptState = false;
                nfa.Transitions.Add(new Transition<NFA.State>(oldAcceptState, newAcceptState));
            }
            nfa.States.Add(newAcceptState);

            return nfa;
        }

 public LexerState(NFA nf)
 {
     this.nstates = new int[(nf.nodes.Length + 31) >> 5];
 }

        public static NFA RepeatZeroOrMore(NFA input)
        {
            var nfa = new NFA();

            // Add everything from the input
            nfa.AddAll(input);

            // Create a new starting state, link it to the old accept state with Epsilon
            nfa.StartState = new NFA.State();
            nfa.States.Add(nfa.StartState);
            NFA.State oldAcceptState = input.States.First(f => f.AcceptState);
            nfa.Transitions.Add(new Transition<NFA.State>(nfa.StartState, oldAcceptState));

            // Add epsilon link from old accept state of input to start, to allow for repetition
            nfa.Transitions.Add(new Transition<NFA.State>(oldAcceptState, input.StartState));

            // Create new accept state, link old accept state to new accept state with epsilon
            var acceptState = new NFA.State { AcceptState = true };
            nfa.States.Add(acceptState);
            oldAcceptState.AcceptState = false;
            nfa.Transitions.Add(new Transition<NFA.State>(oldAcceptState, acceptState));
            return nfa;
        }

        private static NFA NumberedRepeat(NFA nfa, int minRepetitions, int maxRepetitions)
        {
            // To create a suitable expression, the special case of infinite max repetitions
            // must be separately handled.
            bool infiniteMax = false;
            if (maxRepetitions == int.MaxValue)
            {
                infiniteMax = true;
                maxRepetitions = minRepetitions;
            }
            else if (maxRepetitions < minRepetitions)
            {
                maxRepetitions = minRepetitions;
            }

            // Copy the NFA max repetitions times, link them together.
            NFA output = nfa.Copy();
            var epsilonLinkStates = new Stack<NFA.State>();
            for (int i = 1; i < maxRepetitions; ++i)
            {
                NFA newNfa = nfa.Copy();
                if (i >= minRepetitions || (infiniteMax && i == maxRepetitions - 1 ))
                {
                    epsilonLinkStates.Push(newNfa.StartState);
                }
                output = And(output, newNfa);
            }

            if (infiniteMax)
            {
                // Use Single to force an exception if this has gone astray
                var finalState = epsilonLinkStates.Single();

                // Make a little epsilon loop from the final accept state to the start state of the final state
                output.Transitions.Add(new Transition<NFA.State>(output.States.Single(f => f.AcceptState), finalState));
            }
            else
            {
                // Add epsilon transitions from accept to beginning states of NFAs in the chain
                var acceptState = output.States.Single(f => f.AcceptState);
                while (epsilonLinkStates.Any())
                {
                    output.Transitions.Add(new Transition<NFA.State>(epsilonLinkStates.Pop(),
                                                                     acceptState));
                }    
            }
            

            return output;
        }

    public static Lexer GetDispatchLexer(STable kl, SubInfo disp)
    {
        LexerCache lc = kl.GetLexerCache();
        Lexer ret;
        if (lc.dispatch_nfas.TryGetValue(disp, out ret))
            return ret;
        if (lc.parent != null && lc.parent.mo.name != "Cursor" && lc.parent.mo.name != "Any") {
            ret = GetDispatchLexer(lc.parent.mo, disp);
            foreach (string u in ret.pad.used_methods) {
                if (lc.repl_methods.Contains(u))
                    goto anew;
            }
            if (LtmTrace)
                Console.WriteLine("Reused {0} dispatch lexer for {1} in {2}",
                        disp.name, lc.parent.mo.name, kl.name);
            return lc.dispatch_nfas[disp] = ret;
        }
        anew:
        if (LtmTrace) {
            Console.WriteLine("Need new dispatch lexer for {0} in {1}",
                    disp.name, kl.name);
        }
        NFA pad = new NFA();
        pad.cursor_class = kl;
        P6any[] cands = (P6any[])disp.param[0];
        LAD[] lads_p = new LAD[cands.Length];

        for (int i = 0; i < lads_p.Length; i++) {
            pad.outer_stack.Add(Kernel.GetOuter(cands[i]));
            pad.info_stack.Add(Kernel.GetInfo(cands[i]));
            lads_p[i] = pad.info_stack[0].ltm.Reify(pad);
            pad.outer_stack.RemoveAt(pad.outer_stack.Count - 1);
            pad.info_stack.RemoveAt(pad.info_stack.Count - 1);
        }

        ret = new Lexer(pad, disp.name, lads_p);
        lc.dispatch_nfas[disp] = ret;
        return ret;
    }