Context-Free Grammars & Pushdown Automata

Why Context-Free Grammars?

Analogy: DFAs are like simple vending machines with no memory. To describe nested structures like balanced parentheses "((()))" or programming language syntax (nested if-else, function calls), you need a STACK for memory. That is exactly what a PDA adds.

Key insight: CFGs describe languages that DFAs CANNOT: - {aⁿbⁿ | n≥0} (equal a's and b's) — requires counting - Balanced brackets: {(ⁿ)ⁿ} - All programming language syntax (nested blocks, expressions)

---

CFG — The Grammar of Languages

CFG G = (V, Σ, R, S)

V   = variables (non-terminals) — e.g., S, A, B
Σ   = terminal alphabet — e.g., {a, b, (, )}
R   = production rules — A → α (replace variable A with string α)
S   = start variable

Language L(G) = all terminal strings derivable from S

Example CFG for {aⁿbⁿ | n≥0}:

G: S → aSb | ε

Derivation of "aabb":
S ⇒ aSb ⇒ aaSbb ⇒ aaεbb = aabb ✓

Derivation of "aaabbb":
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaεbbb = aaabbb ✓

Example CFG for arithmetic expressions:

E → E+T | T
T → T*F | F
F → (E) | id

This grammar generates: id+id*id, (id+id)*id, etc.
The precedence (*  before +) is built into the grammar structure!

---

Parse Trees and Derivations

Parse tree = tree representation of a derivation
  Root = start variable S
  Internal nodes = variables
  Leaves = terminals

Leftmost derivation: always replace the LEFTMOST variable first
Rightmost derivation: always replace the RIGHTMOST variable first

Ambiguity:

A grammar is AMBIGUOUS if some string has TWO different parse trees
(equivalently: two different leftmost derivations)

Example: S → S+S | S*S | id
String "id+id*id" has TWO parse trees:
  Tree 1: (id+id)*id  (add first)
  Tree 2: id+(id*id)  (multiply first)
→ Ambiguous grammar!

The expression grammar E → E+T | T fixed this by enforcing precedence.

---

CNF — Chomsky Normal Form

Every CFG can be converted to CNF where every rule is: - A → BC (two variables), OR - A → a (one terminal)

Why useful: CNF is needed for CYK parsing algorithm (decides if string ∈ CFL in O(n³)).

Conversion steps:

1. Add new start: S₀ → S
2. Remove ε-productions: for each A → ε, add rules skipping A
3. Remove unit productions: A → B, trace chains
4. Break long rules: A → BCDE becomes A → BX, X → CY, Y → DE
5. Replace terminals in long rules: A → aB becomes A → XB, X → a

---

Pushdown Automaton (PDA)

Analogy: A DFA with a STACK. The stack is infinite memory. The machine can push and pop symbols to remember context.

PDA = (Q, Σ, Γ, δ, q₀, Z₀, F)

Γ = stack alphabet
δ: Q × (Σ ∪ {ε}) × Γ → 2^{Q × Γ*}  (non-deterministic)

Each transition:
  (read input symbol OR ε) + (pop stack top) → (new state, push string to stack)

Acceptance: by final state OR by empty stack (both equivalent in power)

PDA for {aⁿbⁿ}:

State q0: reading a's — push 'a' for each 'a' read
State q1: reading b's — pop 'a' for each 'b' read
Accept when: all b's read and stack is empty

Transition to q1: when first 'b' arrives, switch to popping mode

---

Pumping Lemma for CFLs

If L is CFL, ∃ pumping length p:
Every w ∈ L with |w| ≥ p can be split as w = uvxyz where:
  1. |vxy| ≤ p      (the "middle" is short)
  2. |vy| ≥ 1       (v or y is non-empty)
  3. ∀ i ≥ 0: uvⁱxyⁱz ∈ L  (pump v and y TOGETHER)

Key idea: v and y are pumped simultaneously

Classic Example: L = {aⁿbⁿcⁿ | n≥0} is NOT a CFL.

Choose w = aᵖbᵖcᵖ
Split as uvxyz with |vxy| ≤ p

Case 1: vxy is all within a's or b's or c's only
  Pumping v and y multiplies only 1 or 2 of the 3 symbol counts → unbalanced → NOT in L

Case 2: vxy spans two different symbol groups (e.g., some a's and some b's)
  Pumping changes a and b counts but NOT c → unbalanced → NOT in L

In all cases, uv²xy²z ∉ L. Contradiction. □

---

Closure Properties

CFLs ARE closed under:      CFLs are NOT closed under:
  ✓ Union                     ✗ Intersection
  ✓ Concatenation             ✗ Complement
  ✓ Kleene star
  ✓ Reversal
  ✓ Homomorphism
  ✓ Intersection with REGULAR language

GATE TRAP: "Intersection of two CFLs" — NOT necessarily a CFL!
Classic example: {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ} which is NOT a CFL!

---

Chomsky Hierarchy — The Power Ladder

Regular (DFA/NFA/RE)
    ⊂ Context-Free (PDA/CFG)
        ⊂ Context-Sensitive (LBA)
            ⊂ Recursively Enumerable (Turing Machine)

Each level can describe strictly more languages than the level below.

---

Quick Check

Q1. Is every regular language also a CFL? Answer: Yes. Regular ⊂ CFL. Every DFA can be converted to a PDA (just ignore the stack). But not every CFL is regular — {aⁿbⁿ} is CFL but not regular.

Q2. Why are CFLs not closed under intersection? Answer: {aⁿbⁿcᵐ | n,m≥0} and {aᵐbⁿcⁿ | n,m≥0} are both CFLs. Their intersection is {aⁿbⁿcⁿ}, which is NOT a CFL (shown by pumping lemma). So intersection of CFLs is not always CFL.

Q3. What is an ambiguous grammar? Give a fix strategy. Answer: A grammar where some string has two parse trees. Fix by restructuring rules to enforce associativity and precedence (like separating E → E+T, T → TF, F for arithmetic).*