How prefix property of language affects the PDA

Question

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.

Answer 1

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.