🧠 CFG Fundamentals

🎯 What is a Context-Free Grammar?

A Context-Free Grammar (CFG) is a formal system for generating strings. It consists of rewrite rules that replace a single nonterminal symbol with a sequence of symbols. CFGs are more powerful than regular expressions — they can describe nested structures like balanced parentheses, arithmetic expressions, and programming language syntax.

Why CFGs Matter

Power: Beyond regular languages (can count). Nesting: Handles recursive structures. Compilers: Syntax analysis. Parsing: CYK, Earley, LL, LR. Natural language: Sentence structure. Foundation: Chomsky hierarchy (Type 2).

📌 Rewrite rules📌 Nested structures📌 Parsing📌 Compilers

# Context-Free Grammar — the big picture
print("""
=== What Makes a Grammar Context-Free? ===

A rule replaces ONE nonterminal:

  CONTEXT-FREE:     A → α      (A is a single nonterminal)
  CONTEXT-SENSITIVE: αAβ → αγβ  (A depends on context)

"Context-free" means the replacement of A
doesn't depend on what's around it.

=== Real-World Example: Arithmetic Expressions ===

Grammar G:
  E → E + T | T
  T → T * F | F
  F → ( E ) | id

This generates expressions like:
  id
  id + id
  id * id
  (id + id) * id
  id + id * id

The nesting of parentheses is what makes this
impossible for regular expressions!

=== The Chomsky Hierarchy ===

Type 0: Recursively Enumerable (Turing machines)
Type 1: Context-Sensitive (Linear bounded automata)
Type 2: Context-Free (Pushdown automata)  ← CFGs
Type 3: Regular (Finite automata)

CFGs are strictly more powerful than regular languages.
""")

# ANALOGY
print("=== Analogy: Recipe Book ===")
print("""
A CFG is like a recipe book with variables:

  Dish → Main Course | Dessert
  Main Course → Protein + Side
  Protein → Chicken | Fish | Tofu
  Side → Rice | Salad | Potato
  Dessert → Cake | Ice Cream

You start with "Dish" and apply rules
until you get a concrete meal.

Similarly, a CFG starts with S (start symbol)
and applies rules until you get a string of terminals.

The "context-free" part means each rule
can be applied regardless of context.
""")

# LANGUAGE CLASSIFICATION
print("=== Language Classification ===")
print("""
REGULAR LANGUAGES (Type 3):
  - Recognized by DFA/NFA
  - Described by regex
  - Examples: a*b*, (ab)*
  - Cannot count or nest

CONTEXT-FREE LANGUAGES (Type 2):
  - Recognized by PDA
  - Described by CFG
  - Examples: a^n b^n, balanced parens, arithmetic
  - Can count (one counter) and nest

CONTEXT-SENSITIVE (Type 1):
  - Recognized by LBA
  - Examples: a^n b^n c^n
  - Can count multiple things

RECURSIVELY ENUMERABLE (Type 0):
  - Recognized by Turing machines
  - Everything computable
""")

# PYTHON CFG EXAMPLE
print("=== Python: Simple CFG ===")

import random

class CFG:
    """A simple context-free grammar."""
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules  # dict: nonterminal -> list of productions
    
    def generate(self, symbol=None, max_depth=10):
        """Generate a random string from the grammar."""
        if symbol is None:
            symbol = self.start
        
        if max_depth <= 0:
            # Try to terminate
            if symbol not in self.rules:
                return symbol
            # Pick shortest production
            prods = self.rules[symbol]
            prods = sorted(prods, key=lambda p: (len(p), p))
            return self.generate(prods[0], 0)
        
        if symbol not in self.rules:
            return symbol  # terminal
        
        # Pick a random production
        prod = random.choice(self.rules[symbol])
        
        # Generate each symbol in the production
        result = []
        for s in prod:
            result.append(self.generate(s, max_depth - 1))
        return ''.join(result)
    
    def derive(self, string):
        """Check if string can be derived (brute force, limited)."""
        # BFS over derivations
        from collections import deque
        queue = deque([(self.start, [self.start])])
        visited = set()
        
        for _ in range(10000):
            if not queue:
                break
            current, path = queue.popleft()
            
            if current == string:
                return True, path
            
            if current in visited:
                continue
            visited.add(current)
            
            if len(current) > len(string) + 5:
                continue
            
            # Find first nonterminal
            for i, c in enumerate(current):
                if c in self.rules:
                    for prod in self.rules[c]:
                        new = current[:i] + prod + current[i+1:]
                        if len(new) <= len(string) + 5:
                            queue.append((new, path + [new]))
                    break
        
        return False, None


# Example: Balanced parentheses
paren_grammar = CFG('S', {
    'S': ['(S)', 'SS', '()'],
})

print("Balanced Parentheses Grammar:")
print("  S → (S) | SS | ()")
print("\nGenerated strings:")
for _ in range(8):
    s = paren_grammar.generate(max_depth=5)
    print(f"  '{s}'")

# Example: a^n b^n
anbn_grammar = CFG('S', {
    'S': ['aSb', ''],
})

print("\na^n b^n Grammar:")
print("  S → aSb | ε")
print("\nGenerated strings:")
for _ in range(6):
    s = anbn_grammar.generate(max_depth=5)
    print(f"  '{s}'")

# Check derivation
print("\nDerivation check:")
test_strings = ['()', '(())', '()()', '((()))', '(()']
for s in test_strings:
    result, path = paren_grammar.derive(s)
    if result:
        print(f"  '{s}' → ✓ derivable")
        print(f"    Path: {' → '.join(path[:6])}{'...' if len(path) > 6 else ''}")
    else:
        print(f"  '{s}' → ✗ not derivable")

print("""
=== Key Properties ===

1. GENERATIVE
   CFGs generate strings through derivations.

2. RECURSIVE
   Rules can refer to themselves (S → aSb).
   This enables nesting and counting.

3. CONTEXT-FREE
   Each rule replaces a single nonterminal.
   No dependence on surrounding symbols.

4. AMBIGUOUS
   Some strings have multiple parse trees.
   (See ambiguity section)

5. PARSING
   Given a string, find a derivation.
   CYK: O(n³), Earley: O(n³), LL/LR: O(n)
""")

📐 Formal Definition

🎯 The 4-Tuple

A CFG is formally defined as a 4-tuple G = (V, Σ, R, S), where each component plays a specific role in generating strings.

The Components

V: Finite set of nonterminals (variables). Σ: Finite set of terminals (disjoint from V). R: Finite set of production rules. S: Start symbol (S ∈ V). L(G): Language generated by G. Derivation: Sequence of rule applications.

V NonterminalsΣ TerminalsR RulesS Start

# Formal Definition of CFG
from dataclasses import dataclass, field
from typing import Set, Dict, List, Tuple, FrozenSet

@dataclass
class CFG:
    """
    Formal CFG as 4-tuple G = (V, Σ, R, S)
    
    V: nonterminals (variables)
    Σ: terminals
    R: production rules (V → (V ∪ Σ)*)
    S: start symbol
    """
    V: FrozenSet[str]                      # Nonterminals
    Sigma: FrozenSet[str]                  # Terminals
    R: Dict[str, List[Tuple[str, ...]]]    # Rules
    S: str                                 # Start symbol
    
    def __post_init__(self):
        # Validate
        assert self.S in self.V, "Start symbol must be a nonterminal"
        assert self.V & self.Sigma == frozenset(), "V and Σ must be disjoint"
        
        for lhs, productions in self.R.items():
            assert lhs in self.V, f"LHS {lhs} must be nonterminal"
            for rhs in productions:
                for symbol in rhs:
                    assert symbol in self.V or symbol in self.Sigma, \
                        f"Symbol {symbol} not in V ∪ Σ"
    
    def __repr__(self):
        lines = [f"G = (V, Σ, R, S)"]
        lines.append(f"  V = {sorted(self.V)}")
        lines.append(f"  Σ = {sorted(self.Sigma)}")
        lines.append(f"  S = {self.S}")
        lines.append(f"  R:")
        for lhs in sorted(self.R.keys()):
            for rhs in self.R[lhs]:
                rhs_str = ' '.join(rhs) if rhs else 'ε'
                lines.append(f"    {lhs} → {rhs_str}")
        return '\n'.join(lines)


# Example: Arithmetic expressions
expr_cfg = CFG(
    V=frozenset({'E', 'T', 'F'}),
    Sigma=frozenset({'id', '+', '*', '(', ')'}),
    R={
        'E': [('E', '+', 'T'), ('T',)],
        'T': [('T', '*', 'F'), ('F',)],
        'F': [('(', 'E', ')'), ('id',)],
    },
    S='E'
)

print(expr_cfg)

# DERIVATION
def derive_one_step(cfg, sentential_form):
    """Find all one-step derivations from a sentential form."""
    results = []
    for i, symbol in enumerate(sentential_form):
        if symbol in cfg.V:
            for rhs in cfg.R.get(symbol, []):
                new_form = sentential_form[:i] + rhs + sentential_form[i+1:]
                results.append((i, symbol, rhs, new_form))
    return results


def leftmost_derivation(cfg, target, max_steps=20):
    """Find a leftmost derivation of target."""
    start = (cfg.S,)
    
    def helper(form, steps, path):
        if steps > max_steps:
            return None
        
        # Check if form is all terminals
        if all(s in cfg.Sigma for s in form):
            if ''.join(form) == target:
                return path + [form]
            return None
        
        # Find leftmost nonterminal
        for i, symbol in enumerate(form):
            if symbol in cfg.V:
                for rhs in cfg.R[symbol]:
                    new_form = form[:i] + rhs + form[i+1:]
                    result = helper(new_form, steps + 1, path + [new_form])
                    if result:
                        return result
                break  # only expand leftmost
        
        return None
    
    return helper(start, 0, [start])


# Test derivation
print("\n=== Leftmost Derivation ===")
target = 'id+id*id'
path = leftmost_derivation(expr_cfg, target)

if path:
    print(f"Target: {target}")
    print("Derivation:")
    for i, form in enumerate(path):
        form_str = ' '.join(form) if form else 'ε'
        print(f"  Step {i}: {form_str}")
else:
    print(f"Could not derive {target} in 20 steps")

# LANGUAGE OF A CFG
print("""
=== Language of a CFG ===

L(G) = { w ∈ Σ* | S ⇒* w }

The language of a CFG is the set of all strings
of terminals derivable from the start symbol.

=== Examples ===

G1: S → aSb | ε
  L(G1) = { a^n b^n | n ≥ 0 }

G2: S → (S) | SS | ε
  L(G2) = balanced parentheses

G3: E → E+T | T
    T → T*F | F
    F → (E) | id
  L(G3) = arithmetic expressions

=== Key Facts ===

1. Every regular language is context-free.
2. Not every CFL is regular (e.g., a^n b^n).
3. CFLs are closed under union, concat, star.
4. CFLs are NOT closed under intersection.
5. Membership is decidable: O(n³) via CYK.
""")

# MORE EXAMPLES
print("=== More CFG Examples ===")
print("""
1. PALINDROMES over {a, b}:
   S → aSa | bSb | a | b | ε
   L = { w | w = w^R }

2. EQUAL a's and b's:
   S → aSb | bSa | SS | ε
   L = { w | #a(w) = #b(w) }

3. a^i b^j with i ≠ j:
   S → A | B
   A → aAb | aA | a      (more a's)
   B → aBb | Bb | b      (more b's)

4. ARITHMETIC EXPRESSIONS:
   E → E + T | T
   T → T * F | F
   F → ( E ) | id

5. PROGRAMMING LANGUAGE:
   Program → StmtList
   StmtList → Stmt StmtList | ε
   Stmt → id = Expr ; | if ( Expr ) Stmt | { StmtList }
   Expr → ...
""")

# PYTHON PARSER SIMULATION
print("=== Python: CYK-style Membership (simplified) ===")

def cfg_membership(cfg, string, max_len=20):
    """
    Check if string is in L(G) using BFS over derivations.
    (Not efficient, but works for small examples.)
    """
    from collections import deque
    
    # Convert string to tuple of chars for easier handling
    if len(string) > max_len:
        return False
    
    start = (cfg.S,)
    queue = deque([start])
    visited = set()
    
    for _ in range(100000):
        if not queue:
            break
        
        form = queue.popleft()
        
        if form in visited:
            continue
        visited.add(form)
        
        # Check if form is the target string (all terminals)
        if all(s in cfg.Sigma for s in form):
            if ''.join(form) == string:
                return True
            continue
        
        # Check length bound
        terminal_len = sum(1 for s in form if s in cfg.Sigma)
        if terminal_len > len(string):
            continue
        
        # Expand leftmost nonterminal
        for i, symbol in enumerate(form):
            if symbol in cfg.V:
                for rhs in cfg.R[symbol]:
                    new_form = form[:i] + rhs + form[i+1:]
                    if len(new_form) <= len(string) + 5:
                        queue.append(new_form)
                break  # leftmost only
    
    return False


