Are endmarkers necessary for Deterministic Pushdown Automata?

Question

In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to accept as arguments triples $(q, \sigma, \gamma)$ with $\sigma$ that might be a right endmarker symbol. It is written: "The right endmarker delimits the input string and is a necessary addition. With NPDAs, we could guess where the end of the input string was, but with DPDAs we have no such luxury." (p. 176). Can we show that this condition is necessary? Can we give an example of a language accepted by this kind of DPDA's that is not accepted by any DPDA whose transition function has no argument with an endmarker?

Answer 1

Short answer: it depends on how you set the acceptance condition of the DPDA model: final state or empty stack.

The endmarkers are not necessary for DPDAs in which the accept condition is final state (which is also used to define the deterministic context-free languages - DCFLs): for all $L \dashv$ ("endmarked" language) recognized by a DPDA there is a DPDA that recognizes $L$.

See:

Theorem 2.43. $A$ is a DCFL if and only if $A \dashv$ is DCFL

in Michael Sipser's Introduction to the Theory of Computation.

But endmarkers play a role when proving equivalence between DPDAs and DCFGs (deterministic context free grammars):

Theorem: An endmarked language is generated by a deterministic CFG iff it can be recognized by a DPDA

Very informally a DCFG for $L$ exists if and only if there is a DPDA that accepts $L$ with empty stack acceptance condition (the stack is empty at the end of the input); which is not the "standard" definition of a DPDA. With non-determinism the two conditions are equivalent because the PDA can guess the end of the input and clear the stack with $\epsilon$ moves; without non-determinism they are not equivalent.

Without the endmarker DCFGs can only generate a proper subset of the languages recognized by DPDAs: DCFGs can only generate the prefix-free languages recognized by DPDAs (no string is a prefix of another string).

As a simple example consider this language: $L = \{ a^n b^m \mid m < n \}$. There is no DPDA with empty stack acceptance condition for it.

Note on the Kozen's book

In Lecture 23 he defines PDA as: $M = ( Q, \Sigma, \Gamma, \delta, s, \bot, F)$ where "... $F\subseteq Q$ is the final or accepts states". Then he describes the two different acceptance conditions and proves their equivalence for (N)PDAs.

In Supplementary Lecture F he defines DPDA as: "$M = ( Q, \Sigma, \Gamma, \delta, s, \dashv, \bot, F)$ where everything is the same as with NPDAs except (i) $\vdash$ is a special symbol not in $\Sigma$, called the right-endmarker ..." (then he adds the other conditions to forbid non-determinism and to prevent the pop of the $\bot$ symbol).

He then says: "We consider only acceptance by final state. One can define acceptance by empty stack and prove that such machines are equivalent. The assumption (iii) would have to be modified accordingly" (which is correct because the model described uses the extra endmarker $\dashv$).