Acceptance by Final State and Empty Stack

Two Acceptance Modes

PDAs have two different ways to accept strings:

1. Acceptance by Final State (PDA_F)
2. Acceptance by Empty Stack (PDA_N)

Important: Both are equally powerful! They recognize the same class of languages (CFLs).

Simple Analogy

Think of finishing a task:

• Final state: Reaching a specific “done” checkpoint
• Empty stack: Completing all sub-tasks (stack empty)

Both indicate success, just different criteria!

Acceptance by Final State (PDA_F)

Definition

PDA M accepts string w by final state if:

(q₀, w, Z₀) ⊢* (p, ε, α)

where:

• q₀ is start state
• Z₀ is initial stack symbol
• p ∈ F (p is a final state)
• ε means input exhausted
• α is any stack contents (don’t care!)

Key points:

• Must reach a state in F
• Must consume all input
• Stack contents don’t matter

Notation

L(M) = Language accepted by M (by final state)

L(M) = {w ∈ Σ* | (q₀, w, Z₀) ⊢* (p, ε, α) for some p ∈ F, α ∈ Γ*}

Example 1: {aⁿbⁿ} by Final State

PDA Definition:

Q = {q₀, q₁, q₂}
Σ = {a, b}
Γ = {A, Z₀}
Start: q₀
Initial stack: Z₀
Final: F = {q₂}  ← Important!

Transitions:

δ(q₀, a, Z₀) = {(q₀, AZ₀)}
δ(q₀, a, A) = {(q₀, AA)}
δ(q₀, b, A) = {(q₁, ε)}
δ(q₁, b, A) = {(q₁, ε)}
δ(q₁, ε, Z₀) = {(q₂, Z₀)}  ← Move to final state

Acceptance for “aabb”:

(q₀, aabb, Z₀)
  ⊢* (q₁, ε, Z₀)
  ⊢ (q₂, ε, Z₀)  ← q₂ ∈ F, input empty ✓

Stack has Z₀, but that’s OK! (We only care about final state)

Example 2: Balanced Parentheses by Final State

PDA:

Q = {q₀, qf}
Σ = {(, )}
Γ = {X, Z₀}
Final: F = {qf}

Transitions:

δ(q₀, (, Z₀) = {(q₀, XZ₀)}
δ(q₀, (, X) = {(q₀, XX)}
δ(q₀, ), X) = {(q₀, ε)}
δ(q₀, ε, Z₀) = {(qf, Z₀)}  ← Go to final

Accept ”(())“:

(q₀, (()), Z₀)
  ⊢* (q₀, ε, Z₀)
  ⊢ (qf, ε, Z₀)  ← Final state! ✓

Acceptance by Empty Stack (PDA_N)

Definition

PDA M accepts string w by empty stack if:

(q₀, w, Z₀) ⊢* (p, ε, ε)

where:

• q₀ is start state
• Z₀ is initial stack symbol
• p is any state (don’t care!)
• ε means input exhausted
• ε means stack empty

Key points:

• Must empty the stack
• Must consume all input
• Final state doesn’t matter (usually F = ∅)

Notation

N(M) = Language accepted by M (by empty stack)

N(M) = {w ∈ Σ* | (q₀, w, Z₀) ⊢* (p, ε, ε) for some p ∈ Q}

Example 1: {aⁿbⁿ} by Empty Stack

PDA Definition:

Q = {q₀, q₁}
Σ = {a, b}
Γ = {A, Z₀}
Start: q₀
Initial stack: Z₀
Final: F = ∅  ← No final states needed!

Transitions:

δ(q₀, a, Z₀) = {(q₀, AZ₀)}
δ(q₀, a, A) = {(q₀, AA)}
δ(q₀, b, A) = {(q₁, ε)}
δ(q₁, b, A) = {(q₁, ε)}
δ(q₁, ε, Z₀) = {(q₁, ε)}  ← Pop Z₀ to empty stack!

Acceptance for “aabb”:

(q₀, aabb, Z₀)
  ⊢ (q₀, abb, AZ₀)
  ⊢ (q₀, bb, AAZ₀)
  ⊢ (q₁, b, AZ₀)
  ⊢ (q₁, ε, Z₀)
  ⊢ (q₁, ε, ε)  ← Stack empty! ✓

Input consumed AND stack empty = ACCEPT!

Example 2: Balanced Parentheses by Empty Stack

PDA:

Q = {q₀}
Σ = {(, )}
Γ = {X, Z₀}
Start: q₀
Final: ∅  ← No final states

Transitions:

δ(q₀, (, Z₀) = {(q₀, XZ₀)}
δ(q₀, (, X) = {(q₀, XX)}
δ(q₀, ), X) = {(q₀, ε)}
δ(q₀, ε, Z₀) = {(q₀, ε)}  ← Pop Z₀

Accept ”(())“:

(q₀, (()), Z₀)
  ⊢ (q₀, ()), XZ₀)
  ⊢ (q₀, )), XXZ₀)
  ⊢ (q₀, ), XZ₀)
  ⊢ (q₀, ε, Z₀)
  ⊢ (q₀, ε, ε)  ← Empty stack! ✓