# Test with balanced parentheses
print("Balanced parentheses grammar:")
print("  S → (S) | SS | ()")
for s in ['()', '(())', '()()', '((()))', '(()', ')(', '()()()']:
    result = cfg_membership(paren_grammar, s, max_len=8)
    print(f"  '{s}' → {'✓' if result else '✗'}")

# Test with a^n b^n
print("\na^n b^n grammar:")
print("  S → aSb | ε")
for s in ['', 'ab', 'aabb', 'aaabbb', 'aab', 'abb', 'ba']:
    result = cfg_membership(anbn_grammar, s, max_len=8)
    print(f"  '{s}' → {'✓' if result else '✗'}")

# TEST WITH EXPRESSIONS
print("\nArithmetic expressions:")
for s in ['id', 'id+id', 'id*id', 'id+id*id', '(id+id)*id', 'id+', '+id']:
    result = cfg_membership(expr_cfg, s, max_len=10)
    print(f"  '{s}' → {'✓' if result else '✗'}")

🔄 Derivations

🎯 How Strings Are Generated

A derivation is a sequence of rule applications that transforms the start symbol into a string of terminals. Derivations show how a string is generated by the grammar.

Derivation Types

Leftmost: Always expand leftmost nonterminal. Rightmost: Always expand rightmost nonterminal. Mixed: Any order. Sentential form: Intermediate string. ⇒*: Zero or more steps. Parse tree: Tree representation of derivation.

⬅️ Leftmost➡️ Rightmost📝 Sentential form🌳 Parse tree

# Derivations in detail
print("=" * 60)
print("DERIVATIONS")
print("=" * 60)

print("""
=== Definition ===

A derivation is a sequence:
  α₀ ⇒ α₁ ⇒ α₂ ⇒ ... ⇒ αₙ
  
where each αᵢ₊₁ is obtained from αᵢ by
replacing a nonterminal using a production rule.

Notation:
  α ⇒ β     (one step)
  α ⇒* β    (zero or more steps)
  α ⇒+ β    (one or more steps)

=== Example ===

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

Derivation of "id + id * id":

LEFTMOST:
  E
  ⇒ E + T
  ⇒ T + T
  ⇒ F + T
  ⇒ id + T
  ⇒ id + T * F
  ⇒ id + F * F
  ⇒ id + id * F
  ⇒ id + id * id

RIGHTMOST:
  E
  ⇒ E + T
  ⇒ E + T * F
  ⇒ E + T * id
  ⇒ E + F * id
  ⇒ E + id * id
  ⇒ T + id * id
  ⇒ F + id * id
  ⇒ id + id * id

Both are valid derivations of the same string.
""")

# TYPES OF DERIVATIONS
print("=== Types of Derivations ===")
print("""
1. LEFTMOST DERIVATION
   - Always expand the leftmost nonterminal
   - Notation: ⇒_lm
   - Unique for unambiguous grammars
   - Used by LL parsers

2. RIGHTMOST DERIVATION
   - Always expand the rightmost nonterminal
   - Notation: ⇒_rm
   - Reverse of leftmost
   - Used by LR parsers

3. MIXED DERIVATION
   - Any order of expansion
   - Multiple possible sequences
   - All produce the same parse tree

=== Key Fact ===

For a given parse tree, there is:
  - Exactly ONE leftmost derivation
  - Exactly ONE rightmost derivation

But there may be multiple mixed derivations.
""")

# DERIVATION IN CODE
print("=== Derivation in Code ===")

class CFG:
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules
    
    def is_terminal(self, symbol):
        return symbol not in self.rules and symbol != 'ε'
    
    def leftmost_derivation(self, target, max_steps=30):
        """Find leftmost derivation of target."""
        start = (self.start,)
        
        def expand(form, steps):
            if steps > max_steps:
                return None
            
            # Check if all terminals
            if all(self.is_terminal(s) for s in form):
                if ''.join(form) == target:
                    return [form]
                return None
            
            # Find leftmost nonterminal
            for i, symbol in enumerate(form):
                if symbol in self.rules:
                    for rhs in self.rules[symbol]:
                        rhs_tuple = rhs if rhs else ('ε',)
                        if rhs_tuple == ('ε',):
                            rhs_tuple = ()
                        new_form = form[:i] + rhs_tuple + form[i+1:]
                        result = expand(new_form, steps + 1)
                        if result:
                            return [form] + result
                    break
            
            return None
        
        return expand(start, 0)
    
    def rightmost_derivation(self, target, max_steps=30):
        """Find rightmost derivation of target."""
        start = (self.start,)
        
        def expand(form, steps):
            if steps > max_steps:
                return None
            
            if all(self.is_terminal(s) for s in form):
                if ''.join(form) == target:
                    return [form]
                return None
            
            # Find rightmost nonterminal
            for i in range(len(form) - 1, -1, -1):
                if form[i] in self.rules:
                    for rhs in self.rules[form[i]]:
                        rhs_tuple = rhs if rhs else ('ε',)
                        if rhs_tuple == ('ε',):
                            rhs_tuple = ()
                        new_form = form[:i] + rhs_tuple + form[i+1:]
                        result = expand(new_form, steps + 1)
                        if result:
                            return [form] + result
                    break
            
            return None
        
        return expand(start, 0)


# Example grammar
grammar = CFG('E', {
    'E': [('E', '+', 'T'), ('T',)],
    'T': [('T', '*', 'F'), ('F',)],
    'F': [('(', 'E', ')'), ('id',)],
})

# Leftmost derivation
print("Grammar: E → E+T | T; T → T*F | F; F → (E) | id")
print("\nTarget: id+id*id")

lm = grammar.leftmost_derivation('id+id*id')
if lm:
    print("\nLeftmost derivation:")
    for i, form in enumerate(lm):
        form_str = ' '.join(form) if form else 'ε'
        print(f"  {i}: {form_str}")

rm = grammar.rightmost_derivation('id+id*id')
if rm:
    print("\nRightmost derivation:")
    for i, form in enumerate(rm):
        form_str = ' '.join(form) if form else 'ε'
        print(f"  {i}: {form_str}")

# SENTENTIAL FORMS
print("""
=== Sentential Forms ===

A sentential form is any string derivable from S.
  S ⇒* α  (α is a sentential form)

Types:
  - Left-sentential: from leftmost derivation
  - Right-sentential: from rightmost derivation
  - Sentence: sentential form with only terminals

=== Example ===

For E → E+T | T:
  E           (start, sentential form)
  E + T       (sentential form)
  T + T       (sentential form)
  F + T       (sentential form)
  id + T      (sentential form)
  id + F      (sentential form)
  id + id     (sentence — all terminals)
""")

# DERIVATION TREES
print("""
=== Derivation Trees (Parse Trees) ===

A derivation tree shows the structure:
  - Root: start symbol
  - Internal nodes: nonterminals
  - Leaves: terminals
  - Children of A: RHS of production A → ...

Example for id + id * id:

        E
       /|\
      E + T
      |   /|\
      T  T * F
      |  |   |
      F  F  id
      |  |
     id id

Each internal node corresponds to a rule application.
The yield of the tree is the derived string.
""")

# DERIVATION EXAMPLES
print("=== More Derivation Examples ===")
print("""
Grammar: S → aSb | ε

Derivation of aabb:
  S ⇒ aSb ⇒ aaSbb ⇒ aabb

Grammar: S → (S) | SS | ε

Derivation of (()):
  S ⇒ (S) ⇒ (SS) ⇒ ((S)S) ⇒ (()S) ⇒ (())

Derivation of ()():
  S ⇒ SS ⇒ ()S ⇒ ()(S) ⇒ ()()

Grammar: S → 0S1 | 01

Derivation of 000111:
  S ⇒ 0S1 ⇒ 00S11 ⇒ 000S111 ⇒ 000111
""")

# LEFT VS RIGHT DERIVATION
print("=== Leftmost vs Rightmost ===")
print(f"{'Aspect':<30} {'Leftmost':<25} {'Rightmost':<25}")
print("-" * 80)
print(f"{'Expansion order':<30} {'Leftmost first':<25} {'Rightmost first':<25}")
print(f"{'Notation':<30} {'⇒_lm':<25} {'⇒_rm':<25}")
print(f"{'Used by':<30} {'LL parsers':<25} {'LR parsers':<25}")
print(f"{'Parse tree':<30} {'Preorder':<25} {'Reverse postorder':<25}")
print(f"{'Unique for':<30} {'Unambiguous grammars':<25} {'Unambiguous grammars':<25}")
print(f"{'Equivalent':<30} {'Yes (same tree)':<25} {'Yes (same tree)':<25}")

# IMPORTANT THEOREM
print("""
=== Important Theorem ===

For any grammar G and string w ∈ L(G):

  w has a leftmost derivation
    ⟺
  w has a rightmost derivation
    ⟺
  w has a parse tree

All three are equivalent representations
of the same underlying structure.

This is why parsing works:
  - We can parse left-to-right (LL)
  - Or right-to-left (LR)
  - Or build a tree
  - All give the same result (for unambiguous grammars)
""")

🌳 Parse Trees

🎯 Tree Representation of Derivations

A parse tree (or derivation tree) is a tree that represents the syntactic structure of a string according to a grammar. The root is the start symbol, internal nodes are nonterminals, and leaves are terminals.

Parse Tree Properties

Root: Start symbol S. Internal: Nonterminals. Leaves: Terminals (or ε). Yield: Concatenation of leaves. Children: RHS of production. Structure: Captures nesting and precedence.

🌱 Root = S🌿 Internal = V🍃 Leaves = Σ📖 Yield = string

# Parse Trees in detail
print("=" * 60)
print("PARSE TREES")
print("=" * 60)

print("""
=== Definition ===

A parse tree for a CFG G = (V, Σ, R, S) is a tree where:
  1. Root is labeled S (start symbol)
  2. Internal nodes are labeled with nonterminals
  3. Leaves are labeled with terminals or ε
  4. If node A has children X₁, X₂, ..., Xₖ,
     then A → X₁X₂...Xₖ is a production in R

=== Yield ===

The yield of a parse tree is the string obtained
by reading the leaves left to right.

w ∈ L(G) ⟺ there exists a parse tree for w

=== Example ===

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

Parse tree for "id + id * id":

            E
           /|\
          / | \
         E  +  T
         |    /|\
         T   T * F
         |   |   |
         F   F  id
         |   |
        id  id

Yield: id + id * id ✓
""")

# PARSE TREE IN CODE
print("=== Parse Tree Implementation ===")

class ParseTreeNode:
    def __init__(self, symbol, children=None):
        self.symbol = symbol
        self.children = children or []
    
    def is_leaf(self):
        return len(self.children) == 0
    
    def yield_string(self):
        """Get the yield of the tree."""
        if self.is_leaf():
            return self.symbol if self.symbol != 'ε' else ''
        return ''.join(child.yield_string() for child in self.children)
    
    def __repr__(self, level=0):
        indent = "  " * level
        result = f"{indent}{self.symbol}\n"
        for child in self.children:
            result += child.__repr__(level + 1)
        return result
    
    def to_ascii(self):
        """Pretty ASCII tree."""
        lines = []
        
        def build(node, prefix="", is_last=True):
            connector = "└── " if is_last else "├── "
            lines.append(prefix + connector + node.symbol)
            
            new_prefix = prefix + ("    " if is_last else "│   ")
            for i, child in enumerate(node.children):
                build(child, new_prefix, i == len(node.children) - 1)
        
        lines.append(self.symbol)
        for i, child in enumerate(self.children):
            build(child, "", i == len(self.children) - 1)
        
        return '\n'.join(lines)


# Build parse tree for id + id * id
# E → E + T
# E → T → F → id
# T → T * F
# T → F → id
# F → id

tree = ParseTreeNode('E', [
    ParseTreeNode('E', [
        ParseTreeNode('T', [
            ParseTreeNode('F', [ParseTreeNode('id')])
        ])
    ]),
    ParseTreeNode('+'),
    ParseTreeNode('T', [
        ParseTreeNode('T', [
            ParseTreeNode('F', [ParseTreeNode('id')])
        ]),
        ParseTreeNode('*'),
        ParseTreeNode('F', [ParseTreeNode('id')])
    ])
])

print("Parse tree for 'id + id * id':")
print(tree.to_ascii())
print(f"\nYield: {tree.yield_string()}")

# PARSE TREE FOR BALANCED PARENS
print("\n=== Parse Tree for Balanced Parentheses ===")

# S → (S) | SS | ε
# Parse tree for "(())"

paren_tree = ParseTreeNode('S', [
    ParseTreeNode('('),
    ParseTreeNode('S', [
        ParseTreeNode('('),
        ParseTreeNode('S', []),  # ε
        ParseTreeNode(')')
    ]),
    ParseTreeNode(')')
])

print("Parse tree for '(())':")
print(paren_tree.to_ascii())
print(f"\nYield: {paren_tree.yield_string()}")

