CS Atlas GATE 2027
TOC course
0 / 91 complete

TOC/Phase 3 · CFG, PDA & Context-Free Languages

Lesson 3.3.4 · Item 57 of 91

CFG ↔ PDA equivalence

Read at your own pace. Try the questions before opening the answers.

On this page

Recall warm-up

  1. Standard CFL that is not a DCFL?
    Stuck? Peek at 3.3.3 Designing PDAs; DPDA vs NPDA; DCFL ⊂ CFL
    • Recipe: stack stores what is unbounded; states store the phase; Z₀ detects empty; accept via ε, Z₀.
    • DPDA: ≤ 1 move per (q, a|ε, X), and no ε-move competing with input moves.
    • Regular ⊊ DCFL ⊊ CFL. wwᴿ, aⁿbⁿ ∪ aⁿb²ⁿ, aⁱbʲcᵏ (i=j or j=k): CFL not DCFL.
    • DCFL ⇒ unambiguous grammar; not conversely.

    Read lesson 3.3.3

  2. Derivation steps for length n in GNF?
    Stuck? Peek at 3.2.2 Chomsky and Greibach normal forms
    • CNF: A → BC | a (+ S → ε). Length n ⇒ 2n − 1 steps; n − 1 binary nodes. Height h ⇒ |w| ≤ 2^(h−1).
    • Conversion: simplify, replace terminals in long bodies, split long bodies.
    • GNF: A → aα. Length n ⇒ n steps. No left recursion.

    Read lesson 3.2.2

  3. How does a DFA become a right-linear grammar?
    Stuck? Peek at 2.3.2 Right-linear and left-linear grammars
    • Right-linear: A → wB | w. Left-linear: A → Bw | w. Regular grammar = one of the two (not mixed).
    • DFA → grammar: δ(A,a)=B ⇒ A → aB; A accepting ⇒ A → ε.
    • Grammar → NFA: A → aB is an arrow; A → a goes to a new accepting state.
    • Mixed linear can give aⁿbⁿ. Non-regular grammar does not imply non-regular language.

    Read lesson 2.3.2

The Hook

For regular languages you saw machines turn into grammars and back (2.3.2). The same happens one level up: CFGs and PDAs describe exactly the same languages. GATE asks this at the concept level — which direction is easy, what the PDA built from a grammar looks like, and what follows.

Predict First

A leftmost derivation always rewrites the leftmost variable. If you kept the unfinished part of a sentential form on a stack, what would be on top?

Core Concept

Prediction check

The leftmost symbol. If it is a terminal, it must match the next input symbol; if it is a variable, rewrite it by some rule. That is the whole CFG → PDA construction.

steps illustration
The stack holds the unfinished part of a leftmost derivation.

CFG → PDA

One working state q (plus start and accept states):

  • Start: push S on Z₀.
  • For each rule A → α: move (q, ε, A) → (q, α) — expand.
  • For each terminal a: move (q, a, a) → (q, ε) — match.
  • Accept when Z₀ is back on top and the input is finished.

It simulates leftmost derivations; nondeterminism picks the rule.

PDA built from S → aSb | ε

States: p, q, f

Transitions: p>q: ε,Z/SZ; q>q: ε,S/aSb | ε,S/ε | a,a/ε | b,b/ε; q>f: ε,Z/Z

The PDA built from S → aSb | ε. Step through aabb: expand, match, expand, match, …

PDA → CFG (idea)

Make variables [p X q] meaning “starting in p with X on top, the PDA can read some string and end in q having popped X (net)”. Rules come from moves: a move that pops X goes straight into a terminal rule; a move that replaces X by Y₁…Yₖ splits into k nested pops through intermediate states. The construction is mechanical and gives a CFG for N(P).

variablemeaning
[p X q]from p with X on top, read some w, end in q with X gone
[q₀ Z₀ q] for every qstart rules: S → [q₀ Z₀ q]
δ(p,a,X) ∋ (r, ε)[p X r] → a
δ(p,a,X) ∋ (r, Y₁Y₂)[p X s] → a [r Y₁ t][t Y₂ s] for all t, s
The triple construction at a glance.

