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 '18 at 21:36
• @Evil In that case, it's just a DFA (or an NFA?). Would this be sufficient proof? – Paradox Jan 30 '18 at 21:40
• It wouldn't be a formal proof, but it's easy to get there from the idea. – Raphael Jan 30 '18 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 '18 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. – Ran G. Feb 1 '18 at 6:50
• Thankyou @RanG. for poitning out the mistake. I edited the answer. – Pragya Feb 1 '18 at 6:59