# AMBIGUITY AND PARSE TREES
print("""
=== Parse Trees and Ambiguity ===

A grammar is AMBIGUOUS if some string has
TWO OR MORE different parse trees.

Example:
  Grammar: E → E + E | E * E | id
  String: id + id * id
  
  Tree 1: (+ is root)
        E
       /|\
      E + E
      |   |
     id  E*E
         | |
        id id
  Value: id + (id * id) = id + id*id

  Tree 2: (* is root)
        E
       /|\
      E * E
     /|\  |
    E + E id
    |   |
   id  id
  Value: (id + id) * id = id + id*id

Both trees yield the same string!
This grammar is ambiguous.

=== Why Ambiguity Matters ===

1. COMPILERS
   - Need unambiguous grammar
   - Otherwise, meaning is unclear
   - Precedence and associativity

2. PARSING
   - Multiple parse trees = multiple meanings
   - Harder to parse efficiently

3. SOLUTION
   - Rewrite grammar to be unambiguous
   - Use precedence rules
   - Use associativity rules
""")

# PARSE TREE PROPERTIES
print("=== Parse Tree Properties ===")
print("""
1. YIELD
   The string derived from the tree.
   Root-to-leaf concatenation.

2. HEIGHT
   Longest path from root to leaf.
   Related to derivation length.

3. DEPTH
   Level of a node.
   Root is depth 0.

4. ARITY
   Number of children.
   For CFG: any number ≥ 0.

5. FRONTIER
   The leaves (terminals).
   Same as yield.

=== Relationship to Derivations ===

Parse tree ⟺ Leftmost derivation
Parse tree ⟺ Rightmost derivation

For unambiguous grammar:
  Each string has exactly ONE parse tree
  (and hence one leftmost and one rightmost derivation)
""")

# PARSE TREE VISUALIZATION
print("=== Parse Tree Visualization ===")
print("""
For grammar S → aSb | ε:

Parse tree for "aaabbb":

        S
       /|\
      a S b
       /|\
      a S b
       /|\
      a S b
        |
        ε

Yield: a a a b b b = aaabbb ✓

For grammar E → E+T | T:
              T → T*F | F
              F → (E) | id

Parse tree for "(id + id) * id":

            E
            |
            T
           /|\
          T * F
          |   |
          F  id
         /|\
        ( E )
          |
         E+T
        /|\
       T + T
       |   |
       F   F
       |   |
      id  id

Yield: ( id + id ) * id ✓
""")

# COUNTING PARSE TREES
print("=== Counting Parse Trees ===")

def count_derivations(grammar, target, max_steps=15):
    """Count the number of distinct parse trees (derivations)."""
    from functools import lru_cache
    
    memo = {}
    
    def count(symbol, s, i, j):
        """Count ways to derive s[i:j] from symbol."""
        key = (symbol, i, j)
        if key in memo:
            return memo[key]
        
        if i == j:
            # Empty string: check if symbol → ε
            result = 1 if symbol in grammar.rules and () in [tuple(r) for r in grammar.rules[symbol]] else 0
            memo[key] = result
            return result
        
        total = 0
        for rhs in grammar.rules.get(symbol, []):
            if len(rhs) == 1 and rhs[0] in grammar.rules:
                # A → B
                total += count(rhs[0], s, i, j)
            elif len(rhs) == 2:
                # A → BC
                for k in range(i + 1, j):
                    total += count(rhs[0], s, i, k) * count(rhs[1], s, k, j)
            elif len(rhs) == 1 and rhs[0] not in grammar.rules:
                # A → terminal
                if j == i + 1 and rhs[0] == s[i]:
                    total += 1
            elif len(rhs) == 0:
                # A → ε
                if i == j:
                    total += 1
        
        memo[key] = total
        return total
    
    return count(grammar.start, target, 0, len(target))


# Example: ambiguous expression grammar
ambig_expr = CFG('E', {
    'E': [('E', '+', 'E'), ('E', '*', 'E'), ('id',)],
})

print("Ambiguous grammar: E → E + E | E * E | id")
print("\nNumber of parse trees:")
for s in ['id', 'id+id', 'id+id*id', 'id*id+id']:
    n = count_derivations(ambig_expr, s)
    print(f"  '{s}' → {n} parse tree(s)")

print("""
For 'id+id*id', there are 2 parse trees:
  - (id + id) * id
  - id + (id * id)

This grammar is ambiguous!
""")

# UNAMBIGUOUS VERSION
print("=== Unambiguous Version ===")

unambig_expr = CFG('E', {
    'E': [('E', '+', 'T'), ('T',)],
    'T': [('T', '*', 'F'), ('F',)],
    'F': [('id',)],
})

print("Unambiguous grammar:")
print("  E → E + T | T")
print("  T → T * F | F")
print("  F → id")
print("\nNumber of parse trees:")
for s in ['id', 'id+id', 'id+id*id', 'id*id+id']:
    n = count_derivations(unambig_expr, s)
    print(f"  '{s}' → {n} parse tree(s)")

print("""
Now each string has exactly ONE parse tree.
The grammar enforces:
  - * has higher precedence than +
  - + is left-associative
  - * is left-associative
""")

⚠️ Ambiguity

🎯 When Grammars Have Multiple Meanings

A grammar is ambiguous if some string in its language has two or more different parse trees. Ambiguity is a property of the grammar, not the language — some languages have both ambiguous and unambiguous grammars.

Ambiguity Types

Grammar ambiguity: A grammar with multiple parse trees. Language ambiguity: All grammars for L are ambiguous (inherently ambiguous). Parse tree: Different structures. Derivation: Multiple leftmost derivations. Precedence: Usually causes ambiguity. Associativity: Also a common cause.

⚠️ Multiple trees🔀 Precedence↔️ Associativity❓ Inherent

# Ambiguity in detail
print("=" * 60)
print("AMBIGUITY")
print("=" * 60)

print("""
=== Definition ===

A CFG G is AMBIGUOUS if there exists a string
w ∈ L(G) with two or more distinct parse trees.

Equivalently:
  w has two or more distinct leftmost derivations.

=== Example ===

Grammar: E → E + E | E * E | id

String: id + id * id

Parse Tree 1:              Parse Tree 2:
      E                          E
     /|\                        /|\
    E + E                      E * E
    |   |                     /|\   |
   id  E * E                 E + E id
       |   |                 |   |
      id  id                id  id

Tree 1: id + (id * id)     Tree 2: (id + id) * id

Both trees yield "id + id * id"
But they mean different things!

This grammar is AMBIGUOUS.
""")

# AMBIGUITY IN CODE
print("=== Detecting Ambiguity ===")

class CFG:
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules
    
    def count_parse_trees(self, target, max_steps=15):
        """Count distinct parse trees for target."""
        from functools import lru_cache
        
        memo = {}
        
        def count(symbol, i, j, depth=0):
            if depth > max_steps:
                return 0
            
            key = (symbol, i, j, depth)
            if key in memo:
                return memo[key]
            
            if i == j:
                # ε production
                if symbol in self.rules:
                    for rhs in self.rules[symbol]:
                        if rhs == () or rhs == ('ε',):
                            memo[key] = 1
                            return 1
                memo[key] = 0
                return 0
            
            total = 0
            for rhs in self.rules.get(symbol, []):
                if rhs == () or rhs == ('ε',):
                    continue
                if len(rhs) == 1:
                    if rhs[0] in self.rules:
                        total += count(rhs[0], i, j, depth + 1)
                    else:
                        if j == i + 1 and rhs[0] == target[i]:
                            total += 1
                elif len(rhs) == 2:
                    for k in range(i + 1, j):
                        total += count(rhs[0], i, k, depth + 1) * count(rhs[1], k, j, depth + 1)
            
            memo[key] = total
            return total
        
        return count(self.start, 0, len(target))


# Ambiguous grammar
ambig = CFG('E', {
    'E': [('E', '+', 'E'), ('E', '*', 'E'), ('id',)],
})

print("Ambiguous grammar: E → E + E | E * E | id")
print("\nCounting parse trees:")
test_strings = ['id', 'id+id', 'id+id*id', 'id*id+id', 'id+id+id']

for s in test_strings:
    n = ambig.count_parse_trees(s)
    status = "AMBIGUOUS" if n > 1 else "unambiguous"
    print(f"  '{s}' → {n} tree(s) — {status}")

# UNAMBIGUOUS VERSION
print("\n=== Unambiguous Version ===")

unambig = CFG('E', {
    'E': [('E', '+', 'T'), ('T',)],
    'T': [('T', '*', 'F'), ('F',)],
    'F': [('id',)],
})

print("Unambiguous grammar:")
print("  E → E + T | T")
print("  T → T * F | F")
print("  F → id")
print("\nCounting parse trees:")
for s in test_strings:
    n = unambig.count_parse_trees(s)
    print(f"  '{s}' → {n} tree(s)")

# WHY AMBIGUITY MATTERS
print("""
=== Why Ambiguity Matters ===

1. COMPILERS
   - Ambiguous grammar → ambiguous meaning
   - Need unambiguous grammar for parsing
   - Precedence and associativity

2. NATURAL LANGUAGE
   - Ambiguity is common
   - "I saw the man with the telescope"
   - Multiple interpretations

3. PARSING ALGORITHMS
   - LL/LR parsers need unambiguous grammars
   - CYK/Earley handle ambiguity (list all trees)
   - Ambiguity increases complexity

4. LANGUAGE DESIGN
   - Programming languages avoid ambiguity
   - Use precedence rules
   - Use associativity rules
""")

# CAUSES OF AMBIGUITY
print("=== Common Causes of Ambiguity ===")
print("""
1. OPERATOR PRECEDENCE
   E → E + E | E * E | id
   Is id + id * id = (id+id)*id or id+(id*id)?

2. ASSOCIATIVITY
   E → E - E | id
   Is id - id - id = (id-id)-id or id-(id-id)?

3. DANGLING ELSE
   S → if E then S | if E then S else S | ...
   Is else matched with inner or outer if?

4. DERIVATION ORDER
   Multiple leftmost derivations
   (same as multiple parse trees)

=== Solutions ===

1. PRECEDENCE
   E → E + T | T
   T → T * F | F
   F → id

2. ASSOCIATIVITY
   E → E + T | T    (left-associative)
   E → T + E | T    (right-associative)

3. REWRITE GRAMMAR
   Eliminate ambiguity by restructuring rules.
""")

# DANGLING ELSE EXAMPLE
print("=== Dangling Else Example ===")
print("""
Ambiguous grammar:
  S → if E then S
    | if E then S else S
    | other

String: if E1 then if E2 then S1 else S2

Parse 1: else matches INNER if
  if E1 then (if E2 then S1 else S2)

Parse 2: else matches OUTER if
  if E1 then (if E2 then S1) else S2

Solution (unambiguous grammar):
  S → M | U
  M → if E then M else M | other
  U → if E then S
    | if E then M else U

This forces else to match the nearest if.
""")

# INHERENT AMBIGUITY
print("=== Inherent Ambiguity ===")
print("""
Some languages are INHERENTLY AMBIGUOUS:
Every grammar for the language is ambiguous.

Example:
  L = { a^i b^j c^k | i = j or j = k }

This language is inherently ambiguous.
No matter how you write the grammar,
some string will have multiple parse trees.

Proof: Requires advanced techniques
(see Ogden's lemma for CFLs).

=== Key Facts ===

1. Ambiguity is undecidable for CFGs.
   (No algorithm can decide if a CFG is ambiguous.)

2. Some languages are inherently ambiguous.

3. For practical purposes:
   - Most programming languages have unambiguous grammars
   - We design them carefully
   - We use precedence and associativity
""")

# AMBIGUITY IN PRACTICE
print("=== Ambiguity in Practice ===")
print("""
1. EXPRESSION GRAMMARS
   Most common source of ambiguity.
   Solved by layered grammar (E, T, F).

2. IF-THEN-ELSE
   Dangling else problem.
   Solved by grammar restructuring.

3. NATURAL LANGUAGE
   "Time flies like an arrow"
   - Time (verb) flies (noun)...
   - Time (noun) flies (verb)...
   Multiple meanings.

4. PROGRAMMING LANGUAGES
   C, Java, Python: carefully designed
   to be unambiguous (mostly).
   
5. PARSER GENERATORS
   Yacc/Bison: detect ambiguity
   ANTLR: resolves with precedence rules
   Happy: reports conflicts
""")

# SUMMARY TABLE
print("=== Summary ===")
print(f"{'Aspect':<30} {'Ambiguous':<25} {'Unambiguous':<25}")
print("-" * 80)
print(f"{'Parse trees':<30} {'Multiple':<25} {'Unique':<25}")
print(f"{'Leftmost derivation':<30} {'Multiple':<25} {'Unique':<25}")
print(f"{'Meaning':<30} {'Unclear':<25} {'Clear':<25}")
print(f"{'Parsing':<30} {'Complex':<25} {'Efficient':<25}")
print(f"{'Compilers':<30} {'Bad':<25} {'Good':<25}")
print(f"{'Example':<30} {'E → E+E | E*E':<25} {'E → E+T | T':<25}")

