2
$\begingroup$

Every single NFA has an equivalent DFA representation so that every language recognized by NFA is recognized by the DFA, but is it also true that the language recognized by NFA is recognized by a push down automata and a Turing machine?

$\endgroup$
5
$\begingroup$

A language is recognized by an NFA iff it is regular. It is recognized by a push-down automaton iff it is context-free. It is recognized by a Turing machine iff it is computable. Every regular language is context-free. Every context-free language is computable.

Even without knowing these facts, it is not difficult to simulate an NFA by a push-down automaton and a DFA by a Turing machine.

$\endgroup$
1
  • $\begingroup$ Comprehensive answer! learned something new along the way $\endgroup$
    – Fraïssé
    Dec 15 '14 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.