Context-Free Grammars & Pushdown Automata

Context-Free Grammars (CFGs) and Pushdown Automata (PDAs) describe the next level of the Chomsky hierarchy — Context-Free Languages. This is the class that captures the structure of most programming languages.

Context-Free Grammar — formal definition:
A CFG is a 4-tuple (V, Σ, R, S):
- V — variables (non-terminals): symbols that can be replaced. Written in UPPERCASE or <angle brackets>
- Σ — terminals: the actual symbols in strings (alphabet). Written in lowercase
- R — production rules: V → (V ∪ Σ)* — each variable maps to a string of variables and terminals
- S — start variable

Derivation: start with S, repeatedly replace any variable using a production rule, until only terminals remain. The set of all strings derivable from S is the language L(G).

Example: grammar for balanced parentheses:
S → ε | SS | (S)
- ε (empty string) — zero pairs
- SS — two balanced groups concatenated
- (S) — a balanced group wrapped in parens
Derives: ε, (), (()), ()(), ((())), etc.

Parse trees: derivations can be visualized as trees. The leaves (read left to right) give the derived string. Parse trees expose the STRUCTURE of the string (precedence, association) — this is what compilers build.

Ambiguity: a grammar is AMBIGUOUS if some string has two different parse trees. This is bad for compilers — two parses mean two interpretations! Classic example: E → E+E | E*E | id. The string "id+id*id" has two parse trees (add first, or multiply first?). Fix: rewrite grammar to encode precedence.

CFL Pumping Lemma: if L is context-free, long enough strings have the form uvwxy where:
- |vwx| ≤ p (pumping length)
- |vx| ≥ 1
- For all i ≥ 0: uvⁱwxⁱy ∈ L
Used to prove languages are NOT context-free. Example: aⁿbⁿcⁿ is not CFL.

Pushdown Automaton (PDA) — FA + stack:
A PDA is an NFA with an unlimited stack. On each transition:
- Read input symbol (or ε)
- Pop a symbol from stack (or ε)
- Push a string of symbols onto stack (or ε)
- Move to next state

The stack provides the "counting" ability DFAs lack. To recognize aⁿbⁿ:
① Push 'a' onto stack for each 'a' read
② Pop one 'a' for each 'b' read
③ Accept if stack is empty at end

Every CFL has a PDA and every PDA recognizes a CFL — they are equivalent.

Chomsky Normal Form (CNF): every CFG can be converted to CNF where every rule is either:
- A → BC (two variables)
- A → a (one terminal)
CNF is used by the CYK parsing algorithm — O(n³) — can parse ANY CFG.