Comparison: Final State vs Empty Stack

Visual Comparison

Acceptance by Final State:
─────────────────────────────
Start: (q₀, w, Z₀)
         |
        ...
         |
End: (qf, ε, anything)
      ↑          ↑
   Must be    Stack can
   in F       be anything

Acceptance by Empty Stack:
─────────────────────────────
Start: (q₀, w, Z₀)
         |
        ...
         |
End: (any, ε, ε)
      ↑        ↑
   State     Must be
   doesn't   empty
   matter

Table Comparison

Equivalence Theorem

Statement

Theorem: For every language L:

• If L = L(M) for some PDA M (final state), then L = N(M’) for some PDA M’ (empty stack)
• If L = N(M) for some PDA M (empty stack), then L = L(M’) for some PDA M’ (final state)

In other words: Both acceptance modes are equally powerful!

Why This Matters

• Can use whichever is more convenient
• Both recognize exactly the CFLs
• Can convert between them

Converting Final State → Empty Stack

Goal: Given PDA M accepting by final state, construct M’ accepting by empty stack

Strategy: When M reaches final state, empty the stack

Algorithm

Input: M = (Q, Σ, Γ, δ, q₀, Z₀, F) accepting L(M)
Output: M' = (Q', Σ, Γ', δ', q₀', X₀, ∅) accepting N(M') = L(M)

Steps:
1. Add new start state q₀' with new bottom marker X₀
2. Add new state q_empty for emptying stack
3. Start by pushing Z₀ onto X₀
4. Simulate M normally
5. When reaching state in F, can transition to q_empty
6. In q_empty, pop everything until stack empty

Detailed Construction

New PDA M’:

Q' = Q ∪ {q₀', q_empty}  (add 2 new states)
Γ' = Γ ∪ {X₀}  (add new bottom marker)
Start: q₀'
Final: ∅

New transitions δ’:

1. δ'(q₀', ε, X₀) = {(q₀, Z₀X₀)}
   "Start M with Z₀ on top of X₀"

2. For all transitions in δ: include them in δ'
   "Simulate M normally"

3. For all p ∈ F, all A ∈ Γ':
   δ'(p, ε, A) = {(q_empty, ε)}
   "When reaching final state, go to emptying state"

4. For all A ∈ Γ':
   δ'(q_empty, ε, A) = {(q_empty, ε)}
   "Pop everything in emptying state"

Example: {aⁿbⁿ}

Original M (final state):

Q = {q₀, q₁, q₂}
F = {q₂}
Transitions:
  δ(q₀, a, Z₀) = {(q₀, AZ₀)}
  δ(q₀, a, A) = {(q₀, AA)}
  δ(q₀, b, A) = {(q₁, ε)}
  δ(q₁, b, A) = {(q₁, ε)}
  δ(q₁, ε, Z₀) = {(q₂, Z₀)}  ← final state

Converted M’ (empty stack):

Q' = {q₀', q₀, q₁, q₂, q_empty}
Γ' = {A, Z₀, X₀}
F' = ∅

Transitions:
  // New start
  δ'(q₀', ε, X₀) = {(q₀, Z₀X₀)}

  // Copy old transitions
  δ'(q₀, a, Z₀) = {(q₀, AZ₀)}
  δ'(q₀, a, A) = {(q₀, AA)}
  δ'(q₀, b, A) = {(q₁, ε)}
  δ'(q₁, b, A) = {(q₁, ε)}
  δ'(q₁, ε, Z₀) = {(q₂, Z₀)}

  // Empty stack from final state
  δ'(q₂, ε, Z₀) = {(q_empty, ε)}
  δ'(q_empty, ε, X₀) = {(q_empty, ε)}