🧹 Grammar Simplification

🎯 Cleaning Up Grammars

Grammar simplification removes unnecessary symbols and rules without changing the language. This makes grammars easier to work with and is a prerequisite for Chomsky Normal Form.

Simplification Steps

1. Remove ε-productions: Eliminate A → ε. 2. Remove unit productions: Eliminate A → B. 3. Remove useless symbols: Unreachable and non-generating. 4. Remove duplicates: Redundant rules. 5. Result: Simplified grammar. Preserves: L(G) unchanged (except maybe ε).

🗑️ ε-productions🔗 Unit rules🚫 Useless✅ Same language

# Grammar Simplification
print("=" * 60)
print("GRAMMAR SIMPLIFICATION")
print("=" * 60)

print("""
=== Why Simplify? ===

1. EASIER TO ANALYZE
   Fewer rules and symbols.

2. REQUIRED FOR CNF
   Chomsky Normal Form needs no ε or unit rules.

3. PARSING EFFICIENCY
   Simpler grammars parse faster.

4. PROOF SIMPLICITY
   Fewer cases to consider.

=== Order Matters ===

1. Remove ε-productions
2. Remove unit productions
3. Remove useless symbols
   (both unreachable and non-generating)

Doing these in the right order preserves the language.
""")

# 1. REMOVE ε-PRODUCTIONS
print("=== 1. Remove ε-Productions ===")
print("""
A rule A → ε is an ε-production.

PROCEDURE:
  1. Find all nullable nonterminals (can derive ε).
  2. For each rule with nullable symbols, add new rules
     with those symbols omitted.
  3. Remove all A → ε (except possibly S → ε).

EXAMPLE:
  S → AB
  A → aA | ε
  B → bB | ε

  Nullable: A, B, S

  New rules:
  S → AB | A | B | ε
  A → aA | a
  B → bB | b

  Remove ε (except S → ε if needed):
  S → AB | A | B
  A → aA | a
  B → bB | b
""")

def find_nullable(cfg):
    """Find all nullable nonterminals."""
    nullable = set()
    
    # Iteratively find nullable
    changed = True
    while changed:
        changed = False
        for lhs, productions in cfg.rules.items():
            if lhs in nullable:
                continue
            for rhs in productions:
                if rhs == () or rhs == ('ε',):
                    nullable.add(lhs)
                    changed = True
                    break
                if all(s in nullable for s in rhs):
                    nullable.add(lhs)
                    changed = True
                    break
    
    return nullable


def remove_epsilon(cfg):
    """Remove ε-productions."""
    nullable = find_nullable(cfg)
    
    new_rules = {}
    for lhs, productions in cfg.rules.items():
        new_prods = set()
        for rhs in productions:
            if rhs == () or rhs == ('ε',):
                continue  # skip ε
            
            # Generate all combinations of omitting nullable symbols
            from itertools import combinations
            
            # Find positions of nullable symbols
            nullable_positions = [i for i, s in enumerate(rhs) if s in nullable]
            
            # Generate all subsets
            for r in range(len(nullable_positions) + 1):
                for omit in combinations(nullable_positions, r):
                    new_rhs = tuple(s for i, s in enumerate(rhs) if i not in omit)
                    if new_rhs:  # don't add empty
                        new_prods.add(new_rhs)
            
            # Also add original if no nullable
            if not nullable_positions:
                new_prods.add(rhs)
        
        if new_prods:
            new_rules[lhs] = list(new_prods)
    
    # Handle start symbol
    if cfg.start in nullable:
        # Add S → ε only if ε ∈ L
        if cfg.start not in new_rules:
            new_rules[cfg.start] = []
        new_rules[cfg.start].append(())
    
    return CFG(cfg.start, new_rules)


# Example
cfg1 = CFG('S', {
    'S': [('A', 'B')],
    'A': [('a', 'A'), ()],
    'B': [('b', 'B'), ()],
})

print("Original grammar:")
print("  S → AB")
print("  A → aA | ε")
print("  B → bB | ε")

print(f"\nNullable: {find_nullable(cfg1)}")

cfg1_noeps = remove_epsilon(cfg1)
print("\nAfter removing ε-productions:")
for lhs, prods in sorted(cfg1_noeps.rules.items()):
    for rhs in prods:
        rhs_str = ' '.join(rhs) if rhs else 'ε'
        print(f"  {lhs} → {rhs_str}")

# 2. REMOVE UNIT PRODUCTIONS
print("\n=== 2. Remove Unit Productions ===")
print("""
A unit production is A → B (single nonterminal).

PROCEDURE:
  1. For each A, find all B such that A ⇒* B (using only unit rules).
  2. For each such B and each B → α (non-unit),
     add A → α.
  3. Remove all unit productions.

EXAMPLE:
  S → A | B
  A → a
  B → b

  Unit pairs: (S,A), (S,B)
  
  Add:
  S → a (from A → a)
  S → b (from B → b)
  
  Remove unit rules:
  S → a | b
  A → a
  B → b
""")

def find_unit_pairs(cfg):
    """Find all pairs (A, B) where A ⇒* B via unit rules."""
    units = {A: set() for A in cfg.rules}
    
    # Direct unit rules
    for lhs, productions in cfg.rules.items():
        for rhs in productions:
            if len(rhs) == 1 and rhs[0] in cfg.rules:
                units[lhs].add(rhs[0])
    
    # Transitive closure
    changed = True
    while changed:
        changed = False
        for A in cfg.rules:
            for B in list(units[A]):
                for C in units.get(B, set()):
                    if C not in units[A]:
                        units[A].add(C)
                        changed = True
    
    return units


def remove_unit_productions(cfg):
    """Remove unit productions."""
    unit_pairs = find_unit_pairs(cfg)
    
    new_rules = {}
    for lhs in cfg.rules:
        new_prods = set()
        
        # Add non-unit productions
        for rhs in cfg.rules[lhs]:
            if len(rhs) == 1 and rhs[0] in cfg.rules:
                continue  # skip unit
            new_prods.add(rhs)
        
        # Add productions from unit-reachable nonterminals
        for B in unit_pairs[lhs]:
            for rhs in cfg.rules.get(B, []):
                if len(rhs) == 1 and rhs[0] in cfg.rules:
                    continue
                new_prods.add(rhs)
        
        if new_prods:
            new_rules[lhs] = list(new_prods)
    
    return CFG(cfg.start, new_rules)


# Example
cfg2 = CFG('S', {
    'S': [('A',), ('B',)],
    'A': [('a',)],
    'B': [('b',)],
})

print("Original grammar:")
print("  S → A | B")
print("  A → a")
print("  B → b")

unit_pairs = find_unit_pairs(cfg2)
print(f"\nUnit pairs: {unit_pairs}")

cfg2_nounit = remove_unit_productions(cfg2)
print("\nAfter removing unit productions:")
for lhs, prods in sorted(cfg2_nounit.rules.items()):
    for rhs in prods:
        rhs_str = ' '.join(rhs) if rhs else 'ε'
        print(f"  {lhs} → {rhs_str}")

# 3. REMOVE USELESS SYMBOLS
print("\n=== 3. Remove Useless Symbols ===")
print("""
A symbol is USELESS if it's:
  - Not generating (can't derive a terminal string), OR
  - Not reachable (can't be reached from S)

PROCEDURE:
  1. Find generating symbols (can derive terminals).
  2. Remove non-generating symbols and their rules.
  3. Find reachable symbols (from S).
  4. Remove unreachable symbols and their rules.

EXAMPLE:
  S → A B | a
  A → a
  B → b
  C → c  (unreachable)
  D → D  (non-generating)

  Generating: S, A, B, C (D is not)
  Reachable: S, A, B (C is not)
  
  Remove D (non-generating), C (unreachable):
  S → A B | a
  A → a
  B → b
""")

def find_generating(cfg):
    """Find all generating nonterminals."""
    generating = set()
    
    changed = True
    while changed:
        changed = False
        for lhs, productions in cfg.rules.items():
            if lhs in generating:
                continue
            for rhs in productions:
                if all(s not in cfg.rules or s in generating for s in rhs):
                    generating.add(lhs)
                    changed = True
                    break
    
    return generating


def find_reachable(cfg, generating):
    """Find all reachable symbols from S."""
    reachable = {cfg.start}
    queue = [cfg.start]
    
    while queue:
        symbol = queue.pop(0)
        for rhs in cfg.rules.get(symbol, []):
            for s in rhs:
                if s not in reachable:
                    reachable.add(s)
                    if s in cfg.rules:
                        queue.append(s)
    
    return reachable


def remove_useless(cfg):
    """Remove useless symbols."""
    generating = find_generating(cfg)
    
    # Keep only generating rules
    rules_gen = {}
    for lhs, productions in cfg.rules.items():
        if lhs not in generating:
            continue
        new_prods = []
        for rhs in productions:
            if all(s not in cfg.rules or s in generating for s in rhs):
                new_prods.append(rhs)
        if new_prods:
            rules_gen[lhs] = new_prods
    
    cfg_gen = CFG(cfg.start, rules_gen)
    
    # Find reachable
    reachable = find_reachable(cfg_gen, generating)
    
    # Keep only reachable rules
    rules_final = {}
    for lhs, productions in cfg_gen.rules.items():
        if lhs not in reachable:
            continue
        new_prods = []
        for rhs in productions:
            if all(s not in cfg_gen.rules or s in reachable for s in rhs):
                new_prods.append(rhs)
        if new_prods:
            rules_final[lhs] = new_prods
    
    return CFG(cfg.start, rules_final)


# Example
cfg3 = CFG('S', {
    'S': [('A', 'B'), ('a',)],
    'A': [('a',)],
    'B': [('b',)],
    'C': [('c',)],
    'D': [('D',)],
})

print("Original grammar:")
for lhs, prods in sorted(cfg3.rules.items()):
    for rhs in prods:
        rhs_str = ' '.join(rhs) if rhs else 'ε'
        print(f"  {lhs} → {rhs_str}")

print(f"\nGenerating: {find_generating(cfg3)}")

cfg3_clean = remove_useless(cfg3)
print("\nAfter removing useless symbols:")
for lhs, prods in sorted(cfg3_clean.rules.items()):
    for rhs in prods:
        rhs_str = ' '.join(rhs) if rhs else 'ε'
        print(f"  {lhs} → {rhs_str}")

# FULL SIMPLIFICATION PIPELINE
print("\n=== Full Simplification Pipeline ===")

def simplify_cfg(cfg):
    """Apply all simplification steps."""
    cfg = remove_epsilon(cfg)
    cfg = remove_unit_productions(cfg)
    cfg = remove_useless(cfg)
    return cfg


# Test on a complex grammar
complex_cfg = CFG('S', {
    'S': [('A', 'B'), ('C',)],
    'A': [('a', 'A'), ()],
    'B': [('b', 'B'), ()],
    'C': [('c',)],
    'D': [('d',)],  # unreachable
    'E': [('E',)],  # non-generating
})

print("Complex grammar:")
for lhs, prods in sorted(complex_cfg.rules.items()):
    for rhs in prods:
        rhs_str = ' '.join(rhs) if rhs else 'ε'
        print(f"  {lhs} → {rhs_str}")

simplified = simplify_cfg(complex_cfg)
print("\nAfter full simplification:")
for lhs, prods in sorted(simplified.rules.items()):
    for rhs in prods:
        rhs_str = ' '.join(rhs) if rhs else 'ε'
        print(f"  {lhs} → {rhs_str}")

# IMPORTANT NOTES
print("""
=== Important Notes ===

1. ORDER MATTERS
   - Remove ε first, then unit, then useless.
   - Wrong order can leave useless symbols.

2. LANGUAGE PRESERVATION
   - L(G) is preserved (except maybe ε).
   - If ε ∈ L, keep S → ε.

3. TERMINATION
   - All procedures terminate.
   - Grammar size may grow temporarily.

4. USES
   - Preparation for CNF/GNF.
   - Parsing optimization.
   - Proof simplification.

5. LIMITATIONS
   - Some grammars can't be made unambiguous.
   - Simplification doesn't remove ambiguity.
""")

📘 Chomsky Normal Form

🎯 A Standard Form for CFGs

Chomsky Normal Form (CNF) is a restricted form of CFG where every production is either A → BC (two nonterminals) or A → a (one terminal). CNF is used by the CYK parsing algorithm.

CNF Rules

Form 1: A → BC (B, C nonterminals). Form 2: A → a (a terminal). Optional: S → ε (if ε ∈ L). No: Mixed rules, long rules, ε, units. Every CFG: Has an equivalent CNF. CYK: Requires CNF.

A → BCA → aNo ε (except S)No units

# Chomsky Normal Form
print("=" * 60)
print("CHOMSKY NORMAL FORM (CNF)")
print("=" * 60)

