Pushdown Automata & Context-Free Languages: CFGs, PDAs, Parsing & Proofs

TAKEAWAYS:

• Understand the stack-based memory of PDAs and how it enables parsing nested structures (e.g., parentheses, brackets).
• Master CFG simplification (removing useless symbols, unit productions, and chaining) to standardize grammars for analysis.
• Design PDAs for languages like {aⁿbⁿ} or {w wᵣ | w ∈ Σ*} using epsilon transitions and stack operations.
• Apply the Pumping Lemma for CFGs to prove languages are not context-free (e.g., {aⁿbⁿcⁿ}).
• Compare top-down vs. bottom-up parsing (e.g., recursive descent vs. LR parsers) and their real-world use in compilers.
• Recognize ambiguity in CFGs and its impact on parsing efficiency (e.g., arithmetic expressions).

1. Context-Free Grammars (CFGs): Formal Definition and Structure

A Context-Free Grammar (CFG) is a 4-tuple $G=(V,\Sigma ,R,S)$, where:

• $V$: Non-terminal symbols (e.g., $S,A,B$).
• $\Sigma$: Terminal symbols (e.g., $a,b,c$).
• $R$: Production rules (e.g., $S\to aSb$).
• $S$: Start symbol.

Key Components Visualized

classDiagram
    class CFG {
        +V: Non-terminals
        +Σ: Terminals
        +R: Productions
        +S: Start symbol
    }
    CFG --> "1" Production : contains
    Production --> "0..*" Symbol : expands to
    Symbol <|-- NonTerminal
    Symbol <|-- Terminal

Example CFG for $L=\{a^n{b}^n|n\ge 1\}$

S → aSb | ab

• Derivation: $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabbb$ (for $n=3$).

Simplifying CFGs

Goal: Remove useless symbols (non-generating or unreachable) and unit productions (e.g., $A\to B$). Steps:

1. Remove unreachable non-terminals: Delete symbols not derivable from $S$.
2. Remove non-generating symbols: Delete symbols that cannot derive any terminal string.
3. Remove unit productions: Replace $A\to B$ with productions of $B$.

Example: Original CFG:

S → Aa | Bb
A → aA | ε
B → bB | ε

Simplified CFG (after removing $B$ and unit productions):

S → aA | b
A → aA | ε

2. Pushdown Automata (PDAs): The Stack-Based Machine

A PDA extends a DFA with a stack to recognize context-free languages (CFLs). Formal Definition: $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$, where:

• $\Gamma$: Stack alphabet.
• $\delta$: Transition function $\delta (q,a,X)\to \{(p,\gamma )\}$ (push/pop).
• $Z_0$: Start stack symbol.
• $F$: Accepting states.

PDA Block Diagram

Example PDA for $L=\{a^n{b}^n|n\ge 1\}$

States: $\{q_0,q_1,q_{accept}\}$. Stack Alphabet: $\{Z_0,A\}$. Transitions:

1. Push $A$ for each $a$: $\delta (q_0,a,Z_0)\to (q_0,A{Z}_0)$.
2. Pop $A$ for each $b$: $\delta (q_0,b,A)\to (q_0,ϵ)$.
3. Accept if stack is empty: $\delta (q_0,ϵ,Z_0)\to (q_{accept},ϵ)$.

Trace for aab:

3. Epsilon Transitions in PDAs

Definition: Transitions without consuming input ($\delta (q,ϵ,X)$). Purpose:

• Simplify PDA design (e.g., handle nested structures like aⁿbᵐcⁿ).
• Enable non-determinism (guessing stack operations).

Example PDA for $L=\{a^n{b}^m{c}^n|n,m\ge 1\}$:

1. Push $A$ for each $a$.
2. Use $ϵ$-transitions to switch to $b$-mode.
3. Pop $A$ for each $c$.

stateDiagram-v2
    [*] --> q0 : read a
    q0 --> q0 : push A, read a
    q0 --> q1 : ε
    q1 --> q1 : pop A, read b
    q1 --> q2 : ε
    q2 --> q2 : pop A, read c
    q2 --> q_accept : ε, stack empty

4. Parsing Techniques: Top-Down vs. Bottom-Up

Real-World Example: Compilers (e.g., GCC, Clang)

• Front-end parsers use LR parsers (bottom-up) to validate code syntax.
• Ambiguous grammars (e.g., if-else statements) require disambiguation rules.

5. Proving Languages Are Not Context-Free

Tool: Pumping Lemma for CFGs. Statement: For any CFG $G$, there exists a pumping length $p$ such that for any string $z\in L(G)$ with $|z|\ge p$, $z$ can be divided into $z=xyz$ where:

1. $|xy|\le p$,
2. $|y|\ge 1$,
3. $x{y}_{i}z\in L(G)$ for all $i\ge 0$.

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

Proof:

1. Assume $L$ is CFL. Let $p$ be the pumping length.
2. Take $z=a^p{b}^p{c}^p$. Divide into $xyz$:
   • $x=a^k$, $y=a^l$, $z=b^p{c}^p$ (where $k+l=p$).
3. Pump $y$: $x{y}^{2}z=a^{k+2l}{b}^p{c}^p$. This is not in $L$ unless $l=0$.
4. Contradiction: No valid pumping exists. Thus, $L$ is not CFL.

6. Ambiguity in CFGs

Definition: A CFG is ambiguous if a string has multiple leftmost derivations. Example: Grammar for arithmetic expressions:

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

• String id + id * id has 5 parse trees.

Real-World Impact:

• Compilers must resolve ambiguity (e.g., operator precedence).
• Pathao’s ride-sharing app uses CFGs to parse user queries (e.g., "Go to Thamel via Ring Road") but avoids ambiguity with disambiguation rules.

## In the Real World

1. Khalti’s Transaction Validation

   • Uses PDAs to parse nested JSON/XML requests (e.g., {"user": {"payment": {"amount": 1000}}} ).
   • The stack ensures balanced tags (like aⁿbⁿ but for <?xml>...</xml>).

2. Daraz’s Order Processing Queue

   • CFGs model order states: Order → Placed → Shipped → Delivered.
   • Ambiguity is avoided by strict production rules (e.g., Shipped → Delivered only after PaymentConfirmed).

3. Ncell’s USSD Menu Parser

   • Top-down parsing handles nested menus:

     Main → Balance → *123# → Check → *123*1# → Display
     

   • PDAs validate input sequences (e.g., reject *123*2# if 2 is invalid).

## Exam Tip

1. For CFG Simplification:

   • Always remove unit productions first, then useless symbols.
   • Mark steps clearly (e.g., "After Step 2, $A$ is non-generating").

2. For PDA Design:

   • Label transitions with stack operations (e.g., "Push $X$").
   • Test edge cases: Empty string, single symbol, and maximum stack depth.

3. For Pumping Lemma Proofs:

   • Pick the "worst-case" string (e.g., $a^p{b}^p{c}^p$).
   • Show why pumping fails (e.g., unbalanced counts).

4. Ambiguity Questions:

   • Draw parse trees for the given string to prove ambiguity.
   • Suggest fixes (e.g., add precedence rules).

Visual Summary:

mindmap
  root((Pushdown Automata & CFGs))
    CFG
      Definition
      Simplification
      Ambiguity
    PDA
      Stack Operations
      Epsilon Transitions
      Design Steps
    Parsing
      Top-Down
      Bottom-Up
    Proofs
      Pumping Lemma
      Non-CFL Examples