Trace for “aabb”:

(q₀', aabb, X₀)
  ⊢ (q₀, aabb, Z₀X₀)
  ⊢* (q₂, ε, Z₀X₀)     ← Final state
  ⊢ (q_empty, ε, X₀)   ← Pop Z₀
  ⊢ (q_empty, ε, ε)     ← Pop X₀, ACCEPT! ✓

Converting Empty Stack → Final State

Goal: Given PDA M accepting by empty stack, construct M’ accepting by final state

Strategy: When stack becomes empty, transition to final state

Algorithm

Input: M = (Q, Σ, Γ, δ, q₀, Z₀, ∅) accepting N(M)
Output: M' = (Q', Σ, Γ', δ', q₀', X₀, F') accepting L(M') = N(M)

Steps:
1. Add new start state q₀' with new bottom marker X₀
2. Add new final state qf
3. Start by pushing Z₀ onto X₀
4. Simulate M normally (X₀ stays at bottom)
5. When M empties its stack (only X₀ left), go to qf
6. qf is the only final state

Detailed Construction

New PDA M’:

Q' = Q ∪ {q₀', qf}
Γ' = Γ ∪ {X₀}
Start: q₀'
Final: F' = {qf}

New transitions δ’:

1. δ'(q₀', ε, X₀) = {(q₀, Z₀X₀)}
   "Start M with Z₀ on top of X₀"

2. For all δ(q, a, A) = {(p, α)} where A ≠ X₀:
   δ'(q, a, A) = {(p, α)}
   "Simulate M, but don't touch X₀"

3. For all q ∈ Q:
   δ'(q, ε, X₀) = {(qf, X₀)}
   "When X₀ exposed (stack empty), go to final"

Example: {aⁿbⁿ}

Original M (empty stack):

Q = {q₀, q₁}
F = ∅
Transitions:
  δ(q₀, a, Z₀) = {(q₀, AZ₀)}
  δ(q₀, a, A) = {(q₀, AA)}
  δ(q₀, b, A) = {(q₁, ε)}
  δ(q₁, b, A) = {(q₁, ε)}
  δ(q₁, ε, Z₀) = {(q₁, ε)}  ← empties stack

Converted M’ (final state):

Q' = {q₀', q₀, q₁, qf}
Γ' = {A, Z₀, X₀}
F' = {qf}

Transitions:
  // New start
  δ'(q₀', ε, X₀) = {(q₀, Z₀X₀)}

  // Copy old (but protect X₀)
  δ'(q₀, a, Z₀) = {(q₀, AZ₀)}
  δ'(q₀, a, A) = {(q₀, AA)}
  δ'(q₀, b, A) = {(q₁, ε)}
  δ'(q₁, b, A) = {(q₁, ε)}
  δ'(q₁, ε, Z₀) = {(q₁, ε)}

  // Go to final when X₀ exposed
  δ'(q₀, ε, X₀) = {(qf, X₀)}
  δ'(q₁, ε, X₀) = {(qf, X₀)}

Trace for “aabb”:

