🧠 PDA Fundamentals

🎯 What is a Pushdown Automaton?

A Pushdown Automaton (PDA) is a finite automaton equipped with a stack — an unbounded last-in-first-out (LIFO) memory. This extra memory allows PDAs to recognize context-free languages, which are strictly more powerful than regular languages.

Key insight: The stack gives a PDA one "counter" — enough to match nested structures like balanced parentheses or aⁿbⁿ, but not enough for aⁿbⁿcⁿ (which needs two counters).

Why PDAs Matter

Power: Beyond regular languages. Stack: Unbounded LIFO memory. CFG equivalence: Same power as CFGs. Parsing: Foundation of parsers. Nondeterminism: Essential for full power. Compilers: Syntax analysis.

📌 Stack memory📌 Context-free📌 CFG equivalent📌 Nondeterministic

# Pushdown Automaton — the big picture
print("""
=== What Makes a PDA Special? ===

DFA/NFA:      Finite states only
PDA:          Finite states + STACK

The stack is:
  - Unbounded (can grow arbitrarily)
  - LIFO (last-in, first-out)
  - Only top is accessible

This gives PDAs the ability to:
  - Count (match a's with b's)
  - Remember nested structure
  - Parse context-free languages

=== Real-World Analogy: Plate Stack ===

Imagine a stack of plates:
  - You can only add/remove from the TOP
  - Can't access middle plates directly
  - Can grow arbitrarily high

A PDA uses its stack like this:
  - Push: add a plate
  - Pop: remove top plate
  - Peek: look at top plate

=== The Key Limitation ===

A single stack gives ONE counter.

  a^n b^n:        ✓ PDA can do (one counter)
  a^n b^n c^n:    ✗ PDA can't (two counters needed)
  ww:             ✗ PDA can't (needs to copy)
  ww^R:           ✓ PDA can do (palindrome — stack!)

=== PDA vs Other Models ===

DFA:   Finite memory → regular languages
PDA:   Stack memory → context-free languages
LBA:   Linear memory → context-sensitive
TM:    Infinite memory → recursively enumerable
""")

# ANALOGY
print("=== Analogy: Well-Balanced Parentheses ===")
print("""
How does a PDA check if parentheses are balanced?

Input: ( ( ) ( ) )

Process:
  Read '(' → push '(' onto stack
  Read '(' → push '(' onto stack
  Read ')' → pop '(' from stack ✓
  Read '(' → push '(' onto stack
  Read ')' → pop '(' from stack ✓
  Read ')' → pop '(' from stack ✓
  
  End of input: stack is empty → ACCEPT

If stack is non-empty or we try to pop from empty:
  → REJECT

The stack remembers how many unmatched '(' we have.
This is impossible for a DFA (finite memory)!

=== Why a^n b^n c^n is Hard ===

To match a^n b^n c^n, we need to:
  - Count a's (push)
  - Match b's (pop)
  - Match c's with... what? The stack is empty!

One stack can only do ONE count.
After matching a's with b's, there's nothing left
to match c's with.

So a^n b^n c^n is NOT context-free.
""")

# PDA IN CODE
print("=== Python: Simple PDA Simulation ===")

from collections import deque

class PDA:
    """A simple nondeterministic pushdown automaton."""
    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  # (state, input, stack_top) -> [(next_state, push)]
        self.q0 = start_state
        self.Z0 = start_stack
        self.F = accept_states
    
    def accepts(self, input_string, max_steps=10000):
        """Simulate PDA (nondeterministic, BFS)."""
        # Configuration: (state, remaining_input_index, stack_tuple)
        initial = (self.q0, 0, (self.Z0,))
        queue = deque([(initial, [])])
        visited = set()
        steps = 0
        
        while queue and steps < max_steps:
            (state, idx, stack), path = queue.popleft()
            steps += 1
            
            key = (state, idx, stack)
            if key in visited:
                continue
            visited.add(key)
            
            # Acceptance: input consumed and (in accept state OR empty stack)
            if idx == len(input_string):
                if state in self.F or len(stack) == 0:
                    return True, path
            
            # Try epsilon transitions
            if stack:
                top = stack[0]
                for (ns, push) in self.delta.get((state, 'ε', top), []):
                    new_stack = tuple(push) + stack[1:]
                    queue.append(((ns, idx, new_stack), path + [(state, 'ε', top, ns, push)]))
            
            # Try consuming input
            if idx < len(input_string) and stack:
                symbol = input_string[idx]
                top = stack[0]
                for (ns, push) in self.delta.get((state, symbol, top), []):
                    new_stack = tuple(push) + stack[1:]
                    queue.append(((ns, idx + 1, new_stack), 
                                  path + [(state, symbol, top, ns, push)]))
        
        return False, None


# Example: PDA for a^n b^n
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("PDA for a^n b^n")
print("Testing:")
for s in ['', 'ab', 'aabb', 'aaabbb', 'aab', 'abb', 'ba', 'aabbb']:
    accepted, path = pda_anbn.accepts(s)
    result = "✓ ACCEPT" if accepted else "✗ REJECT"
    print(f"  '{s}' → {result}")

# Trace one example
print("\nTrace for 'aabb':")
accepted, path = pda_anbn.accepts('aabb')
if path:
    for i, (state, symbol, top, ns, push) in enumerate(path):
        print(f"  Step {i+1}: ({state}, {symbol}, {top}) → ({ns}, push {push})")

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

A PDA M accepts a string w if there exists
a sequence of transitions from the start
configuration to an accepting configuration.

Two acceptance modes:
  1. Accept by final state: end in F
  2. Accept by empty stack: stack is empty

L(M) = { w | M accepts w }

=== Key Facts ===

1. Every CFG can be converted to a PDA.
2. Every PDA can be converted to a CFG.
3. Therefore: PDA ⟺ CFG (same power).
4. Nondeterminism is essential for full power.
5. Deterministic PDAs are weaker (DCFL).

=== Comparison ===

Model   Memory          Languages
DFA     None            Regular
PDA     Stack           Context-Free
LBA     Linear tape     Context-Sensitive
TM      Infinite tape   Recursively Enumerable
""")

📐 Formal Definition

🎯 The 7-Tuple

A PDA is formally defined as a 7-tuple M = (Q, Σ, Γ, δ, q₀, Z₀, F), where each component plays a specific role in the machine's operation.

The Components

Q: Finite set of states. Σ: Input alphabet. Γ: Stack alphabet. δ: Transition function Q × (Σ∪{ε}) × Γ → P(Q × Γ*). q₀: Start state. Z₀: Initial stack symbol. F: Accept states.

Q StatesΣ InputΓ Stackδ Transitionsq₀ StartZ₀ Stack initF Accept

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

@dataclass
class PDA:
    """
    Formal PDA as 7-tuple M = (Q, Σ, Γ, δ, q₀, Z₀, F)
    
    Q:  finite set of states
    Σ:  input alphabet
    Γ:  stack alphabet
    δ:  Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)   transition function
    q₀: start state
    Z₀: initial stack symbol
    F:  set of accept states
    """
    Q: FrozenSet[str]                                    # States
    Sigma: FrozenSet[str]                                # Input alphabet
    Gamma: FrozenSet[str]                                # Stack alphabet
    delta: Dict[Tuple[str, str, str], List[Tuple[str, Tuple[str, ...]]]]
    q0: str                                              # Start state
    Z0: str                                              # Initial stack symbol
    F: FrozenSet[str]                                    # Accept states
    
    def __post_init__(self):
        # Validate
        assert self.q0 in self.Q, "Start state must be in Q"
        assert self.Z0 in self.Gamma, "Z0 must be in Γ"
        assert self.F.issubset(self.Q), "F must be subset of Q"
        assert self.Sigma & self.Gamma == frozenset() or True, \
            "Σ and Γ may overlap (usually don't)"
        
        for (q, a, Z), results in self.delta.items():
            assert q in self.Q, f"State {q} not in Q"
            assert a in self.Sigma or a == 'ε', f"Symbol {a} not valid"
            assert Z in self.Gamma, f"Stack symbol {Z} not in Γ"
            for (next_q, push) in results:
                assert next_q in self.Q, f"Next state {next_q} not in Q"
                for s in push:
                    assert s in self.Gamma, f"Push symbol {s} not in Γ"
    
    def __repr__(self):
        lines = [f"PDA M = (Q, Σ, Γ, δ, q₀, Z₀, F)"]
        lines.append(f"  Q = {sorted(self.Q)}")
        lines.append(f"  Σ = {sorted(self.Sigma)}")
        lines.append(f"  Γ = {sorted(self.Gamma)}")
        lines.append(f"  q₀ = {self.q0}")
        lines.append(f"  Z₀ = {self.Z0}")
        lines.append(f"  F = {sorted(self.F)}")
        lines.append(f"  δ:")
        for (q, a, Z), results in sorted(self.delta.items()):
            for (nq, push) in results:
                push_str = ''.join(push) if push else 'ε'
                lines.append(f"    δ({q}, {a}, {Z}) ∋ ({nq}, {push_str})")
        return '\n'.join(lines)


# Example: PDA for a^n b^n
pda_anbn = PDA(
    Q=frozenset({'q0', 'q1', 'q2'}),
    Sigma=frozenset({'a', 'b'}),
    Gamma=frozenset({'Z', 'A'}),
    delta={
        ('q0', 'a', 'Z'): [('q0', ('A', 'Z'))],
        ('q0', 'a', 'A'): [('q0', ('A', 'A'))],
        ('q0', 'b', 'A'): [('q1', ())],
        ('q1', 'b', 'A'): [('q1', ())],
        ('q1', 'ε', 'Z'): [('q2', ('Z',))],
    },
    q0='q0',
    Z0='Z',
    F=frozenset({'q2'})
)

print(pda_anbn)

# CONFIGURATION
print("""
=== Configurations ===

A configuration (or instantaneous description)
of a PDA is a triple:
  (q, w, γ)

where:
  q ∈ Q       current state
  w ∈ Σ*      remaining input
  γ ∈ Γ*      current stack contents

=== Initial Configuration ===
  (q₀, w, Z₀)

=== Accepting Configuration ===
  Accept by final state:  (q, ε, γ) with q ∈ F
  Accept by empty stack:  (q, ε, ε) for any q

=== Transition Relation ⊢ ===

