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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ What happens when you take PDA and ignore stack (not use it)? $\endgroup$– EvilJan 30, 2018 at 21:36
-
$\begingroup$ @Evil In that case, it's just a DFA (or an NFA?). Would this be sufficient proof? $\endgroup$– ParadoxJan 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$– RaphaelJan 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$– EvilJan 30, 2018 at 23:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$– PragyaFeb 1, 2018 at 6:59
-
$\begingroup$ what about NFAs? Can every NFA be simulated by a PDA? $\endgroup$– x89Aug 9, 2020 at 17:47
-
$\begingroup$ @x89 Sure, every NFA can be converted to a DFA so every NFA can be simulated by a PDA $\endgroup$– HavaldMar 21, 2023 at 21:57