print("""
=== Definition ===

A CFG is in Chomsky Normal Form if every rule is:

  1. A → BC    (two nonterminals)
  2. A → a     (one terminal)

Plus optionally:
  3. S → ε     (only if ε ∈ L)

=== No Other Forms Allowed ===

✗ A → ε      (except S)
✗ A → B      (unit)
✗ A → Bc     (mixed)
✗ A → BCD    (longer than 2)
✗ A → aB     (mixed)

=== Conversion Steps ===

1. Simplify grammar (remove ε, unit, useless)
2. Handle terminals in long rules
3. Break long rules into binary rules
4. Result: CNF

=== Why CNF? ===

- CYK algorithm requires CNF
- Parsing complexity analysis
- Proof simplicity
- Every CFG has equivalent CNF
""")

# CNF CONVERSION IN CODE
print("=== CNF Conversion Algorithm ===")

class CFG:
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules
    
    def __repr__(self):
        lines = []
        for lhs in sorted(self.rules.keys()):
            for rhs in self.rules[lhs]:
                rhs_str = ' '.join(rhs) if rhs else 'ε'
                lines.append(f"  {lhs} → {rhs_str}")
        return '\n'.join(lines)


def to_cnf(cfg):
    """Convert CFG to Chomsky Normal Form."""
    # Step 0: Simplify (assume already simplified for this demo)
    
    new_rules = {}
    counter = [0]
    
    def new_nonterminal():
        counter[0] += 1
        return f"X{counter[0]}"
    
    # Step 1: Handle terminals in RHS of length > 1
    # Replace each terminal a with a new nonterminal Ta → a
    terminal_map = {}
    for lhs, productions in cfg.rules.items():
        for rhs in productions:
            if len(rhs) >= 2:
                for symbol in rhs:
                    if symbol not in cfg.rules:  # terminal
                        if symbol not in terminal_map:
                            ta = new_nonterminal()
                            terminal_map[symbol] = ta
                            if ta not in new_rules:
                                new_rules[ta] = [(symbol,)]
    
    # Step 2: Rewrite rules with terminals replaced
    intermediate_rules = {}
    for lhs, productions in cfg.rules.items():
        new_prods = []
        for rhs in productions:
            if len(rhs) >= 2:
                new_rhs = tuple(
                    terminal_map.get(s, s) if s not in cfg.rules else s
                    for s in rhs
                )
                new_prods.append(new_rhs)
            else:
                new_prods.append(rhs)
        intermediate_rules[lhs] = new_prods
    
    # Step 3: Break long rules (length > 2) into binary rules
    final_rules = dict(new_rules)
    
    for lhs, productions in intermediate_rules.items():
        new_prods = []
        for rhs in productions:
            if len(rhs) <= 2:
                new_prods.append(rhs)
            else:
                # Break A → B1 B2 ... Bk into
                # A → B1 X1
                # X1 → B2 X2
                # ...
                # Xk-2 → Bk-1 Bk
                current_lhs = lhs
                for i in range(len(rhs) - 2):
                    xi = new_nonterminal()
                    if i == 0:
                        new_prods.append((rhs[0], xi))
                    else:
                        final_rules[current_lhs] = [(rhs[i], xi)]
                    current_lhs = xi
                # Last pair
                final_rules[current_lhs] = [(rhs[-2], rhs[-1])]
        
        if new_prods:
            final_rules[lhs] = new_prods
    
    return CFG(cfg.start, final_rules)


# Example: Convert to CNF
print("Original grammar:")
print("  S → a B c")
print("  B → b")

original = CFG('S', {
    'S': [('a', 'B', 'c')],
    'B': [('b',)],
})

print(original)

cnf = to_cnf(original)
print("\nAfter CNF conversion:")
print(cnf)

# MORE COMPLEX EXAMPLE
print("\n=== More Complex Example ===")

complex = CFG('S', {
    'S': [('A', 'B', 'C', 'D')],
    'A': [('a',)],
    'B': [('b',)],
    'C': [('c',)],
    'D': [('d',)],
})

print("Original grammar:")
print(complex)

cnf_complex = to_cnf(complex)
print("\nAfter CNF conversion:")
print(cnf_complex)

# CNF PROPERTIES
print("""
=== Properties of CNF ===

1. DERIVATION LENGTH
   For string of length n:
   - Exactly 2n-1 steps in any derivation
   - n-1 steps using A → BC
   - n steps using A → a

2. PARSE TREE
   - Binary tree (each internal node has 2 children)
   - Height ≤ n (for string of length n)
   - Exactly 2n-1 internal nodes

3. CYK ALGORITHM
   - Requires CNF
   - O(n³) time
   - O(n²) space

4. EVERY CFG
   - Has an equivalent CNF
   - Conversion may increase size
   - Preserves language

=== Example Derivation in CNF ===

Grammar:
  S → AB
  A → a
  B → b

Derivation of "ab":
  S ⇒ AB ⇒ aB ⇒ ab
  (3 steps for n=2: 2n-1 = 3 ✓)
""")

# GREIBACH NORMAL FORM
print("=== Greibach Normal Form (GNF) ===")
print("""
Another normal form:

  A → a α    where a is terminal, α is (V)*

Every rule starts with exactly one terminal.

Properties:
  - Every CFG has equivalent GNF
  - Derivation length = n (for string of length n)
  - Useful for top-down parsing
  - No left recursion

Comparison:
  CNF: A → BC | a
  GNF: A → a α

Both are normal forms for CFGs.
CNF is used for CYK (bottom-up).
GNF is used for top-down parsing.
""")

# CONVERSION COMPLEXITY
print("=== Conversion Complexity ===")
print(f"{'Step':<35} {'Complexity':<20}")
print("-" * 55)
print(f"{'Simplify (ε, unit, useless)':<35} {'O(|G|²)':<20}")
print(f"{'Handle terminals':<35} {'O(|G|)':<20}")
print(f"{'Break long rules':<35} {'O(|G|)':<20}")
print(f"{'Total':<35} {'O(|G|²)':<20}")
print()
print("Grammar size may increase:")
print("  - Each long rule → multiple binary rules")
print("  - Each terminal in long rule → new nonterminal")
print("  - Worst case: |G'| = O(|G|²)")

# CNF LIMITATIONS
print("=== CNF Limitations ===")
print("""
1. GRAMMAR SIZE
   CNF conversion can significantly increase
   the number of rules and nonterminals.

2. READABILITY
   CNF grammars are hard for humans to read.
   Use only for parsing algorithms.

3. AMBIGUITY
   CNF doesn't remove ambiguity.
   An ambiguous grammar becomes ambiguous CNF.

4. ε-PRODUCTIONS
   Only S → ε allowed.
   Other ε-productions must be eliminated.

5. PRACTICAL USE
   - CYK algorithm
   - Theoretical proofs
   - Not for hand-written parsers
""")

# SUMMARY
print("=== Summary ===")
print("""
CNF:
  A → BC  (binary nonterminal)
  A → a   (terminal)

Conversion:
  1. Simplify
  2. Handle terminals
  3. Break long rules

Properties:
  - Every CFG has equivalent CNF
  - 2n-1 steps for length n
  - Binary parse tree
  - Used by CYK

Key insight:
  Any CFG can be transformed into CNF
  without changing the language.
  This enables uniform parsing algorithms.
""")

🔍 CYK Algorithm

🎯 Parsing with Dynamic Programming

The CYK algorithm (Cocke-Younger-Kasami) determines if a string can be generated by a CFG in Chomsky Normal Form. It uses dynamic programming in O(n³) time.

CYK Table

Table: T[i][j] = nonterminals deriving s[i..j]. Base: T[i][i] = {A | A → s[i]}. Inductive: T[i][j] from T[i][k] and T[k+1][j]. Accept: S ∈ T[0][n-1]. Complexity: O(n³) time, O(n²) space. Requires: CNF grammar.

📊 Table🔢 DP⏱️ O(n³)📘 CNF required

# CYK Algorithm
print("=" * 60)
print("CYK ALGORITHM")
print("=" * 60)

print("""
=== Overview ===

CYK (Cocke-Younger-Kasami) determines membership
in a CFL using dynamic programming.

Input: Grammar G in CNF, string w = a₁a₂...aₙ
Output: True if w ∈ L(G), False otherwise

=== Algorithm ===

1. Build table T[i][j] = set of nonterminals
   that derive substring w[i..j].

2. Base case: For each i:
   T[i][i] = { A | A → aᵢ is a rule }

3. Inductive case: For length L = 2 to n:
   For each i, j = i+L-1:
     T[i][j] = { A | A → BC, B ∈ T[i][k], C ∈ T[k+1][j] }

4. Accept if S ∈ T[0][n-1].

=== Complexity ===

Time: O(n³ × |G|)
Space: O(n² × |G|)

=== Example ===

Grammar (CNF):
  S → AB | BC
  A → BA | a
  B → CC | b
  C → AB | a

String: "baaba"

Table (bottom-up):
""")

# CYK IMPLEMENTATION
print("=== CYK Implementation ===")

class CNFGrammar:
    """CFG in Chomsky Normal Form."""
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules  # lhs -> list of rhs (tuples)
    
    def is_cnf(self):
        """Check if grammar is in CNF."""
        for lhs, productions in self.rules.items():
            for rhs in productions:
                if len(rhs) == 1:
                    # Must be terminal
                    if rhs[0] in self.rules:
                        return False
                elif len(rhs) == 2:
                    # Both must be nonterminals
                    if rhs[0] not in self.rules or rhs[1] not in self.rules:
                        return False
                elif len(rhs) == 0:
                    # Only S → ε allowed
                    if lhs != self.start:
                        return False
                else:
                    return False
        return True


def cyk_parse(grammar, string):
    """
    CYK algorithm for membership testing.
    Returns (accepted, table).
    """
    n = len(string)
    
    if n == 0:
        # Check if S → ε
        return (grammar.start in grammar.rules and 
                any(rhs == () for rhs in grammar.rules[grammar.start])), {}
    
    # Initialize table: T[i][j] = set of nonterminals
    # representing substring from i to j (inclusive)
    T = [[set() for _ in range(n)] for _ in range(n)]
    
    # Base case: substrings of length 1
    for i in range(n):
        char = string[i]
        for lhs, productions in grammar.rules.items():
            for rhs in productions:
                if len(rhs) == 1 and rhs[0] == char:
                    T[i][i].add(lhs)
    
    # Inductive case: substrings of length 2 to n
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # Try all split points
            for k in range(i, j):
                # Check all binary rules
                for lhs, productions in grammar.rules.items():
                    for rhs in productions:
                        if len(rhs) == 2:
                            B, C = rhs
                            if B in T[i][k] and C in T[k+1][j]:
                                T[i][j].add(lhs)
    
    # Check if start symbol is in T[0][n-1]
    accepted = grammar.start in T[0][n-1]
    return accepted, T


def print_cyk_table(T, string):
    """Pretty print CYK table."""
    n = len(string)
    print(f"\nCYK Table for '{string}':")
    print()
    
    # Header
    print("     ", end="")
    for j in range(n):
        print(f"{string[j]:>8}", end="")
    print()
    print("    " + "-" * (8 * n + 4))
    
    for i in range(n):
        print(f"{string[i]:>3} |", end="")
        for j in range(n):
            if i <= j:
                cell = ','.join(sorted(T[i][j])) if T[i][j] else '∅'
                print(f"{cell:>8}", end="")
            else:
                print(f"{'':>8}", end="")
        print()


# Example grammar (CNF)
grammar = CNFGrammar('S', {
    'S': [('A', 'B'), ('B', 'C')],
    'A': [('B', 'A'), ('a',)],
    'B': [('C', 'C'), ('b',)],
    'C': [('A', 'B'), ('a',)],
})

print("Grammar (CNF):")
for lhs, prods in sorted(grammar.rules.items()):
    for rhs in prods:
        rhs_str = ' '.join(rhs) if rhs else 'ε'
        print(f"  {lhs} → {rhs_str}")

print(f"\nIs CNF: {grammar.is_cnf()}")

# Test strings
test_strings = ['baaba', 'baab', 'ab', 'a', 'b', 'ba']

print("\n=== Membership Testing ===")
for s in test_strings:
    accepted, T = cyk_parse(grammar, s)
    result = "✓ ACCEPT" if accepted else "✗ REJECT"
    print(f"  '{s}' → {result}")

# Show table for one string
accepted, T = cyk_parse(grammar, 'baaba')
print_cyk_table(T, 'baaba')

