CS Atlas GATE 2027
TOC course
0 / 91 complete

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

Lesson 3.3.2 · Item 55 of 91

Acceptance by final state vs empty stack

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

On this page

Recall warm-up

  1. What does the PDA label a, A / AA do?
    Stuck? Peek at 3.3.1 Stack primer and the push-down automaton
    • PDA (Q, Σ, Γ, δ, q₀, Z₀, F); δ(q, a|ε, X) ⊆ Q × Γ*; label a, X/γ (γ = ε pop, X keep, YX push).
    • ID (q, w, γ), top first; ⊢ one move, ⊢* many.
    • Nondeterministic by default; ε-moves still see the stack.

    Read lesson 3.3.1

  2. What makes a grammar ambiguous?
    Stuck? Peek at 3.1.3 Ambiguity
    • Ambiguous: some w has ≥ 2 parse trees (≡ ≥ 2 leftmost derivations).
    • Witnesses: E+E/E*E with id+id*id; SS with three pieces; aS|Sa with aa; dangling else.
    • Fix with precedence layers E → E+T | T, T → T*F | F, F → (E) | id.
    • Inherently ambiguous language: every grammar ambiguous, e.g. aⁱbʲcᵏ with i=j or j=k. No algorithm decides ambiguity in general.

    Read lesson 3.1.3

  3. When does an NFA accept?
    Stuck? Peek at 1.2.1 Nondeterminism and the NFA
    • NFA: δ : Q × Σ → P(Q); moves may be 0, 1, many.
    • Accept iff some path ends in F ⇔ δ̂(q₀, w) ∩ F ≠ ∅. Track the set of active states.
    • DFA ⊆ NFA; NFAs accept exactly the regular languages.
    • No dead state needed. Swapping F does NOT complement an NFA.

    Read lesson 1.2.1

The Hook

Some textbooks say a PDA accepts when it ends in an accepting state; others when its stack is empty. GATE questions sometimes state the convention, sometimes not. You need to know both, how to convert between them, and the one place where they differ: deterministic PDAs.

Predict First

The aⁿbⁿ PDA by empty stack (below) pops Z at the end. Does it accept ε?

Core Concept

Prediction check

No: on ε the machine is in q0 with Z on the stack, and q0 has no ε-move that pops Z. The stack never empties, so ε is rejected — this machine accepts aⁿbⁿ with n ≥ 1.

PDA for aⁿbⁿ, n ≥ 1 (empty stack)

States: q0, q1

Transitions: q0>q0: a,Z/AZ | a,A/AA; q0>q1: b,A/ε; q1>q1: b,A/ε | ε,Z/ε

Empty-stack acceptance: the last move ε, Z / ε empties the stack. Try ab and abb.

Acceptance by final state

L(P) = { w | (q₀, w, Z₀) ⊢* (q, ε, γ) for some q ∈ F and any γ }.

Input fully read, in an accepting state; whatever is left on the stack does not matter.

input
fully read
state
in F
stack
anything
Final-state acceptance.

Acceptance by empty stack

N(P) = { w | (q₀, w, Z₀) ⊢* (q, ε, ε) for any state q }.

Input fully read and the stack completely empty (Z₀ popped too). F is irrelevant.

input
fully read
stack
completely empty
state
anything
Empty-stack acceptance.

Equivalence for (nondeterministic) PDAs

The two conventions accept the same family — the CFLs.

  • Final state → empty stack: from every accepting state add ε-moves into a new state that pops everything. Put a new bottom marker under Z₀ first so the stack never empties by accident.
  • Empty stack → final state: put a new bottom marker X₀ under Z₀; when X₀ appears on top (the old stack is empty), take an ε-move to a new accepting state.
final-state PDA
accept → drain the stack
empty-stack PDA
see new bottom → accept
final-state PDA
Conversions both ways (nondeterministic PDAs).

The deterministic caveat

For deterministic PDAs (next lesson) the conventions differ: empty-stack DPDAs can only accept prefix-free languages (no string in L is a proper prefix of another), because after accepting w the stack is empty and the machine cannot continue. Final-state DPDAs accept all deterministic CFLs.

GATE convention: unless stated, PDAs accept by final state, and “DPDA” / “DCFL” refer to final-state acceptance.
{aⁿbⁿ : n ≥ 1}
prefix-free: an empty-stack DPDA works
a*
a is a prefix of aa: no empty-stack DPDA, but a final-state DPDA works
Why DPDAs use final-state acceptance.

