🧠 DPDA Fundamentals

🎯 What is a DPDA?

A Deterministic Pushdown Automaton (DPDA) is a pushdown automaton where every configuration has at most one possible next move. Unlike general PDAs, DPDAs cannot "guess" — they must follow a unique computation path. DPDAs recognize the deterministic context-free languages (DCFLs), a strict subset of the context-free languages.

Key insight: Determinism does restrict power for PDAs, unlike for finite automata where DFA = NFA. Some context-free languages (like palindromes) require nondeterminism.

Why DPDAs Matter

Deterministic: No guessing, unique path. Efficient: O(n) parsing. Practical: Programming languages. LR parsing: DPDA is the model. DCFL: Strict subset of CFL. Complement: DCFLs closed under complement.

📌 Unique transition📌 O(n) parsing📌 DCFL subset📌 LR grammars

# Deterministic Pushdown Automaton — the big picture
print("""
=== DFA vs NFA vs DPDA vs PDA ===

DFA = NFA (same power)
  Determinism doesn't restrict finite automata.

DPDA ⊊ PDA (strict subset)
  Determinism DOES restrict pushdown automata!

This is a fundamental difference.

=== Why the Difference? ===

For finite automata:
  - NFA can be converted to DFA (subset construction)
  - No loss of power

For pushdown automata:
  - NFA→DFA conversion doesn't work
  - Stack creates infinite configurations
  - Some CFLs require nondeterminism

=== Intuition ===

Nondeterminism lets a PDA "guess":
  - Where the middle of a palindrome is
  - Which branch to take
  - When to switch phases

A DPDA can't guess — it must decide based on:
  - Current state
  - Input symbol
  - Stack top

Sometimes that's not enough information!

=== Real-World Analogy ===

Nondeterministic PDA:
  Like a detective who can explore all leads
  simultaneously. If ANY lead solves the case,
  the case is solved.

Deterministic PDA:
  Like a detective who must follow ONE lead
  at a time. If that lead is wrong, the case fails.

For some problems, you NEED to explore multiple
leads — nondeterminism is essential.
""")

# THE DETERMINISM CONDITIONS
print("=== The Determinism Conditions ===")
print("""
A PDA M = (Q, Σ, Γ, δ, q₀, Z₀, F) is DETERMINISTIC if:

CONDITION 1: No multiple transitions
  For every q ∈ Q, a ∈ Σ, Z ∈ Γ:
    |δ(q, a, Z)| ≤ 1

CONDITION 2: No ε/input conflict
  For every q ∈ Q, Z ∈ Γ:
    If δ(q, ε, Z) ≠ ∅, then δ(q, a, Z) = ∅ for all a ∈ Σ.

In other words:
  - At most one transition per (state, input, stack) triple
  - Can't have both an ε-transition and an input transition
    for the same (state, stack top)

=== Why These Conditions? ===

Given a configuration (q, w, γ):
  - We know the state q
  - We know the remaining input w
  - We know the stack top Z

If |δ(q, a, Z)| > 1:
  Multiple choices → nondeterministic.

If both δ(q, ε, Z) and δ(q, a, Z) exist:
  Can either consume input or not → nondeterministic.
""")

# DPDA IN CODE
print("=== Python: DPDA Simulation ===")

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) — single value
        self.q0 = start_state
        self.Z0 = start_stack
        self.F = accept_states
    
    def is_deterministic(self):
        """Verify determinism conditions."""
        # Condition 1: no multiple transitions
        # (In our representation, each key maps to a single tuple, so OK)
        
        # Condition 2: 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, f"Conflict: δ({q}, ε, {Z}) and δ({q}, {symbol}, {Z})"
        return True, "Deterministic"
    
    def accepts(self, input_string, max_steps=10000):
        """Simulate DPDA (deterministic — single path)."""
        state = self.q0
        idx = 0
        stack = (self.Z0,)
        trace = [(state, idx, stack)]
        
        for _ in range(max_steps):
            # Check acceptance
            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
            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 available
            return False, trace
        
        return False, trace


# Example: DPDA for a^n b^n
dpda_anbn = 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'}
)

det, msg = dpda_anbn.is_deterministic()
print(f"DPDA for a^n b^n")
print(f"Deterministic: {det} — {msg}")
print(f"\nTesting:")
for s in ['', 'ab', 'aabb', 'aaabbb', 'aab', 'abb', 'ba', 'aabbb']:
    accepted, trace = dpda_anbn.accepts(s)
    result = "✓ ACCEPT" if accepted else "✗ REJECT"
    print(f"  '{s}' → {result}")

# Trace
print("\nTrace for 'aabb':")
accepted, trace = dpda_anbn.accepts('aabb')
for i, (state, idx, stack) in enumerate(trace):
    stack_str = '[' + ' '.join(stack) + ']' if stack else '[ ]'
    remaining = 'aabb'[idx:] if idx < len('aabb') else 'ε'
    print(f"  Step {i}: state={state}, remaining='{remaining}', stack={stack_str}")

print("""
=== Key Observations ===

1. DPDA has exactly ONE computation path.
   No branching, no guessing.

2. If that path fails, the DPDA rejects.
   There's no "other path" to try.

3. This is why DPDA is weaker than PDA.
   Some languages need multiple paths.

4. But DPDA is fast: O(n) time.
   Each input symbol triggers one transition.

5. DPDAs are the model for LR parsers.
   Real compilers use DPDA-like machines.
""")

📐 Formal Definition

🎯 The 7-Tuple (Deterministic)

A DPDA is formally defined as a 7-tuple M = (Q, Σ, Γ, δ, q₀, Z₀, F) where δ is a partial function (not a set-valued function) satisfying determinism conditions.

The Components

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

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

# Formal Definition of DPDA
from dataclasses import dataclass
from typing import Set, Dict, Tuple, FrozenSet, Optional