# TRACE THE ALGORITHM
print("=== Algorithm Trace for 'baaba' ===")
print("""
Step 1: Length 1 (base case)
  T[0][0] = {A, C}  (b → B? No, wait...)
  
  Let's check: b → B (rule B → b)
  So T[0][0] = {B}
  
  a → A, C (rules A → a, C → a)
  So T[1][1] = {A, C}
  
  a → A, C
  T[2][2] = {A, C}
  
  b → B
  T[3][3] = {B}
  
  a → A, C
  T[4][4] = {A, C}

Step 2: Length 2
  T[0][1] for "ba":
    split k=0: T[0][0]={B}, T[1][1]={A,C}
    Rules: S → AB (B in T[0][0], A in T[1][1]) ✓ → S
           S → BC (B in T[0][0], C in T[1][1]) ✓ → S
           A → BA (B in T[0][0], A in T[1][1]) ✓ → A
           C → AB (A? not in T[0][0]) ✗
    T[0][1] = {S, A}
  
  T[1][2] for "aa":
    T[1][1]={A,C}, T[2][2]={A,C}
    Rules: S → AB (A in T[1][1], B? not in T[2][2]) ✗
           S → BC (B? not in T[1][1]) ✗
           A → BA (B? not in T[1][1]) ✗
           B → CC (C in T[1][1], C in T[2][2]) ✓ → B
           C → AB (A in T[1][1], B? not in T[2][2]) ✗
    T[1][2] = {B}
  
  T[2][3] for "ab":
    T[2][2]={A,C}, T[3][3]={B}
    S → AB (A in T[2][2], B in T[3][3]) ✓ → S
    S → BC (B? not in T[2][2]) ✗
    A → BA (B? not in T[2][2]) ✗
    C → AB (A in T[2][2], B in T[3][3]) ✓ → C
    T[2][3] = {S, C}
  
  T[3][4] for "ba":
    T[3][3]={B}, T[4][4]={A,C}
    S → AB (B in T[3][3], A in T[4][4]) ✓ → S
    S → BC (B in T[3][3], C in T[4][4]) ✓ → S
    A → BA (B in T[3][3], A in T[4][4]) ✓ → A
    T[3][4] = {S, A}

Step 3: Length 3
  ... (continue)

Final: S ∈ T[0][4] → ACCEPT
""")

# CYK WITH PARSE TREE RECONSTRUCTION
print("=== CYK with Parse Tree Reconstruction ===")

def cyk_with_tree(grammar, string):
    """CYK that also reconstructs a parse tree."""
    n = len(string)
    
    if n == 0:
        if grammar.start in grammar.rules:
            for rhs in grammar.rules[grammar.start]:
                if rhs == ():
                    return True, (grammar.start, [])
        return False, None
    
    # T[i][j] = dict: nonterminal -> (split_k, left_tree, right_tree)
    T = [[{} for _ in range(n)] for _ in range(n)]
    
    # Base case
    for i in range(n):
        char = string[i]
        for lhs, productions in grammar.rules.items():
            for rhs in productions:
                if len(rhs) == 1 and rhs[0] == char:
                    T[i][i][lhs] = (None, char, None)
    
    # Inductive
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                for lhs, productions in grammar.rules.items():
                    for rhs in productions:
                        if len(rhs) == 2:
                            B, C = rhs
                            if B in T[i][k] and C in T[k+1][j]:
                                if lhs not in T[i][j]:
                                    T[i][j][lhs] = (k, B, C)
    
    if grammar.start in T[0][n-1]:
        # Reconstruct tree
        def build(i, j, symbol):
            entry = T[i][j].get(symbol)
            if entry is None:
                return None
            if i == j:
                return ParseTreeNode(symbol, [ParseTreeNode(entry[1])])
            k, B, C = entry
            left = build(i, k, B)
            right = build(k+1, j, C)
            return ParseTreeNode(symbol, [left, right])
        
        tree = build(0, n-1, grammar.start)
        return True, tree
    
    return False, None


class ParseTreeNode:
    def __init__(self, symbol, children=None):
        self.symbol = symbol
        self.children = children or []
    
    def to_ascii(self):
        lines = []
        def build(node, prefix="", is_last=True):
            connector = "└── " if is_last else "├── "
            lines.append(prefix + connector + node.symbol)
            new_prefix = prefix + ("    " if is_last else "│   ")
            for i, child in enumerate(node.children):
                build(child, new_prefix, i == len(node.children) - 1)
        lines.append(self.symbol)
        for i, child in enumerate(self.children):
            build(child, "", i == len(self.children) - 1)
        return '\n'.join(lines)


# Test tree reconstruction
accepted, tree = cyk_with_tree(grammar, 'baaba')
if accepted:
    print("Parse tree for 'baaba':")
    print(tree.to_ascii())
else:
    print("'baaba' not in language")

# CYK COMPLEXITY
print("""
=== CYK Complexity ===

Time: O(n³ × |G|)
  - n² substrings
  - n split points per substring
  - |G| rules to check

Space: O(n² × |G|)
  - n² table cells
  - Each cell stores up to |G| nonterminals

For a fixed grammar, O(n³) time and O(n²) space.

=== Optimizations ===

1. BIT VECTORS
   Represent sets of nonterminals as bit vectors.

2. EARLEY PARSING
   O(n³) worst case, O(n) for many grammars.

3. PACKRAT PARSING
   Memoization + backtracking.

4. VALIANT'S ALGORITHM
   O(n^ω) where ω < 2.373 (matrix multiplication).

=== Comparison ===

Algorithm    Time       Space     Grammar
CYK          O(n³)      O(n²)     CNF
Earley       O(n³)      O(n²)     Any CFG
LL(k)        O(n)       O(1)      LL(k)
LR(k)        O(n)       O(1)      LR(k)
""")

🤖 CFG ↔ PDA

🎯 Grammars and Pushdown Automata

Context-free grammars and pushdown automata (PDAs) are equivalent: every CFG has a corresponding PDA, and vice versa. PDAs are the "machines" for CFLs, just as DFAs are for regular languages.

Equivalence

CFG → PDA: Nondeterministic PDA. PDA → CFG: Construct grammar from PDA. PDA: FSM + stack. Stack: Unbounded memory. Nondeterminism: Required for equivalence. Deterministic PDAs: Weaker (DCFL).

🤖 PDA📗 CFG↔️ Equivalent📚 Stack

# CFG ↔ PDA Equivalence
print("=" * 60)
print("CFG ↔ PDA EQUIVALENCE")
print("=" * 60)

print("""
=== Pushdown Automaton (PDA) ===

A PDA is a 7-tuple M = (Q, Σ, Γ, δ, q₀, Z₀, F):
  Q: finite states
  Σ: input alphabet
  Γ: stack alphabet
  δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)  (transition function)
  q₀: start state
  Z₀: initial stack symbol
  F: accept states

Key difference from DFA:
  - Has a STACK (unbounded memory)
  - Can push/pop symbols
  - Nondeterministic in general

=== Equivalence Theorem ===

L is context-free
  ⟺
L is accepted by some PDA

This is the CFL analog of:
  L is regular ⟺ L is accepted by some DFA

=== Two Acceptance Modes ===

1. ACCEPT BY FINAL STATE
   - End in an accept state
   - Stack contents irrelevant

2. ACCEPT BY EMPTY STACK
   - End with empty stack
   - State irrelevant

Both modes are equivalent!
""")

# PDA IMPLEMENTATION
print("=== PDA Implementation ===")

class PDA:
    """
    Pushdown Automaton.
    Transitions: (state, input_symbol, stack_top) -> list of (next_state, stack_push)
    """
    def __init__(self, states, input_alphabet, stack_alphabet, 
                 transitions, start_state, start_stack, accept_states):
        self.Q = states
        self.Sigma = input_alphabet
        self.Gamma = stack_alphabet
        self.delta = transitions
        self.q0 = start_state
        self.Z0 = start_stack
        self.F = accept_states
    
    def accepts(self, input_string, max_steps=1000):
        """Simulate PDA (nondeterministic)."""
        # Configuration: (state, remaining_input, stack)
        initial = (self.q0, input_string, (self.Z0,))
        
        from collections import deque
        queue = deque([(initial, 0)])
        visited = set()
        
        while queue:
            (state, remaining, stack), steps = queue.popleft()
            
            if steps > max_steps:
                continue
            
            key = (state, remaining, stack)
            if key in visited:
                continue
            visited.add(key)
            
            # Check acceptance
            if state in self.F and not remaining:
                return True
            # Also accept by empty stack
            if not stack:
                return True
            
            # Try epsilon transitions
            if stack:
                top = stack[0]
                for next_state, push in self.delta.get((state, 'ε', top), []):
                    new_stack = tuple(push) + stack[1:]
                    queue.append(((next_state, remaining, new_stack), steps + 1))
            
            # Try consuming input
            if remaining and stack:
                symbol = remaining[0]
                top = stack[0]
                for next_state, push in self.delta.get((state, symbol, top), []):
                    new_stack = tuple(push) + stack[1:]
                    queue.append(((next_state, remaining[1:], new_stack), steps + 1))
        
        return False


# Example: PDA for a^n b^n
print("=== Example: PDA for a^n b^n ===")
print("""
States: {q0, q1, q2}
Input: {a, b}
Stack: {Z, A}
Start: q0, Z
Accept: {q2}

Transitions:
  (q0, a, Z) → (q0, AZ)    push A
  (q0, a, A) → (q0, AA)    push A
  (q0, b, A) → (q1, ε)     pop A, switch to q1
  (q1, b, A) → (q1, ε)     pop A
  (q1, ε, Z) → (q2, Z)     accept

This PDA:
  - Pushes A for each 'a'
  - Pops A for each 'b'
  - Accepts when stack has only Z and input is done
""")

pda_anbn = PDA(
    states={'q0', 'q1', 'q2'},
    input_alphabet={'a', 'b'},
    stack_alphabet={'Z', 'A'},
    transitions={
        ('q0', 'a', 'Z'): [('q0', ('A', 'Z'))],
        ('q0', 'a', 'A'): [('q0', ('A', 'A'))],
        ('q0', 'b', 'A'): [('q1', ())],
        ('q1', 'b', 'A'): [('q1', ())],
        ('q1', 'ε', 'Z'): [('q2', ('Z',))],
    },
    start_state='q0',
    start_stack='Z',
    accept_states={'q2'}
)

print("Testing a^n b^n PDA:")
for s in ['', 'ab', 'aabb', 'aaabbb', 'aab', 'abb', 'ba', 'aaabbb']:
    result = pda_anbn.accepts(s)
    print(f"  '{s}' → {'✓' if result else '✗'}")

# CFG TO PDA CONSTRUCTION
print("\n=== CFG to PDA Construction ===")
print("""
Given CFG G = (V, Σ, R, S), construct PDA M:

M = ({q0, q1}, Σ, V ∪ Σ ∪ {Z}, δ, q0, Z, {q1})

Transitions:
1. (q0, ε, Z) → (q1, S Z)    [start: push S]
2. For each rule A → α:
   (q1, ε, A) → (q1, α^R)    [expand A]
3. For each terminal a:
   (q1, a, a) → (q1, ε)      [match terminal]
4. (q1, ε, Z) → (q1, ε)      [accept: empty stack]

Idea:
  - Push start symbol
  - Nondeterministically expand nonterminals
  - Match terminals with input
  - Accept when stack is empty

This PDA accepts by empty stack.
""")

def cfg_to_pda(cfg):
    """Convert CFG to PDA (accept by empty stack)."""
    states = {'q0', 'q1'}
    stack_alphabet = set(cfg.rules.keys()) | set('Z') | set()
    for prods in cfg.rules.values():
        for rhs in prods:
            stack_alphabet |= set(rhs)
    
    transitions = {}
    
    # Start: push S
    transitions[('q0', 'ε', 'Z')] = [('q1', (cfg.start, 'Z'))]
    
    # Expand nonterminals (push RHS in reverse)
    for lhs, prods in cfg.rules.items():
        for rhs in prods:
            key = ('q1', 'ε', lhs)
            if key not in transitions:
                transitions[key] = []
            # Push in reverse order (stack is LIFO)
            transitions[key].append(('q1', tuple(reversed(rhs))))
    
    # Match terminals
    terminals = set()
    for prods in cfg.rules.values():
        for rhs in prods:
            for s in rhs:
                if s not in cfg.rules:
                    terminals.add(s)
    
    for a in terminals:
        transitions[('q1', a, a)] = [('q1', ())]
    
    # Accept: empty stack
    transitions[('q1', 'ε', 'Z')] = [('q1', ())]
    
    return PDA(states, terminals, stack_alphabet, transitions, 'q0', 'Z', {'q1'})


# Example: Convert a^n b^n grammar
anbn_grammar = CFG('S', {
    'S': [('a', 'S', 'b'), ()],
})

pda_from_cfg = cfg_to_pda(anbn_grammar)

print("CFG: S → aSb | ε")
print("\nConverted PDA:")
print(f"  States: {pda_from_cfg.Q}")
print(f"  Input: {pda_from_cfg.Sigma}")
print(f"  Stack: {pda_from_cfg.Gamma}")
print(f"  Transitions: {len(pda_from_cfg.delta)}")

