Deterministic versus nondeterministic PDA

Why it exists

For finite automata nondeterminism adds no power (subset construction). For pushdown automata it does: some context-free languages need guessing. The languages that a deterministic PDA can accept are the deterministic context-free languages (DCFLs); they are exactly the languages for which a compiler can build a fast left-to-right parser without backtracking. GATE asks: which of these languages is deterministic, is DPDA equal to NPDA, which closure properties DCFLs have.

Prerequisites

You need PDAs, configurations and acceptance by final state or empty stack (PDA).

Precise definitions

A PDA $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ is deterministic (a DPDA) if in every configuration at most one move is possible. Formally, for all $q \in Q$, $X \in \Gamma$:

1. $\delta(q, a, X)$ has at most one element for every $a \in \Sigma \cup \{\varepsilon\}$;
2. if $\delta(q, \varepsilon, X) \ne \emptyset$ then $\delta(q, a, X) = \emptyset$ for every $a \in \Sigma$ (an $\varepsilon$-move must not compete with an input move).

A language is a deterministic context-free language (DCFL) if some DPDA accepts it by final state. DPDAs accepting by empty stack accept fewer languages (below), so by convention a DPDA accepts by final state.

A DPDA may have $\varepsilon$-moves (they are not choices as long as they are the only move). Its computation on an input is a single path.

How it works

Deterministic examples

$a^n b^n$ ($n \ge 0$), the machine of the PDA page: push on $a$, pop on $b$, an $\varepsilon$-move to the final state only when the bottom marker shows and no input move applies. Its start state is also accepting (for $n = 0$) so no $\varepsilon$-move competes with the move on $a$.

$w\,c\,w^R$ (a marked palindrome, $c \notin \{a, b\}$): the marker $c$ tells the machine where the middle is, so no guessing is needed. Push the symbols of $w$; on $c$ switch to popping; match each symbol against the top; accept when the bottom marker is exposed.

Equal numbers of $a$ and $b$ and balanced parentheses: the stack holds the surplus. The first versions in these pages end with an $\varepsilon$-move into an accepting state at any time, which competes with the input moves: nondeterministic. The deterministic versions use a state $q_0$ that means "only the bottom marker is on the stack" and is accepting, and a special symbol $D$ for the lowest surplus symbol, so popping $D$ returns to $q_0$. Both languages are DCFLs (the machines were checked on all strings up to length $10$ or $12$).

Nondeterministic is stronger: no DPDA for $ww^R$

The set of even palindromes $\{w w^R\}$ is context-free but is not a DCFL. Intuition: after reading $abb$ the machine must be ready for two different futures: the middle may have been after $ab$ (then the string continues with $a$, giving $abba$) or after $abb$ (then it continues with $bba$, giving $abbbba$). With one stack and no way to look ahead, a deterministic machine must commit to one of the two readings after each symbol and the other is lost. (The full proof is a longer argument, quoted as a textbook theorem.) The same is true for $\{a^i b^j c^k : i = j \text{ or } j = k\}$ (it needs to guess which comparison to make) and for $\{a^n b^n\} \cup \{a^n b^{2n}\}$.

So DPDA $\subsetneq$ NPDA in power:

$\text{regular} \;\subsetneq\; \text{DCFL} \;\subsetneq\; \text{CFL}.$

Strictness: $a^n b^n$ is a DCFL but not regular; $ww^R$ is context-free but not a DCFL.

Acceptance by empty stack is weaker for DPDAs

A DPDA that accepts by empty stack cannot move once the stack is empty. Therefore it can never accept a string and also a longer string that extends it: its language has the prefix property (no string of the language is a proper prefix of another). On 300 random deterministic PDAs accepting by empty stack the accepted language was prefix-free in every case. The language $\{a^n b^n : n \ge 0\}$ contains $\varepsilon$, a prefix of every other string, so no DPDA accepts it by empty stack, although a DPDA accepts it by final state. The version with $n \ge 1$ is prefix-free and a deterministic empty-stack machine for it exists (checked). For nondeterministic PDAs the two acceptance conditions are equivalent (PDA).

Closure properties

The DCFL column is a set of textbook results, quoted. Two of them can be explained: the product of a DPDA with a DFA is again a DPDA (checked), so DCFLs are closed under intersection with regular languages; and the complement is obtained by swapping the accepting states of a DPDA after making it complete and loop-free (the construction needs care with $\varepsilon$-loops and with states reached after the input ends). The union of two DCFLs is not always a DCFL: $\{a^i b^j c^k : i = j\} \cup \{a^i b^j c^k : j = k\}$ is the union of two DCFLs but is not deterministic. From closure under complement and the failure of closure under union it follows that DCFLs are not closed under intersection either (De Morgan).

Why DCFLs matter

The languages generated by LR($k$) grammars are exactly the DCFLs (textbook theorem, quoted); LR parsers are DPDAs (LR parsing). Every DCFL has an unambiguous grammar (quoted), so inherently ambiguous languages and nondeterministic languages like $ww^R$ cannot be parsed by an LR parser. LL($k$) grammars give a smaller class.

Worked examples

Cheat box

Traps and GATE patterns

Connections

DCFLs are the languages of LR parsing in compilers (LR parsing); the closure properties of the whole class of CFLs are on the next page (closure of CFLs); the place of DCFLs in the Chomsky hierarchy is on the hierarchy page.

PYQs

Which of the following pairs have DIFFERENT
expressive power?

Which ONE of the following languages is accepted by a
deterministic pushdown automaton?

Consider the following languages:
L1 = {ww | w ∈ {a, b}* }
L2 = {anbncm | m, n≥ 0}
L3 = {ambncn | m, n≥ 0}
Which of the following statements is/are FALSE?

Consider the transition diagram of a PDA given below
with input alphabet Σ = {a,b} and stack alphabet Γ =
{X,Z}. Z is the initial stack symbol. Let L denote the
language accepted by the PDA.

Which one of the following is TRUE?

Which one of the following is FALSE?

Consider the following languages.
L1={ai b j ck | i =j, k>=1}
L2={ai b j | j=2i , i >=0}
Which of the following is true?

Which of the following languages is accepted by a non-
deterministic pushdown automaton (NPDA) but NOT
by a deterministic NPDA?

Consider the languages:

L1 = {wwr | w ∈ {0, 1}*}

L2 = {w#wr | w ∈ {0, 1}*}, where # is a special
symbol

L3 = {ww | w ∈ {0, 1}*}
Which one of the following is TRUE?

The language L={ 0i21i | i≥0 } over the alphabet {0,1,2}
is:

Self-check

Revision card

References