Is it correct to say that there are languages that a NFA with epsilon recognizes but a PDA is not? I think that it is wrong but I cannot find a suitable explanation.


1 Answer 1


This follows immediately from the definitions and the basic characterizations of the different kinds of automata. Every NFA, with or without $\epsilon$-transitions, recognizes a regular language. Every regular language is context-free. Every context-free language is recognized by a PDA.

  • $\begingroup$ Thank you did not expect something that simple. $\endgroup$
    – Saraki
    Aug 25, 2014 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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