Putting it together

  • Final state: read everything and stop in F. Empty stack: read everything and pop Z₀ too.
  • For nondeterministic PDAs the two are equally powerful.
  • For DPDAs, empty-stack acceptance is weaker (prefix-free), so GATE uses final state.

Visual

aabb on the empty-stack PDA
(q0,aabb,Z) ⊢ (q0,abb,AZ) ⊢ (q0,bb,AAZ) ⊢ (q1,b,AZ) ⊢ (q1,ε,Z) ⊢ (q1,ε,ε)   stack empty → ACCEPT
aab:  (q0,aab,Z) ⊢ (q0,ab,AZ) ⊢ (q0,b,AAZ) ⊢ (q1,ε,AZ)                         A left → REJECT

Worked Examples

Easy

A PDA by empty stack ends with input read, state non-accepting, stack empty. Accept?

Show the full solution

Yes — states don’t matter for empty-stack acceptance.

Medium

Why add a new bottom marker when converting final-state acceptance to empty-stack acceptance?

Show the full solution

The original PDA might empty its stack in the middle of a string it rejects; that would be wrongly accepted. A new marker underneath can only be popped by the added “drain” state, reached only from accepting states.

GATE-level

Which are true? (i) N(P) and L(P) are always the same language for a given PDA P. (ii) The class of languages accepted by PDAs by empty stack equals the CFLs. (iii) A DPDA by empty stack can accept {a, aa}. (iv) A DPDA by final state can accept a*.

Show the full solution

(i) false: the same machine read two ways can accept different languages. (ii) true. (iii) false: a is a prefix of aa. (iv) true. Answer: (ii) and (iv).

GATE Traps

  • The same PDA can accept different languages under the two conventions.
  • Empty stack means Z₀ popped too.
  • For NPDAs the conventions are equally powerful; for DPDAs empty-stack acceptance is weaker (prefix-free only).
  • Final-state acceptance requires the whole input to be read.

Memory Hook

Final state = “end on the winning square”. Empty stack = “clear every plate off the table”. Same power for a guesser; the cautious (deterministic) waiter needs the winning square.

Connect the Dots

So far we have built PDAs by intuition. Next: a design recipe, the difference between deterministic and nondeterministic PDAs, and the proof that guessing really adds power for stack machines — unlike for finite automata.

Self-Test

  1. MCQ

    Acceptance by empty stack requires:

    1. an accepting state
    2. the input read and the stack empty
    3. the stack empty at any time
    4. only Z₀ on the stack
  2. MSQ

    Which statements are true?

    1. NPDAs by empty stack accept exactly the CFLs
    2. DPDAs by empty stack accept exactly the prefix-free DCFLs
    3. DPDAs by final state and by empty stack are equally powerful
    4. Converting empty stack → final state uses a new bottom marker
  3. MCQ

    Is { a, ab } prefix-free?

    1. yes
    2. no — a is a prefix of ab
    3. only if a ≠ b
    4. the question does not apply to finite languages

Rule Card

  • Final state: input read, state ∈ F, stack anything. Empty stack: input read, stack empty, state anything.
  • NPDA: both conventions = CFL (convert with a new bottom marker).
  • DPDA: empty stack ⇒ only prefix-free DCFLs; final state ⇒ all DCFLs. GATE default: final state.

Concept Ledger

  • acceptance by final state L(P)
  • acceptance by empty stack N(P)
  • prefix-free language
  • new bottom-marker trick

Answer Vault

Reveal answers when you’re ready

Warm-up answers

  1. Reads a with A on top and pushes another A.
  2. A string with two parse trees.
  3. When some path ends in an accepting state.

Self-test answers

  1. B — Both conditions at the end.
    • A: States are irrelevant.
    • C: Input must be fully read.
    • D: Z₀ must be popped too.
  2. ABD — The DPDA asymmetry.
    • C: Empty-stack DPDAs are weaker.
  3. B — A proper prefix exists.
    • A: a is a prefix of ab.
    • C: Unrelated.
    • D: It applies.

Flashcards

  1. Are final-state and empty-stack acceptance equivalent for NPDAs?
    Reveal answerYes — both give the CFLs.
  2. What can an empty-stack DPDA accept?
    Reveal answerOnly prefix-free DCFLs.
  3. GATE’s default PDA acceptance?
    Reveal answerFinal state.
ONE MORE CONNECTION MADE

Ready for the next idea?

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