2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What happens when you take PDA and ignore stack (not use it)? $\endgroup$ – Evil Jan 30 '18 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 '18 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 '18 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 '18 at 23:24
1
$\begingroup$

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

$\endgroup$
  • $\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 '18 at 6:50
  • $\begingroup$ Thankyou @RanG. for poitning out the mistake. I edited the answer. $\endgroup$ – Pragya Feb 1 '18 at 6:59

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.