I know that every DPDA (deterministic PDA) is a PDA (more specifically, non-deterministic PDA). But I found it hard to understand, not that every DPDA is an NPDA, but some results that contradict this fact:

  • In PDA we have two modes of accepting the language, which are "empty stack method" and "final state acceptance method".
  • Language accepted by both of these modes in PDA (NPDA) are equal, but in DPDA language accepted by "final state method" > "empty stack method" (strictly).
  • Thirdly we know that those "deterministic context-free language" having prefix property can not be accepted by "empty stack". An example is $L = \{ a^n \mid n>0 \}$. So for these languages, we need final state method of DPDA.

Now my doubt is that if every DPDA is NPDA then the language accepted by both of the modes should be same in DPDA. I think that I am missing something here because individually all of the above result are ok, but when put sequentially they seems to cause a contradiction.


The root of your problem is in the second statement:

Language accepted by both of these modes in PDA (NPDA) are equal.

I'm not sure what you mean by that. You might mean the following false statement:

The language accepted by a PDA using the empty state acceptance condition is the same as the language accepted by the same PDA using the final state acceptance condition.

The true statement is the following:

If a language is accepted by some PDA using the empty stack acceptance condition, then it is accepted by a different PDA using the final state acceptance condition; and vice versa.

This involves two conversions: from an "empty stack" PDA to a "final state" PDA, and vice versa. The first conversion preserves determinism, the second doesn't. In other words, if we apply the first conversion to an "empty stack" DPDA, then we get a "final state" DPDA. But if we apply the second conversion to a "final state" DPDA, we get an "empty stack" NPDA which is in general not deterministic.

The same statement can be stated differently:

The set of languages accepted by "empty stack" PDAs is the same as the set of languages accepted by "final state" PDAs.

The same doesn't hold for DPDAs, though it is true that the set of languages accepted by "empty stack" DPDAs is a subset of the set of languages accepted by "final state" PDAs.

| cite | improve this answer | |
  • $\begingroup$ if you could please give me an example of the conversion of when final state DPDA converted to empty stack DPDA it results in NPDA , reason being i do not see any difference when converting , so if you may then please $\endgroup$ – Noob Dec 14 '18 at 8:08
  • $\begingroup$ if you could then show for the same language as said above in the question , this will help me to clear many doubts $\endgroup$ – Noob Dec 14 '18 at 8:11
  • $\begingroup$ You don't need me for that. The conversion is described in textbooks. Take a "final state" DPDA for your $L$, apply the conversion to an "empty stack" PDA, and see what happens. $\endgroup$ – Yuval Filmus Dec 14 '18 at 8:19

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.