print("\nTesting:")
for s in ['', 'ab', 'aabb', 'aaabbb', 'aab', 'abb', 'ba']:
    result = pda_from_cfg.accepts(s)
    print(f"  '{s}' → {'✓' if result else '✗'}")

# PDA TO CFG (sketch)
print("""
=== PDA to CFG (Sketch) ===

Given PDA M, construct CFG G:

Idea: Nonterminals are triples [p, A, q]
  meaning: "from state p with A on stack,
            go to state q and pop A"

Rules:
1. For each state q: [q, A, q] → ε
2. For transition (p, a, A) → (r, B₁B₂...Bₖ):
   [p, A, q] → a [r, B₁, q₁] [q₁, B₂, q₂] ... [qₖ, Bₖ, q]

Start symbol: [q₀, Z₀, q_accept]

This is complex but shows the equivalence.
In practice, we usually go CFG → PDA.
""")

# DETERMINISTIC PDAs
print("=== Deterministic PDAs (DPDAs) ===")
print("""
A DPDA has at most one transition per configuration.

  |δ(q, a, Z)| ≤ 1

DPDAs are WEAKER than nondeterministic PDAs!

Languages accepted by DPDAs:
  - Called DETERMINISTIC CFLs (DCFLs)
  - Strict subset of CFLs
  - Include most programming languages
  - Parsed by LR(k) parsers

Example of CFL not accepted by DPDA:
  L = { ww^R | w ∈ {a,b}* }
  (palindromes)
  Requires nondeterminism to guess the middle.

Example of DCFL:
  L = { a^n b^n | n ≥ 0 }
  Deterministic: push a's, then pop b's.

=== Comparison ===

Type          Machine         Languages
DFA           Finite states   Regular
DPDA          Stack (det.)    DCFL
PDA           Stack (nondet.) CFL
LBA           Linear bounded  CSL
TM            Infinite tape   RE
""")

# SUMMARY TABLE
print("=== Summary ===")
print(f"{'Aspect':<30} {'CFG':<25} {'PDA':<25}")
print("-" * 80)
print(f"{'Type':<30} {'Grammar':<25} {'Machine':<25}")
print(f"{'Memory':<30} {'Rules':<25} {'Stack':<25}")
print(f"{'Nondeterminism':<30} {'Inherent':<25} {'Allowed':<25}")
print(f"{'Acceptance':<30} {'Derivation':<25} {'Final state/empty stack':<25}")
print(f"{'Deterministic?':<30} {'N/A':<25} {'DPDA (weaker)':<25}")
print(f"{'Closure ∪':<30} {'Yes':<25} {'Yes':<25}")
print(f"{'Closure ∩':<30} {'No':<25} {'No':<25}")
print(f"{'Membership':<30} {'O(n³) CYK':<25} {'O(n³)':<25}")
print(f"{'Example':<30} {'S → aSb':<25} {'Push/pop a/b':<25}")

🔒 Closure Properties

🎯 What Operations Preserve CFLs?

Context-free languages are closed under union, concatenation, Kleene star, and more. But they are NOT closed under intersection or complement.

Closure Properties of CFLs

Closed under: Union, concat, star, reversal, homomorphism. NOT closed under: Intersection, complement. Closed under: ∩ regular. Proof: Constructive with CFGs. Key: Intersection of two CFLs may not be CFL. Example: aⁿbⁿcⁿ.

✅ Union✅ Concat✅ Star❌ Intersection

# Closure Properties of CFLs
print("=" * 60)
print("CLOSURE PROPERTIES OF CFLs")
print("=" * 60)

print("""
=== Operations that PRESERVE Context-Freeness ===

✓ UNION: L1 ∪ L2
  Construction: New start S → S1 | S2
  G = (V1 ∪ V2 ∪ {S}, Σ, R1 ∪ R2 ∪ {S → S1 | S2}, S)

✓ CONCATENATION: L1 · L2
  Construction: New start S → S1 S2
  G = (V1 ∪ V2 ∪ {S}, Σ, R1 ∪ R2 ∪ {S → S1 S2}, S)

✓ KLEENE STAR: L*
  Construction: New start S → S S1 | ε
  G = (V1 ∪ {S}, Σ, R1 ∪ {S → S S1 | ε}, S)

✓ REVERSAL: L^R
  Construction: Reverse all RHS in rules
  A → α becomes A → α^R

✓ HOMOMORPHISM: h(L)
  Construction: Apply h to all terminals in rules
  A → a becomes A → h(a)

✓ INVERSE HOMOMORPHISM: h⁻¹(L)
  More complex, but still CFL.

✓ INTERSECTION WITH REGULAR: L ∩ R
  Construction: Product of PDA and DFA.
  (Key: CFL ∩ Regular = CFL)
""")

# CLOSURE CONSTRUCTIONS IN CODE
print("=== Closure Constructions ===")

class CFG:
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules
    
    def __repr__(self):
        lines = []
        for lhs in sorted(self.rules.keys()):
            for rhs in self.rules[lhs]:
                rhs_str = ' '.join(rhs) if rhs else 'ε'
                lines.append(f"  {lhs} → {rhs_str}")
        return '\n'.join(lines)


def union_cfg(g1, g2, new_start='S_union'):
    """L(G1) ∪ L(G2)"""
    new_rules = dict(g1.rules)
    for lhs, prods in g2.rules.items():
        if lhs in new_rules:
            new_rules[lhs] = new_rules[lhs] + prods
        else:
            new_rules[lhs] = prods
    
    # Add new start
    new_rules[new_start] = [(g1.start,), (g2.start,)]
    
    return CFG(new_start, new_rules)


def concat_cfg(g1, g2, new_start='S_concat'):
    """L(G1) · L(G2)"""
    new_rules = dict(g1.rules)
    for lhs, prods in g2.rules.items():
        if lhs in new_rules:
            new_rules[lhs] = new_rules[lhs] + prods
        else:
            new_rules[lhs] = prods
    
    new_rules[new_start] = [(g1.start, g2.start)]
    
    return CFG(new_start, new_rules)


def star_cfg(g, new_start='S_star'):
    """L(G)*"""
    new_rules = dict(g.rules)
    new_rules[new_start] = [(new_start, g.start), ()]
    
    return CFG(new_start, new_rules)


def reverse_cfg(g, new_start=None):
    """L(G)^R"""
    new_rules = {}
    for lhs, prods in g.rules.items():
        new_prods = []
        for rhs in prods:
            new_prods.append(tuple(reversed(rhs)))
        new_rules[lhs] = new_prods
    
    return CFG(g.start, new_rules)


# Example
g1 = CFG('S1', {'S1': [('a', 'S1', 'b'), ()]})  # a^n b^n
g2 = CFG('S2', {'S2': [('c', 'S2', 'd'), ()]})  # c^n d^n

print("G1: a^n b^n")
print(g1)
print("\nG2: c^n d^n")
print(g2)

union = union_cfg(g1, g2)
print("\nUnion (G1 ∪ G2):")
print(union)

concat = concat_cfg(g1, g2)
print("\nConcatenation (G1 · G2):")
print(concat)

star = star_cfg(g1)
print("\nStar (G1*):")
print(star)

# NON-CLOSURE
print("""
=== Operations that DO NOT Preserve Context-Freeness ===

✗ INTERSECTION: L1 ∩ L2
  Counterexample:
    L1 = { aⁿbⁿcᵐ | n, m ≥ 0 }  (CFL)
    L2 = { aⁿbᵐcᵐ | n, m ≥ 0 }  (CFL)
    L1 ∩ L2 = { aⁿbⁿcⁿ | n ≥ 0 }  (NOT CFL)

✗ COMPLEMENT: Σ* \ L
  Counterexample:
    L = { ww | w ∈ {a,b}* } is NOT CFL.
    But complement of L is also NOT CFL.
    (Actually, if L were CFL and complement CFL,
     then L ∩ complement would be CFL, but...)
    
  More precisely:
    CFLs are not closed under complement.
    Proof: If they were, then since they're closed
    under union, they'd be closed under intersection
    (by De Morgan). But they're not.

✗ DIFFERENCE: L1 \ L2
  Since L1 \ L2 = L1 ∩ complement(L2),
  and intersection/complement fail,
  difference also fails.
""")

# INTERSECTION WITH REGULAR
print("=== Intersection with Regular ===")
print("""
KEY THEOREM: CFL ∩ Regular = CFL

If L is context-free and R is regular,
then L ∩ R is context-free.

Proof idea:
  - Take PDA for L
  - Take DFA for R
  - Build product PDA
  - States: Q_PDA × Q_DFA
  - Accept: both accept

This is useful for proving languages are NOT CFL:
  If L ∩ R is not CFL (and R is regular),
  then L is not CFL.

Example:
  L = { aⁱbʲcᵏ | i < j < k }
  R = a*b*c* (regular)
  L ∩ R = { aⁱbʲcᵏ | i < j < k } = known not CFL
  Therefore L is not CFL.
""")

# SUMMARY TABLE
print("=== Closure Summary Table ===")
print(f"{'Operation':<30} {'Regular':<15} {'CFL':<15}")
print("-" * 60)
print(f"{'Union':<30} {'✓':<15} {'✓':<15}")
print(f"{'Intersection':<30} {'✓':<15} {'✗':<15}")
print(f"{'Complement':<30} {'✓':<15} {'✗':<15}")
print(f"{'Difference':<30} {'✓':<15} {'✗':<15}")
print(f"{'Concatenation':<30} {'✓':<15} {'✓':<15}")
print(f"{'Kleene Star':<30} {'✓':<15} {'✓':<15}")
print(f"{'Reversal':<30} {'✓':<15} {'✓':<15}")
print(f"{'Homomorphism':<30} {'✓':<15} {'✓':<15}")
print(f"{'Inverse Homomorphism':<30} {'✓':<15} {'✓':<15}")
print(f"{'∩ Regular':<30} {'✓':<15} {'✓':<15}")

print("""
=== Key Insight ===

CFLs are "almost" closed under everything,
EXCEPT intersection and complement.

This is why:
  - aⁿbⁿ is CFL (one counter)
  - aⁿbⁿcⁿ is NOT CFL (two counters)
  - { ww } is NOT CFL (copying)
  - { ww^R } IS CFL (palindrome — one stack)

The stack gives ONE counter.
To recognize aⁿbⁿcⁿ, you'd need TWO counters,
which requires more than a stack.

=== Decision Problems ===

Membership:     Decidable (CYK, O(n³))
Emptiness:      Decidable (check generating)
Finiteness:     Decidable
Equivalence:    UNDECIDABLE
Ambiguity:      UNDECIDABLE
Universality:   UNDECIDABLE

For regular languages:
  All these are decidable!
""")

💼 Applications

🎯 CFGs in the Real World

Context-free grammars are the backbone of compiler design, natural language processing, and data format specification. Every programming language has a CFG.

Application Domains

Compilers: Syntax analysis. Parsing: LL, LR, CYK, Earley. NLP: Sentence structure. Data formats: JSON, XML, YAML. Protocols: Message formats. Bioinformatics: RNA folding.

💻 Compilers📝 Parsing🌐 NLP📄 Data formats

# Applications of CFGs
print("=" * 60)
print("APPLICATIONS OF CFGs")
print("=" * 60)

# 1. COMPILERS
print("""
=== 1. Compilers ===

The most important application.

Pipeline:
  Source code → Lexer → Tokens → Parser → AST → Code gen

Parser uses CFG:
  - Grammar specifies syntax
  - Parser checks if tokens form valid program
  - Builds parse tree (AST)

Example: Expression grammar
  E → E + T | T
  T → T * F | F
  F → ( E ) | id

This handles:
  - Precedence (* before +)
  - Associativity (left)
  - Parentheses (nesting)

Tools:
  - Yacc/Bison (LR)
  - ANTLR (LL)
  - JavaCC
  - Happy (Haskell)
""")

# 2. PARSING ALGORITHMS
print("""
=== 2. Parsing Algorithms ===

CFGs enable systematic parsing:

TOP-DOWN:
  - Recursive descent
  - LL(1), LL(k)
  - Predictive parsing

BOTTOM-UP:
  - LR(0), SLR(1), LALR(1), LR(1)
  - Shift-reduce parsing
  - Yacc/Bison

GENERAL:
  - CYK (O(n³), CNF)
  - Earley (O(n³), any CFG)
  - GLR (generalized LR)

Each has trade-offs:
  - LL: simple, fast, limited grammars
  - LR: powerful, fast, complex tables
  - CYK: general, slow
  - Earley: general, medium
""")

# 3. NATURAL LANGUAGE
print("""
=== 3. Natural Language Processing ===

CFGs model sentence structure:

  S → NP VP
  NP → Det N | Det Adj N | NP PP
  VP → V NP | V PP | V
  PP → P NP

Example: "The cat sat on the mat"
  S
  ├── NP
  │   ├── Det: The
  │   └── N: cat
  └── VP
      ├── V: sat
      └── PP
          ├── P: on
          └── NP
              ├── Det: the
              └── N: mat

Used in:
  - Parsing (syntax)
  - Machine translation
  - Information extraction
  - Question answering
""")

