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

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

<p>See: </p>

<p><strong>Theorem 2.43.</strong> <span class="math-container">$A$</span> is a DCFL if and only if <span class="math-container">$A \dashv$</span> is DCFL</p>

<p>in Michael Sipser's <em>Introduction to the Theory of Computation</em>.</p>

<p><em>But</em> endmarkers play a role when proving equivalence between DPDAs and DCFGs (<a href="https://en.wikipedia.org/wiki/Deterministic_context-free_grammar" rel="noreferrer">deterministic context free grammars</a>):</p>

<p><strong>Theorem</strong>: An <em>endmarked language</em> is generated by a deterministic CFG iff it can be recognized by a DPDA</p>

<p>Very informally a DCFG for <span class="math-container">$L$</span> exists if and only if there is a DPDA that accepts <span class="math-container">$L$</span> with <em>empty stack</em> 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 <em>guess</em> the end of the input and clear the stack with <span class="math-container">$\epsilon$</span> moves; without non-determinism they are not equivalent.</p>

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

<p>As a simple example consider this language: <span class="math-container">$L = \{ a^n b^m \mid m &lt; n \}$</span>. There is no DPDA with empty stack acceptance condition for it.</p>

<p><em>Note on the Kozen's book</em></p>

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

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

<p>He then says: <em>"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"</em> (which is correct because the model described uses the extra endmarker <span class="math-container">$\dashv$</span>).</p>

CC BY-SA 4.0
2019-11-11T08:32:30.893Z
2019-11-12T11:32:53.910Z
2019-11-12T11:32:53.910Z
Marzio De Biasi
<p>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 <span class="math-container">$(q, \sigma, \gamma)$</span> with <span class="math-container">$\sigma$</span> 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?</p>

<automata-theory><context-free>
Are endmarkers necessary for Deterministic Pushdown Automata?
user251130
# Are endmarkers necessary for Deterministic Pushdown Automata?

(Asked by: username_0 on 2019-11-09)

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?

**Tags:** automata-theory, context-free


---

## 1 answers

### Answer by username_1 on 2019-11-11. Score: 8 | Accepted answer

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](https://en.wikipedia.org/wiki/Deterministic_context-free_grammar)):

**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$).


---

