Rick Busdiecker writes: > Not true. What that means is that a polynomial time solution exists > for an NFA. The only part has not been shown. Mike McNally responds: >While we're being picky, I'll point out that (unless I'm wrong of >course) it's not really an NFA, but a non-deterministic Turing >machine (an "NTM"?) that's the automaton at issue here. and I then gibbered : That is correct. As a matter of fact, it's an easy theorem that an NFA has the same computing capacity as a DFA; it is not known whether this theorem holds for more powerful machines, and is in fact the heart of the P ?= NP conjecture. Whups. Teach me to post before eating breakfast.... Ignore what I just said above. - kitten