# 4. DATA FORMATS
print("""
=== 4. Data Formats ===

Many data formats are context-free:

JSON:
  value → object | array | string | number | true | false | null
  object → { members } | { }
  members → pair | pair , members
  pair → string : value
  array → [ elements ] | [ ]
  elements → value | value , elements

XML:
  element →  content 
  content → element | text | content content

YAML:
  (indentation-based, but still CFG)

These require nesting, so regex can't parse them!
""")

# 5. PROTOCOLS
print("""
=== 5. Network Protocols ===

Message formats:

HTTP:
  request → method SP url SP version CRLF headers CRLF body
  headers → header | header CRLF headers
  header → name : value

Email (RFC 5322):
  message → headers CRLF body
  headers → header | header CRLF headers

SIP, SMTP, FTP:
  All have CFG-based message formats.

Why?
  - Nested structures
  - Variable-length fields
  - Context-dependent parsing
""")

# 6. BIOINFORMATICS
print("""
=== 6. Bioinformatics ===

RNA secondary structure:
  - RNA folds into shapes
  - Base pairs: A-U, G-C
  - Nested structure = CFG

Grammar for RNA:
  S → a S u | c S g | g S c | u S a | S S | ε

This models:
  - Stems (base pairs)
  - Loops
  - Branches

Used in:
  - RNA folding prediction
  - Sequence analysis
  - Drug design
""")

# 7. PROGRAMMING LANGUAGES
print("""
=== 7. Programming Languages ===

Every language has a CFG:

Python:
  file_input → (NEWLINE | stmt)* ENDMARKER
  stmt → simple_stmt | compound_stmt
  compound_stmt → if_stmt | while_stmt | for_stmt | ...
  if_stmt → 'if' test ':' suite ('elif' test ':' suite)*
            ['else' ':' suite]

Java:
  CompilationUnit → PackageDeclaration? ImportDeclaration*
                    TypeDeclaration*
  TypeDeclaration → ClassDeclaration | InterfaceDeclaration
  ClassDeclaration → Modifier* 'class' Identifier ...

C:
  translation_unit → external_declaration+
  external_declaration → function_definition | declaration
  function_definition → declaration_specifiers declarator
                        compound_statement

These grammars are published in language specs.
""")

# 8. TOOLS
print("""
=== 8. Tools ===

PARSER GENERATORS:
  - Yacc/Bison (C)
  - ANTLR (Java, Python, C++, ...)
  - JavaCC (Java)
  - Happy (Haskell)
  - PLY (Python)
  - PEG.js (JavaScript)

PARSING LIBRARIES:
  - Lark (Python)
  - pyparsing (Python)
  - Parsec (Haskell)
  - Nom (Rust)
  - Boost.Spirit (C++)

Each takes a grammar and generates a parser.

Example (Lark):
  grammar = '''
    start: expr
    ?expr: expr "+" term -> add
         | term
    ?term: term "*" factor -> mul
         | factor
    ?factor: "(" expr ")"
           | NUMBER
    %import common.NUMBER
    %import common.WS
    %ignore WS
  '''
""")

# 9. SUMMARY TABLE
print("=== Application Summary ===")
print(f"{'Domain':<25} {'Use Case':<30} {'CFG Role':<25}")
print("-" * 80)
print(f"{'Compilers':<25} {'Syntax analysis':<30} {'Grammar specification':<25}")
print(f"{'Parsing':<25} {'Parse algorithms':<30} {'Input grammar':<25}")
print(f"{'NLP':<25} {'Sentence parsing':<30} {'Syntactic structure':<25}")
print(f"{'Data formats':<25} {'JSON, XML':<30} {'Format definition':<25}")
print(f"{'Protocols':<25} {'Message parsing':<30} {'Protocol grammar':<25}")
print(f"{'Bioinformatics':<25} {'RNA folding':<30} {'Nested structure':<25}")
print(f"{'Languages':<25} {'Language design':<30} {'Language spec':<25}")
print(f"{'Tools':<25} {'Parser generators':<30} {'Input grammar':<25}")

# 10. CASE STUDY: PYTHON GRAMMAR
print("""
=== Case Study: Python Grammar (excerpt) ===

From Python's official Grammar file:

  single_input: NEWLINE | simple_stmt | compound_stmt NEWLINE
  file_input: (NEWLINE | stmt)* ENDMARKER
  eval_input: testlist NEWLINE* ENDMARKER

  stmt: simple_stmt | compound_stmt
  simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE
  small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt |
               import_stmt | global_stmt | nonlocal_stmt | assert_stmt)
  compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt |
                 with_stmt | funcdef | classdef | decorated | async_stmt

  if_stmt: 'if' test ':' suite ('elif' test ':' suite)*
           ['else' ':' suite]
  while_stmt: 'while' test ':' suite ['else' ':' suite]
  for_stmt: 'for' exprlist 'in' testlist ':' suite ['else' ':' suite]

  expr: xor_expr ('|' xor_expr)*
  xor_expr: and_expr ('^' and_expr)*
  and_expr: shift_expr ('&' shift_expr)*
  shift_expr: arith_expr (('<<'|'>>') arith_expr)*
  arith_expr: term (('+'|'-') term)*
  term: factor (('*'|'@'|'/'|'%'|'//') factor)*
  factor: ('+'|'-'|'~') factor | power
  power: atom_expr ['**' factor]

This grammar defines ALL of Python's syntax!
""")

🚀 Advanced Topics

🎯 Beyond Basic CFGs

CFGs are the foundation for many advanced topics: parsing algorithms, grammar transformations, formal language theory, and modern applications.

Advanced Directions

Earley: General parsing. GLR: Generalized LR. PEG: Parsing expression grammars. Probabilistic: PCFGs for NLP. Tree: Tree adjoining grammars. Quantum: Quantum grammars.

🔍 Earley🌲 Tree grammars📊 PCFG⚛️ Quantum

# Advanced Topics in CFGs
print("=" * 60)
print("ADVANCED TOPICS")
print("=" * 60)

# 1. EARLEY PARSING
print("""
=== 1. Earley Parsing ===

A general parsing algorithm for ANY CFG.

Idea: Dynamic programming with "dotted rules."

Items: A → α · β   (α parsed, β remaining)
  - Predictor: expand nonterminals
  - Scanner: match terminals
  - Completer: combine completed items

Complexity:
  O(n³) for general CFGs
  O(n²) for unambiguous grammars
  O(n) for LL(k)/LR(k) grammars

Advantages:
  - Handles any CFG
  - Handles ambiguity (lists all parses)
  - Handles left recursion
  - Online (processes left-to-right)

Used in:
  - NLP (natural language parsing)
  - Some compiler frontends
  - Grammar development tools
""")

# 2. GLR PARSING
print("""
=== 2. GLR Parsing ===

Generalized LR parsing.

Idea: When LR parser encounters a conflict,
fork the parse stack.

Handles:
  - Ambiguous grammars
  - Non-LR grammars
  - Multiple parse trees

Complexity: O(n³) worst case

Used in:
  - C++ parsers (some)
  - Elkhound (C++)
  - Bison with GLR mode
  - Parsing ambiguous languages
""")

# 3. PEG (PARSING EXPRESSION GRAMMARS)
print("""
=== 3. PEG ===

Parsing Expression Grammars (Ford, 2004).

Different from CFG:
  - Ordered choice (not unordered)
  - Greedy matching
  - No ambiguity by design

Operators:
  e1 e2      Sequence
  e1 / e2    Ordered choice
  e*         Zero or more
  e+         One or more
  e?         Optional
  &e         And-predicate
  !e         Not-predicate

Advantages:
  - No ambiguity
  - Simple to implement
  - Good for DSLs

Used in:
  - PEG.js (JavaScript)
  - Pest (Rust)
  - LPeg (Lua)
  - Python's pegen

Note: PEGs are not CFGs!
They recognize a different class of languages.
""")

# 4. PROBABILISTIC CFGs
print("""
=== 4. Probabilistic CFGs (PCFGs) ===

Each rule has a probability:
  A → α    with probability p

Sum of probabilities for each A = 1.

Used in NLP:
  - Parsing ambiguous sentences
  - Choosing most likely parse
  - Language modeling

Example:
  S → NP VP    [0.8]
  S → VP       [0.2]
  
  NP → Det N   [0.6]
  NP → N       [0.4]
  
  P(tree) = product of rule probabilities

CKY can be extended to find most probable parse.
""")

# 5. TREE ADJOINING GRAMMARS
print("""
=== 5. Tree Adjoining Grammars (TAG) ===

More powerful than CFGs.

Idea: Combine tree fragments using:
  - Substitution (replace leaf with tree)
  - Adjunction (insert tree into tree)

Generates:
  - All CFLs
  - Some non-CFLs (e.g., aⁿbⁿcⁿdⁿ)
  - Mildly context-sensitive languages

Used in:
  - NLP (some theories)
  - Treebanks
  - Computational linguistics

Complexity: O(n⁶) parsing
""")

# 6. QUANTUM GRAMMARS
print("""
=== 6. Quantum Grammars ===

Quantum context-free grammars:
  - Rules have quantum amplitudes
  - Superposition of derivations
  - Measurement at the end

Research area:
  - Quantum natural language processing
  - Quantum compiler design
  - Theoretical computer science

Still experimental.
""")

# 7. MODERN PARSING
print("""
=== 7. Modern Parsing Trends ===

1. NEURAL PARSING
   - Deep learning for parsing
   - No explicit grammar
   - Still uses CFG concepts

2. PARSING WITH TRANSFORMERS
   - Attention-based parsing
   - Fast, accurate
   - Black-box models

3. HYBRID APPROACHES
   - CFG + neural
   - Best of both worlds

4. INCREMENTAL PARSING
   - Online, left-to-right
   - Important for interactive systems

5. MULTILINGUAL PARSING
   - Universal Dependencies
   - Cross-lingual transfer
""")

# 8. OPEN PROBLEMS
print("""
=== 8. Open Problems ===

1. EFFICIENT GENERAL PARSING
   - Can we parse any CFG in O(n²)?
   - Valiant's algorithm: O(n^ω)
   - Lower bounds unclear

2. AMBIGUITY RESOLUTION
   - How to choose the right parse?
   - Statistical vs rule-based
   - Neural approaches

3. GRAMMAR INDUCTION
   - Learn CFG from examples
   - Active learning
   - Still hard

4. PARSING NATURAL LANGUAGE
   - Garden path sentences
   - Center embedding
   - Human parsing limitations

5. QUANTUM PARSING
   - Quantum algorithms for parsing
   - Potential speedups
   - Early stage
""")

# 9. RECOMMENDATIONS
print("""
=== Recommendations ===

For compiler developers:
  1. Master LL and LR parsing
  2. Understand CFG transformations
  3. Learn parser generators
  4. Handle ambiguity carefully

For NLP practitioners:
  1. Learn PCFGs and CKY
  2. Understand Earley parsing
  3. Explore neural parsing
  4. Study treebanks

For researchers:
  1. Explore efficient parsing
  2. Study grammar induction
  3. Investigate quantum grammars
  4. Work on multilingual parsing

For students:
  1. Implement CYK from scratch
  2. Build a recursive descent parser
  3. Study Yacc/Bison
  4. Learn about ambiguity
""")

# 10. FINAL THOUGHTS
print("""
=== Final Thoughts ===

CFGs are:

✓ FOUNDATIONAL
  Type 2 in Chomsky hierarchy.

✓ POWERFUL
  Can express nesting and counting.

✓ PRACTICAL
  Used in every compiler.

✓ THEORETICAL
  Rich theory (normal forms, closure).

✓ EXTENSIBLE
  PCFGs, TAGs, quantum grammars.

✓ EVOLVING
  Neural parsing, grammar induction.

Key takeaway:
  CFGs are the sweet spot between
  regular expressions (too weak)
  and Turing machines (too powerful).

They capture exactly what's needed for
most programming languages and
many natural language phenomena.

"Context-free grammars are the
backbone of computer science."
  — Anonymous

Go build a parser!
""")

# QUICK REFERENCE
print("""
=== Quick Reference ===

CFG: G = (V, Σ, R, S)
  V: nonterminals
  Σ: terminals
  R: rules A → α
  S: start symbol

Derivation: S ⇒* w
  Leftmost: expand left first
  Rightmost: expand right first

Parse tree:
  Root: S
  Internal: nonterminals
  Leaves: terminals

Ambiguity:
  Multiple parse trees for same string
  Inherent: every grammar is ambiguous

CNF: A → BC | a
  CYK: O(n³) parsing

PDA: CFG equivalent
  Stack = unbounded memory

Closure:
  ✓ Union, concat, star, reversal
  ✗ Intersection, complement

Decision problems:
  Membership: Decidable
  Emptiness: Decidable
  Equivalence: Undecidable
  Ambiguity: Undecidable
""")