Can every DFA be simulated by a PDA?

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?

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

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)$

• 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. Feb 1, 2018 at 6:50
• Thankyou @RanG. for poitning out the mistake. I edited the answer. Feb 1, 2018 at 6:59
• what about NFAs? Can every NFA be simulated by a PDA?
– x89
Aug 9, 2020 at 17:47