I have recently read that turing machine can be remodeled to perform as PDA now, i have a question that since DTM = NDTM ( non deterministic Turing machine) then every DTM can remodeled to be NDTM thus taking same analogy to PDA , we have DPDA = DTM( remodeled) = NDTM = NPDA thus creating DPDA = PDA . there is no debate on the fact that DPDA != NPDA. but the above relation is contradiction this. further,like we have TM- as deterministic by default , PDA - as non deterministic by deafult , then what about LBA? and FA?, like is there any same deafault criteria associated with LBA and FA ?

  • 1
    $\begingroup$ You have to be more careful with words. What does "remodel to perform as" mean, precisely? Hint: DTM can simulate DPDA, but not the other way around! $\endgroup$ – Raphael Dec 15 '18 at 7:47
  • $\begingroup$ @Raphael remodel - means some changes like tape is assumed as stack , like that $\endgroup$ – Noob Dec 15 '18 at 7:49
  • $\begingroup$ @rajendra So you are propounding a DPDA can simulate a (regular) DTM by manipulating the TM work tape as a stack? $\endgroup$ – dkaeae Dec 15 '18 at 8:18
  • $\begingroup$ @dkaeae am i wrong here ? $\endgroup$ – Noob Dec 15 '18 at 8:19
  • $\begingroup$ @rajendra Ponder about what happens when you pop a symbol from the stack... $\endgroup$ – dkaeae Dec 15 '18 at 8:29

The set of languages that can be accepted by DPDA is not equal to NPDA. For example we can accept the following language using NPDA but there is no DPDA which can accept it.

$$L = \{ww^R\;| \; w\in\{0,1\}^*\}.$$

Why DPDA can't accept $L$? Because D in DPDA stands for Determinism. That is DPDA can not decide in nondeterministic way where is the middle of input string (for accepting $ww^R$ it should find its middle first! check it one time!). So Class of languages NPDA can accept is bigger than DPDA.

Note that Turing machine is very powerful model. You don't have power of Deterministic Turing machine in DPDA to simulate its nondeterministic version.


The other answers have already covered why NPDAs are strictly more computationally powerful than DPDAs (and even yourself said "there is no debate" about it). Let me then address what seems to be the root of your misunderstanding (judging from the comments).

You propounded a (D)PDA can simulate a DTM by manipulating the TM's work tape as a stack. Indeed, you can push the symbols in the TM tape as the read/write head moves to the right and thus save them in the stack. The problem arises when the head moves back to the left. When doing so, the PDA is forced the pop those symbols, and they are then deleted for good. Even if you try to save them within the PDA's state, you can only save a constant number of symbols, whereas TMs (or even LBAs) are allowed to use at least as much space as the input length (i.e., an unbounded amount of space).

It is relevant to note, however, a (D)PDA with two stacks does suffice to simulate a TM. The reason for this is closely linked to the above reasoning: When the head moves back to the left, you pop the symbols from that stack, but save them in the other one.


As we know that NPDA and DPDA are not equivalent in their power. NPDA can accept the context free languages but DPDA cannot.So, every language accepted by DPDA can also be accepteded by NPDA but vice versa is not true.And I don't think NPDA always simulate NDTM because TM can accept recursively enumerable languages but PDA is only limited to Context free languages.

  • $\begingroup$ It might be useful to add why NPDAs can accept all languages DPDAs can. Also, languages cannot be "simulated", only machines can. $\endgroup$ – dkaeae Dec 15 '18 at 8:14
  • $\begingroup$ @dkaeae Thanks for your response.I have corrected my mistakes and I think the answer below satisfies why NPDAs can accept all languages DPDAs can. $\endgroup$ – mondyfy Dec 15 '18 at 12:47

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.