I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA: FA

Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed? PDA

  • 1
    $\begingroup$ I don't really understand the picture to say if it's correct, but yes, for regular languages you don't need a stack. Stack gives PDA power to recognize languages which FA can't. So it's natural that you don't need this power for regular languages. $\endgroup$ – Dmitry Jul 15 at 9:38
  • $\begingroup$ By "don't need" I mean that PDA won't use it. Of course, to match PDA definition, you still have to write some trivial rules for stack manipulation: in the beginning put a certain symbol (say, S) on the stack, and for each transition simply replace S with S. $\endgroup$ – Dmitry Jul 15 at 9:48
  • $\begingroup$ This is my confusion. If in exams the question is to draw a PDA for an FA do I have to draw a PDA with all the push, pop symbols or I can just draw it with read, start and accept symbols. I got it that we don't need a stack but on paper how will we draw such PDA? $\endgroup$ – Mateen Kiani Jul 15 at 9:58
  • 2
    $\begingroup$ We can't answer your question; your instructor would be the one to ask. $\endgroup$ – Rick Decker Jul 15 at 14:15
  • $\begingroup$ For those who are as confused as I was by the diagrams in this question: (1) DFA +/- notation; (2) read/push/pop PDA notation. The PDA notation I'm familiar with is completely different (basically the JFLAP-style DFA notation but with more stuff written on each transition edge). $\endgroup$ – Aaron Rotenberg Jul 15 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.