Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 59 ยท Pushdown Automata

Deterministic vs Nondeterministic PDA

Understand deterministic and nondeterministic pushdown automata, why NPDAs are strictly stronger, and test determinism of a PDA with Python.

For finite automata, nondeterminism is a convenience: every NFA can be converted to a DFA. For pushdown automata the story is different. A deterministic PDA (DPDA) recognizes strictly fewer languages than a nondeterministic PDA (NPDA). This split is the reason parsing a programming language is easier than parsing arbitrary context-free text, and it is a favorite exam topic.

When is a PDA deterministic?

A PDA is deterministic when, in every configuration, at most one move is possible. Formally, for every state q and stack symbol X:

  1. For each input symbol a, ฮด(q, a, X) has at most one element.
  2. ฮด(q, ฮต, X) has at most one element.
  3. If ฮด(q, ฮต, X) is non-empty, then ฮด(q, a, X) is empty for every a. An ฮต-move and a reading move on the same state and top symbol would be a conflict.

Notice that a DPDA is allowed to have no move; it then blocks. In many textbooks, a DPDA is also required to accept by final state, because acceptance by empty stack on a DPDA gives only languages with the prefix property (no accepted string is a prefix of another accepted string).

We can turn these three conditions into a short checker:

Python Is this PDA deterministic?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first machine is deterministic because the symbol c appears exactly once, so the switch from pushing to popping needs no guessing. The second is not: in state q0 with a on top, the machine may read another a or take an ฮต-move to start popping. Nothing in the input tells it which is correct.

Why a DPDA cannot do palindromes

Consider the language { w w^R : w โˆˆ {a,b}* }. After reading aa, a machine cannot know whether it has seen the whole palindrome aa or just the start of aabbaa. It must keep both futures open, which means guessing the middle. One can prove that no DPDA accepts this language, even though an NPDA does (see the palindrome constructions).

So the picture is:

flowchart TB
    R["Regular languages<br/>(DFA / NFA)"] --> D["Deterministic context-free<br/>(DPDA)"]
    D --> C["Context-free languages<br/>(NPDA)"]

Each box is strictly contained in the next: regular โŠ‚ DCFL โŠ‚ CFL.

Examples that separate the classes:

Language Regular DCFL CFL
Strings ending in ab yes yes yes
a^n b^n no yes yes
w c w^R no yes yes
w w^R no no yes
a^n b^n โˆช a^n b^{2n} no no yes

The last language is the classic union that breaks determinism: after the as, the machine must know whether to pop one or two as per b, and it learns the answer only when the bs are over.

Properties compared

Property DPDA NPDA
Moves per configuration at most one any number
Power deterministic CFLs all CFLs
Closed under complement yes no
Closed under union no yes
Closed under intersection with a regular language yes yes
Parsing time linear (LR(k) parsers) cubic in general (CYK, Earley)
Equivalence of two machines decidable undecidable

The complement closure is notable. Complementing a DPDA works much like complementing a DFA, with extra care to make the machine always read all its input (no infinite ฮต-loops). NPDAs are not closed under complement, which is one way to show the CFL class is not closed under complement either.

The deterministic context-free languages are exactly those with an LR(1) grammar. Real programming-language parsers (yacc, bison and friends) are built on this fact.

Seeing nondeterminism in action

Run the NPDA for w w^R and look at how many configurations are alive at once. The number counts the guesses the machine is tracking:

Python Counting live branches

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For abbaabba the output is [1, 1, 2, 2, 2, 2, 3, 3]: besides the branch that is still pushing, other branches have switched to popping at different places and survive as long as the symbols keep matching. For abababab the extra branches die at once, so the count stays at 1. A DPDA would have exactly one configuration at every step.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which condition makes a PDA nondeterministic?

    At that configuration two different moves apply, so the machine has a choice. Having a stack or several states does not by itself cause choice.
  2. 2. Which language is accepted by an NPDA but by no DPDA?

    w w^R needs the machine to guess the middle of the string, which a deterministic machine cannot do.
  3. 3. Which closure property distinguishes DPDAs from NPDAs?

    Deterministic context-free languages are closed under complement; context-free languages in general are not.
  4. 4. How do the three language classes relate?

    Every regular language is a DCFL (no stack needed), every DCFL is context-free, and both inclusions are strict.

Summary

  • A DPDA has at most one applicable move in every configuration; ฮต-moves must not compete with reading moves.
  • DPDAs accept the deterministic context-free languages; NPDAs accept all context-free languages.
  • w c w^R is deterministic, w w^R is not; the union a^n b^n โˆช a^n b^{2n} needs a guess too.
  • DPDA languages are closed under complement and parse in linear time, which is why compilers use deterministic (LR) parsing.

Next: PDAs for matching counts