Given a Deterministic Finite Automata (DFA) $M_1$, does there always exist a Pushdown Automata (PDA) $M_2$ that accepts the same language as $M_1$? I.e. can any DFA be simulated by a PDA? Intuitively, it makes sense to me that a PDA is more powerful since it has an arbitrary amount of memory and can therefore accept more languages than a DFA, but how could this be formally proven?

  • 1
    $\begingroup$ What happens when you take PDA and ignore stack (not use it)? $\endgroup$
    – Evil
    Jan 30, 2018 at 21:36
  • $\begingroup$ @Evil In that case, it's just a DFA (or an NFA?). Would this be sufficient proof? $\endgroup$
    – Paradox
    Jan 30, 2018 at 21:40
  • 1
    $\begingroup$ It wouldn't be a formal proof, but it's easy to get there from the idea. $\endgroup$
    – Raphael
    Jan 30, 2018 at 22:00
  • $\begingroup$ It is rather a concept, something that directly and intuitively maps problem, but as proof it is not even hand waving yet. $\endgroup$
    – Evil
    Jan 30, 2018 at 23:24

1 Answer 1


I hope this answer will help you to understand the mapping. Any DFA is also a PDA. The state transitions in the DFA are similar for PDA without stack. For every transition you perform in DFA, make the similar transition in PDA and do not push/pull from stack.

For a transition

In DFA : $\delta(q_x,0) \rightarrow q_y$

In stack : $\delta(q_x,0) \rightarrow (q_y,\epsilon)$

For accepting state

In DFA : $\delta(q_x,0) \rightarrow q_f$

In stack : $\delta(q_x,0) \rightarrow (q_f,\epsilon)$

  • $\begingroup$ Of course there is a formal proof, and what you write here is the first part of it. The other part is showing that the two machines behave exactly the same on any input. $\endgroup$
    – Ran G.
    Feb 1, 2018 at 6:50
  • $\begingroup$ Thankyou @RanG. for poitning out the mistake. I edited the answer. $\endgroup$
    – Pragya
    Feb 1, 2018 at 6:59
  • $\begingroup$ what about NFAs? Can every NFA be simulated by a PDA? $\endgroup$
    – x89
    Aug 9, 2020 at 17:47

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.