Context-Free Languages & Pushdown Automata: Grammars, Parsing, and PDA

TAKEAWAYS:

• Context-free grammars (CFGs) define languages where production rules apply to non-terminals without context, enabling syntax for programming languages and natural language parsing.
• Chomsky Normal Form (CNF) simplifies CFGs into binary productions (A→BC or A→a), crucial for parsing algorithms like CYK and Earley.
• Pushdown Automata (PDAs) extend finite automata with a stack, accepting context-free languages by tracking nested structures (e.g., balanced parentheses).
• The Pumping Lemma for CFLs proves languages like {aⁿbⁿcⁿ} are not context-free by showing no finite "pumpable" substring can generate all strings.
• Real-world applications include compilers (validating code syntax), HTML/XML parsers (checking tag balance), and stack-based algorithms (e.g., evaluating arithmetic expressions).
• Key difference: CFGs handle recursion/nesting (e.g., loops in code), while regular grammars only handle linear patterns (e.g., fixed-length IDs).

1. Context-Free Grammars (CFGs): Definitions and Examples

A context-free grammar (CFG) is a 4-tuple $G=(V,\Sigma ,R,S)$, where:

• $V$: finite set of non-terminals (e.g., S, A, B).
• $\Sigma$: finite set of terminals (e.g., a, b, +).
• $R$: set of production rules (e.g., $S\to aSb$).
• $S$: start symbol (a non-terminal).

Key Property: Productions apply to single non-terminals without context (hence "context-free"). Example: Grammar for balanced parentheses:

S → SS | (S) | ε

Visualization:

graph TD
  S["S"] --> S1["S → S S"]
  S --> P[(S)]
  S --> E["ε"]
  P --> L[(
  L --> S2["S"]
  S2 --> R[")"]

Derivation Trace for (()):

1. $S\Rightarrow (S)$
2. $(S)\Rightarrow ((S))$
3. $((S))\Rightarrow ((\epsilon ))\Rightarrow (())$

2. Chomsky Normal Form (CNF)

CNF restricts productions to:

1. $A\to BC$ (two non-terminals), or
2. $A\to a$ (single terminal), or
3. $S\to \epsilon$ (only for start symbol).

Why CNF?

• Simplifies parsing algorithms (e.g., CYK dynamic programming).
• Proves equivalence between CFGs and PDAs.

Example: Convert $S\to aSb\mid \epsilon$ to CNF.

1. Introduce new non-terminals:
   • $S\to aAB\mid \epsilon$
   • $A\to Sb$
   • $B\to \epsilon$
2. Eliminate $\epsilon$-productions (if needed) by adding $B\to \epsilon$.

3. Pushdown Automata (PDAs): Stack-Based Recognition

A PDA extends NFAs with a stack to handle nested structures. Formal Definition: $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$, where:

• $\Gamma$: stack alphabet.
• $\delta$: transition function (may push/pop stack).
• $Z_0$: start stack symbol.

Example: PDA for $L=\{a^n{b}^n\mid n\ge 0\}$.

Trace for aabb:

1. Push A for each a: stack = [A, A].
2. Pop A for each b: stack empties → accept.

4. The Pumping Lemma for Context-Free Languages (CFLs)

Statement: If $L$ is CFL, there exists a pump length $p$ such that any $z\in L$ with $|z|\ge p$ can be divided into $z=xyz$, where:

• $|xy|\le p$,
• $|y|\ge 1$,
• $x{y}^{i}z\in L$ for all $i\ge 0$.

Proof Sketch:

1. Assume $L$ is CFL; derive a PDA.
2. Show the PDA’s stack cannot "remember" unbounded context (e.g., $a^n{b}^n{c}^n$ requires 3 stacks).

Example: Prove $L=\{a^n{b}^n{c}^n\}$ is not CFL.

• Assume $L$ is CFL; pick $z=a^p{b}^p{c}^p$.
• Pump $y=a^i{b}^i$: $x{y}^{2}z=a^{p+i}{b}^{p+i}{c}^p\notin L$ (unbalanced $c$s).
• Contradiction: $L$ cannot be CFL.

5. Applications in Real-World Systems

In the Real World

1. Compilers (e.g., GCC, Java Compiler)

   • Idea Used: CFGs define syntax rules (e.g., if (condition) { statements }).
   • How: Parsers (e.g., recursive descent) use CFGs to validate code structure before execution.

2. HTML/XML Parsers (e.g., Chrome’s Blink Engine)

   • Idea Used: PDA-like stack to track nested tags (e.g., <div><p></p></div>).
   • How: Push opening tags, pop on closing tags; mismatch → error.

3. Arithmetic Expression Evaluators (e.g., Python’s eval())

   • Idea Used: PDA stack to handle operator precedence (e.g., 3 + 4 * 2).
   • How: Push operands, apply operations when higher-precedence operators are encountered.

4. Nepali Apps: eSewa/Khalti Transaction Validation

   • Idea Used: CFGs validate transaction formats (e.g., PAY <amount> <to> <ref>).
   • How: Reject malformed inputs (e.g., PAY 500 without recipient).

5. Bank Loan Amortization (Nepal’s NMB/Global IME)

   • Idea Used: Recursive CFG to model loan repayment schedules.
   • How: Each payment reduces principal + interest, mirrored in PDA stack states.

6. Worked Example: PDA for Balanced Parentheses

Language: $L=\{w\mid w\text{ has balanced parentheses}\}$. PDA Design:

stateDiagram-v2
  [*] --> q0: start
  q0 --> q0: read '(', push '('
  q0 --> q1: read ')', pop '('
  q1 --> q1: read ')', pop '('
  q1 --> q0: read '(', push '('
  q0 --> accept: stack empty, read ε

Trace for (()):

1. Push (, (: stack = [(, (].
2. Pop (, (: stack empty → accept.

7. Comparison: Regular vs. Context-Free Languages

8. Exam Tip: How to Score Full Marks

1. For CFG → CNF Conversion:

   • Show every intermediate step (e.g., introducing $A\to \epsilon$).
   • Label new non-terminals clearly (e.g., $A_1,A_2$).

2. For PDA Construction:

   • Draw the state diagram with stack operations.
   • Trace one example string (e.g., aabb for $a^n{b}^n$).

3. Pumping Lemma Proofs:

   • Assume the language is CFL → derive contradiction.
   • Pick a string with $n\ge p$ (e.g., $a^p{b}^p{c}^p$).
   • Pump $y$ and show the result violates the language definition.

4. Real-World Links:

   • Tie CFGs to compiler syntax or HTML parsing.
   • For PDAs, mention stack-based algorithms (e.g., Dijkstra’s shortest path).

5. Avoid Common Mistakes:

   • ❌ Forgetting to handle $\epsilon$-productions in CNF.
   • ❌ PDA transitions without stack updates.
   • ❌ Pumping Lemma: not all substrings can be pumped (e.g., $y$ must be derivable from $S$).

Derivation tree for $S\to aSb\mid \epsilon$ (Image: MartinThoma, CC BY 3.0, via Wikimedia Commons)