1# CFG and PDA simulations
2
3# ── CFG: generate strings from a grammar ──────────────
4import random
5from collections import defaultdict
6
7class CFG:
8    def __init__(self, productions, start):
9        """productions: dict {variable: [list of alternatives]}
10           Each alternative is a list of symbols"""
11        self.productions = productions
12        self.start       = start
13
14    def generate(self, symbol=None, max_depth=10, depth=0):
15        """Randomly generate a string from the grammar"""
16        if symbol is None:
17            symbol = self.start
18        if depth > max_depth:
19            return ""
20        if symbol not in self.productions:
21            return symbol   # terminal
22        alternatives = self.productions[symbol]
23        chosen = random.choice(alternatives)
24        return "".join(self.generate(s, max_depth, depth+1) for s in chosen)
25
26    def derives(self, target, symbol=None, memo=None):
27        """Check if target can be derived (for small grammars)"""
28        if memo is None: memo = {}
29        if symbol is None: symbol = self.start
30        if (symbol, target) in memo: return memo[(symbol, target)]
31
32        if symbol not in self.productions:
33            result = symbol == target
34        else:
35            result = False
36            for alt in self.productions[symbol]:
37                if len(alt) == 1:
38                    result = result or self.derives(target, alt[0], memo)
39                # (simplified — full CYK for general case)
40        memo[(symbol, target)] = result
41        return result
42
43# ── Balanced parentheses grammar ───────────────────────
44# S → ε | (S) | SS
45balanced_grammar = CFG(
46    productions = {
47        "S": [[], ["(", "S", ")"], ["S", "S"]],
48    },
49    start = "S"
50)
51
52print("Generating balanced parentheses strings:")
53random.seed(42)
54generated = set()
55for _ in range(20):
56    s = balanced_grammar.generate(max_depth=6)
57    generated.add(s)
58for s in sorted(generated, key=len)[:10]:
59    print(f"  '{s}'")
60
61# ── PDA for aⁿbⁿ ──────────────────────────────────────
62class PDA:
63    """Nondeterministic PDA simulation"""
64    def __init__(self, transitions, start, accept, bottom="Z"):
65        """transitions: list of (state, input_sym, stack_top, next_state, stack_push)
66           None = epsilon for input or stack"""
67        self.transitions = transitions
68        self.start       = start
69        self.accept      = accept
70        self.bottom      = bottom
71
72    def accepts(self, string):
73        # (state, input_pos, stack)
74        configs = {(self.start, 0, (self.bottom,))}
75
76        for _ in range(len(string) * 10 + 10):  # bound iterations
77            new_configs = set()
78            for state, pos, stack in configs:
79                for (q, inp, stk_top, next_q, push) in self.transitions:
80                    if q != state: continue
81                    # Check input
82                    if inp is None:
83                        new_pos = pos
84                    elif pos < len(string) and string[pos] == inp:
85                        new_pos = pos + 1
86                    else:
87                        continue
88                    # Check stack top
89                    if not stack: continue
90                    if stk_top is None:
91                        new_stack = stack
92                    elif stack[-1] == stk_top:
93                        new_stack = stack[:-1]
94                    else:
95                        continue
96                    # Push to stack
97                    if push:
98                        new_stack = new_stack + tuple(reversed(push))
99                    new_configs.add((next_q, new_pos, new_stack))
100            configs |= new_configs
101
102        return any(
103            state in self.accept and pos == len(string)
104            for state, pos, stack in configs
105        )
106
107# PDA for aⁿbⁿ
108pda = PDA(
109    transitions = [
110        # (state, input, stack_top, next_state, push_string)
111        ("q0", "a", "Z", "q0", "AZ"),   # push A, keep Z
112        ("q0", "a", "A", "q0", "AA"),   # push A
113        ("q0", "b", "A", "q1", ""),     # pop A (start matching)
114        ("q1", "b", "A", "q1", ""),     # pop A
115        ("q1", None,"Z", "q2", "Z"),    # epsilon: if stack = Z, accept
116    ],
117    start  = "q0",
118    accept = {"q2"},
119)
120
121print("
122PDA: aⁿbⁿ")
123tests = ["", "ab", "aabb", "aaabbb", "aab", "abb", "abab", "aaabb"]
124for s in tests:
125    result = pda.accepts(s)
126    n = len(s) // 2
127    expected = s == "a"*n + "b"*n and len(s) % 2 == 0
128    check = "✓" if result == expected else "?"
129    print(f"  '{s}' → {'ACCEPT' if result else 'REJECT'} {check}")
130
131# ── Real-world CFG: Python uses a CFG! ────────────────
132print("
133Python's grammar IS a CFG:")
134print("  stmt  → expr_stmt | if_stmt | while_stmt | ...")
135print("  if_stmt → 'if' expr ':' suite ['else' ':' suite]")
136print("  expr  → expr '+' term | term")
137print("  term  → term '*' factor | factor")
138print("  factor → '(' expr ')' | NUMBER | NAME")
139print()
140print("  import ast")
141print("  tree = ast.parse('x = 1 + 2 * 3')")
142print("  ast.dump(tree)  ← THIS IS THE PARSE TREE")
143import ast
144tree = ast.parse("x = 1 + 2 * 3")
145print(f"
146  {ast.dump(tree, indent=2)[:300]}...")