We write:
  (q, aw, Zγ) ⊢ (q', w, αγ)
  
if δ(q, a, Z) contains (q', α).

This means:
  - In state q
  - Reading 'a' (or ε)
  - With Z on top of stack
  - Move to state q'
  - Replace Z with α
  
⊢* is the reflexive-transitive closure.
""")

# CONFIGURATION TRACE
print("=== Configuration Trace: 'aabb' ===")
print("""
PDA for a^n b^n:

  δ(q0, a, Z) = (q0, AZ)
  δ(q0, a, A) = (q0, AA)
  δ(q0, b, A) = (q1, ε)
  δ(q1, b, A) = (q1, ε)
  δ(q1, ε, Z) = (q2, Z)

Input: aabb

Start:  (q0, aabb, Z)
        
Read 'a': (q0, aabb, Z) ⊢ (q0, abb, AZ)
Read 'a': (q0, abb, AZ) ⊢ (q0, bb, AAZ)
Read 'b': (q0, bb, AAZ) ⊢ (q1, b, AZ)
Read 'b': (q1, b, AZ) ⊢ (q1, ε, Z)
ε-move:   (q1, ε, Z) ⊢ (q2, ε, Z)

Accept: q2 ∈ F and input consumed ✓
""")

# FORMAL ACCEPTANCE
print("""
=== Formal Acceptance Definitions ===

ACCEPT BY FINAL STATE:
  L(M) = { w | (q₀, w, Z₀) ⊢* (q, ε, γ) for some q ∈ F, γ ∈ Γ* }

ACCEPT BY EMPTY STACK:
  N(M) = { w | (q₀, w, Z₀) ⊢* (q, ε, ε) for some q ∈ Q }

=== Equivalence ===

For any PDA M1 (final state), there exists M2 (empty stack)
such that L(M1) = N(M2), and vice versa.

Therefore, the two modes are equivalent.

=== Standard Convention ===

We usually specify:
  - Start state q0
  - Initial stack symbol Z0
  - Accept states F

And use "accept by final state" as the default.
""")

# VALIDATION
print("=== Validation ===")

def validate_pda(pda):
    """Validate a PDA's structure."""
    errors = []
    
    if pda.q0 not in pda.Q:
        errors.append(f"Start state {pda.q0} not in Q")
    
    if pda.Z0 not in pda.Gamma:
        errors.append(f"Z0 {pda.Z0} not in Γ")
    
    if not pda.F.issubset(pda.Q):
        errors.append(f"F not subset of Q")
    
    for (q, a, Z), results in pda.delta.items():
        if q not in pda.Q:
            errors.append(f"State {q} not in Q")
        if a != 'ε' and a not in pda.Sigma:
            errors.append(f"Symbol {a} not in Σ ∪ {{ε}}")
        if Z not in pda.Gamma:
            errors.append(f"Stack symbol {Z} not in Γ")
        for (nq, push) in results:
            if nq not in pda.Q:
                errors.append(f"Next state {nq} not in Q")
            for s in push:
                if s not in pda.Gamma:
                    errors.append(f"Push symbol {s} not in Γ")
    
    if errors:
        print("❌ Validation errors:")
        for e in errors:
            print(f"  - {e}")
    else:
        print("✓ PDA is valid")
    
    return len(errors) == 0


validate_pda(pda_anbn)

# MORE EXAMPLES
print("\n=== More PDA Examples ===")
print("""
1. PALINDROMES over {a, b}:
   Q = {q0, q1, q2}
   Γ = {Z, a, b}
   Push all symbols, guess middle, pop and match.
   
2. BALANCED PARENTHESES:
   Q = {q0, q1}
   Γ = {Z, (}
   Push '(', pop on ')'.
   
3. a^i b^j with i > j:
   Push a's, pop on b's, accept if stack still has a's.
   
4. EQUAL a's and b's (any order):
   Push when seeing a, pop when seeing b, or vice versa.
   Nondeterministic choice.
""")

📚 The Stack

🎯 The PDA's Memory

The stack is a LIFO (last-in, first-out) data structure. It's the key difference between a PDA and a finite automaton, giving the PDA its extra computational power.

Stack Operations

Push: Add symbol to top. Pop: Remove top symbol. Peek: Read top symbol. Replace: Pop then push. Empty: No symbols. LIFO: Last in, first out.

⬆️ Push⬇️ Pop👁️ Peek🔄 Replace

# The Stack in detail
print("=" * 60)
print("THE STACK")
print("=" * 60)

print("""
=== Stack Basics ===

A stack is a LIFO (Last-In, First-Out) data structure.

Operations:
  push(x):   Add x to the top
  pop():     Remove and return the top
  peek():    Return the top without removing
  isEmpty(): Check if empty

=== Stack in a PDA ===

The PDA's stack:
  - Starts with symbol Z₀ (bottom marker)
  - Can grow arbitrarily high
  - Only top is accessible
  - Operations:
    * Push symbols (δ returns a string to push)
    * Pop symbol (δ returns empty string)
    * Replace (push a string in place of top)

=== Visualizing the Stack ===

Empty:        [ ]

After push A: [ A ]

After push B: [ B A ]

After pop:    [ A ]

After push C: [ C A ]

Note: The top is on the LEFT in our notation.
""")

# STACK IMPLEMENTATION
print("=== Python: Stack Implementation ===")

class Stack:
    """Simple stack for PDA simulation."""
    def __init__(self, initial=None):
        # We'll use a list with the top at the END for efficiency
        # But for PDA display, top is often shown first
        self.items = list(initial) if initial else []
    
    def push(self, symbols):
        """Push a sequence of symbols."""
        # If pushing string "ABC", A goes on top
        # So we push in reverse order
        for s in reversed(symbols):
            self.items.append(s)
    
    def pop(self):
        """Pop the top symbol."""
        if self.items:
            return self.items.pop()
        return None
    
    def peek(self):
        """Return the top symbol."""
        return self.items[-1] if self.items else None
    
    def is_empty(self):
        return len(self.items) == 0
    
    def __repr__(self):
        # Display with top on the left
        return '[' + ' '.join(reversed(self.items)) + ']'


# Demonstrate stack operations
print("Stack operations:")
s = Stack()
print(f"  Initial:     {s}")

s.push("Z")
print(f"  push Z:      {s}")

s.push("A")
print(f"  push A:      {s}")

s.push("B")
print(f"  push B:      {s}")

top = s.pop()
print(f"  pop → {top}:   {s}")

s.push("C")
print(f"  push C:      {s}")

print(f"  peek:        {s.peek()}")
print(f"  is_empty:    {s.is_empty()}")

# STACK IN PDA TRANSITIONS
print("""
=== Stack Operations in PDA Transitions ===

Each transition δ(q, a, Z) = (q', γ) does:

  1. Pop Z from the stack top
  2. Push γ (a string of stack symbols)
  3. Move to state q'

Examples:

δ(q, a, Z) = (q', ε)
  → Pop Z, push nothing (net: pop Z)

δ(q, a, Z) = (q', A)
  → Pop Z, push A (net: replace Z with A)

δ(q, a, Z) = (q', AB)
  → Pop Z, push AB (A on top of B)
  → Net: replace Z with A, then B below A

δ(q, a, Z) = (q', Z)
  → Pop Z, push Z back (net: no change, just read input)
""")

# STACK TRACE VISUALIZATION
print("=== Stack Trace for a^n b^n on 'aabb' ===")
print("""
Input: a a b b

Start:          Stack: [Z]

Read 'a':       Push A         Stack: [A Z]
Read 'a':       Push A         Stack: [A A Z]
Read 'b':       Pop A          Stack: [A Z]
Read 'b':       Pop A          Stack: [Z]
ε-move:         No change      Stack: [Z]

Accept: stack has Z, in accept state q2 ✓

Visual:
  Start     Read a    Read a    Read b    Read b    Accept
  [Z]  →   [A Z]  →  [A A Z] → [A Z]  →  [Z]   →  [Z]
           push A    push A    pop A     pop A
""")

# STACK FOR DIFFERENT LANGUAGES
print("=== Stack Usage for Different Languages ===")
print("""
1. a^n b^n (n ≥ 0)
   Push A for each a, pop A for each b.
   Accept if stack returns to Z.
   
2. BALANCED PARENTHESES
   Push '(' for each '('.
   Pop '(' for each ')'.
   Accept if stack returns to Z.
   
3. PALINDROMES (w = w^R)
   Push all symbols until middle (guess).
   Pop and match for second half.
   Accept if all match.
   
4. a^i b^j (i > j)
   Push A for each a.
   Pop A for each b.
   Accept if stack still has A's left.
   
5. a^i b^j (i < j)
   Push A for each a.
   Pop A for each b.
   Accept if we run out of A's before input.
   (Need to check we don't have extra A's.)
   
6. EQUAL a's and b's (any order)
   Nondeterministically push A for a, pop A for b,
   OR push B for b, pop B for a.
""")

# STACK SIMULATION IN CODE
print("=== Full Stack Simulation ===")

class PDASimulator:
    """PDA simulator with stack visualization."""
    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 simulate(self, input_string, verbose=False):
        """Simulate PDA (BFS, returns acceptance and trace)."""
        from collections import deque
        
        initial = (self.q0, 0, (self.Z0,))
        queue = deque([(initial, [])])
        visited = set()
        
        while queue:
            (state, idx, stack), path = queue.popleft()
            
            if (state, idx, stack) in visited:
                continue
            visited.add((state, idx, stack))
            
            # Accept?
            if idx == len(input_string) and (state in self.F or len(stack) == 0):
                return True, path
            
            if stack:
                top = stack[0]
                
                # Epsilon transitions
                for (ns, push) in self.delta.get((state, 'ε', top), []):
                    new_stack = tuple(push) + stack[1:]
                    queue.append(((ns, idx, new_stack), 
                                  path + [(state, 'ε', top, ns, push)]))
                
                # Input transitions
                if idx < len(input_string):
                    symbol = input_string[idx]
                    for (ns, push) in self.delta.get((state, symbol, top), []):
                        new_stack = tuple(push) + stack[1:]
                        queue.append(((ns, idx + 1, new_stack),
                                      path + [(state, symbol, top, ns, push)]))
        
        return False, []
    
    def print_trace(self, input_string):
        """Print detailed trace."""
        accepted, path = self.simulate(input_string)
        
        print(f"\nInput: '{input_string}'")
        print(f"Result: {'ACCEPT ✓' if accepted else 'REJECT ✗'}")
        
        if path:
            # Reconstruct stack states
            stack = [self.Z0]
            state = self.q0
            print(f"\n{'Step':<6} {'State':<8} {'Read':<6} {'Top':<6} {'Next':<8} {'Push':<10} {'Stack':<20}")
            print("-" * 70)
            
            print(f"{'0':<6} {state:<8} {'—':<6} {'—':<6} {'—':<8} {'—':<10} {str(stack):<20}")
            
            for i, (q, sym, top, ns, push) in enumerate(path):
                # Update stack
                stack = stack[1:]  # pop
                stack = list(push) + stack  # push
                state = ns
                push_str = ''.join(push) if push else 'ε'
                read_str = sym if sym != 'ε' else 'ε'
                stack_str = '[' + ' '.join(stack) + ']' if stack else '[ ]'
                print(f"{i+1:<6} {ns:<8} {read_str:<6} {top:<6} {'—':<8} {push_str:<10} {stack_str:<20}")
        else:
            print("No accepting path found.")


# Example: a^n b^n
pda = PDASimulator(
    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'}
)

pda.print_trace('aabb')
pda.print_trace('aaabbb')
pda.print_trace('aab')

# STACK LIMITATIONS
print("""
=== Stack Limitations ===

The stack gives ONE counter. This means:

✓ CAN DO:
  - Match a's with b's
  - Check balanced parentheses
  - Palindromes
  - One comparison

✗ CANNOT DO:
  - a^n b^n c^n (two counters)
  - ww (copying)
  - a^n b^n c^n d^n
  - Multiple independent counts

=== Why Two Counters Fail ===

To recognize a^n b^n c^n, we need to:
  1. Count a's (push)
  2. Match b's (pop)
  3. Match c's with... nothing!

After step 2, the stack is empty.
There's no memory left for c's.

You'd need TWO stacks (or more) to do this.
A two-stack PDA is equivalent to a Turing machine!

=== Interesting Fact ===

1-stack PDA = CFG (context-free)
2-stack PDA = TM (Turing machine)
""")

🔄 Transition Function

🎯 The Heart of the PDA

The transition function δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*) defines how the PDA moves. It reads the current state, input symbol (or ε), and stack top, and produces a set of possible next moves.

Transition Types

Read input: Consumes a symbol. ε-transition: No input consumed. Push: Add to stack. Pop: Remove from stack. Replace: Pop then push. Nondeterminism: Multiple choices.

📖 Readε No input⬆️ Push⬇️ Pop

# Transition Function in detail
print("=" * 60)
print("TRANSITION FUNCTION δ")
print("=" * 60)

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

δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)