Consequences

  • CFL = languages of CFGs = languages of NPDAs (final state) = languages of NPDAs (empty stack).
  • The PDA from a grammar has one main state: states add no power to PDAs beyond one (the stack does all the work).
  • Closure proofs can use whichever side is easier: grammars for union/concatenation/star, PDAs for intersection with regular languages.
CFG
leftmost derivations
PDA
expand / match, 1 working state
net pops
CFG
[p X q] triples
The two descriptions of context-free languages.

Putting it together

  • A PDA can simulate leftmost derivations of any CFG with one working state.
  • A PDA can be turned into a CFG with [p X q] variables.
  • CFGs and NPDAs describe exactly the CFLs.

Visual

CFG → PDA for  E → E+T | T,  T → id     input id+id
stack (top first)       move
E Z                     expand E → E+T
E + T Z                 expand E → T
T + T Z                 expand T → id
id + T Z                match id
+ T Z                   match +
T Z                     expand T → id
id Z                    match id
Z                       accept

Worked Examples

Easy

In the CFG → PDA construction, what move handles the terminal b?

Show the full solution

δ(q, b, b) = {(q, ε)}: if b is on top and the input is b, pop it.

Medium

How many states does the basic CFG → PDA construction need?

Show the full solution

One working state (often plus a start state that pushes S and an accepting state). The stack carries everything.

GATE-level

Which are true? (i) Every PDA with many states has an equivalent PDA with one state (empty-stack acceptance). (ii) The PDA built from a CFG is deterministic. (iii) CFL = languages accepted by NPDAs. (iv) The CFG → PDA construction simulates rightmost derivations.

Show the full solution

(i) true (PDA → CFG → one-state PDA). (ii) false in general: choosing the rule is a guess. (iii) true. (iv) false: leftmost. Answer: (i) and (iii).

GATE Traps

  • The grammar-built PDA is usually nondeterministic.
  • It simulates leftmost derivations, not rightmost.
  • Equivalence is with NPDAs; DPDAs only cover the DCFLs.

Memory Hook

The PDA is a to-do list: the top item is the next thing to produce — a word to say (match) or a task to break down (expand).

Connect the Dots

Grammars and stack machines are two views of one family. Now: what the family is closed under (and the famous failures), which questions have algorithms, and how to prove a language is not context-free.

Self-Test

  1. MCQ

    In the CFG → PDA construction, a variable A on top of the stack is:

    1. matched against the input
    2. replaced by the body of some rule for A
    3. popped and ignored
    4. pushed twice
  2. MSQ

    Which describe exactly the CFLs?

    1. CFGs
    2. NPDAs by final state
    3. NPDAs by empty stack
    4. DPDAs by final state
  3. MCQ

    The CFG → PDA construction simulates:

    1. rightmost derivations
    2. leftmost derivations
    3. any derivation order
    4. CYK

Rule Card

  • CFG → PDA: push S; expand (q, ε, A) → (q, α); match (q, a, a) → (q, ε); accept on Z₀. Simulates leftmost derivations; nondeterministic.
  • PDA → CFG: variables [p X q] (net pop of X from p to q).
  • CFG = NPDA (final state) = NPDA (empty stack). One working state suffices.

Concept Ledger

  • CFG → PDA (expand / match)
  • PDA → CFG (triple variables [pXq])
  • CFG ≡ NPDA

Answer Vault

Reveal answers when you’re ready

Warm-up answers

  1. wwᴿ.
  2. n.
  3. Each arrow δ(A,a)=B becomes A → aB; accepting states get A → ε.

Self-test answers

  1. B — Expand step.
    • A: Only terminals are matched.
    • C: It must be expanded.
    • D: No.
  2. ABC — DPDAs give DCFLs only.
    • D: Misses wwᴿ.
  3. B — The top of the stack is the leftmost unfinished symbol.
    • A: No.
    • C: A fixed order: leftmost.
    • D: Different algorithm.

Flashcards

  1. CFG → PDA: two kinds of moves?
    Reveal answerExpand a variable by a rule (ε-move); match a terminal with the input.
  2. How many working states does the grammar-built PDA need?
    Reveal answerOne.
  3. Which derivation does it simulate?
    Reveal answerLeftmost.
ONE MORE CONNECTION MADE

Ready for the next idea?

Mark this item complete when you’ve finished reading and working through it.