Mike McNally says:
Rick Busdiecker writes:
No, NFA is acceptable and correct, it's Non-determinisic Finite Automaton. A non-deterministic Turing machine is a perfectly reasonable example, however.
Uhh, isn't it the case that a Turing machine can simulate an NFA, but not the reverse? An NFA has no tape, and therefore is not as powerful an automaton as a Turing machine. Thus an NFA can be implemented by an NTM, but not the reverse.
I think.
Correct. The hierarchy as I remember it is roughly (from least to most powerful in terms of size of the recognizable languages) FAs, PDAs (that is, deterministic push-down automata), NPDAs, TMs. Its been a while, but I seem to recall that non-deterministic pushdown automata could recognise some languages that deterministic ones could not. Perry