(q₀', aabb, X₀)
  ⊢ (q₀, aabb, Z₀X₀)
  ⊢* (q₁, ε, Z₀X₀)
  ⊢ (q₁, ε, X₀)      ← Z₀ popped, X₀ exposed
  ⊢ (qf, ε, X₀)      ← Final state! ✓

Why Both Modes Are Useful

Final State Mode

Advantages:

• More intuitive for humans
• Easier to design
• Clear acceptance condition
• Stack can be reused after acceptance

Use cases:

• Practical parsers
• Compiler design
• Most applications

Example: Checking balanced parentheses

Empty Stack Mode

Advantages:

• Simpler theoretical proofs
• Natural for some constructions
• No need for final states
• Directly corresponds to consuming all resources

Use cases:

• Theoretical analysis
• CFG ↔ PDA conversion proofs
• Simplifying formal arguments

Example: Converting from CFG to PDA

Special Cases

Empty String (ε)

By final state:

δ(q₀, ε, Z₀) = {(qf, Z₀)}

Go directly to final state

By empty stack:

δ(q₀, ε, Z₀) = {(q₀, ε)}

Pop everything immediately

Single Character Languages

L = {a}

Final state:

δ(q₀, a, Z₀) = {(qf, Z₀)}

Empty stack:

δ(q₀, a, Z₀) = {(q₁, ε)}

Important Theorems

Theorem 1: Equivalence

For any language L: L is accepted by PDA by final state ⟺ L is accepted by PDA by empty stack

Proof: By construction (shown above)

Theorem 2: CFL Characterization

L is context-free ⟺ L = L(M) for some PDA M ⟺ L = N(M’) for some PDA M’

All three are equivalent!

Theorem 3: Conversion Preserves Language

If M accepts L by final state, then M’ (constructed as above) accepts L by empty stack, and vice versa

Common Exam Questions

Q1: Convert given PDA (final state) to empty stack

Solution:

1. Add new start state and bottom marker
2. Add emptying state
3. From final states, go to emptying state
4. Empty everything

Q2: Convert given PDA (empty stack) to final state

Solution:

1. Add new start state and bottom marker
2. Add final state
3. Protect bottom marker in simulation
4. When bottom exposed, go to final

Q3: Why are both modes equally powerful?

Answer: Can convert between them while preserving language (construction shown in theorems).

Q4: Which mode is better for practical use?

Answer: Final state (more intuitive), but empty stack is useful for theoretical proofs.

Important Exam Points

1. ✓ Two modes: Final state (L(M)) and empty stack (N(M))
2. ✓ Final state: Must reach state in F, stack doesn’t matter
3. ✓ Empty stack: Must empty stack, state doesn’t matter
4. ✓ Both consume input: Must process entire string
5. ✓ Equivalence: Both modes equally powerful
6. ✓ Conversion F→N: Add emptying state and new bottom marker
7. ✓ Conversion N→F: Add final state, detect empty via bottom marker
8. ✓ Use cases: Final state for practice, empty stack for theory
9. ✓ CFLs: Both characterize context-free languages
10. ✓ Choice: Use whichever is more convenient for the problem

Common Mistakes to Avoid

✗ Mistake 1: Thinking stack must be empty for final state acceptance
✓ Correct: Final state: stack can have anything

✗ Mistake 2: Thinking final states matter for empty stack
✓ Correct: Empty stack: state doesn’t matter (F = ∅)

✗ Mistake 3: Not consuming all input
✓ Correct: Both modes require input to be exhausted

✗ Mistake 4: Wrong conversion (forgetting bottom marker)
✓ Correct: Always add new bottom marker for conversions

✗ Mistake 5: Thinking one mode is more powerful
✓ Correct: Both equally powerful (can convert between them)

✗ Mistake 6: In conversion, touching bottom marker prematurely
✓ Correct: Protect bottom marker during simulation

Practice Questions

Q1: Does PDA accept by final state if stack is empty?

Answer: Yes, if it reaches final state (stack contents don’t matter).

Q2: Does PDA accept by empty stack if in non-final state?

Answer: Yes, state doesn’t matter for empty stack mode.

Q3: Why add new bottom marker in conversions?

Answer: To detect when original stack becomes empty.

Q4: Can a PDA accept by both modes simultaneously?

Answer: Not in general, but can be designed to do so for some languages.

Q5: Which is easier to design: final state or empty stack?

Answer: Usually final state (more intuitive).

Q6: Convert δ(q₀, a, Z₀) = {(qf, Z₀)} (final) to empty stack

Answer: Add δ(qf, ε, Z₀) = {(q_empty, ε)} and δ(q_empty, ε, X₀) = {(q_empty, ε)}.

Summary

• Two acceptance modes: Final state (L(M)) and empty stack (N(M))
• Final state: Reach state in F, input exhausted, stack anything
• Empty stack: Stack empty, input exhausted, state anything
• Equivalence: Both modes equally powerful (can convert)
• Conversion F→N: Add emptying mechanism when reaching final
• Conversion N→F: Add detection for empty stack via bottom marker
• Use cases: Final state (practical), empty stack (theoretical)
• Both consume input: Must process entire string
• CFLs: Both characterize context-free languages
• Choice: Use whichever is more convenient
• Key insight: Different acceptance criteria, same expressive power
• Applications: Parser design, CFG equivalence proofs

Understanding both modes and their equivalence is crucial for working with pushdown automata!