@dataclass
class DPDA:
    """
    Formal DPDA as 7-tuple M = (Q, Σ, Γ, δ, q₀, Z₀, F)
    
    δ: Q × (Σ ∪ {ε}) × Γ → Q × Γ*   (partial function)
    """
    Q: FrozenSet[str]
    Sigma: FrozenSet[str]
    Gamma: FrozenSet[str]
    delta: Dict[Tuple[str, str, str], Tuple[str, Tuple[str, ...]]]
    q0: str
    Z0: str
    F: FrozenSet[str]
    
    def __post_init__(self):
        # Validate basic structure
        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"
        
        # Validate transitions
        for (q, a, Z), (nq, push) 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 Γ"
            assert nq in self.Q, f"Next state {nq} not in Q"
            for s in push:
                assert s in self.Gamma, f"Push symbol {s} not in Γ"
        
        # Verify determinism
        self._check_determinism()
    
    def _check_determinism(self):
        """Verify determinism conditions."""
        # Condition 2: no ε/input conflict
        for (q, a, Z) in self.delta:
            if a == 'ε':
                for symbol in self.Sigma:
                    if (q, symbol, Z) in self.delta:
                        raise ValueError(
                            f"Nondeterministic: δ({q}, ε, {Z}) and "
                            f"δ({q}, {symbol}, {Z}) both defined"
                        )
    
    def __repr__(self):
        lines = [f"DPDA 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), (nq, push) in sorted(self.delta.items()):
            push_str = ''.join(push) if push else 'ε'
            lines.append(f"    δ({q}, {a}, {Z}) = ({nq}, {push_str})")
        return '\n'.join(lines)
    
    def accepts(self, w, max_steps=10000):
        """Simulate DPDA."""
        state = self.q0
        idx = 0
        stack = (self.Z0,)
        
        for _ in range(max_steps):
            if idx == len(w) and (state in self.F or len(stack) == 0):
                return True
            
            if not stack:
                return idx == len(w)
            
            top = stack[0]
            
            # ε-transition
            if (state, 'ε', top) in self.delta:
                nq, push = self.delta[(state, 'ε', top)]
                stack = tuple(push) + stack[1:]
                state = nq
                continue
            
            # Input transition
            if idx < len(w) and (state, w[idx], top) in self.delta:
                nq, push = self.delta[(state, w[idx], top)]
                stack = tuple(push) + stack[1:]
                state = nq
                idx += 1
                continue
            
            return False
        
        return False


# Example
dpda = DPDA(
    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(dpda)

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

A configuration of a DPDA is a triple (q, w, γ):
  q ∈ Q       current state
  w ∈ Σ*      remaining input
  γ ∈ Γ*      current stack contents

=== Deterministic Transition ===

Since δ is a partial function:
  (q, aw, Zγ) ⊢ (q', w, αγ)  if δ(q, a, Z) = (q', α)
  (q, w, Zγ)  ⊢ (q', w, αγ)  if δ(q, ε, Z) = (q', α)

At most ONE of these applies.

=== Acceptance ===

L(M) = { w | (q₀, w, Z₀) ⊢* (q, ε, γ) for some q ∈ F }
""")

# DETERMINISM VERIFICATION
print("=== Determinism Verification ===")

def check_dpda_determinism(delta, Sigma):
    """Check if a transition function is deterministic."""
    issues = []
    
    # Check 1: No multiple transitions (in dict representation, automatic)
    
    # Check 2: No ε/input conflict
    for (q, a, Z) in delta:
        if a == 'ε':
            for symbol in Sigma:
                if (q, symbol, Z) in delta:
                    issues.append(
                        f"Conflict at ({q}, {Z}): "
                        f"both ε and '{symbol}' transitions"
                    )
    
    if issues:
        return False, issues
    return True, ["Deterministic ✓"]


# Valid DPDA
valid_delta = {
    ('q0', 'a', 'Z'): ('q0', ('A', 'Z')),
    ('q0', 'b', 'A'): ('q1', ()),
    ('q1', 'ε', 'Z'): ('q2', ('Z',)),
}

det, msgs = check_dpda_determinism(valid_delta, {'a', 'b'})
print("Valid DPDA:")
for msg in msgs:
    print(f"  {msg}")

# Invalid DPDA (ε conflict)
invalid_delta = {
    ('q0', 'a', 'Z'): ('q0', ('A', 'Z')),
    ('q0', 'ε', 'Z'): ('q1', ('Z',)),  # Conflict!
}

det, msgs = check_dpda_determinism(invalid_delta, {'a', 'b'})
print("\nInvalid DPDA:")
for msg in msgs:
    print(f"  {msg}")

# PARTIAL FUNCTION
print("""
=== Partial Function ===

δ is a PARTIAL function:
  - Not defined for every (q, a, Z)
  - Missing transitions mean "no move" (stuck/reject)

This is different from a total function.
In a total function, every input has a defined output.

Why partial?
  - Allows rejection by getting stuck
  - Simpler than adding explicit reject states

Example:
  δ(q0, 'a', Z) = (q0, AZ)
  δ(q0, 'b', A) = (q1, ε)
  (no δ(q0, 'b', Z) — if we see 'b' with Z, we reject)
""")

# MORE EXAMPLES
print("=== More DPDA Examples ===")
print("""
1. a^n b^n (n ≥ 0):
   δ(q0, a, Z) = (q0, AZ)
   δ(q0, a, A) = (q0, AA)
   δ(q0, b, A) = (q1, ε)
   δ(q1, b, A) = (q1, ε)
   δ(q1, ε, Z) = (q2, Z)

2. Balanced parentheses:
   δ(q0, (, Z) = (q0, (Z)
   δ(q0, (, () = (q0, (()
   δ(q0, ), () = (q0, ε)
   δ(q0, ε, Z) = (q1, Z)

3. a^i b^j (i > j):
   δ(q0, a, Z) = (q0, AZ)
   δ(q0, a, A) = (q0, AA)
   δ(q0, b, A) = (q1, ε)
   δ(q1, b, A) = (q1, ε)
   δ(q1, ε, A) = (q2, A)   ← accept if A remains
""")

⚙️ Determinism Conditions

🎯 What Makes a DPDA Deterministic?

A PDA is deterministic if every configuration has at most one possible next move. This requires two conditions: no multiple transitions, and no ε/input conflicts.

The Two Conditions

Condition 1: |δ(q,a,Z)| ≤ 1 for all q,a,Z. Condition 2: ε and input transitions don't conflict. Effect: Unique computation path. Result: No guessing, no backtracking. Power: DCFL ⊊ CFL. Time: O(n) parsing.

1️⃣ At most one🚫 No ε-conflict➡️ Unique path⏱️ O(n)

# Determinism Conditions in detail
print("=" * 60)
print("DETERMINISM CONDITIONS")
print("=" * 60)

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

A PDA M = (Q, Σ, Γ, δ, q₀, Z₀, F) is DETERMINISTIC if:

For all q ∈ Q, Z ∈ Γ:

  CONDITION 1:
    |δ(q, a, Z)| ≤ 1 for all a ∈ Σ
    (At most one transition per input symbol)

  CONDITION 2:
    |δ(q, ε, Z)| ≤ 1
    (At most one ε-transition)

  CONDITION 3:
    If δ(q, ε, Z) ≠ ∅, then δ(q, a, Z) = ∅ for all a ∈ Σ
    (No ε/input conflict)

=== Combined ===

For every configuration (q, w, Zγ),
there is AT MOST ONE possible next configuration.

=== Visual ===

Nondeterministic PDA:
  δ(q, a, Z) = {(q1, α), (q2, β), (q3, γ)}  ← multiple choices

Deterministic PDA:
  δ(q, a, Z) = (q1, α)                       ← single choice
  OR
  δ(q, a, Z) = undefined                     ← no move
""")

# CONDITION 1: NO MULTIPLE TRANSITIONS
print("=== Condition 1: No Multiple Transitions ===")
print("""
BAD (nondeterministic):
  δ(q0, 'a', Z) = {(q1, AZ), (q2, ε)}
  
  Two choices: push A or pop Z.
  PDA must "guess" which to do.

GOOD (deterministic):
  δ(q0, 'a', Z) = (q1, AZ)
  
  Only one choice: push A.

=== Why This Matters ===

With multiple transitions, the PDA has a CHOICE.
It must explore both possibilities.
This is nondeterminism.

For a DPDA, the choice is forced by:
  - Current state
  - Input symbol
  - Stack top
""")

# CONDITION 2 & 3: EPSILON CONFLICT
print("=== Conditions 2 & 3: Epsilon Conflicts ===")
print("""
BAD (nondeterministic):
  δ(q0, 'a', Z) = (q1, AZ)
  δ(q0, 'ε', Z) = (q2, ε)
  
  Conflict: with Z on stack, the PDA can:
    - Read 'a' and push A
    - OR take ε-transition and pop Z (without reading)
  
  This is a choice → nondeterministic!

GOOD (deterministic):
  δ(q0, 'a', Z) = (q1, AZ)
  (no ε-transition for Z)
  
  OR
  
  δ(q0, 'ε', Z) = (q2, ε)
  (no input transitions for Z)

=== Why This Matters ===

If both ε and input transitions exist, the PDA
can choose to consume input or not.
This is another form of choice.

A DPDA must know unambiguously whether to:
  - Consume the next input symbol
  - Take an ε-transition
""")

# DETERMINISM CHECK IN CODE
print("=== Determinism Check in Code ===")

def analyze_determinism(delta, Q, Sigma, Gamma):
    """Analyze a transition function for determinism."""
    issues = []
    
    # Group transitions by (q, Z)
    by_state_stack = {}
    for (q, a, Z), result in delta.items():
        key = (q, Z)
        if key not in by_state_stack:
            by_state_stack[key] = []
        by_state_stack[key].append((a, result))
    
    # Check each (q, Z) group
    for (q, Z), transitions in by_state_stack.items():
        # Condition 1: multiple input transitions
        input_trans = [(a, r) for a, r in transitions if a != 'ε']
        if len(input_trans) > 1:
            issues.append(
                f"Multiple input transitions for ({q}, {Z}): "
                f"{[a for a, _ in input_trans]}"
            )
        
        # Condition 2: multiple ε-transitions
        eps_trans = [(a, r) for a, r in transitions if a == 'ε']
        if len(eps_trans) > 1:
            issues.append(
                f"Multiple ε-transitions for ({q}, {Z})"
            )
        
        # Condition 3: ε/input conflict
        if eps_trans and input_trans:
            issues.append(
                f"ε/input conflict for ({q}, {Z}): "
                f"ε and {[a for a, _ in input_trans]}"
            )
    
    return issues


# Test cases
print("Test 1: DPDA for a^n b^n")
delta1 = {
    ('q0', 'a', 'Z'): ('q0', ('A', 'Z')),
    ('q0', 'a', 'A'): ('q0', ('A', 'A')),
    ('q0', 'b', 'A'): ('q1', ()),
    ('q1', 'b', 'A'): ('q1', ()),
    ('q1', 'ε', 'Z'): ('q2', ('Z',)),
}
issues1 = analyze_determinism(delta1, {'q0', 'q1', 'q2'}, {'a', 'b'}, {'Z', 'A'})
if issues1:
    print("  Issues found:")
    for issue in issues1:
        print(f"    - {issue}")
else:
    print("  ✓ Deterministic")

print("\nTest 2: NPDA for palindromes")
delta2 = {
    ('q0', 'a', 'Z'): [('q0', ('A', 'Z')), ('q1', ('Z',))],
    ('q0', 'a', 'A'): [('q0', ('A', 'A')), ('q1', ('A',))],
}
# Convert to our format (take first for analysis)
delta2_simple = {k: v[0] for k, v in delta2.items()}
# But this has multiple, so let's check manually
print("  Nondeterministic: multiple transitions for (q0, a, Z)")
print("    δ(q0, a, Z) = {(q0, AZ), (q1, Z)}")

print("\nTest 3: Invalid (ε conflict)")
delta3 = {
    ('q0', 'a', 'Z'): ('q0', ('A', 'Z')),
    ('q0', 'ε', 'Z'): ('q1', ('Z',)),
}
issues3 = analyze_determinism(delta3, {'q0', 'q1'}, {'a', 'b'}, {'Z', 'A'})
if issues3:
    print("  Issues found:")
    for issue in issues3:
        print(f"    - {issue}")
else:
    print("  ✓ Deterministic")

# DETERMINISM VS NONDETERMINISM
print("""
=== Determinism vs Nondeterminism ===

DETERMINISTIC PDA:
  - At most one move per configuration
  - Single computation path
  - Fast: O(n)
  - Weaker: DCFL
  - Used in: compilers, parsers

NONDETERMINISTIC PDA:
  - Multiple moves possible
  - Multiple computation paths
  - Accepts if ANY path accepts
  - Slower: O(n³) for simulation
  - Stronger: all CFLs
  - Used in: theory, NLP

=== Key Insight ===

For finite automata: DFA = NFA (same power)
For pushdown automata: DPDA ⊊ PDA (strict!)

The stack makes nondeterminism more powerful.
""")

# WHY DETERMINISM FAILS FOR SOME LANGUAGES
print("=== Why Determinism Fails: Palindromes ===")
print("""
L = { w | w = w^R } over {a, b}

A DPDA CANNOT recognize this!

Why? To recognize palindromes, the PDA must:
  1. Push first half
  2. Know when middle is reached
  3. Pop and match second half

Step 2 is the problem: how does the DPDA know
when it's at the middle?

Nondeterministic PDA:
  - Guess the middle (ε-transition)
  - Try ALL possible middle positions
  - Accept if any guess works

Deterministic PDA:
  - Must know the middle exactly
  - But it can't! The input length isn't known in advance.
  - The stack only holds the first half, not its length.

=== Formal Proof ===

Palindromes are not DCFL.
(Proof uses closure properties or direct argument.)

=== Other Non-DCFL Examples ===

1. ww^R (palindromes)
2. { a^i b^j c^k | i = j or j = k } (ambiguous)
3. { a^i b^j c^k | i ≠ j or j ≠ k }
4. Any language requiring "guessing"
""")

# DESIGNING DETERMINISTIC PDAs
print("=== Designing DPDAs ===")
print("""
For a DPDA, the transition must be UNIQUELY DETERMINED
by (state, input, stack top).

Design principles:
  1. Each phase has a clear trigger
  2. Stack top tells you what to expect
  3. Input symbol tells you what to do
  4. No ambiguity in decisions

Example: a^n b^n
  - While seeing 'a' with Z or A on top → push A
  - When seeing 'b' with A on top → switch to popping
  - When seeing 'b' with A on top → pop
  - When stack has Z and input done → accept

Each decision is forced by the configuration.

=== Common DPDA Patterns ===

1. PHASE SWITCHING
   State change triggered by specific input/stack.
   
2. STACK-DRIVEN
   Stack top determines action.
   
3. INPUT-DRIVEN
   Input symbol determines action.
   
4. COMBINED
   Both input and stack determine action.
""")

📊 DCFL & Properties

🎯 Deterministic Context-Free Languages

DCFLs are the languages accepted by DPDAs. They form a strict subset of the context-free languages: DCFL ⊊ CFL. DCFLs have better closure and decision properties than general CFLs.

DCFL Properties

Subset: DCFL ⊊ CFL. Complement: Closed under complement! Union: NOT closed. Intersection: NOT closed. Decision: Equivalence decidable. Parsing: LR(k) grammars.

📉 Subset of CFL✅ Complement❌ Union🔍 LR parsing

# DCFL and its properties
print("=" * 60)
print("DETERMINISTIC CONTEXT-FREE LANGUAGES (DCFLs)")
print("=" * 60)

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

DCFL = { L | L is accepted by some DPDA }

=== Relationship to Other Classes ===

Regular ⊊ DCFL ⊊ CFL ⊊ CSL ⊊ RE

Each inclusion is STRICT:
  - Regular ⊊ DCFL: a^n b^n is DCFL but not regular
  - DCFL ⊊ CFL: palindromes are CFL but not DCFL
  - CFL ⊊ CSL: a^n b^n c^n is CSL but not CFL
  - CSL ⊊ RE: halting problem is RE but not CSL

=== Visual ===

  Regular
     ↓ (strict)
  DCFL
     ↓ (strict)
  CFL
     ↓ (strict)
  CSL
     ↓ (strict)
  RE
""")

# DCFL EXAMPLES
print("=== Examples of DCFLs ===")
print("""
✓ a^n b^n (n ≥ 0)
✓ Balanced parentheses
✓ Arithmetic expressions
✓ Most programming languages
✓ { w | w has equal a's and b's } — wait, is this DCFL?
   Actually NO — this requires nondeterminism.
   
Let me reconsider:

✓ a^n b^n — DCFL (push a, pop b)
✓ Balanced parentheses — DCFL
✓ a^i b^j (i > j) — DCFL
✓ a^i b^j (i < j) — DCFL
✓ a^i b^j (i = j) — DCFL (= a^n b^n)
✓ wcw^R — DCFL (c marks the middle)
✓ Arithmetic expressions — DCFL
✓ Programming language syntax — DCFL

✗ Palindromes (w = w^R) — NOT DCFL
✗ ww^R (same as palindromes) — NOT DCFL
✗ Equal a's and b's (any order) — NOT DCFL
✗ { a^i b^j c^k | i = j or j = k } — NOT DCFL
✗ { ww } — NOT CFL at all

=== Key Insight ===

DCFLs can handle:
  - One counter
  - Deterministic phase switches
  - Marked centers (w c w^R)

DCFLs CANNOT handle:
  - Guessing the middle (palindromes)
  - Multiple independent choices
  - Ambiguity
""")

# DCFL VS CFL
print("=== DCFL vs CFL: Key Differences ===")
print(f"{'Aspect':<30} {'DCFL':<25} {'CFL':<25}")
print("-" * 80)
print(f"{'Machine':<30} {'DPDA':<25} {'NPDA':<25}")
print(f"{'Determinism':<30} {'Yes':<25} {'No':<25}")
print(f"{'Parsing':<30} {'O(n) LR':<25} {'O(n³) CYK':<25}")
print(f"{'Complement':<30} {'Closed':<25} {'NOT closed':<25}")
print(f"{'Union':<30} {'NOT closed':<25} {'Closed':<25}")
print(f"{'Intersection':<30} {'NOT closed':<25} {'NOT closed':<25}")
print(f"{'Equivalence':<30} {'Decidable':<25} {'Undecidable':<25}")
print(f"{'Example':<30} {'a^n b^n':<25} {'Palindromes':<25}")
print(f"{'Practical':<30} {'Compilers':<25} {'NLP':<25}")

# CLOSURE PROPERTIES
print("=== Closure Properties of DCFLs ===")
print("""
DCFLs are CLOSED under:
  ✓ COMPLEMENT: DCFL is closed under complement!
    (This is surprising — CFLs are not.)
    Proof: Swap accept and non-accept states in DPDA.
    (Need to handle "stuck" configurations carefully.)
  
  ✓ INTERSECTION WITH REGULAR: DCFL ∩ Regular = DCFL
  
  ✓ REVERSAL: L^R is DCFL if L is DCFL
  
  ✓ INVERSE HOMOMORPHISM

DCFLs are NOT closed under:
  ✗ UNION: L1 ∪ L2 may not be DCFL
    Example: { a^i b^j c^k | i=j } ∪ { a^i b^j c^k | j=k }
    This is CFL but not DCFL.
  
  ✗ INTERSECTION: L1 ∩ L2 may not be DCFL
  
  ✗ CONCATENATION: L1 · L2 may not be DCFL
  
  ✗ KLEENE STAR: L* may not be DCFL
  
  ✗ HOMOMORPHISM

=== Interesting Contrast ===

CFL:  Closed under union, NOT complement
DCFL: NOT closed under union, Closed under complement

This is because:
  - Nondeterminism helps with union (choose a branch)
  - Determinism helps with complement (swap accept/reject)
""")

# DECISION PROBLEMS
print("=== Decision Problems for DCFLs ===")
print(f"{'Problem':<30} {'DCFL':<15} {'CFL':<15}")
print("-" * 60)
print(f"{'Membership':<30} {'O(n)':<15} {'O(n³)':<15}")
print(f"{'Emptiness':<30} {'Decidable':<15} {'Decidable':<15}")
print(f"{'Finiteness':<30} {'Decidable':<15} {'Decidable':<15}")
print(f"{'Equivalence':<30} {'Decidable':<15} {'Undecidable':<15}")
print(f"{'Ambiguity':<30} {'Always unambig':<15} {'Undecidable':<15}")
print(f"{'Universality':<30} {'Decidable':<15} {'Undecidable':<15}")
print(f"{'Inclusion':<30} {'Decidable':<15} {'Undecidable':<15}")

print("""
=== Key Result ===

Equivalence of DCFLs is DECIDABLE!

This is a major advantage over CFLs.
For CFLs, equivalence is undecidable.

Algorithm:
  1. Compute minimal DPDA for each language
  2. Compare (isomorphic?)
  3. Decidable

This is why programming languages are designed
to have DCFL syntax — compilers can verify
equivalence and optimize.

=== Universality ===

Given a DPDA M, is L(M) = Σ*?
DECIDABLE for DPDAs!

For general PDAs, this is undecidable.

=== Why the Difference? ===

Determinism gives us:
  - Canonical forms
  - Decidable equivalence
  - Better closure properties

The price: less expressive power.
""")

# DCFL IN PRACTICE
print("=== DCFLs in Practice ===")
print("""
Programming languages are designed as DCFLs:

C, Java, Python, JavaScript, ...

Why?
  1. Efficient parsing (O(n) with LR)
  2. Unambiguous syntax
  3. Compiler can verify correctness

Examples of DCFL constructs:
  - Expressions with precedence
  - Statement blocks { ... }
  - Function definitions
  - Type declarations

Non-DCFL constructs:
  - Palindromic identifiers (not used!)
  - Ambiguous grammar (avoided)

=== LR(k) Grammars ===

LR(k) grammars generate DCFLs.
LALR(1), SLR(1), LR(1) are all DCFL.

Yacc, Bison, CUP use LR parsing.
ANTLR uses LL(*) which also handles DCFLs.

So: programming languages = DCFLs = LR-parseable
""")

# SUMMARY
print("=== Summary ===")
print("""
DCFL:
  - Accepted by DPDA
  - Strict subset of CFL
  - Closed under complement
  - NOT closed under union
  - Decidable equivalence
  - O(n) parsing
  - Programming languages

Key takeaway:
  Determinism trades power for efficiency.
  DCFLs are smaller than CFLs but much more
  practical for real-world parsing.
""")

🎯 Classic Examples

🎯 DPDAs for Common Languages

These examples show DPDAs for classic deterministic context-free languages. Each demonstrates a different technique for deterministic recognition.

Example Categories

Matching: aⁿbⁿ. Comparing: i > j, i < j. Marked center: wcw^R. Balanced: Parentheses. Expressions: Arithmetic. Practical: Programming syntax.

🔗 Matching⚖️ Comparing🎯 Marked center📝 Expressions

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

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

DPDA:
  States: q0 (reading a's), q1 (reading b's), q2 (accept)
  Stack: Z, A
  
  δ(q0, a, Z) = (q0, AZ)
  δ(q0, a, A) = (q0, AA)
  δ(q0, b, A) = (q1, ε)
  δ(q1, b, A) = (q1, ε)
  δ(q1, ε, Z) = (q2, Z)

Deterministic: ✓
  - Each configuration has exactly one move
  - No ε/input conflicts

Parsing:
  'aabb' → push A, push A, pop A, pop A → accept
""")

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

DPDA:
  States: q0 (reading), q1 (accept)
  Stack: Z, (
  
  δ(q0, '(', Z) = (q0, (Z)
  δ(q0, '(', () = (q0, (()
  δ(q0, ')', () = (q0, ε)
  δ(q0, ε, Z) = (q1, Z)

Deterministic: ✓
  - Only one transition per (state, input, stack)
  - ε-transition only when stack has Z

Parsing:
  '(())' → push (, push (, pop (, pop ( → accept
""")

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

DPDA:
  States: q0 (reading a's), q1 (reading b's), q2 (accept)
  Stack: Z, A
  
  δ(q0, a, Z) = (q0, AZ)
  δ(q0, a, A) = (q0, AA)
  δ(q0, b, A) = (q1, ε)
  δ(q1, b, A) = (q1, ε)
  δ(q1, ε, A) = (q2, A)     ← accept if A remains

Deterministic: ✓
  - Stack top A after reading b's → i > j

Parsing:
  'aab' → push A, push A, pop A → A remains → accept
  'abb' → push A, pop A, pop from empty → reject
""")

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

DPDA:
  States: q0, q1, q2
  Stack: Z, A
  
  δ(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

Deterministic: ✓
  - When stack top is Z and we see b → i < j

Parsing:
  'abb' → push A, pop A, see b with Z → accept
  'aab' → push A, push A, pop A, stack has A → reject
""")

# 5. a^i b^j (i = j)
print("""
=== 5. L = { aⁱbʲ | i = j } ===

Same as a^n b^n! DCFL.

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

# 6. wcw^R (marked palindrome)
print("""
=== 6. L = { w c wᴿ | w ∈ {a,b}* } ===

This IS a DCFL! The 'c' marks the middle.

DPDA:
  States: q0 (pushing), q1 (popping), q2 (accept)
  Stack: Z, A, B
  
  # Pushing phase
  δ(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)
  
  # Switch at 'c'
  δ(q0, c, Z) = (q1, Z)
  δ(q0, c, A) = (q1, A)
  δ(q0, c, B) = (q1, B)
  
  # Popping phase
  δ(q1, a, A) = (q1, ε)
  δ(q1, b, B) = (q1, ε)
  δ(q1, ε, Z) = (q2, Z)

Deterministic: ✓
  - 'c' is the unambiguous middle marker
  - No guessing needed!

Parsing:
  'abcba' → push a, push b, read c, pop b, pop a → accept
""")

# 7. ARITHMETIC EXPRESSIONS
print("""
=== 7. Arithmetic Expressions ===

L = expressions with +, *, (, ), id

DPDA (parser):
  This is what LR parsers do!
  
  States: LR item sets
  Stack: states + symbols
  
  Actions:
    Shift: push next token
    Reduce: pop and apply grammar rule
    Accept: done
    Error: reject

Deterministic: ✓
  - LR(1) parsing table gives unique action

Parsing:
  'id + id * id'
  Shift id → reduce to F → reduce to T → ...
  Shift + → shift id → reduce to F → shift * → ...
  Reduce to T → reduce to E → accept
""")

# 8. PROGRAMMING LANGUAGE SYNTAX
print("""
=== 8. Programming Language Syntax ===

All practical programming languages are DCFLs.

Example: Simplified C-like language
  Program → StmtList
  StmtList → Stmt StmtList | ε
  Stmt → id = Expr ;
       | if ( Expr ) Stmt
       | { StmtList }
  Expr → Expr + Term | Term
  Term → Term * Factor | Factor
  Factor → id | ( Expr )

This is a DCFG (deterministic CFG).
Parsed by LR or LL parser in O(n).

The DPDA is the parser:
  - Stack holds partial parse
  - Deterministic actions
  - No backtracking
""")

# 9. NON-EXAMPLE: PALINDROMES
print("""
=== 9. NOT DCFL: Palindromes ===

L = { w | w = wᴿ }

This is CFL but NOT DCFL!

Why? The DPDA can't know when the middle is.

Attempted DPDA:
  - Push first half
  - When to switch to popping?
  
Problem: No marker tells us the middle!
  'aba' — middle is 'b'
  'abba' — middle is between 'b' and 'b'
  
A DPDA would need to guess the middle.
Guessing = nondeterminism.

=== Proof Idea ===

Assume DPDA M for palindromes.
Consider strings a^n b a^n and a^n b b a^n.
M must behave the same on both until the middle.
But then it can't distinguish them.
Contradiction.

(Formal proof uses more advanced techniques.)
""")

# 10. NON-EXAMPLE: EQUAL COUNTS
print("""
=== 10. NOT DCFL: Equal a's and b's ===

L = { w | #a(w) = #b(w) }

This is CFL but NOT DCFL!

Why? The order of a's and b's is arbitrary.

A DPDA would need to:
  - Push A for 'a', pop A for 'b'
  - OR push B for 'b', pop B for 'a'
  - But it must choose!
  
If it chooses wrong, it fails.

Nondeterministic PDA:
  - Try both strategies
  - Accept if either works

Deterministic PDA:
  - Must commit to one strategy
  - Can't handle all cases

=== Key Insight ===

The DPDA can't know in advance whether
there will be more a's or more b's first.

So it can't decide which symbol to push.
""")

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



  
  
    🚫 Non-DPDA Languages
    🎯 Languages That Need Nondeterminism
Some context-free languages are not deterministic — no DPDA can recognize them. These languages require guessing or nondeterministic choice.
     Why Some CFLs Are Not DCFLs
Guessing: Need to guess middle. Ambiguity: Multiple valid structures. Choice: Must commit without info. Palindromes: Classic non-DCFL. Equal counts: Order-independent. Union: Disjoint DCFLs may not be DCFL.
🎲 Guessing🔀 Ambiguity❓ No info📉 Strict subset
    # Non-DPDA Languages
print("=" * 60)
print("NON-DPDA LANGUAGES")
print("=" * 60)

print("""
=== What Makes a Language Non-DCFL? ===

A language is NOT DCFL if every PDA for it
requires nondeterminism — i.e., some configuration
must have multiple possible moves.

Common reasons:
  1. GUESSING: Need to guess a position (e.g., middle)
  2. CHOICE: Must choose between strategies without info
  3. AMBIGUITY: Multiple valid parse structures
  4. UNION: Combining two DCFLs may not be DCFL
""")

# 1. PALINDROMES
print("""
=== 1. Palindromes: { w | w = wᴿ } ===

STATUS: CFL but NOT DCFL

WHY NOT DCFL:
  A DPDA must decide when to switch from
  "pushing" to "popping" mode.
  
  The switch should happen at the middle.
  But the DPDA doesn't know where the middle is!
  
  Example: aabaa
    - Push a, push a, push b
    - Now at 'a' — is this the middle?
    - If we switch now, we need to match a, then a
    - But we still have 'a' and 'a' left in input
    - We don't know if the string is aabaa or aabaabaa
    
  A nondeterministic PDA can GUESS the middle.
  A DPDA cannot.

FORMAL PROOF SKETCH:
  Assume DPDA M recognizes palindromes.
  Consider inputs a^n b a^n and a^n b b a^n.
  M must process the first a^n b identically
  (same state, same stack) because it can't
  know which string it's reading.
  But then M must accept a^n b a^n and reject
  a^n b b a^n — contradiction.
""")

# 2. EQUAL A'S AND B'S
print("""
=== 2. Equal Counts: { w | #a(w) = #b(w) } ===

STATUS: CFL but NOT DCFL

WHY NOT DCFL:
  The DPDA must choose a strategy:
    Strategy A: Push A for 'a', pop A for 'b'
    Strategy B: Push B for 'b', pop B for 'a'
  
  But it must choose WITHOUT knowing the input!
  
  If input is "ab":
    Strategy A: push A, pop A → accept
    Strategy B: push B, pop B → accept (but different!)
  
  If input is "aabb":
    Strategy A: push A, push A, pop A, pop A → accept
    Strategy B: fails (b comes before a in stack)
  
  The DPDA can't know which strategy will work.
  
  Nondeterministic PDA: try both, accept if any works.
  Deterministic PDA: must commit, may fail.

=== Proof Sketch ===

Assume DPDA M for equal counts.
Consider a^n b^n and b^n a^n.
M must process a^n identically in both.
But a^n b^n ∈ L and a^n b^n ∉ L...
(Actually a^n b^n ∈ L and b^n a^n ∈ L too.)
Need a different argument — use intersection with
a*b* to get a^n b^n, then show the DPDA must
behave deterministically on a*b*... 
The formal proof is more involved.
""")

# 3. AMBIGUOUS UNION
print("""
=== 3. Union of DCFLs May Not Be DCFL ===

L1 = { aⁱbⁱcʲ | i,j ≥ 0 }  — DCFL
L2 = { aⁱbʲcʲ | i,j ≥ 0 }  — DCFL

L1 ∪ L2 = { aⁱbⁱcʲ } ∪ { aⁱbʲcʲ }
        = { aⁱbʲcᵏ | i=j or j=k }

Is L1 ∪ L2 DCFL?
NO! This is a classic non-DCFL.

WHY:
  A DPDA reading a's and b's must decide:
    - Is this L1 (match a's with b's)?
    - Is this L2 (match b's with c's)?
  
  It can't know until it sees the c's.
  But by then, it's too late to change strategy.

  This is a "lookahead" problem.
  Nondeterministic PDA can try both.
  Deterministic PDA cannot.

=== Formal Proof ===

This language is inherently ambiguous.
Every grammar for it is ambiguous.
DCFLs have unambiguous grammars.
Therefore, not DCFL.
""")

# 4. COMPLEMENT OF PALINDROMES
print("""
=== 4. Complement of Palindromes ===

L = { w | w ≠ wᴿ } (non-palindromes)

Is this DCFL?
Actually YES — the complement of palindromes IS DCFL!

Wait, that's surprising. Let me reconsider.

Palindromes: NOT DCFL
Complement: DCFL?

This is possible because DCFLs are closed under complement!
If palindromes were DCFL, complement would be DCFL.
But palindromes are NOT DCFL.
So complement is... NOT necessarily DCFL either?

Actually: DCFLs are closed under complement.
So if L is DCFL, complement is DCFL.
If L is NOT DCFL, complement may or may not be DCFL.

For palindromes:
  Palindromes are NOT DCFL.
  Non-palindromes ARE DCFL! (Can check with a DPDA.)
  
So the complement of a non-DCFL can be DCFL.
""")

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

STATUS: NOT CFL (not even context-free!)

WHY NOT CFL:
  Need to remember the first half AND compare
  with the second half.
  
  Stack is LIFO — stores first half in reverse.
  When reading second half, we need it in forward order.
  Can't match!
  
  (Formal proof uses CFL pumping lemma.)

Since not CFL, definitely not DCFL.
""")

# 6. A^N B^N C^N
print("""
=== 6. aⁿbⁿcⁿ ===

STATUS: NOT CFL

WHY NOT CFL:
  Need TWO counters:
    - Match a's with b's
    - Match b's with c's
  
  One stack = one counter.
  After matching a's with b's, stack is empty.
  Nothing left for c's.
  
  (Formal proof uses CFL pumping lemma.)
""")

# PROOF TECHNIQUES
print("=== Proof Techniques for Non-DCFL ===")
print("""
To prove L is NOT DCFL:

1. DIRECT ARGUMENT
   Show that any DPDA would need to guess.
   Often uses "the DPDA must process x and y identically
   but then can't distinguish them."

2. AMBIGUITY
   Show L is inherently ambiguous.
   DCFLs have unambiguous grammars.
   Inherently ambiguous → not DCFL.

3. CLOSURE PROPERTIES
   If L were DCFL, then some operation
   would give a known non-DCFL.
   
   Example: If L1 ∪ L2 were DCFL...
   
4. INTERSECTION WITH REGULAR
   If L is DCFL, then L ∩ R is DCFL (R regular).
   If L ∩ R is not DCFL, then L is not DCFL.

5. PUMPING LEMMA (for DCFL)
   There's a pumping lemma for DCFLs too!
   More complex than CFL version.
""")

# SUMMARY TABLE
print("=== Summary Table ===")
print(f"{'Language':<35} {'CFL?':<10} {'DCFL?':<10} {'Reason':<25}")
print("-" * 80)
print(f"{'Palindromes':<35} {'Yes':<10} {'NO':<10} {'Need guessing':<25}")
print(f"{'Equal a,b':<35} {'Yes':<10} {'NO':<10} {'Need choice':<25}")
print(f"{'{ aⁱbⁱcʲ } ∪ { aⁱbʲcʲ }':<35} {'Yes':<10} {'NO':<10} {'Ambiguous union':<25}")
print(f"{'wcwᴿ':<35} {'Yes':<10} {'Yes':<10} {'Marker c':<25}")
print(f"{'aⁿbⁿ':<35} {'Yes':<10} {'Yes':<10} {'Push/pop':<25}")
print(f"{'ww':<35} {'NO':<10} {'NO':<10} {'Not CFL':<25}")
print(f"{'aⁿbⁿcⁿ':<35} {'NO':<10} {'NO':<10} {'Not CFL':<25}")

# THE BIG PICTURE
print("""
=== The Big Picture ===

        Regular
           ↓
        DCFL  ← Programming languages
           ↓
        CFL   ← Natural language (approx)
           ↓
        CSL
           ↓
        RE

DCFL sits between regular and CFL.
It's the "practical" class:
  - More powerful than regular
  - Efficient to parse (O(n))
  - Deterministic
  - Closed under complement

Most real-world languages are DCFLs.
Theoretical CFLs that aren't DCFL
(palindromes, equal counts) rarely appear
in practice because they're hard to parse.
""")
  

  
  
    🔍 DPDA & LR Parsing
    🎯 DPDAs Are Parsers
The most important application of DPDAs is LR parsing — the algorithm used by Yacc, Bison, and many compiler tools. An LR parser is essentially a DPDA with a specific structure.
     LR Parsing as DPDA
Stack: States + grammar symbols. States: LR item sets. Actions: Shift, reduce, accept, error. Deterministic: Unique action per config. Time: O(n). Space: O(n) stack.
📚 Stack🎯 LR items⬆️ Shift⬇️ Reduce
    # DPDA and LR Parsing
print("=" * 60)
print("DPDA & LR PARSING")
print("=" * 60)

print("""
=== LR Parsing = DPDA ===

An LR parser is a DPDA with:
  - States: LR(1) item sets
  - Stack: holds states and grammar symbols
  - Input: token stream
  - Actions: shift, reduce, accept, error

The parser is DETERMINISTIC:
  - Parsing table gives exactly one action
  - For each (state, lookahead) pair
  - No backtracking, no guessing

=== LR Parsing Algorithm ===

Configuration: (stack, input)
  stack = s₀ X₁ s₁ X₂ s₂ ... Xₘ sₘ
  input = a₁ a₂ ... aₙ

At each step:
  1. Look at top state sₘ and next input aᵢ
  2. Consult ACTION[sₘ, aᵢ]:
     - Shift s: push aᵢ, push s
     - Reduce A → β: pop 2|β| symbols, push A, push GOTO
     - Accept: done
     - Error: reject

This is exactly a DPDA transition!
""")

# LR PARSER IN CODE
print("=== LR Parser Implementation ===")

class LRParser:
    """
    A simple LR parser (DPDA).
    Grammar:
      E → E + T | T
      T → T * F | F
      F → ( E ) | id
    """
    def __init__(self):
        # Simplified parsing table
        # ACTION[state][token] = ('shift', next_state) or ('reduce', rule) or 'accept'
        self.action = {
            0: {'id': ('shift', 5), '(': ('shift', 4)},
            1: {'+': ('shift', 6), '$': 'accept'},
            2: {'+': ('reduce', 'E→T'), '*': ('shift', 7), ')': ('reduce', 'E→T'), '$': ('reduce', 'E→T')},
            3: {'+': ('reduce', 'T→F'), '*': ('reduce', 'T→F'), ')': ('reduce', 'T→F'), '$': ('reduce', 'T→F')},
            4: {'id': ('shift', 5), '(': ('shift', 4)},
            5: {'+': ('reduce', 'F→id'), '*': ('reduce', 'F→id'), ')': ('reduce', 'F→id'), '$': ('reduce', 'F→id')},
            6: {'id': ('shift', 5), '(': ('shift', 4)},
            7: {'id': ('shift', 5), '(': ('shift', 4)},
            8: {'+': ('shift', 6), ')': ('shift', 11)},
            9: {'+': ('reduce', 'E→E+T'), '*': ('shift', 7), ')': ('reduce', 'E→E+T'), '$': ('reduce', 'E→E+T')},
            10: {'+': ('reduce', 'T→T*F'), '*': ('reduce', 'T→T*F'), ')': ('reduce', 'T→T*F'), '$': ('reduce', 'T→T*F')},
            11: {'+': ('reduce', 'F→(E)'), '*': ('reduce', 'F→(E)'), ')': ('reduce', 'F→(E)'), '$': ('reduce', 'F→(E)')},
        }
        
        self.goto = {
            0: {'E': 1, 'T': 2, 'F': 3},
            4: {'E': 8, 'T': 2, 'F': 3},
            6: {'T': 9, 'F': 3},
            7: {'F': 10},
        }
        
        self.rules = {
            'E→E+T': ('E', 3),
            'E→T': ('E', 1),
            'T→T*F': ('T', 3),
            'T→F': ('T', 1),
            'F→(E)': ('F', 3),
            'F→id': ('F', 1),
        }
    
    def parse(self, tokens):
        """Parse token list. Returns True if accepted."""
        stack = [0]  # state stack
        pos = 0
        tokens = tokens + ['$']
        
        while True:
            state = stack[-1]
            token = tokens[pos]
            
            action = self.action.get(state, {}).get(token)
            
            if action is None:
                return False  # error
            
            if action == 'accept':
                return True
            
            if action[0] == 'shift':
                stack.append(action[1])
                pos += 1
            
            elif action[0] == 'reduce':
                rule = action[1]
                lhs, length = self.rules[rule]
                # Pop 2*length symbols (state + symbol pairs)
                for _ in range(2 * length):
                    stack.pop()
                # GOTO
                top_state = stack[-1]
                next_state = self.goto.get(top_state, {}).get(lhs)
                if next_state is None:
                    return False
                stack.append(next_state)


# Test
parser = LRParser()
test_inputs = [
    ['id'],
    ['id', '+', 'id'],
    ['id', '*', 'id'],
    ['id', '+', 'id', '*', 'id'],
    ['(', 'id', '+', 'id', ')', '*', 'id'],
    ['id', '+'],
    ['+', 'id'],
]

print("LR Parser for expressions:")
print(f"{'Input':<30} {'Result':<15}")
print("-" * 45)
for tokens in test_inputs:
    result = parser.parse(tokens)
    input_str = ' '.join(tokens)
    print(f"{input_str:<30} {'✓ ACCEPT' if result else '✗ REJECT':<15}")

# LR PARSER AS DPDA
print("""
=== LR Parser as DPDA ===

Mapping:
  DPDA states     ↔  LR parser states (item sets)
  DPDA stack      ↔  LR stack (states + symbols)
  DPDA input      ↔  Token stream
  DPDA transitions ↔  ACTION/GOTO tables
  DPDA accept     ↔  Accept action

The parser is deterministic:
  - ACTION[state, token] is a single action
  - No conflicts (for LR(1) grammars)
  - O(n) time, O(n) space

=== Why LR Parsing Works ===

LR(k) grammars are exactly the DCFGs.
LR(1) is sufficient for most programming languages.
LALR(1) is a practical compromise (smaller tables).

Tools:
  - Yacc/Bison: LALR(1)
  - CUP: LALR(1)
  - ANTLR: LL(*), also deterministic
  - JavaCC: LL(k)

All these are DPDA-based parsers!
""")

# LL PARSING
print("""
=== LL Parsing (Also DPDA) ===

LL(k) parsers are also DPDAs.

Configuration:
  stack = expected symbols
  input = remaining tokens

Actions:
  - If top is nonterminal: expand using grammar rule
  - If top is terminal: match with input
  - Accept when both empty

LL(1) parsing table:
  M[A, a] = rule to apply
  Deterministic: one rule per (nonterminal, lookahead)

Difference from LR:
  - LL: top-down (predict then match)
  - LR: bottom-up (shift then reduce)
  - Both are DPDAs
  - LL is simpler, LR is more powerful
""")

# DETERMINISTIC PARSING IN PRACTICE
print("""
=== Deterministic Parsing in Practice ===

Programming languages are designed to be:
  1. DCFL (deterministic)
  2. Unambiguous
  3. Parseable in O(n)

Design choices:
  - Keywords (if, else, while) — avoid ambiguity
  - Braces { } — explicit nesting
  - Semicolons — statement terminators
  - Operator precedence — defined by grammar layers

These choices ensure:
  - DPDA can parse unambiguously
  - Compiler can give good error messages
  - Performance is predictable

=== Example: Python's Indentation ===

Python uses indentation instead of braces.
This requires a slightly more complex lexer
but the parser is still deterministic.

The parser uses a stack to track indentation levels.
This is still a DPDA (with some preprocessing).

=== Example: C's Dangling Else ===

C has the dangling else problem:
  if (a) if (b) x; else y;
  
Is else with inner or outer if?
C resolves this: else matches nearest if.

This is a grammar design choice to keep
the language deterministic.

The 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 nearest if.
""")

# SUMMARY
print("=== Summary ===")
print("""
DPDA = Deterministic Parser

LR parsing:
  - DPDA with item-set states
  - Shift/reduce actions
  - O(n) time
  - Used by Yacc, Bison

LL parsing:
  - DPDA with grammar symbols on stack
  - Predict/match actions
  - O(n) time
  - Used by ANTLR, recursive descent

Both are deterministic.
Both handle DCFLs.
Both are practical.

Programming languages = DCFLs = DPDA-parseable.
This is the fundamental connection between
automata theory and compiler construction.
""")
  

  
  
    📗 Deterministic CFGs
    🎯 Grammars for DPDAs
Deterministic Context-Free Grammars (DCFGs) are grammars that can be parsed deterministically. They generate exactly the DCFLs and have unambiguous parse trees.
     DCFG Properties
Unambiguous: One parse tree per string. LR(k): Parseable by LR(k). DPDA: Equivalent to DPDAs. DCFL: Generate DCFLs. Practical: Programming languages. Efficient: O(n) parsing.
🌳 Unambiguous🔍 LR(k)⚙️ DPDA📗 DCFL
    # Deterministic CFGs
print("=" * 60)
print("DETERMINISTIC CONTEXT-FREE GRAMMARS (DCFGs)")
print("=" * 60)

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

A CFG G is DETERMINISTIC if:
  1. It is unambiguous
  2. It can be parsed by an LR(k) parser
  3. It is equivalent to some DPDA

DCFG = grammar for a DCFL

=== LR(k) Grammars ===

LR(k) grammars are a specific class of DCFGs.

Properties:
  - Left-to-right scan
  - Rightmost derivation (in reverse)
  - k tokens of lookahead
  - Deterministic parsing

LR(1) is sufficient for most languages.
LALR(1) is a practical simplification.
SLR(1) is a further simplification.

=== Unambiguity ===

DCFGs are always unambiguous:
  - Each string has exactly ONE parse tree
  - This is required for deterministic parsing
  - If a grammar is ambiguous, it's not DCFG

However: Unambiguous ≠ DCFG!
  Some unambiguous CFGs are not DCFGs.
  (e.g., some grammars for palindromes)
""")

# LR ITEMS AND PARSING
print("=== LR Items ===")
print("""
An LR item is a production with a dot:
  A → α · β

Meaning: we've seen α, expecting β.

Example: Rule E → E + T

Items:
  E → · E + T    (start)
  E → E · + T    (seen E)
  E → E + · T    (seen E +)
  E → E + T ·    (complete)

=== LR(1) Items ===

An LR(1) item includes lookahead:
  [A → α · β, a]

Meaning: if we reduce A → αβ,
we must see lookahead a.

=== Closure and Goto ===

CLOSURE(I): add items for nonterminals after dot.
GOTO(I, X): move dot over X.

These define the LR automaton.

=== Example: Expression Grammar ===

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

LR(1) automaton has ~12 states.
Each state is a set of LR(1) items.
Parsing table is built from this automaton.
""")

# BUILDING DCFG
print("=== Building a DCFG ===")
print("""
To design a DCFG for a language:

1. START WITH AN UNAMBIGUOUS CFG
   - Layered grammar (E, T, F)
   - Explicit precedence

2. CHECK FOR LR CONFLICTS
   - Shift/reduce conflicts
   - Reduce/reduce conflicts

3. RESOLVE CONFLICTS
   - Use precedence and associativity
   - Rewrite grammar

4. VERIFY WITH PARSER GENERATOR
   - Yacc/Bison reports conflicts
   - Test with sample inputs

=== Example: Expression Grammar ===

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

This is LR(1) — no conflicts!
Parsed by yacc/bison without issues.

=== Example: Dangling Else ===

Ambiguous:
  S → if E then S | if E then S else S | other

Unambiguous (but not LR):
  S → M | U
  M → if E then M else M | other
  U → if E then S | if E then M else U

This is LR(1) — resolved!

Actually, many parser generators handle
dangling else with precedence rules.
""")

# DCFG VS CFG
print("=== DCFG vs CFG ===")
print(f"{'Aspect':<30} {'DCFG':<25} {'CFG':<25}")
print("-" * 80)
print(f"{'Ambiguity':<30} {'Unambiguous':<25} {'May be ambiguous':<25}")
print(f"{'Parsing':<30} {'O(n) LR':<25} {'O(n³) CYK':<25}")
print(f"{'Machine':<30} {'DPDA':<25} {'NPDA':<25}")
print(f"{'Language class':<30} {'DCFL':<25} {'CFL':<25}")
print(f"{'Complement':<30} {'Closed':<25} {'NOT closed':<25}")
print(f"{'Union':<30} {'NOT closed':<25} {'Closed':<25}")
print(f"{'Equivalence':<30} {'Decidable':<25} {'Undecidable':<25}")
print(f"{'Practical':<30} {'Compilers':<25} {'NLP, theory':<25}")

# EXAMPLE: EXPRESSION GRAMMAR
print("=== Example: Expression Grammar (LR(1)) ===")
print("""
Grammar:
  E → E + T | T
  T → T * F | F
  F → ( E ) | id

This grammar is:
  ✓ Unambiguous
  ✓ LR(1)
  ✓ DCFG
  ✓ Parsed in O(n)

Parse of "id + id * id":

Stack                  Input           Action
0                      id + id * id $  shift 5
0 id 5                 + id * id $     reduce F→id
0 F 3                  + id * id $     reduce T→F
0 T 2                  + id * id $     reduce E→T
0 E 1                  + id * id $     shift 6
0 E 1 + 6              id * id $       shift 5
0 E 1 + 6 id 5         * id $          reduce F→id
0 E 1 + 6 F 3          * id $          reduce T→F
0 E 1 + 6 T 9          * id $          shift 7
0 E 1 + 6 T 9 * 7      id $            shift 5
0 E 1 + 6 T 9 * 7 id 5 $               reduce F→id
0 E 1 + 6 T 9 * 7 F 10 $               reduce T→T*F
0 E 1 + 6 T 9          $               reduce E→E+T
0 E 1                  $               accept

Notice: No backtracking, no guessing.
Each step is deterministic.
""")

# PARSER GENERATORS
print("=== Parser Generators ===")
print("""
Parser generators take a DCFG and produce
a DPDA-based parser.

YACC/BISON:
  Input: LALR(1) grammar
  Output: C parser
  Conflicts: reported
  Resolution: precedence/associativity

ANTLR:
  Input: LL(*) grammar
  Output: Java/Python/... parser
  Conflicts: reported
  Resolution: grammar rules

JAVACC:
  Input: LL(k) grammar
  Output: Java parser
  Conflicts: reported

These tools make DPDA construction automatic.

=== Example: Bison Grammar ===

%token ID
%left '+'
%left '*'

%%

E : E '+' T   { $$ = $1 + $3; }
  | T         { $$ = $1; }
  ;

T : T '*' F   { $$ = $1 * $3; }
  | F         { $$ = $1; }
  ;

F : '(' E ')' { $$ = $2; }
  | ID        { $$ = $1; }
  ;

%%

The %left declarations resolve conflicts.
Bison generates an LALR(1) parser.
""")

# SUMMARY
print("=== Summary ===")
print("""
DCFG:
  - Deterministic CFG
  - Unambiguous
  - LR(k) parseable
  - Equivalent to DPDA
  - Generates DCFL

Key relationships:
  DCFG = DPDA = DCFL = LR(k) grammar

Practical:
  - Programming languages are DCFGs
  - Parser generators build DPDAs
  - O(n) parsing is possible
  - No backtracking needed

Why it matters:
  Deterministic parsing is efficient.
  DCFGs guarantee efficiency.
  This is why programming language
  designers aim for DCFGs.
""")
  

  
  
    🔒 Closure Properties
    🎯 What Operations Preserve DCFLs?
DCFLs have different closure properties than CFLs. They are closed under complement but not under union. This is the opposite of CFLs!
     Closure Properties of DCFLs
Closed under: Complement, reversal, ∩ regular, inverse homomorphism. NOT closed under: Union, intersection, concat, star, homomorphism. Contrast: Opposite of CFLs. Why: Determinism changes closure. Proof: Constructive.
✅ Complement✅ ∩ Regular❌ Union❌ Concat
    # Closure Properties of DCFLs
print("=" * 60)
print("CLOSURE PROPERTIES OF DCFLs")
print("=" * 60)

print("""
=== Operations that PRESERVE DCFLs ===

✓ COMPLEMENT: L^c is DCFL if L is DCFL
  Proof: Swap accept and non-accept states in DPDA.
  Need to handle "stuck" configurations carefully.
  
✓ REVERSAL: L^R is DCFL if L is DCFL
  Proof: Reverse DPDA transitions.

✓ INTERSECTION WITH REGULAR: L ∩ R is DCFL
  Proof: Product construction (DPDA × DFA).

✓ INVERSE HOMOMORPHISM: h⁻¹(L) is DCFL
  Proof: Modify input reading.

✓ MIN (prefix-free): min(L) is DCFL
  (When L is prefix-free)

=== Operations that DO NOT PRESERVE ===

✗ UNION: L1 ∪ L2 may not be DCFL
  Counterexample:
    L1 = { aⁱbⁱcʲ | i,j ≥ 0 }  (DCFL)
    L2 = { aⁱbʲcʲ | i,j ≥ 0 }  (DCFL)
    L1 ∪ L2 = { aⁱbʲcᵏ | i=j or j=k }  (NOT DCFL)

✗ INTERSECTION: L1 ∩ L2 may not be DCFL
  Counterexample: Similar.

✗ CONCATENATION: L1 · L2 may not be DCFL

✗ KLEENE STAR: L* may not be DCFL

✗ HOMOMORPHISM: h(L) may not be DCFL
""")

# COMPLEMENT CLOSURE
print("=== Complement Closure ===")
print("""
DCFLs are CLOSED under complement!

This is surprising because CFLs are NOT.

PROOF:
  Given DPDA M = (Q, Σ, Γ, δ, q₀, Z₀, F)
  
  Construct M' for complement:
    - Same states, transitions
    - Accept states = Q \ F (swap)
    - Handle "stuck" configurations: add a reject state
    - Accept if M rejects
  
  Problem: M may get stuck (no transition).
  Need to handle this.
  
  Solution: Add explicit reject state.
  - If no transition available, go to reject
  - If input ends in non-accept, accept
  
  M' accepts exactly when M rejects.

=== Why This Works ===

DPDA has a UNIQUE computation path.
So for each input:
  - M either accepts or rejects (no ambiguity)
  - M' accepts exactly when M rejects

For NPDAs, this doesn't work:
  - Multiple paths may accept
  - Swapping doesn't give complement
""")

# UNION NON-CLOSURE
print("=== Union Non-Closure ===")
print("""
DCFLs are NOT closed under union!

Counterexample:

L1 = { aⁱbⁱcʲ | i,j ≥ 0 }  — DCFL
  (Match a's and b's; c's are free)

L2 = { aⁱbʲcʲ | i,j ≥ 0 }  — DCFL
  (Match b's and c's; a's are free)

L1 ∪ L2 = { aⁱbʲcᵏ | i=j or j=k }

Is this DCFL? NO!

WHY:
  A DPDA reading a's and b's must decide:
    - Is this L1 (match a's with b's)?
    - Is this L2 (match b's with c's)?
  
  It can't know until it sees the c's.
  But by then, it's too late to change strategy.
  
  This is an inherent ambiguity:
    The string aⁱbⁱcⁱ is in both L1 and L2.
    Every grammar has two parse trees for it.
    So the language is ambiguous.
    DCFLs are unambiguous.
    Therefore, not DCFL.

=== Key Insight ===

Nondeterminism helps with union:
  - Try L1's strategy
  - Or try L2's strategy
  - Accept if either works

Determinism prevents this:
  - Must commit to one strategy
  - Can't try both
""")

# INTERSECTION WITH REGULAR
print("=== Intersection with Regular ===")
print("""
DCFL ∩ Regular = DCFL

PROOF:
  Given DPDA M and DFA D:
  - Construct product DPDA M'
  - States: Q_M × Q_D
  - Transitions: simulate both
  - Accept: both accept
  
  M' is deterministic (since both M and D are).
  So M' is a DPDA.
  Therefore L(M) ∩ L(D) is DCFL.

This is useful for proving non-DCFL:
  If L ∩ R is not DCFL (R regular),
  then L is not DCFL.

Example:
  L = { aⁱbʲcᵏ | i=j or j=k }
  R = a*b*c* (regular)
  L ∩ R = L (trivially)
  Not helpful directly.
  
  But: L ∩ aⁱbⁱc* = { aⁱbⁱcᵏ | i=k? no... }
  Hmm, need to be careful.
  
  Actually: L ∩ a*b*c* = L.
  We already know L is not DCFL.
  So this just confirms.
""")

# COMPARISON TABLE
print("=== Closure Comparison: DCFL vs CFL ===")
print(f"{'Operation':<30} {'Regular':<12} {'DCFL':<12} {'CFL':<12}")
print("-" * 70)
print(f"{'Union':<30} {'✓':<12} {'✗':<12} {'✓':<12}")
print(f"{'Intersection':<30} {'✓':<12} {'✗':<12} {'✗':<12}")
print(f"{'Complement':<30} {'✓':<12} {'✓':<12} {'✗':<12}")
print(f"{'Difference':<30} {'✓':<12} {'✗':<12} {'✗':<12}")
print(f"{'Concatenation':<30} {'✓':<12} {'✗':<12} {'✓':<12}")
print(f"{'Kleene Star':<30} {'✓':<12} {'✗':<12} {'✓':<12}")
print(f"{'Reversal':<30} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'∩ Regular':<30} {'✓':<12} {'✓':<12} {'✓':<12}")
print(f"{'Homomorphism':<30} {'✓':<12} {'✗':<12} {'✓':<12}")
print(f"{'Inverse Homomorphism':<30} {'✓':<12} {'✓':<12} {'✓':<12}")

print("""
=== Interesting Patterns ===

Regular:  Closed under almost everything.
DCFL:     Closed under complement, NOT union.
CFL:      Closed under union, NOT complement.

Why the difference?
  - Nondeterminism (CFL) helps with union
  - Determinism (DCFL) helps with complement
  - You can't have both simultaneously!

This is a fundamental trade-off:
  More closure properties vs more expressiveness.

DCFL is less expressive but has better closure.
CFL is more expressive but has worse closure.
""")

# DECISION PROBLEMS
print("=== Decision Problems ===")
print(f"{'Problem':<30} {'DCFL':<15} {'CFL':<15}")
print("-" * 60)
print(f"{'Membership':<30} {'O(n)':<15} {'O(n³)':<15}")
print(f"{'Emptiness':<30} {'Decidable':<15} {'Decidable':<15}")
print(f"{'Finiteness':<30} {'Decidable':<15} {'Decidable':<15}")
print(f"{'Equivalence':<30} {'Decidable':<15} {'Undecidable':<15}")
print(f"{'Ambiguity':<30} {'Always unambig':<15} {'Undecidable':<15}")
print(f"{'Universality':<30} {'Decidable':<15} {'Undecidable':<15}")
print(f"{'Inclusion':<30} {'Decidable':<15} {'Undecidable':<15}")

print("""
=== Why Equivalence is Decidable for DCFLs ===

Given DPDAs M1, M2:
  1. Compute canonical DPDA for each
  2. Compare (isomorphic?)
  3. Decidable

The key: DPDAs have canonical forms.
NPDAs don't have such canonical forms.

For CFLs:
  - No canonical form
  - Equivalence is undecidable

=== Why Universality is Decidable ===

Given DPDA M:
  Is L(M) = Σ*?
  
  Equivalently: Is complement empty?
  Complement of DCFL is DCFL (closure).
  Emptiness of DCFL is decidable.
  So universality is decidable.

For CFLs:
  Complement is not necessarily CFL.
  So this approach fails.
  Universality is undecidable.
""")

# SUMMARY
print("=== Summary ===")
print("""
DCFL Closure:
  ✓ Complement
  ✓ Reversal
  ✓ ∩ Regular
  ✓ Inverse homomorphism
  ✗ Union
  ✗ Intersection
  ✗ Concatenation
  ✗ Kleene Star
  ✗ Homomorphism

DCFL Decision:
  ✓ Membership O(n)
  ✓ Emptiness
  ✓ Finiteness
  ✓ Equivalence
  ✓ Universality
  ✓ Inclusion

Key insight:
  DCFLs are less expressive than CFLs
  but have much better closure and decision properties.
  
  This trade-off is why programming languages
  are designed as DCFLs: we can parse them
  efficiently and verify properties.
""")
  

  
  
    ✅ Decision Problems
    🎯 What Can We Decide About DPDAs?
DPDAs have better decision properties than general PDAs. Equivalence, universality, and inclusion are all decidable for DPDAs but undecidable for NPDAs.
     Decidable Problems
Membership: O(n) simulation. Emptiness: Reachability check. Finiteness: Cycle detection. Equivalence: Canonical forms. Universality: Complement emptiness. Inclusion: L1 ∩ L2^c = ∅.
✅ Decidable⏱️ Efficient🔄 Canonical🔍 Compare
    # Decision Problems for DPDAs
print("=" * 60)
print("DECISION PROBLEMS FOR DPDAs")
print("=" * 60)

print("""
=== Comparison: DPDA vs NPDA ===

Problem          DPDA          NPDA
─────────────────────────────────────
Membership       O(n)          O(n³)
Emptiness        Decidable     Decidable
Finiteness       Decidable     Decidable
Equivalence      Decidable     Undecidable
Universality     Decidable     Undecidable
Inclusion        Decidable     Undecidable
Ambiguity        Always unambig  Undecidable
Intersection     Not always    Not always
Complement       Closed        Not closed

The key difference:
  DPDAs have CANONICAL FORMS.
  NPDAs don't.
  
Canonical forms enable comparison and decision.
""")

# MEMBERSHIP
print("=== Membership ===")
print("""
Problem: Given DPDA M and string w, is w ∈ L(M)?

Algorithm:
  Simulate M on w.
  Since M is deterministic, there's one path.
  Accept if that path accepts.

Time: O(|w|)
Space: O(|w|) for stack

This is optimal — must read input at least once.

=== Why O(n)? ===

Each input symbol triggers at most one transition.
Stack operations are O(1) amortized.
So total time is proportional to input length.

Compare to NPDA:
  Must track all possible configurations.
  O(n³) in worst case.
  
Determinism gives a huge speedup!
""")

# EMPTINESS
print("=== Emptiness ===")
print("""
Problem: Given DPDA M, is L(M) = ∅?

Algorithm:
  Search for a path from start to an accept state.
  This is reachability in the configuration graph.
  
  Configuration graph: potentially infinite
  (stack can grow unboundedly).
  
  But we can use a finite abstraction:
    - States: Q × Γ (state + stack top)
    - This is finite (|Q| × |Γ|)
    - Transitions: from (q, Z) to (q', Z') if
      there's a transition that pops Z and pushes Z' on top
  
  Accept if some (q, Z) is reachable and q ∈ F.

Time: O(|Q|² × |Γ|)
Space: O(|Q| × |Γ|)

=== Key Insight ===

Only the TOP of stack matters for future behavior.
So we can abstract the stack to just its top.
This gives a finite graph.
""")

# EQUIVALENCE
print("=== Equivalence ===")
print("""
Problem: Given DPDAs M1, M2, is L(M1) = L(M2)?

DECIDABLE for DPDAs!
UNDECIDABLE for NPDAs!

=== Algorithm ===

1. CONVERT TO CANONICAL FORM
   - Minimize DPDA
   - Remove redundant states
   - Canonical form is unique

2. COMPARE CANONICAL FORMS
   - Check if isomorphic
   - If yes: equivalent
   - If no: different

=== Why Canonical? ===

DPDAs have a notion of "minimal DPDA"
that is unique up to isomorphism.

This is similar to minimal DFA for regular languages.

NPDAs do NOT have unique minimal forms.
So comparison is impossible.

=== Complexity ===

Polynomial in the size of the DPDAs.
(Specifics depend on the algorithm.)

=== Implications ===

For programming languages:
  - Can check if two grammars define the same language
  - Can verify parser correctness
  - Can optimize by minimizing

This is why DCFGs are preferred for compilers!
""")

# UNIVERSALITY
print("=== Universality ===")
print("""
Problem: Given DPDA M, is L(M) = Σ*?

DECIDABLE for DPDAs!

=== Algorithm ===

1. COMPUTE COMPLEMENT
   Since DCFLs are closed under complement,
   complement(M) is a DCFL.
   
2. CHECK EMPTINESS
   Is complement(M) empty?
   
   - If yes: L(M) = Σ* ✓
   - If no: L(M) ≠ Σ* ✗

=== Why This Works ===

L(M) = Σ* ⟺ Σ* \ L(M) = ∅
         ⟺ complement(M) = ∅
         ⟺ complement(M) is empty

Both complement and emptiness are decidable.
So universality is decidable.

=== For NPDAs ===

Complement is not necessarily CFL.
So this approach fails.
Universality is undecidable.
""")

# INCLUSION
print("=== Inclusion ===")
print("""
Problem: Given DPDAs M1, M2, is L(M1) ⊆ L(M2)?

DECIDABLE for DPDAs!

=== Algorithm ===

L(M1) ⊆ L(M2)
  ⟺ L(M1) \ L(M2) = ∅
  ⟺ L(M1) ∩ complement(L(M2)) = ∅

Steps:
  1. Compute complement(M2) — closed under complement
  2. Compute intersection M1 ∩ complement(M2)
     (This is not always DCFL, but...)
  
  Wait, intersection is not closed!
  
  Better approach:
  1. Since DCFLs are closed under complement,
     compute complement(M2)
  2. Check if L(M1) ∩ complement(M2) = ∅
  
  But intersection may not be DCFL.
  
  Alternative:
  Use the fact that DCFL is closed under
  intersection with regular languages.
  But M1 is not regular...
  
  Actually: Inclusion IS decidable for DPDAs.
  The proof uses more advanced techniques
  (DPDA equivalence and complement).
  
  Simplified:
    L(M1) ⊆ L(M2) ⟺ L(M1) ∪ L(M2) = L(M2)
    But union is not closed...
  
  Correct approach:
    Use the fact that DPDAs have decidable
    equivalence and can be complemented.
    L(M1) ⊆ L(M2) ⟺ L(M1) ∩ L(M2)^c = ∅
    Both DPDAs can be complemented.
    The intersection emptiness problem for
    a DPDA and a DPDA... is decidable?
    
    Actually yes — inclusion is decidable.
    The proof is more involved.
""")

# DECISION PROCEDURES IN CODE
print("=== Decision Procedures in Code ===")

class DPDA:
    def __init__(self, states, input_alphabet, stack_alphabet,
                 transitions, q0, Z0, F):
        self.Q = states
        self.Sigma = input_alphabet
        self.Gamma = stack_alphabet
        self.delta = transitions
        self.q0 = q0
        self.Z0 = Z0
        self.F = F
    
    def accepts(self, w, max_steps=10000):
        """Membership test — O(n)."""
        state = self.q0
        idx = 0
        stack = (self.Z0,)
        
        for _ in range(max_steps):
            if idx == len(w) and (state in self.F or len(stack) == 0):
                return True
            
            if not stack:
                return idx == len(w)
            
            top = stack[0]
            
            if (state, 'ε', top) in self.delta:
                nq, push = self.delta[(state, 'ε', top)]
                stack = tuple(push) + stack[1:]
                state = nq
                continue
            
            if idx < len(w) and (state, w[idx], top) in self.delta:
                nq, push = self.delta[(state, w[idx], top)]
                stack = tuple(push) + stack[1:]
                state = nq
                idx += 1
                continue
            
            return False
        
        return False
    
    def is_empty(self):
        """Check if L(M) = ∅."""
        # Abstract configuration graph
        # States: Q × Γ (state + stack top)
        from collections import deque
        
        visited = set()
        queue = deque()
        
        # Start: (q0, Z0)
        start = (self.q0, self.Z0)
        queue.append(start)
        visited.add(start)
        
        while queue:
            q, Z = queue.popleft()
            
            # Check if accepting
            if q in self.F:
                return False  # non-empty!
            
            # Check empty stack acceptance
            # (If we can pop Z without pushing, stack may become empty)
            
            # Explore transitions
            for a in list(self.Sigma) + ['ε']:
                if (q, a, Z) in self.delta:
                    nq, push = self.delta[(q, a, Z)]
                    
                    if not push:
                        # Stack shrinks — may lead to empty
                        # This is tricky: we need to track
                        # the whole stack, not just top.
                        # For now, check if nq is accepting
                        if nq in self.F:
                            return False
                    else:
                        # New top is push[0]
                        new_top = push[0]
                        state = (nq, new_top)
                        if state not in visited:
                            visited.add(state)
                            queue.append(state)
        
        return True  # empty


# Example: a^n b^n
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',)),
    },
    q0='q0',
    Z0='Z',
    F={'q2'}
)

print("DPDA for a^n b^n")
print(f"  Empty? {dpda.is_empty()}")
print(f"  'aabb' accepted? {dpda.accepts('aabb')}")
print(f"  'aab' accepted? {dpda.accepts('aab')}")

# Empty DPDA
empty_dpda = DPDA(
    states={'q0'},
    input_alphabet={'a'},
    stack_alphabet={'Z'},
    transitions={},  # no transitions
    q0='q0',
    Z0='Z',
    F=set()  # no accept states
)

print(f"\nEmpty DPDA:")
print(f"  Empty? {empty_dpda.is_empty()}")

# SUMMARY
print("=== Summary ===")
print("""
DPDA Decision Problems:

✓ MEMBERSHIP: O(n)
  Simulate the DPDA.

✓ EMPTINESS: Decidable
  Abstract configuration graph.

✓ FINITENESS: Decidable
  Check for cycles in configuration graph.

✓ EQUIVALENCE: Decidable
  Compute canonical forms, compare.

✓ UNIVERSALITY: Decidable
  Complement + emptiness.

✓ INCLUSION: Decidable
  More complex, but decidable.

All these are UNDECIDABLE for NPDAs
(except membership, emptiness, finiteness).

Key insight:
  Determinism gives decidability.
  Canonical forms enable comparison.
  
This is why DPDAs are practical
and NPDAs are more theoretical.
""")
  

  
  
    💼 Applications
    🎯 DPDAs in the Real World
DPDAs are the theoretical foundation of parsing. Every compiler, interpreter, and data processing tool uses deterministic parsing based on DPDAs.
     Application Domains
Compilers: LR/LL parsing. Parsers: Yacc, Bison, ANTLR. Data formats: JSON, XML. Protocols: Message parsing. NLP: Deterministic parsing. Verification: Model checking.
💻 Compilers📝 Parsers📄 Data formats🔍 Verification
    # Applications of DPDAs
print("=" * 60)
print("APPLICATIONS OF DPDAs")
print("=" * 60)

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

The primary application of DPDAs.

Pipeline:
  Source → Lexer → Tokens → Parser (DPDA) → AST → Codegen

Parser:
  - LR(1) or LALR(1)
  - Deterministic
  - O(n) time
  - Built from DCFG

Example: GCC, Clang, javac
  All use deterministic parsers.

Why DPDA?
  - Fast (O(n))
  - Predictable
  - Good error messages
  - No backtracking
""")

# 2. PARSER GENERATORS
print("""
=== 2. Parser Generators ===

Tools that generate DPDAs from grammars:

YACC/BISON:
  - LALR(1) parser generator
  - Input: grammar with actions
  - Output: C parser (a DPDA)
  - Used in: GCC, many Unix tools

ANTLR:
  - LL(*) parser generator
  - Input: grammar
  - Output: Java/Python/... parser
  - Used in: many projects

JAVACC:
  - LL(k) parser generator
  - Output: Java parser

PLY (Python):
  - LALR(1) for Python
  - Used in: many Python tools

All generate deterministic parsers.
""")

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

Deterministic parsing of structured data:

JSON:
  - Deterministic grammar
  - Parsed by recursive descent (LL)
  - O(n) time

XML:
  - Deterministic parsing
  - SAX (push) and DOM (tree)
  - Both use DPDA-like mechanisms

YAML:
  - More complex (indentation)
  - Still deterministic
  - Uses a stack for indentation

CSV:
  - Very simple
  - Deterministic
  - Line-by-line

All these are DCFLs (or close).
""")

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

Protocol message parsing:

HTTP:
  - Request/response format
  - Deterministic grammar
  - Headers: key-value
  - Body: may be nested (JSON, XML)

SMTP:
  - Command-response protocol
  - Deterministic
  - Line-based

SIP:
  - Text-based protocol
  - Deterministic grammar
  - Nested headers

All use deterministic parsing (DPDA).
""")

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

Calculators and interpreters:

Infix expressions:
  3 + 4 * 2
  Parsed deterministically with precedence.

Algorithm:
  - Shift-reduce parsing
  - Operator precedence
  - Stack for operands

This is a DPDA in action!

Example: Python's eval()
  Parses expressions deterministically.
  Uses a DPDA internally.
""")

# 6. CONFIGURATION LANGUAGES
print("""
=== 6. Configuration Languages ===

Many config languages are DCFLs:

Terraform (HCL):
  - Deterministic grammar
  - Nested blocks
  - Parsed by DPDA

Ansible (YAML):
  - Deterministic (indentation)
  - Stack-based parsing

Kubernetes (YAML):
  - Same as Ansible

Docker Compose (YAML):
  - Deterministic

All these benefit from O(n) parsing.
""")

# 7. QUERY LANGUAGES
print("""
=== 7. Query Languages ===

SQL:
  - Deterministic grammar (mostly)
  - Parsed by DPDA
  - O(n) parsing

GraphQL:
  - Deterministic grammar
  - Parsed by DPDA

XPath:
  - Deterministic
  - Stack-based evaluation

These languages are designed as DCFLs
for efficient parsing.
""")

# 8. TEMPLATE LANGUAGES
print("""
=== 8. Template Languages ===

HTML templates:
  - Deterministic grammar
  - Nested tags
  - Stack-based parsing

Jinja2, Django templates:
  - Deterministic parsing
  - Block structure
  - Stack for nesting

Mustache, Handlebars:
  - Simple deterministic grammar
  - Section nesting

All use DPDA-like parsing.
""")

# 9. SUMMARY TABLE
print("=== Application Summary ===")
print(f"{'Domain':<25} {'Use Case':<30} {'DPDA Role':<25}")
print("-" * 80)
print(f"{'Compilers':<25} {'Syntax analysis':<30} {'LR/LL parsing':<25}")
print(f"{'Parser generators':<25} {'Yacc, ANTLR':<30} {'Generate DPDA':<25}")
print(f"{'Data formats':<25} {'JSON, XML':<30} {'Deterministic parse':<25}")
print(f"{'Protocols':<25} {'HTTP, SMTP':<30} {'Message parsing':<25}")
print(f"{'Calculators':<25} {'Expression eval':<30} {'Shift-reduce':<25}")
print(f"{'Config languages':<25} {'Terraform, YAML':<30} {'Stack-based':<25}")
print(f"{'Query languages':<25} {'SQL, GraphQL':<30} {'Deterministic grammar':<25}")
print(f"{'Templates':<25} {'HTML, Jinja':<30} {'Nested parsing':<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:
  - Deterministic (PEG is deterministic by design)
  - Uses a stack internally
  - O(n) for most inputs
  - Backtracking limited

Key insight:
  Even though Python uses PEG (not pure DPDA),
  the underlying mechanism is deterministic
  and stack-based — essentially a DPDA.
""")

# 11. CASE STUDY: GCC
print("""
=== Case Study: GCC ===

GCC uses a hand-written recursive descent parser
for C and C++ (since GCC 3.4).

Recursive descent:
  - Top-down (LL)
  - Deterministic
  - Uses call stack (not explicit stack)
  - Equivalent to a DPDA

Why hand-written?
  - Better error messages
  - Easier to maintain
  - More control

Performance:
  - O(n) parsing
  - Very fast
  - Handles millions of lines

This shows DPDAs in practice:
  - Not always generated by tools
  - Can be hand-written
  - Still deterministic
""")

# 12. TAKEAWAYS
print("""
=== Practical Takeaways ===

1. PROGRAMMING LANGUAGES ARE DCFLs
   Designed for deterministic parsing.

2. PARSERS ARE DPDAs
   Either generated (Yacc) or hand-written.

3. O(n) PARSING IS POSSIBLE
   Because of determinism.

4. TOOLS AUTOMATE DPDA CONSTRUCTION
   Yacc, Bison, ANTLR, etc.

5. DPDAs ARE PRACTICAL
   Not just theory — used everywhere.

6. WHY NOT CFLs?
   CFLs are ambiguous and slow to parse.
   DCFLs are unambiguous and fast.
   Practical languages choose DCFLs.

7. THE TRADE-OFF
   DCFL is less expressive than CFL,
   but much more practical.
""")
  

  
  
    🚀 Advanced Topics
    🎯 Beyond Basic DPDAs
DPDAs are the foundation for many advanced topics: LR(k) parsing, deterministic grammars, visibly pushdown automata, and modern parsing techniques.
     Advanced Directions
LR(k): Full lookahead. LALR: Practical LR. GLR: Generalized LR. VPA: Visibly pushdown. Incremental: Online parsing. Neural: Learned parsing.
🔍 LR(k)⚙️ LALR👁️ VPA🧠 Neural
    # Advanced Topics
print("=" * 60)
print("ADVANCED TOPICS")
print("=" * 60)

# 1. LR(K) PARSING
print("""
=== 1. LR(k) Parsing ===

LR(k) = Left-to-right scan, Rightmost derivation, k lookahead.

LR(0): No lookahead (weak)
SLR(1): Simple LR with 1 lookahead
LALR(1): Look-Ahead LR (practical)
LR(1): Full LR with 1 lookahead
LR(k): Full LR with k lookahead

Power hierarchy:
  LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1) ⊊ LR(k)

All are DCFGs.
LALR(1) is used by Yacc/Bison (good balance).
LR(1) is more powerful but larger tables.

=== LALR(1) ===

LALR(1) merges LR(1) states with same core.
  - Smaller tables than LR(1)
  - Nearly as powerful
  - Used in practice

Trade-off:
  - LR(1): More states, more power
  - LALR(1): Fewer states, slightly less power
""")

# 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

Key insight:
  GLR = DPDA + backtracking
  Still deterministic in the common case.
""")

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

A VPA is a DPDA where stack operations
are determined by input symbols.

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

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

Properties:
  - Determinizable
  - Closed under union, intersection, complement
  - Good for structured data

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

VPAs are a "deterministic" subclass of PDAs
with better closure properties.
""")

# 4. INCREMENTAL PARSING
print("""
=== 4. Incremental Parsing ===

Parse input as it arrives (streaming).

Requirements:
  - Process left-to-right
  - Constant memory per symbol
  - Immediate output

Used in:
  - IDEs (syntax highlighting)
  - Interactive systems
  - Real-time processing

DPDAs are ideal for incremental parsing:
  - Deterministic
  - O(1) per symbol
  - No backtracking

Example: Tree-sitter
  - Incremental parsing library
  - Used in Atom, Neovim
  - DPDA-like mechanism
""")

# 5. ERROR RECOVERY
print("""
=== 5. Error Recovery in DPDA Parsing ===

When a DPDA encounters an error:
  - No transition available
  - Input doesn't match grammar

Error recovery strategies:
  1. Panic mode: skip tokens until sync
  2. Phrase level: local correction
  3. Error productions: grammar rules for errors

Example: missing semicolon
  Parser can insert a virtual semicolon
  and continue parsing.

This is why hand-written parsers
often give better error messages
than generated ones.
""")

# 6. NEURAL PARSING
print("""
=== 6. Neural Parsing ===

Deep learning for parsing.

Approaches:
  - Sequence-to-sequence
  - Attention-based
  - Graph neural networks

Characteristics:
  - No explicit grammar
  - Learned from data
  - Handles ambiguity statistically

Comparison:
  DPDA: Deterministic, fast, precise
  Neural: Probabilistic, slower, flexible

Hybrid approaches:
  - Use DPDA for syntax
  - Use neural for semantics
  - Best of both worlds
""")

# 7. QUANTUM PARSING
print("""
=== 7. Quantum Parsing ===

Quantum algorithms for parsing.

Potential:
  - Speedup for some problems
  - Parallel exploration of parse trees
  - Quantum DPDA?

Research area:
  - Quantum automata
  - Quantum grammars
  - Quantum parsing

Still experimental.
Practical impact unclear.
""")

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

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

2. DETERMINIZATION
   Given a PDA, is there an equivalent DPDA?
   Decidable but complex.

3. MINIMAL DPDA
   Finding minimal DPDA is polynomial?
   (Minimal DFA is easy; DPDA is harder.)

4. ERROR RECOVERY
   Optimal error recovery in deterministic parsing?
   Heuristic approaches dominate.

5. NEURAL-SYMBOLIC
   Combining neural and symbolic parsing?
   Active research area.
""")

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

For compiler developers:
  1. Master LR parsing
  2. Understand LALR(1) tables
  3. Learn Yacc/Bison
  4. Handle error recovery
  5. Consider hand-written parsers

For tool builders:
  1. Study parser generators
  2. Understand DPDA theory
  3. Implement incremental parsing
  4. Handle ambiguity carefully
  5. Test extensively

For researchers:
  1. Explore efficient parsing
  2. Study determinization
  3. Investigate neural parsing
  4. Work on error recovery
  5. Quantum parsing

For students:
  1. Implement an LR parser
  2. Build a DPDA from scratch
  3. Use Yacc/Bison
  4. Study DCFL theory
  5. Understand the trade-offs
""")

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

DPDAs are:

✓ FOUNDATIONAL
  Model for deterministic parsing.

✓ PRACTICAL
  Used in every compiler.

✓ EFFICIENT
  O(n) parsing.

✓ DECIDABLE
  Better decision properties than NPDAs.

✓ EXTENSIBLE
  LR(k), LALR, GLR, VPA.

✓ EVOLVING
  Neural parsing, incremental parsing.

Key takeaway:
  Determinism is a trade-off.
  Less power (DCFL ⊊ CFL)
  but more efficiency (O(n) vs O(n³))
  and better decidability.

Programming languages choose DCFL
because practical concerns dominate.

"Determinism: the key to practical parsing."
  — Anonymous

Go build a parser!
""")

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

DPDA: M = (Q, Σ, Γ, δ, q₀, Z₀, F)
  δ: Q × (Σ∪{ε}) × Γ → Q × Γ*  (partial function)

Determinism:
  1. |δ(q,a,Z)| ≤ 1
  2. No ε/input conflict

DCFL: Languages accepted by DPDAs
  - Strict subset of CFL
  - Closed under complement
  - NOT closed under union
  - Decidable equivalence

LR Parsing:
  - DPDA with item-set states
  - Shift/reduce actions
  - O(n) time

DCFG:
  - Unambiguous CFG
  - LR(k) parseable
  - Equivalent to DPDA

Decision Problems:
  Membership: O(n)
  Emptiness: Decidable
  Equivalence: Decidable
  Universality: Decidable
  Inclusion: Decidable

Key relationship:
  DCFG = DPDA = DCFL = LR(k) grammar
""")