Inputs:
  q ∈ Q         current state
  a ∈ Σ ∪ {ε}   input symbol (or ε)
  Z ∈ Γ         top of stack

Output:
  A SET of pairs (q', γ) where:
    q' ∈ Q      next state
    γ ∈ Γ*      string to replace Z with

=== Reading a Transition ===

  δ(q, a, Z) = (q', γ)

Means:
  "In state q, reading 'a', with Z on top:
   go to state q', pop Z, push γ"

=== Special Cases ===

1. δ(q, a, Z) = (q', ε)
   Pop Z, push nothing. Stack shrinks.

2. δ(q, a, Z) = (q', Z)
   Pop Z, push Z back. No stack change.

3. δ(q, a, Z) = (q', AB)
   Pop Z, push A then B.
   A is on top of B in new stack.

4. δ(q, ε, Z) = (q', γ)
   ε-transition: no input consumed.
""")

# TRANSITION TYPES WITH EXAMPLES
print("=== Transition Types with Examples ===")

examples = [
    ("Push", "δ(q0, 'a', Z) = (q0, AZ)", 
     "Read 'a', push A on top of Z"),
    ("Pop", "δ(q0, 'b', A) = (q1, ε)",
     "Read 'b', pop A"),
    ("Replace", "δ(q0, 'a', Z) = (q1, A)",
     "Read 'a', replace Z with A"),
    ("No change", "δ(q0, 'a', Z) = (q0, Z)",
     "Read 'a', stack unchanged"),
    ("ε-move", "δ(q0, ε, Z) = (q1, Z)",
     "No input, change state only"),
    ("Push two", "δ(q0, 'a', Z) = (q0, ABZ)",
     "Read 'a', push A and B"),
    ("Push three", "δ(q0, 'a', Z) = (q0, ABCZ)",
     "Read 'a', push A, B, C (A on top)"),
    ("Nondeterministic", "δ(q0, 'a', Z) = {(q1, AZ), (q2, ε)}",
     "Two choices: push or pop"),
]

print(f"{'Type':<15} {'Transition':<40} {'Meaning':<30}")
print("-" * 85)
for name, trans, meaning in examples:
    print(f"{name:<15} {trans:<40} {meaning:<30}")

# TRANSITION FUNCTION IN CODE
print("\n=== Transition Function in Code ===")

class PDA:
    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 get_transitions(self, state, symbol, stack_top):
        """Get all transitions for a configuration."""
        return self.delta.get((state, symbol, stack_top), [])
    
    def step(self, state, remaining, stack):
        """Compute all next configurations."""
        results = []
        
        if not stack:
            return results
        
        top = stack[0]
        
        # Epsilon transitions
        for (ns, push) in self.get_transitions(state, 'ε', top):
            new_stack = tuple(push) + stack[1:]
            results.append((ns, remaining, new_stack))
        
        # Input transitions
        if remaining:
            symbol = remaining[0]
            for (ns, push) in self.get_transitions(state, symbol, top):
                new_stack = tuple(push) + stack[1:]
                results.append((ns, remaining[1:], new_stack))
        
        return results


# Example: a^n b^n
pda = 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("Transition table for a^n b^n:")
print(f"{'State':<8} {'Input':<8} {'Stack':<8} {'→ Next':<10} {'Push':<10}")
print("-" * 50)
for (q, a, Z), results in sorted(pda.delta.items()):
    for (nq, push) in results:
        push_str = ''.join(push) if push else 'ε'
        print(f"{q:<8} {a:<8} {Z:<8} {nq:<10} {push_str:<10}")

# NONDETERMINISM
print("""
=== Nondeterminism in PDAs ===

A PDA is NONDETERMINISTIC if:
  |δ(q, a, Z)| > 1 for some (q, a, Z)

Or if it has ε-transitions.

=== Why Nondeterminism Matters ===

Nondeterministic PDAs accept all CFLs.
Deterministic PDAs accept only DCFLs (a strict subset).

Example: PALINDROMES
  L = { w | w = w^R }
  
  Nondeterministic PDA:
    - Push symbols
    - Nondeterministically guess the middle
    - Pop and match
    
  Deterministic PDA: IMPOSSIBLE
    - Can't know when middle is reached
    - Needs to "guess"

=== Example: Nondeterministic Transition ===

δ(q0, 'a', Z) = {(q0, AZ), (q1, Z)}
  Choice 1: push A (continue building)
  Choice 2: go to q1 (start matching)

The PDA explores BOTH possibilities.
Accepts if ANY path accepts.
""")

# EPSILON TRANSITIONS
print("""
=== ε-Transitions ===

ε-transitions consume no input:
  δ(q, ε, Z) = (q', γ)

Uses:
  1. State change without consuming input
  2. Stack manipulation without reading
  3. Model nondeterministic choices
  4. Convert CFG to PDA

Example: CFG to PDA uses ε-transitions:
  For rule A → α:
    δ(q, ε, A) = (q, α^R)

This expands A without consuming input!

=== Important ===

ε-transitions can cause infinite loops:
  δ(q, ε, Z) = (q, Z)  ← loops forever!

In practice:
  - BFS simulation avoids infinite loops
  - Track visited configurations
  - Or design PDAs without such loops
""")

# TRANSITION DESIGN PATTERNS
print("=== Common Transition Patterns ===")
print("""
1. PUSH FOR MATCHING
   δ(q, 'a', Z) = (q, AZ)
   δ(q, 'a', A) = (q, AA)
   Push A for each 'a'.

2. POP FOR MATCHING
   δ(q, 'b', A) = (q, ε)
   Pop A for each 'b'.

3. SWITCH STATE
   δ(q0, 'b', A) = (q1, ε)
   Change state when transitioning.

4. GUESS MIDDLE
   δ(q, ε, A) = (q', A)
   ε-transition to nondeterministically guess.

5. ACCEPT CONDITION
   δ(q, ε, Z) = (qf, Z)
   Move to accept state at end.

6. PUSH BOTTOM MARKER
   δ(q0, ε, Z) = (q0, Z0Z)
   Use special bottom marker.

7. MULTIPLE PUSH
   δ(q, 'a', Z) = (q, ABZ)
   Push multiple symbols at once.
""")

# TRANSITION COMPOSITION
print("""
=== Composing Transitions ===

Complex PDAs are built from simple transitions.

For a^n b^n:
  1. δ(q0, a, Z) = (q0, AZ)   — first a, push A
  2. δ(q0, a, A) = (q0, AA)   — more a's, push A
  3. δ(q0, b, A) = (q1, ε)    — first b, pop A, switch
  4. δ(q1, b, A) = (q1, ε)    — more b's, pop A
  5. δ(q1, ε, Z) = (q2, Z)    — end, accept

The sequence of transitions implements the algorithm:
  Push a's → Pop b's → Accept

This is how all PDAs are designed:
  - Break the language into phases
  - Design transitions for each phase
  - Connect phases with state changes
""")

✅ Acceptance Modes

🎯 Two Ways to Accept

PDAs can accept strings in two ways: by final state (ending in an accept state) or by empty stack (stack completely emptied). The two modes are equivalent in power.

Acceptance Modes

Final state: (q₀,w,Z₀) ⊢* (q,ε,γ), q ∈ F. Empty stack: (q₀,w,Z₀) ⊢* (q,ε,ε). Equivalence: Both accept exactly CFLs. Conversion: Can convert between modes. Standard: Final state is default. Practical: Empty stack is simpler.

🎯 Final state📭 Empty stack↔️ Equivalent🔄 Convertible

# Acceptance Modes
print("=" * 60)
print("ACCEPTANCE MODES")
print("=" * 60)

print("""
=== Two Acceptance Modes ===

1. ACCEPT BY FINAL STATE
   L(M) = { w | (q₀, w, Z₀) ⊢* (q, ε, γ) for some q ∈ F }
   
   - Input must be consumed
   - End in an accept state
   - Stack contents irrelevant

2. ACCEPT BY EMPTY STACK
   N(M) = { w | (q₀, w, Z₀) ⊢* (q, ε, ε) for some q ∈ Q }
   
   - Input must be consumed
   - Stack must be completely empty
   - State irrelevant

=== Theorem ===

For every PDA M1 (final state), there exists a PDA M2
(empty stack) such that L(M1) = N(M2), and vice versa.

Therefore, the two modes are EQUIVALENT.
""")

# FINAL STATE PDA
print("=== Example: Final State 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 move

Acceptance: end in q2 with input consumed.
Stack still has Z at the end.

Trace for "ab":
  (q0, ab, Z) ⊢ (q0, b, AZ)
              ⊢ (q1, ε, Z)
              ⊢ (q2, ε, Z)
  
  q2 ∈ F ✓ ACCEPT
""")

# EMPTY STACK PDA
print("=== Example: Empty Stack PDA for a^n b^n ===")
print("""
States: {q0, q1}
Input:  {a, b}
Stack:  {Z, A}
Start:  q0, Z
Accept: (empty stack — no F needed)

Transitions:
  δ(q0, a, Z) = (q0, AZ)    push A
  δ(q0, a, A) = (q0, AA)    push A
  δ(q0, b, A) = (q1, ε)     pop A
  δ(q1, b, A) = (q1, ε)     pop A
  δ(q1, ε, Z) = (q1, ε)     pop Z (empty stack!)

Acceptance: stack is empty.
No need for accept states.

Trace for "ab":
  (q0, ab, Z) ⊢ (q0, b, AZ)
              ⊢ (q1, ε, Z)
              ⊢ (q1, ε, ε)
  
  Stack empty ✓ ACCEPT
""")

# CONVERSION BETWEEN MODES
print("=== Converting Between Acceptance Modes ===")
print("""
FINAL STATE → EMPTY STACK:

Given M1 = (Q, Σ, Γ, δ, q0, Z0, F), construct M2:

  M2 = (Q ∪ {q0', qe}, Σ, Γ ∪ {X0}, δ', q0', X0, ∅)

  where:
    - q0' is a new start state
    - qe is a new "erase" state
    - X0 is a new bottom marker

  Transitions:
    1. δ'(q0', ε, X0) = (q0, Z0 X0)    [initialize]
    2. δ'(q, a, Z) = δ(q, a, Z)         [copy M1]
    3. For each q ∈ F: δ'(q, ε, Z) = (qe, Z)  [enter erase]
    4. For each Z ∈ Γ: δ'(qe, ε, Z) = (qe, ε)  [erase stack]
    5. δ'(qe, ε, X0) = (qe, ε)           [erase bottom]

Now M2 accepts by empty stack.
""")

# CONVERSION IN CODE
print("=== Converting Final State to Empty Stack ===")

def convert_to_empty_stack(pda):
    """Convert a final-state PDA to an empty-stack PDA."""
    new_q0 = 'q0_init'
    new_qe = 'q_erase'
    new_X0 = 'X0'
    
    new_Q = pda.Q | {new_q0, new_qe}
    new_Gamma = pda.Gamma | {new_X0}
    new_delta = {}
    
    # Copy original transitions
    for key, results in pda.delta.items():
        new_delta[key] = list(results)
    
    # 1. Initialize
    new_delta[(new_q0, 'ε', new_X0)] = [(pda.q0, (pda.Z0, new_X0))]
    
    # 3. From accept states, go to erase state
    for q in pda.F:
        for Z in pda.Gamma:
            key = (q, 'ε', Z)
            if key not in new_delta:
                new_delta[key] = []
            new_delta[key].append((new_qe, (Z,)))
    
    # 4. Erase stack
    for Z in new_Gamma:
        key = (new_qe, 'ε', Z)
        new_delta[key] = [(new_qe, ())]
    
    return PDA(
        states=new_Q,
        input_alphabet=pda.Sigma,
        stack_alphabet=new_Gamma,
        transitions=new_delta,
        start_state=new_q0,
        start_stack=new_X0,
        accept_states=frozenset()  # empty stack acceptance
    )


# Convert example
original = 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'}
)

converted = convert_to_empty_stack(original)

print("Original PDA (final state):")
print(f"  States: {original.Q}")
print(f"  Accept: {original.F}")

print("\nConverted PDA (empty stack):")
print(f"  States: {converted.Q}")
print(f"  Start: {converted.q0}")
print(f"  Start stack: {converted.Z0}")
print(f"  Accept: (empty stack)")

print("\nNew transitions:")
for (q, a, Z), results in sorted(converted.delta.items()):
    for (nq, push) in results:
        push_str = ''.join(push) if push else 'ε'
        print(f"  δ({q}, {a}, {Z}) = ({nq}, {push_str})")

# EMPTY STACK → FINAL STATE
print("""
=== Converting Empty Stack to Final State ===

Given M1 = (Q, Σ, Γ, δ, q0, Z0, ∅), construct M2:

  M2 = (Q ∪ {q0', qf}, Σ, Γ ∪ {X0}, δ', q0', X0, {qf})

  Transitions:
    1. δ'(q0', ε, X0) = (q0, Z0 X0)
    2. δ'(q, a, Z) = δ(q, a, Z)  for all original
    3. For each q: δ'(q, ε, X0) = (qf, X0)

Now M2 accepts by final state.

The idea:
  - Use new bottom marker X0
  - When stack is about to be empty, go to qf
  - qf is the only accept state
""")

# ACCEPTANCE COMPARISON
print("=== Comparison of Acceptance Modes ===")
print(f"{'Aspect':<30} {'Final State':<25} {'Empty Stack':<25}")
print("-" * 80)
print(f"{'Accept condition':<30} {'End in F':<25} {'Stack empty':<25}")
print(f"{'Accept states':<30} {'Required':<25} {'Not needed':<25}")
print(f"{'Stack at end':<30} {'Any':<25} {'Empty':<25}")
print(f"{'Design simplicity':<30} {'More states':<25} {'Simpler':<25}")
print(f"{'Conversion':<30} {'Possible':<25} {'Possible':<25}")
print(f"{'Standard?':<30} {'Yes':<25} {'Sometimes':<25}")
print(f"{'Used in':<30} {'Textbooks':<25} {'CFG→PDA':<25}")

# PRACTICAL CHOICE
print("""
=== Which Mode to Use? ===

FINAL STATE:
  ✓ More intuitive
  ✓ Standard definition
  ✓ Easier to specify accept states
  ✓ Closer to DFA/NFA
  ✓ Used in most textbooks

EMPTY STACK:
  ✓ Simpler construction (CFG → PDA)
  ✓ No need for accept states
  ✓ Natural for some proofs
  ✓ Easier to convert to CFG

In practice:
  - Use final state for design
  - Use empty stack for constructions
  - Convert as needed
""")

# ACCEPTANCE EXAMPLES
print("=== Acceptance Examples ===")
print("""
Test string "aabb" on both PDAs:

FINAL STATE PDA:
  (q0, aabb, Z) ⊢ (q0, abb, AZ)
                ⊢ (q0, bb, AAZ)
                ⊢ (q1, b, AZ)
                ⊢ (q1, ε, Z)
                ⊢ (q2, ε, Z)
  q2 ∈ F → ACCEPT ✓

EMPTY STACK PDA:
  (q0, aabb, Z) ⊢ (q0, abb, AZ)
                ⊢ (q0, bb, AAZ)
                ⊢ (q0, b, AZ)   [wait, need q1]
  
  Actually:
  (q0, aabb, Z) ⊢ (q0, abb, AZ)
                ⊢ (q0, bb, AAZ)
                ⊢ (q1, b, AZ)
                ⊢ (q1, ε, Z)
                ⊢ (q1, ε, ε)
  Stack empty → ACCEPT ✓
""")

⚙️ Deterministic PDAs

🎯 When There's No Choice

A Deterministic Pushdown Automaton (DPDA) has at most one transition for each configuration. DPDAs are weaker than nondeterministic PDAs — they accept the deterministic context-free languages (DCFLs).

DPDA Properties

At most one move: |δ(q,a,Z)| ≤ 1. No ε-conflicts: Can't have both ε and input move. Weaker: Strict subset of CFLs. DCFL: Deterministic CFLs. Parsing: LR(k) grammars. Practical: Most programming languages.

1️⃣ At most one🚫 No ε-conflict📉 Weaker💻 LR parsing

# Deterministic PDAs
print("=" * 60)
print("DETERMINISTIC PDAs")
print("=" * 60)

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

A PDA is DETERMINISTIC if:

1. For every (q, a, Z) with a ∈ Σ:
   |δ(q, a, Z)| ≤ 1

2. For every (q, ε, Z):
   |δ(q, ε, Z)| ≤ 1
   AND if δ(q, ε, Z) ≠ ∅, then δ(q, a, Z) = ∅ for all a ∈ Σ.

In words: at most one transition per configuration,
and no conflict between ε and input transitions.

=== Why "Deterministic"? ===

Given the current configuration (q, w, γ),
there's at most ONE possible next configuration.

No guessing, no backtracking — just follow the path.

=== DCFL ===

Languages accepted by DPDAs are called
DETERMINISTIC CONTEXT-FREE LANGUAGES (DCFLs).

DCFL ⊊ CFL (strict subset)

There are CFLs that no DPDA can recognize!
""")

# DPDA EXAMPLES
print("=== Example: DPDA 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)    [only one choice]
  δ(q0, a, A) = (q0, AA)    [only one choice]
  δ(q0, b, A) = (q1, ε)     [only one choice]
  δ(q1, b, A) = (q1, ε)     [only one choice]
  δ(q1, ε, Z) = (q2, Z)     [only one choice]

This is deterministic!
No configuration has multiple choices.
""")

# NON-DETERMINISTIC EXAMPLE
print("=== Example: NPDA for Palindromes ===")
print("""
L = { w | w = w^R } over {a, b}

A DPDA CANNOT recognize this!

Why? To recognize palindromes, the PDA must
"guess" the middle of the string.

Nondeterministic PDA:
  δ(q0, 'a', Z) = {(q0, AZ), (q1, Z)}
    Choice 1: push A (not at middle yet)
    Choice 2: go to q1 (middle found)
  
  δ(q0, 'b', Z) = {(q0, BZ), (q1, Z)}
    Similar

The PDA guesses when the middle is reached.
Deterministic PDA can't guess!

=== The Key Insight ===

Nondeterminism adds POWER to PDAs.
  PDA (nondeterministic) = all CFLs
  DPDA (deterministic)   = DCFLs ⊊ CFLs

This is different from finite automata!
  DFA = NFA (same power)
  DPDA ⊊ PDA (different power)
""")

# DPDA IN CODE
print("=== DPDA Simulator ===")

class DPDA:
    """Deterministic Pushdown Automaton."""
    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  # (q, a, Z) -> (q', push) or None
        self.q0 = start_state
        self.Z0 = start_stack
        self.F = accept_states
    
    def is_deterministic(self):
        """Check if this PDA is deterministic."""
        # Check no multiple transitions
        for key, val in self.delta.items():
            if isinstance(val, list) and len(val) > 1:
                return False
        
        # Check no ε/input conflict
        for (q, a, Z) in self.delta:
            if a == 'ε':
                for symbol in self.Sigma:
                    if (q, symbol, Z) in self.delta:
                        return False
        
        return True
    
    def accepts(self, input_string, max_steps=10000):
        """Simulate DPDA (deterministic)."""
        state = self.q0
        idx = 0
        stack = (self.Z0,)
        trace = [(state, idx, stack)]
        
        for _ in range(max_steps):
            # Accept?
            if idx == len(input_string):
                if state in self.F or len(stack) == 0:
                    return True, trace
            
            if not stack:
                # Empty stack — accept if input consumed
                if idx == len(input_string):
                    return True, trace
                return False, trace
            
            top = stack[0]
            
            # Try ε-transition first (if deterministic, only one type)
            if (state, 'ε', top) in self.delta:
                next_state, push = self.delta[(state, 'ε', top)]
                stack = tuple(push) + stack[1:]
                state = next_state
                trace.append((state, idx, stack))
                continue
            
            # Try input transition
            if idx < len(input_string):
                symbol = input_string[idx]
                if (state, symbol, top) in self.delta:
                    next_state, push = self.delta[(state, symbol, top)]
                    stack = tuple(push) + stack[1:]
                    state = next_state
                    idx += 1
                    trace.append((state, idx, stack))
                    continue
            
            # No transition — stuck
            return False, trace
        
        return False, trace


# Example DPDA
dpda = DPDA(
    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(f"Is deterministic: {dpda.is_deterministic()}")
print("\nTesting a^n b^n:")
for s in ['', 'ab', 'aabb', 'aaabbb', 'aab', 'abb']:
    accepted, trace = dpda.accepts(s)
    print(f"  '{s}' → {'✓' if accepted else '✗'}")

# DCFL VS CFL
print("""
=== DCFL vs CFL ===

DCFL ⊊ CFL

Examples of DCFLs:
  ✓ a^n b^n
  ✓ Balanced parentheses
  ✓ Arithmetic expressions
  ✓ Most programming languages

Examples of CFLs that are NOT DCFLs:
  ✗ Palindromes: w = w^R
  ✗ ww^R
  ✗ { a^i b^j c^k | i = j or j = k }
  ✗ Any language requiring "guessing"

=== Closure Properties ===

DCFLs are:
  ✓ Closed under complement
  ✗ NOT closed under union
  ✗ NOT closed under intersection
  ✓ Closed under ∩ regular

CFLs are:
  ✗ NOT closed under complement
  ✓ Closed under union
  ✗ NOT closed under intersection
  ✓ Closed under ∩ regular
""")

# PARSING CONNECTION
print("""
=== Connection to Parsing ===

DCFLs are exactly the languages parsed by LR(k) parsers!

  DPDA ⟺ LR(1) grammar
  DPDA ⟺ DCFG (deterministic CFG)

Programming languages:
  - Designed to be DCFLs
  - Parsed by LR parsers (Yacc, Bison)
  - Or LL parsers (ANTLR, recursive descent)

This is why compilers work:
  - Programming languages are deterministic
  - Can be parsed in O(n) time
  - No backtracking needed

=== LR Parsing ===

LR(k) parser = DPDA with:
  - States from item sets
  - Stack holds states + grammar symbols
  - Actions: shift, reduce, accept, error

This is the practical realization of a DPDA.
""")

# SUMMARY
print("=== Summary ===")
print(f"{'Aspect':<30} {'DPDA':<25} {'NPDA':<25}")
print("-" * 80)
print(f"{'Transitions':<30} {'≤ 1 per config':<25} {'Any number':<25}")
print(f"{'ε-conflicts':<30} {'Not allowed':<25} {'Allowed':<25}")
print(f"{'Power':<30} {'DCFL':<25} {'CFL':<25}")
print(f"{'Example':<30} {'a^n b^n':<25} {'Palindromes':<25}")
print(f"{'Parsing':<30} {'LR(k)':<25} {'CYK, Earley':<25}")
print(f"{'Practical':<30} {'Compilers':<25} {'NLP':<25}")
print(f"{'Closure ∪':<30} {'No':<25} {'Yes':<25}")
print(f"{'Closure complement':<30} {'Yes':<25} {'No':<25}")

🎨 Designing PDAs

🎯 Building PDAs for Languages

Designing PDAs is a skill. You need to identify what the stack should remember and design transitions that implement the recognition algorithm.

Design Methodology

1. Understand: What language? 2. Stack strategy: What to push/pop? 3. Phases: Break into stages. 4. States: One per phase. 5. Transitions: Push/pop/switch. 6. Accept: When to stop. 7. Test: Verify with examples.

🎯 Understand📚 Stack plan🔄 Phases✅ Test

# Designing PDAs
print("=" * 60)
print("DESIGNING PDAs")
print("=" * 60)

print("""
=== Design Template ===

Step 1: WHAT is the language?
  - Describe in words
  - Identify the pattern
  - Consider edge cases

Step 2: WHAT should the stack remember?
  - What needs to be counted?
  - What needs to be matched?
  - What's the "state of knowledge"?

Step 3: HOW to break into phases?
  - Phase 1: Push / build up
  - Phase 2: Pop / match
  - Phase 3: Accept / clean up

Step 4: HOW MANY states?
  - Usually one per phase
  - Plus accept state(s)

Step 5: TRANSITIONS?
  - For each (state, input, stack) → next
  - Push on one symbol, pop on another

Step 6: ACCEPT?
  - Final state or empty stack

Step 7: TEST
  - Positive and negative examples
""")

# EXAMPLE 1: a^n b^n
print("=== Example 1: a^n b^n ===")
print("""
Step 1: L = { a^n b^n | n ≥ 0 }

Step 2: Stack strategy
  - Push A for each 'a'
  - Pop A for each 'b'
  - Match ensures equal counts

Step 3: Phases
  - Phase 1: Read a's, push A
  - Phase 2: Read b's, pop A
  - Phase 3: Accept

Step 4: States
  - q0: reading a's
  - q1: reading b's
  - q2: accept

Step 5: Transitions
  δ(q0, a, Z) = (q0, AZ)    push A
  δ(q0, a, A) = (q0, AA)    push A
  δ(q0, b, A) = (q1, ε)     pop A, switch
  δ(q1, b, A) = (q1, ε)     pop A
  δ(q1, ε, Z) = (q2, Z)     accept

Step 6: Accept = {q2}

Step 7: Test
  'aabb' → push, push, pop, pop → accept ✓
  'aab'  → push, push, pop → stack has A → reject ✓
  'abb'  → push, pop, pop from empty → reject ✓
""")

# EXAMPLE 2: BALANCED PARENTHESES
print("=== Example 2: Balanced Parentheses ===")
print("""
Step 1: L = { w | w has balanced ( and ) }

Step 2: Stack strategy
  - Push '(' for each '('
  - Pop '(' for each ')'
  - Stack empty at end = balanced

Step 3: Phases
  - Single phase (always matching)

Step 4: States
  - q0: reading input
  - q1: accept

Step 5: Transitions
  δ(q0, '(', Z) = (q0, (Z)      push (
  δ(q0, '(', () = (q0, (()      push (
  δ(q0, ')', () = (q0, ε)       pop (
  δ(q0, ε, Z) = (q1, Z)         accept

Step 6: Accept = {q1}

Step 7: Test
  '()' → push, pop → accept ✓
  '(())' → push, push, pop, pop → accept ✓
  '(()' → push, push, pop → stack has ( → reject ✓
  ')(' → pop from empty → reject ✓
""")

# EXAMPLE 3: PALINDROMES
print("=== Example 3: Palindromes (w = w^R) ===")
print("""
Step 1: L = { w | w = w^R } over {a, b}

Step 2: Stack strategy
  - Push first half
  - Guess middle
  - Pop and match second half

Step 3: Phases
  - Phase 1: Push (first half)
  - Phase 2: Guess middle (nondeterministic!)
  - Phase 3: Pop and match (second half)

Step 4: States
  - q0: pushing
  - q1: matching (after middle)
  - q2: accept

Step 5: Transitions
  δ(q0, 'a', Z) = (q0, AZ)    push a
  δ(q0, 'a', A) = (q0, AA)    push a
  δ(q0, 'b', Z) = (q0, BZ)    push b
  δ(q0, 'b', B) = (q0, BB)    push b

  Guess middle:
  δ(q0, ε, Z) = (q1, Z)       middle (even length)
  δ(q0, ε, A) = (q1, A)       middle (odd, skip middle)
  δ(q0, ε, B) = (q1, B)       middle (odd, skip middle)

  Matching:
  δ(q1, 'a', A) = (q1, ε)     match a
  δ(q1, 'b', B) = (q1, ε)     match b

  Accept:
  δ(q1, ε, Z) = (q2, Z)

Step 6: Accept = {q2}

Step 7: Test
  'aba' → push a, push b, guess odd, pop b, pop a → accept ✓
  'abba' → push a, push b, guess even, pop b, pop a → accept ✓
  'ab' → push a, push b, guess even, pop b (matches? no, need 'a')
        → reject ✓
""")

# EXAMPLE 4: EQUAL A'S AND B'S
print("=== Example 4: Equal a's and b's (any order) ===")
print("""
Step 1: L = { w | #a(w) = #b(w) }

Step 2: Stack strategy
  - Nondeterministic choice:
    * Push A for 'a', pop A for 'b'
    * OR push B for 'b', pop B for 'a'
  - Accept if stack empty

Step 3: Phases
  - Single phase, but nondeterministic

Step 4: States
  - q0: reading
  - q1: accept

Step 5: Transitions
  # Option 1: push a, pop b
  δ(q0, 'a', Z) = {(q0, AZ), (q0, BZ)}  # choose!
  δ(q0, 'a', A) = {(q0, AA), (q0, ε)}   # push or pop
  δ(q0, 'a', B) = {(q0, AB), (q0, ε)}   # push or pop
  δ(q0, 'b', Z) = {(q0, AZ), (q0, BZ)}
  δ(q0, 'b', A) = {(q0, BA), (q0, ε)}
  δ(q0, 'b', B) = {(q0, BB), (q0, ε)}
  δ(q0, ε, Z) = (q1, Z)  # accept empty stack

Step 6: Accept = {q1}

Step 7: Test
  'ab' → push A, pop A → accept ✓
  'ba' → push B, pop B → accept ✓
  'aabb' → push A, push A, pop A, pop A → accept ✓
  'aab' → push A, push A, pop A → stack has A → reject ✓
""")

# EXAMPLE 5: a^i b^j, i > j
print("=== Example 5: a^i b^j with i > j ===")
print("""
Step 1: L = { a^i b^j | i > j ≥ 0 }

Step 2: Stack strategy
  - Push A for each 'a'
  - Pop A for each 'b'
  - Accept if stack still has A's (i > j)

Step 3: Phases
  - Phase 1: Read a's, push
  - Phase 2: Read b's, pop
  - Phase 3: Accept if stack has A

Step 4: States
  - q0: reading a's
  - q1: reading b's
  - q2: accept

Step 5: Transitions
  δ(q0, a, Z) = (q0, AZ)
  δ(q0, a, A) = (q0, AA)
  δ(q0, b, A) = (q1, ε)     switch to b's
  δ(q1, b, A) = (q1, ε)     pop more
  δ(q1, ε, A) = (q2, A)     accept if A's left

Step 6: Accept = {q2}

Step 7: Test
  'aab' → push A, push A, pop A, stack has A → accept ✓
  'abb' → push A, pop A, then pop from empty → reject ✓
  'a'   → push A, stack has A → accept ✓
""")

# DESIGN PATTERNS
print("=== Common Design Patterns ===")
print("""
1. MATCHING PAIRS
   Push for opening, pop for closing.
   Example: a^n b^n, parentheses.

2. COUNTING COMPARISON
   Push for one symbol, pop for another.
   Accept based on stack state.
   Example: i > j, i < j, i = j.

3. GUESSING MIDDLE
   Use nondeterministic ε-transition.
   Example: palindromes, ww^R.

4. MULTIPLE CHOICES
   Nondeterministically push A or B.
   Example: equal a's and b's (any order).

5. PHASE TRANSITIONS
   State change marks phase boundary.
   Example: a^n b^n, a^i b^j.

6. STACK MARKERS
   Use special symbols for tracking.
   Example: bottom marker Z, phase markers.
""")

# SYSTEMATIC CODE
print("=== Systematic Design in Code ===")

def design_pda_matching(symbols_open, symbols_close):
    """
    Design PDA for matching pairs.
    Example: a^n b^n uses open='a', close='b'
    """
    return f"""
PDA for matching {symbols_open} with {symbols_close}:

States: q0 (reading {symbols_open}), q1 (reading {symbols_close}), q2 (accept)
Stack: Z, A

Transitions:
  δ(q0, {symbols_open}, Z) = (q0, AZ)
  δ(q0, {symbols_open}, A) = (q0, AA)
  δ(q0, {symbols_close}, A) = (q1, ε)
  δ(q1, {symbols_close}, A) = (q1, ε)
  δ(q1, ε, Z) = (q2, Z)

Accept: {{q2}}
"""

print(design_pda_matching('a', 'b'))
print(design_pda_matching('(', ')'))

📗 CFG ↔ PDA

🎯 The Fundamental Equivalence

Context-free grammars and pushdown automata are equivalent: every CFG has a corresponding PDA and vice versa. This is the CFG analog of the DFA/regex equivalence.

Equivalence Theorem

CFG → PDA: Nondeterministic PDA (empty stack). PDA → CFG: Construct grammar from PDA. Both directions: Constructive proofs. Same power: Both recognize CFLs. Key insight: Stack simulates derivation.

📗 CFG🤖 PDA↔️ Equivalent🔨 Constructive

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

print("""
=== Theorem ===

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

=== Proof Strategy ===

(⟹) CFG → PDA:
  Construct a PDA that simulates leftmost derivations.
  
(⟸) PDA → CFG:
  Construct a grammar where nonterminals represent
  "from state p with stack A, go to state q".

Both constructions are constructive.
""")

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

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

Transitions:
1. START: δ(q0, ε, Z) = (q1, S Z)
   Push start symbol S.

2. EXPAND: For each rule A → α in R:
   δ(q1, ε, A) = (q1, α^R)
   Push RHS in reverse (so leftmost is on top).

3. MATCH: For each terminal a ∈ Σ:
   δ(q1, a, a) = (q1, ε)
   Match input with top of stack.

4. ACCEPT: δ(q1, ε, Z) = (q1, ε)
   Empty the stack to accept.

=== Key Idea ===

The PDA simulates a LEFTMOST derivation:
  - Stack holds the current sentential form
  - Top of stack = leftmost symbol
  - Nonterminal → expand (nondeterministic)
  - Terminal → match with input

=== Example ===

Grammar: S → aSb | ε

PDA transitions:
  δ(q0, ε, Z) = (q1, SZ)
  δ(q1, ε, S) = (q1, bSa)    [S → aSb, reversed]
  δ(q1, ε, S) = (q1, ε)      [S → ε]
  δ(q1, a, a) = (q1, ε)
  δ(q1, b, b) = (q1, ε)
  δ(q1, ε, Z) = (q1, ε)
""")

# CFG TO PDA IN CODE
print("=== CFG to PDA in Code ===")

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)


class PDA:
    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 __repr__(self):
        lines = [f"PDA:"]
        lines.append(f"  States: {sorted(self.Q)}")
        lines.append(f"  Input:  {sorted(self.Sigma)}")
        lines.append(f"  Stack:  {sorted(self.Gamma)}")
        lines.append(f"  Start:  {self.q0}, {self.Z0}")
        lines.append(f"  Accept: {sorted(self.F)}")
        lines.append(f"  Transitions:")
        for (q, a, Z), results in sorted(self.delta.items()):
            for (nq, push) in results:
                push_str = ''.join(push) if push else 'ε'
                lines.append(f"    δ({q}, {a}, {Z}) = ({nq}, {push_str})")
        return '\n'.join(lines)


def cfg_to_pda(cfg):
    """Convert CFG to PDA (accept by empty stack)."""
    q0, q1 = 'q0', 'q1'
    Z = 'Z'
    
    states = {q0, q1}
    stack_alphabet = set(cfg.rules.keys()) | {Z}
    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
    for lhs, prods in cfg.rules.items():
        for rhs in prods:
            key = (q1, 'ε', lhs)
            if key not in transitions:
                transitions[key] = []
            # Push reversed RHS
            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
anbn_cfg = CFG('S', {
    'S': [('a', 'S', 'b'), ()],
})

print("CFG:")
print(anbn_cfg)

pda = cfg_to_pda(anbn_cfg)
print("\nConverted PDA:")
print(pda)

# PDA TO CFG
print("""
=== PDA → CFG Construction ===

Given PDA M = (Q, Σ, Γ, δ, q0, Z0, F), construct CFG G:

Nonterminals: [p, A, q] for all p, q ∈ Q, A ∈ Γ
  Meaning: "from state p with A on top of stack,
            go to state q with A popped"

Start symbol: [q0, Z0, qf] for some qf ∈ F
  (Or for all qf ∈ F, use a new start symbol)

Rules:
1. For each state q: [q, A, q] → ε
   (Pop A and return to same state — no net change)

2. For transition δ(p, a, A) ∋ (r, B1 B2 ... Bk):
   For all states q1, q2, ..., qk:
     [p, A, qk] → a [r, B1, q1] [q1, B2, q2] ... [qk-1, Bk, qk]

3. Start: S → [q0, Z0, qf] for each qf ∈ F

=== Intuition ===

[p, A, q] generates strings that:
  - Start from state p
  - End in state q
  - Net effect: pop A from stack

The rules simulate the PDA's computation.
""")

# EQUIVALENCE SUMMARY
print("=== Equivalence 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} {'In rules':<25} {'In transitions':<25}")
print(f"{'Derivation':<30} {'S ⇒* w':<25} {'(q0,w,Z0) ⊢* (q,ε,γ)':<25}")
print(f"{'Acceptance':<30} {'w ∈ L(G)':<25} {'Final state or empty stack':<25}")
print(f"{'Normal forms':<30} {'CNF, GNF':<25} {'DPDA (restricted)':<25}")
print(f"{'Membership':<30} {'CYK O(n³)':<25} {'O(n³) simulation':<25}")
print(f"{'Equivalence':<30} {'Undecidable':<25} {'Undecidable':<25}")
print(f"{'Emptiness':<30} {'Decidable':<25} {'Decidable':<25}")

# WHY EQUIVALENCE MATTERS
print("""
=== Why This Equivalence Matters ===

1. TWO PERSPECTIVES
   - Grammar: generative (how to build strings)
   - PDA: recognitive (how to accept strings)
   Both describe the same class.

2. PROOF TECHNIQUES
   - Prove properties of CFGs using PDAs
   - Prove properties of PDAs using CFGs
   - Choose whichever is easier

3. PARSING
   - CFG specifies syntax
   - PDA (parser) recognizes it
   - Compilers use both views

4. THEORETICAL FOUNDATION
   - Establishes CFG = PDA
   - Type 2 in Chomsky hierarchy
   - Central result in automata theory

5. PRACTICAL TOOLS
   - Parser generators (Yacc, ANTLR)
   - Take CFG, produce PDA-like parser
   - This equivalence is why they work
""")

🎯 Classic Examples

🎯 PDAs for Common Languages

These examples show PDAs for classic context-free languages. Each demonstrates a different stack technique.

Example Categories

Matching: aⁿbⁿ, parentheses. Comparing: i > j, i < j. Guessing: Palindromes. Nondeterministic: Equal counts. Multiple: ww^R. Complex: Balanced with multiple types.

🔗 Matching⚖️ Comparing🎲 Guessing🔀 Nondeterministic

# Classic PDA Examples
print("=" * 60)
print("CLASSIC PDA EXAMPLES")
print("=" * 60)

# 1. a^n b^n
print("""
=== 1. L = { aⁿbⁿ | n ≥ 0 } ===

Stack technique: Push for a, pop for b.

States: q0 (reading a), q1 (reading b), q2 (accept)
Stack: Z, A

Transitions:
  δ(q0, a, Z) = (q0, AZ)
  δ(q0, a, A) = (q0, AA)
  δ(q0, b, A) = (q1, ε)
  δ(q1, b, A) = (q1, ε)
  δ(q1, ε, Z) = (q2, Z)

Accept: {q2}
""")

# 2. Balanced Parentheses
print("""
=== 2. L = Balanced Parentheses ===

Stack technique: Push '(', pop on ')'.

States: q0 (reading), q1 (accept)
Stack: Z, (

Transitions:
  δ(q0, '(', Z) = (q0, (Z)
  δ(q0, '(', () = (q0, (()
  δ(q0, ')', () = (q0, ε)
  δ(q0, ε, Z) = (q1, Z)

Accept: {q1}
""")

# 3. Palindromes
print("""
=== 3. L = { w | w = wᴿ } ===

Stack technique: Push first half, guess middle, pop second half.

States: q0 (pushing), q1 (matching), q2 (accept)
Stack: Z, A, B

Transitions:
  # Pushing
  δ(q0, a, Z) = (q0, AZ)
  δ(q0, a, A) = (q0, AA)
  δ(q0, a, B) = (q0, AB)
  δ(q0, b, Z) = (q0, BZ)
  δ(q0, b, A) = (q0, BA)
  δ(q0, b, B) = (q0, BB)
  
  # Guess middle (nondeterministic!)
  δ(q0, ε, Z) = (q1, Z)     # even length
  δ(q0, ε, A) = (q1, A)     # odd, skip middle
  δ(q0, ε, B) = (q1, B)     # odd, skip middle
  
  # Matching
  δ(q1, a, A) = (q1, ε)
  δ(q1, b, B) = (q1, ε)
  δ(q1, ε, Z) = (q2, Z)

Accept: {q2}
""")

# 4. ww^R
print("""
=== 4. L = { wwᴿ | w ∈ {a,b}* } ===

Same as palindromes! (w w^R is a palindrome)

States: q0, q1, q2
Stack: Z, A, B

Transitions:
  δ(q0, a, Z) = (q0, AZ)
  δ(q0, a, A) = (q0, AA)
  δ(q0, a, B) = (q0, AB)
  δ(q0, b, Z) = (q0, BZ)
  δ(q0, b, A) = (q0, BA)
  δ(q0, b, B) = (q0, BB)
  δ(q0, ε, Z) = (q1, Z)
  δ(q0, ε, A) = (q1, A)
  δ(q0, ε, B) = (q1, B)
  δ(q1, a, A) = (q1, ε)
  δ(q1, b, B) = (q1, ε)
  δ(q1, ε, Z) = (q2, Z)
""")

# 5. a^i b^j, i > j
print("""
=== 5. L = { aⁱbʲ | i > j ≥ 0 } ===

Stack technique: Push a's, pop b's, accept if A's remain.

States: q0, q1, q2
Stack: Z, A

Transitions:
  δ(q0, a, Z) = (q0, AZ)
  δ(q0, a, A) = (q0, AA)
  δ(q0, b, A) = (q1, ε)
  δ(q1, b, A) = (q1, ε)
  δ(q1, ε, A) = (q2, A)     # A's remain → i > j

Accept: {q2}
""")

# 6. a^i b^j, i < j
print("""
=== 6. L = { aⁱbʲ | i < j } ===

Stack technique: Push a's, pop b's, accept if we run out of A's
                 and still have b's.

States: q0, q1, q2
Stack: Z, A

Transitions:
  δ(q0, a, Z) = (q0, AZ)
  δ(q0, a, A) = (q0, AA)
  δ(q0, b, A) = (q1, ε)
  δ(q1, b, A) = (q1, ε)
  δ(q1, b, Z) = (q2, Z)     # ran out of A's, more b's

Accept: {q2}
""")

# 7. Equal a's and b's (any order)
print("""
=== 7. L = { w | #a(w) = #b(w) } ===

Stack technique: Nondeterministic — push A for a, pop A for b,
                 OR push B for b, pop B for a.

States: q0, q1
Stack: Z, A, B

Transitions:
  # Choose to push A or B on first symbol
  δ(q0, a, Z) = {(q0, AZ), (q0, BZ)}
  δ(q0, b, Z) = {(q0, AZ), (q0, BZ)}
  
  # Push or pop depending on top
  δ(q0, a, A) = {(q0, AA), (q0, ε)}
  δ(q0, a, B) = {(q0, AB), (q0, ε)}
  δ(q0, b, A) = {(q0, BA), (q0, ε)}
  δ(q0, b, B) = {(q0, BB), (q0, ε)}
  
  # Accept empty stack
  δ(q0, ε, Z) = (q1, ε)

Accept: {q1} (or empty stack)
""")

# 8. WW
print("""
=== 8. L = { ww | w ∈ {a,b}* } ===

This is NOT context-free!
No PDA can recognize it.

Why? Need to remember the first half and compare
with the second half. But after reading the first half,
the stack has it in REVERSE order. When reading the
second half, we'd need it in FORWARD order.

The stack is LIFO — can't reverse!

=== Attempt ===
  Push first half: stack = reverse(w)
  Read second half: need to match w, but stack has reverse(w)
  ✗ Doesn't work!

This is why ww is not CFL, but ww^R is.
""")

# 9. a^n b^n c^n
print("""
=== 9. L = { aⁿbⁿcⁿ | n ≥ 0 } ===

This is NOT context-free!
No PDA can recognize it.

Why? Need TWO counters:
  - Count a's and match with b's
  - Count b's and match with c's
  
One stack = one counter.
After matching a's with b's, stack is empty.
Nothing left for c's.

=== Proof ===
Use the CFL pumping lemma.
Choose w = aᵖbᵖcᵖ.
Any pumping breaks the balance.
Contradiction. ∎
""")

# SUMMARY TABLE
print("=== Summary Table ===")
print(f"{'Language':<30} {'CFL?':<10} {'Stack Technique':<30}")
print("-" * 75)
print(f"{'aⁿbⁿ':<30} {'Yes':<10} {'Push a, pop b':<30}")
print(f"{'Balanced parens':<30} {'Yes':<10} {'Push (, pop )':<30}")
print(f"{'Palindromes':<30} {'Yes':<10} {'Push, guess, pop':<30}")
print(f"{'wwᴿ':<30} {'Yes':<10} {'Push, guess, pop':<30}")
print(f"{'aⁱbʲ, i>j':<30} {'Yes':<10} {'Push a, pop b, check':<30}")
print(f"{'aⁱbʲ, i



  
  
    🔒 Closure & Properties
    🎯 What Operations Preserve CFLs?
Context-free languages (accepted by PDAs) have specific closure properties. They're closed under union, concatenation, and star, but not under intersection or complement.
     Closure Properties
Closed under: Union, concat, star, reversal, homomorphism. NOT closed under: Intersection, complement. Closed under: ∩ regular. Proof: Constructive with PDAs/CFGs. Key example: aⁿbⁿcⁿ. DCFL: Different closure properties.
✅ 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 state with ε to both.
  PDA: Nondeterministically choose which PDA to simulate.

✓ CONCATENATION: L1 · L2
  Construction: Connect M1's accept to M2's start.
  PDA: Simulate M1, then M2.

✓ KLEENE STAR: L*
  Construction: New start/accept with ε-loops.
  PDA: Loop back after accepting.

✓ REVERSAL: L^R
  Construction: Reverse all transitions.
  PDA: Reverse input and transitions.

✓ HOMOMORPHISM: h(L)
  Construction: Apply h to terminals in rules.
  PDA: Apply h to input symbols.

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

✓ INTERSECTION WITH REGULAR: L ∩ R
  Construction: Product of PDA and DFA.
  PDA: Run both machines in parallel.

=== Operations that DO NOT Preserve ===

✗ 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ⁿ }  (NOT CFL)

✗ COMPLEMENT: Σ* \ L
  If CFLs were closed under complement,
  then since they're closed under union,
  they'd be closed under intersection
  (by De Morgan). But they're not.

✗ DIFFERENCE: L1 \ L2
  = L1 ∩ complement(L2) — both fail.
""")

# CONSTRUCTION: UNION
print("=== PDA Construction: Union ===")
print("""
Given PDAs M1, M2 for L1, L2:

Construct M for L1 ∪ L2:

  - New start state q0
  - ε-transition to M1's start
  - ε-transition to M2's start
  - Accept states = F1 ∪ F2

M nondeterministically chooses which PDA to run.

  δ(q0, ε, Z) = {(q0_1, Z0_1 Z), (q0_2, Z0_2 Z)}
  
  where q0_1, Z0_1 are M1's start, and similarly for M2.

M accepts if either M1 or M2 accepts.
""")

# CONSTRUCTION: CONCATENATION
print("=== PDA Construction: Concatenation ===")
print("""
Given PDAs M1, M2 for L1, L2:

Construct M for L1 · L2:

  - Run M1
  - When M1 accepts, ε-transition to M2's start
  - Run M2
  - Accept if M2 accepts

Key issue: M1's stack must be cleared before M2 starts,
or we need to handle two stacks.

Solution: Use accept-by-empty-stack.
  - M1 accepts by empty stack
  - Then M2 starts with empty stack
""")

# CONSTRUCTION: STAR
print("=== PDA Construction: Kleene Star ===")
print("""
Given PDA M for L:

Construct M* for L*:

  - New start/accept state
  - ε from new start to M's start
  - ε from M's accept back to M's start
  - ε from M's accept to new accept

This allows:
  - Zero repetitions (ε-transition to accept)
  - One or more repetitions (loop)
""")

# 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 (product construction):
  - PDA M1 for L
  - DFA M2 for R
  - Product PDA:
    * States: Q1 × Q2
    * Transitions: simulate both
    * Accept: both accept

Used for proving non-CFL:
  If L ∩ R is not CFL (R 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 } = not CFL
  Therefore L is not CFL.
""")

# DECISION PROBLEMS
print("=== Decision Problems for CFLs ===")
print(f"{'Problem':<30} {'Decidable?':<15} {'Complexity':<20}")
print("-" * 65)
print(f"{'Membership':<30} {'Yes':<15} {'O(n³) CYK':<20}")
print(f"{'Emptiness':<30} {'Yes':<15} {'O(|G|)':<20}")
print(f"{'Finiteness':<30} {'Yes':<15} {'O(|G|)':<20}")
print(f"{'Equivalence':<30} {'NO':<15} {'Undecidable':<20}")
print(f"{'Ambiguity':<30} {'NO':<15} {'Undecidable':<20}")
print(f"{'Universality':<30} {'NO':<15} {'Undecidable':<20}")
print(f"{'Intersection':<30} {'NO':<15} {'Not always CFL':<20}")
print(f"{'Complement':<30} {'NO':<15} {'Not always CFL':<20}")

print("""
=== Why Some Problems are Undecidable ===

Equivalence of CFLs:
  If we could decide L1 = L2 for CFLs,
  we could decide ambiguity.
  But ambiguity is undecidable.
  So equivalence is undecidable.

Ambiguity:
  No algorithm can decide if a CFG is ambiguous.
  This is a fundamental limitation.

Universality:
  Given CFG G, is L(G) = Σ*?
  Undecidable (related to equivalence).

For REGULAR languages:
  All these problems are DECIDABLE!
""")

# DCFL CLOSURE
print("=== DCFL Closure Properties ===")
print(f"{'Operation':<30} {'CFL':<15} {'DCFL':<15}")
print("-" * 60)
print(f"{'Union':<30} {'✓':<15} {'✗':<15}")
print(f"{'Intersection':<30} {'✗':<15} {'✗':<15}")
print(f"{'Complement':<30} {'✗':<15} {'✓':<15}")
print(f"{'Concatenation':<30} {'✓':<15} {'✗':<15}")
print(f"{'Kleene Star':<30} {'✓':<15} {'✗':<15}")
print(f"{'Reversal':<30} {'✓':<15} {'✓':<15}")
print(f"{'∩ Regular':<30} {'✓':<15} {'✓':<15}")
print(f"{'Homomorphism':<30} {'✓':<15} {'✗':<15}")

print("""
Interesting: DCFLs are closed under complement
but NOT under union. This is opposite to CFLs!

This is because:
  - DCFLs have deterministic parsers
  - Complement just swaps accept/reject
  - But union requires nondeterministic choice
""")

# SUMMARY
print("=== Summary ===")
print("""
CFL Closure:
  ✓ Union, concat, star, reversal, homomorphism
  ✓ Intersection with regular
  ✗ Intersection (of two CFLs)
  ✗ Complement
  ✗ Difference

DCFL Closure:
  ✓ Complement
  ✓ Reversal
  ✓ Intersection with regular
  ✗ Union
  ✗ Intersection
  ✗ Concat
  ✗ Star

Decision Problems:
  ✓ Membership (O(n³))
  ✓ Emptiness
  ✓ Finiteness
  ✗ Equivalence
  ✗ Ambiguity
  ✗ Universality

Key insight:
  CFLs are "almost" closed under everything,
  except intersection and complement.
  This is why aⁿbⁿcⁿ is not CFL.
""")
  

  
  
    💼 Applications
    🎯 PDAs in the Real World
PDAs are the theoretical foundation for parsing, which is used in every compiler, interpreter, and data processing tool. The stack is the key to handling nested structures.
     Application Domains
Compilers: Syntax analysis. Parsers: LR, LL, recursive descent. Data formats: JSON, XML, YAML. Protocols: Message parsing. NLP: Sentence structure. Web: HTML parsing.
💻 Compilers📝 Parsers📄 Data formats🌐 Protocols
    # Applications of PDAs
print("=" * 60)
print("APPLICATIONS OF PDAs")
print("=" * 60)

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

The most important application.

Pipeline:
  Source → Lexer → Tokens → Parser → AST → Codegen

Parser uses PDA:
  - Stack holds partial parse tree
  - Shift: push token
  - Reduce: pop and build tree
  - Accept: full parse

Example: LR parser for expressions
  Stack: [E, +, T]
  Input: id * id
  
  Actions:
    Shift id → [E, +, T, id]
    Reduce F → id → [E, +, T, F]
    Shift * → [E, +, T, F, *]
    ...

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

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

PDAs are the machine model for parsers:

TOP-DOWN (LL):
  - Recursive descent
  - Predictive parsing
  - Stack holds expected symbols

BOTTOM-UP (LR):
  - Shift-reduce parsing
  - Stack holds processed symbols
  - Actions: shift, reduce, accept, error

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

Each is a form of PDA simulation.
""")

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

JSON parsing:
  - Nested objects and arrays
  - Stack tracks nesting depth
  - Push on { or [
  - Pop on } or ]

XML parsing:
  - Nested tags
  - Stack tracks open tags
  - Push on 
  - Pop on 
  - Accept if stack empty

YAML:
  - Indentation-based nesting
  - Stack tracks indentation levels

All require a stack (PDA) to parse correctly!
""")

# 4. NETWORK PROTOCOLS
print("""
=== 4. Network Protocols ===

HTTP message parsing:
  - Headers are key-value pairs
  - Body can be nested (JSON, XML)
  - Stack helps with nested structures

Email (MIME):
  - Multipart messages
  - Nested parts
  - Stack tracks nesting

Protocol buffers:
  - Nested messages
  - Stack for parsing

SIP, FTP, SMTP:
  - Line-based but with nesting
""")

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

Sentence parsing:
  S → NP VP
  NP → Det N | Det Adj N
  VP → V NP | V PP
  PP → P NP

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

The stack tracks the current parse state.
""")

# 6. EXPRESSION EVALUATION
print("""
=== 6. Expression Evaluation ===

Calculator using stack:

Input: 3 + 4 * 2

Process:
  Read 3     → push 3
  Read +     → push +
  Read 4     → push 4
  Read *     → push *
  Read 2     → push 2
  End        → pop 2, pop *, pop 4 → 4*2=8
             → pop 8, pop +, pop 3 → 3+8=11
  Result: 11

This is exactly how PDAs work!
The stack holds operands and operators.
""")

# 7. BALANCED SYMBOLS
print("""
=== 7. Balanced Symbols ===

Checking balanced brackets in code:

  if (x > 0) { if (y > 0) { ... } }

Stack tracks:
  ( → push (
  ) → pop (
  { → push {
  } → pop {

If stack is empty at end → balanced.

This is a classic PDA application.
""")

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

PARSER GENERATORS:
  - Yacc/Bison (C, LR)
  - ANTLR (Java, Python, ...)
  - JavaCC (Java)
  - Happy (Haskell)
  - PLY (Python)

PARSING LIBRARIES:
  - Lark (Python)
  - pyparsing (Python)
  - Parsec (Haskell)
  - Nom (Rust)

All generate PDA-like parsers from grammars.
""")

# 9. SUMMARY TABLE
print("=== Application Summary ===")
print(f"{'Domain':<25} {'Use Case':<30} {'PDA Role':<25}")
print("-" * 80)
print(f"{'Compilers':<25} {'Syntax analysis':<30} {'Stack-based parsing':<25}")
print(f"{'Parsers':<25} {'LL, LR, CYK':<30} {'Stack simulation':<25}")
print(f"{'Data formats':<25} {'JSON, XML':<30} {'Nesting tracking':<25}")
print(f"{'Protocols':<25} {'Message parsing':<30} {'Nested structure':<25}")
print(f"{'NLP':<25} {'Sentence parsing':<30} {'Syntactic stack':<25}")
print(f"{'Calculators':<25} {'Expression eval':<30} {'Operand stack':<25}")
print(f"{'Code analysis':<25} {'Bracket matching':<30} {'Balance checking':<25}")

# 10. CASE STUDY: PYTHON PARSER
print("""
=== Case Study: Python's Parser ===

Python uses a PEG parser (since 3.9).

Pipeline:
  1. Tokenizer (lexer) → tokens
  2. PEG parser → AST
  3. Compiler → bytecode

The PEG parser uses a stack internally
to handle recursion and backtracking.

Key insight:
  Even though Python uses PEG (not pure PDA),
  the underlying mechanism is stack-based,
  just like a PDA.
""")
  

  
  
    🚀 Advanced Topics
    🎯 Beyond Basic PDAs
PDAs are the foundation for many advanced topics: deterministic parsing, tree automata, visibly pushdown automata, and higher-order pushdown automata.
     Advanced Directions
DPDA: Deterministic parsing. VPA: Visibly pushdown. HOPDA: Higher-order. Tree PDA: Tree languages. Quantum PDA: Quantum. Weighted PDA: Probabilistic.
⚙️ DPDA👁️ VPA📚 HOPDA🌲 Tree
    # Advanced Topics
print("=" * 60)
print("ADVANCED TOPICS")
print("=" * 60)

# 1. VISIBLY PUSHDOWN AUTOMATA
print("""
=== 1. Visibly Pushdown Automata (VPA) ===

A VPA is a PDA where the stack operation
is determined by the input symbol.

Input alphabet is partitioned:
  Σ = Σ_call ∪ Σ_return ∪ Σ_internal

- Call symbols: push
- Return symbols: pop
- Internal symbols: no stack change

Properties:
  - Closed under union, intersection, complement
  - Determinizable
  - Good for structured data (XML, JSON)

Used in:
  - XML validation
  - Program analysis
  - Streaming data
""")

# 2. HIGHER-ORDER PUSHDOwn
print("""
=== 2. Higher-Order Pushdown Automata ===

A k-order PDA has k nested stacks:
  - 1-PDA: regular stack
  - 2-PDA: stack of stacks
  - k-PDA: k levels

Power:
  1-PDA = CFL
  2-PDA ⊋ CFL
  k-PDA grows with k
  ∞-PDA = TM

Used in:
  - Program analysis (recursion)
  - Model checking
  - Higher-order programs
""")

# 3. TREE PUSHDOWN AUTOMATA
print("""
=== 3. Tree Pushdown Automata ===

PDAs that process trees instead of strings.

Applications:
  - XML schema validation
  - Compiler ASTs
  - Term rewriting
  - Program analysis

Related to:
  - Tree automata
  - Tree grammars
  - Regular tree languages
""")

# 4. QUANTUM PDAs
print("""
=== 4. Quantum PDAs ===

Quantum version of PDAs:
  - States are quantum superpositions
  - Transitions are unitary
  - Stack is quantum

Research area:
  - Quantum computing theory
  - Potential speedups
  - Still experimental

Challenges:
  - Decoherence
  - Measurement
  - Error correction
""")

# 5. WEIGHTED PDAs
print("""
=== 5. Weighted PDAs ===

Each transition has a weight (cost, probability).

Used in:
  - Probabilistic parsing (PCFGs)
  - Speech recognition
  - Machine translation
  - NLP

Algorithms:
  - Inside-outside algorithm
  - Viterbi parsing
  - Weighted CYK
""")

# 6. ALTERNATING PDAs
print("""
=== 6. Alternating PDAs ===

Alternating automata:
  - States are existential or universal
  - Existential: accept if some path accepts
  - Universal: accept if all paths accept

Power:
  Alternating PDA = TM

This shows how adding alternation
can dramatically increase power.

Used in:
  - Formal verification
  - Model checking
  - Game theory
""")

# 7. PUSHDOWN SYSTEMS
print("""
=== 7. Pushdown Systems ===

A pushdown system (PDS) is a PDA without input.

  PDS = (Q, Γ, δ)
  δ ⊆ Q × Γ × Q × Γ*

Configurations: Q × Γ*

Used in:
  - Program analysis (recursion)
  - Model checking
  - Interprocedural analysis

Key algorithms:
  - Pre* and Post* (reachability)
  - Saturation
  - Automata-based

These algorithms are used in:
  - SLAM project (Microsoft)
  - Blast
  - Software verification
""")

# 8. MODERN PARSING
print("""
=== 8. Modern Parsing ===

NEURAL PARSING:
  - Deep learning for parsing
  - No explicit grammar
  - Still uses stack-like mechanisms

TRANSFORMER PARSING:
  - Attention-based
  - Parallel parsing
  - Fast, accurate

HYBRID:
  - PDA + neural
  - Best of both worlds

INCREMENTAL:
  - Online parsing
  - Interactive systems
  - Left-to-right

PROBABILISTIC:
  - PCFGs
  - Weighted PDAs
  - Statistical parsing
""")

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

1. DETERMINIZABILITY
   Given a PDA, is there an equivalent DPDA?
   This is decidable but complex.

2. UNIVERSALITY
   Is L(M) = Σ* for a PDA M?
   Undecidable.

3. EQUIVALENCE
   Is L(M1) = L(M2)?
   Undecidable.

4. AMBIGUITY
   Is a PDA ambiguous?
   Undecidable.

5. EFFICIENT PARSING
   Can we parse any CFG in O(n²)?
   Valiant: O(n^ω), ω < 2.373.
   Lower bound unknown.

6. QUANTUM PARSING
   Can quantum PDAs parse faster?
   Research area.
""")

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

PDAs are:

✓ FOUNDATIONAL
  Model for context-free languages.

✓ EQUIVALENT TO CFGs
  Same power, different perspective.

✓ PRACTICAL
  Used in every compiler.

✓ EXTENSIBLE
  VPA, HOPDA, tree PDA, quantum PDA.

✓ THEORETICAL
  Rich theory, interesting properties.

✓ EVOLVING
  Modern parsing, verification, NLP.

Key takeaway:
  The stack is the key to context-free power.
  One stack = context-free.
  Two stacks = Turing machine.

"Pushdown automata: the sweet spot
between finite automata and Turing machines."
  — Anonymous

Go build a parser!
""")

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

PDA: M = (Q, Σ, Γ, δ, q₀, Z₀, F)
  Q: states
  Σ: input alphabet
  Γ: stack alphabet
  δ: Q × (Σ∪{ε}) × Γ → P(Q × Γ*)
  q₀: start state
  Z₀: initial stack symbol
  F: accept states

Acceptance:
  Final state: end in F
  Empty stack: stack empty

Equivalence:
  CFG ⟺ PDA

DPDA:
  At most one transition per configuration.
  Accepts DCFLs (strict subset of CFLs).

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

Decision:
  Membership: Decidable O(n³)
  Emptiness: Decidable
  Equivalence: Undecidable
  Ambiguity: Undecidable
""")