🧠 DFA Fundamentals

🎯 What is a DFA?

A Deterministic Finite Automaton (DFA) is the simplest model of computation — a theoretical machine that reads an input string one symbol at a time and either accepts or rejects it. For every state and input symbol, there is exactly one next state. DFAs recognize regular languages, the foundation of lexical analysis in compilers.

Why DFAs Matter

Foundation: Simplest computational model. Practical: Lexical analysis, pattern matching. Deterministic: No ambiguity in transitions. Regular languages: Exact characterization. Efficient: O(n) time complexity. Universal: Any DFA can be simulated.

📌 Finite States📌 Deterministic📌 Regular Languages📌 Lexical Analysis

# DFA — the big picture
# A DFA is like a state machine that processes input

# REAL-LIFE EXAMPLE: Turnstile
# States: Locked, Unlocked
# Inputs: Push, Coin

class TurnstileDFA:
    """
    Turnstile DFA:
      States: {Locked, Unlocked}
      Alphabet: {Push, Coin}
      Start: Locked
      Accept: (any state is valid)
    """
    def __init__(self):
        self.state = 'Locked'
        self.transitions = {
            ('Locked', 'Push'): 'Locked',
            ('Locked', 'Coin'): 'Unlocked',
            ('Unlocked', 'Push'): 'Locked',
            ('Unlocked', 'Coin'): 'Unlocked',
        }
    
    def process(self, inputs):
        for symbol in inputs:
            self.state = self.transitions[(self.state, symbol)]
        return self.state

# Test
turnstile = TurnstileDFA()
print(turnstile.process(['Coin', 'Push']))  # Locked
print(turnstile.process(['Coin', 'Coin']))  # Unlocked

# KEY PROPERTIES
print("""
=== DFA Key Properties ===

1. FINITE STATES
   - Fixed, finite set of states
   - No memory beyond current state

2. DETERMINISTIC
   - One transition per (state, symbol) pair
   - No choices, no ambiguity
   - Exactly one next state

3. INPUT PROCESSING
   - Read input left to right
   - One symbol at a time
   - Cannot go back

4. ACCEPTANCE
   - Accept if end in accepting state
   - Reject if end in non-accepting state
   - Input is consumed entirely

5. COMPLEXITY
   - Time: O(n) where n = input length
   - Space: O(1) — just current state

6. EXPRESSIVE POWER
   - Exactly regular languages
   - Equivalent to: NFA, regex, right-linear grammars
""")

📐 Formal Definition

🎯 The 5-Tuple

A DFA is formally defined as a 5-tuple M = (Q, Σ, δ, q₀, F), where each component plays a specific role in the machine's behavior.

The Components

Q: Finite set of states. Σ: Input alphabet. δ: Transition function Q × Σ → Q. q₀: Start state (q₀ ∈ Q). F: Set of accepting states (F ⊆ Q). Recognition: String w accepted if δ*(q₀, w) ∈ F.

Q StatesΣ Alphabetδ Functionq₀ StartF Accept

# Formal definition in code
from dataclasses import dataclass
from typing import Set, Dict, Tuple, FrozenSet

@dataclass
class DFA:
    """
    Formal DFA as 5-tuple M = (Q, Σ, δ, q₀, F)
    """
    Q: FrozenSet[str]                          # States
    Sigma: FrozenSet[str]                      # Alphabet
    delta: Dict[Tuple[str, str], str]          # Transition function
    q0: str                                    # Start state
    F: FrozenSet[str]                          # Accept states
    
    def __post_init__(self):
        # Validate
        assert self.q0 in self.Q, "Start state must be in Q"
        assert self.F.issubset(self.Q), "F must be subset of Q"
        for (q, s), q_next in self.delta.items():
            assert q in self.Q, f"State {q} not in Q"
            assert q_next in self.Q, f"State {q_next} not in Q"
            assert s in self.Sigma, f"Symbol {s} not in Σ"
    
    def accepts(self, input_string: str) -> bool:
        """Check if DFA accepts input_string."""
        state = self.q0
        for symbol in input_string:
            if symbol not in self.Sigma:
                return False  # Invalid symbol
            state = self.delta[(state, symbol)]
        return state in self.F
    
    def trace(self, input_string: str) -> list:
        """Trace execution step by step."""
        state = self.q0
        trace = [f"Start: {state}"]
        for symbol in input_string:
            state = self.delta[(state, symbol)]
            trace.append(f"Read '{symbol}' → {state}")
        result = "ACCEPT" if state in self.F else "REJECT"
        trace.append(f"Result: {result}")
        return trace


# EXAMPLE: DFA for binary strings ending in "01"
dfa_ends_01 = DFA(
    Q=frozenset({'q0', 'q1', 'q2'}),
    Sigma=frozenset({'0', '1'}),
    delta={
        ('q0', '0'): 'q1',   # Seen 0
        ('q0', '1'): 'q0',   # Reset
        ('q1', '0'): 'q1',   # Still 0
        ('q1', '1'): 'q2',   # Seen 01
        ('q2', '0'): 'q1',   # Reset but 0
        ('q2', '1'): 'q0',   # Reset
    },
    q0='q0',
    F=frozenset({'q2'})
)

# Test
for s in ['01', '101', '001', '110', '011', '']:
    result = dfa_ends_01.accepts(s)
    print(f"'{s}' → {result}")

# Trace
print("\n=== Trace for '1101' ===")
for line in dfa_ends_01.trace('1101'):
    print(f"  {line}")

# MORE EXAMPLES
print("""
=== Formal Definition Examples ===

Example 1: Strings with even number of 0s
  Q = {q0, q1}
  Σ = {0, 1}
  δ: (q0,0)→q1, (q0,1)→q0, (q1,0)→q0, (q1,1)→q1
  q₀ = q0
  F = {q0}

Example 2: Binary numbers divisible by 3
  Q = {q0, q1, q2}  (q_i = remainder i)
  Σ = {0, 1}
  δ: (q_i, b) → q_{(2i + b) mod 3}
  q₀ = q0
  F = {q0}

Example 3: Strings starting with 'a'
  Q = {q0, q1, q2}
  Σ = {a, b}
  δ: (q0,a)→q1, (q0,b)→q2, (q1,a)→q1, (q1,b)→q1, (q2,·)→q2
  q₀ = q0
  F = {q1}
""")

🔧 Five Components

🎯 Deep Dive into Each Component

Understanding each of the 5 components in detail is essential for designing and analyzing DFAs.

Component Details

States (Q): Represent memory/configuration. Alphabet (Σ): Finite input symbols. Transition (δ): Total function. Start (q₀): Initial configuration. Accept (F): Goal states. Critical: Total function — defined for every input.

🎯 Q States🔤 Σ Symbols🔄 δ Total▶️ q₀ Initial✅ F Goal

# Deep dive into DFA components
import matplotlib.pyplot as plt
import networkx as nx

# 1. STATES (Q)
print("=== States (Q) ===")
print("""
- Finite set of configurations
- Represent "memory" of the machine
- Usually named q0, q1, q2, ... or by purpose
- At any time, DFA is in exactly one state

Example: States for a vending machine
  Q = {Idle, AwaitingCoin, Dispensing, OutOfStock}

State purposes:
  - Track progress through input
  - Remember previous symbols
  - Encode computational state
""")

# 2. ALPHABET (Σ)
print("=== Alphabet (Σ) ===")
print("""
- Finite set of input symbols
- Also called input alphabet
- Each symbol is atomic (no subparts)

Examples:
  Binary: Σ = {0, 1}
  DNA: Σ = {A, C, G, T}
  English: Σ = {a, b, c, ..., z}
  ASCII: Σ = {all 128 characters}

Note: Σ* = all finite strings over Σ
      Σ+ = all non-empty strings over Σ
      ε = empty string
""")

# 3. TRANSITION FUNCTION (δ)
print("=== Transition Function (δ) ===")
print("""
δ: Q × Σ → Q

- Takes (current_state, input_symbol)
- Returns exactly ONE next state
- MUST be total (defined for all inputs)

Types of transitions:
  1. Self-loop: q → q (stay in same state)
  2. Move: q1 → q2 (change state)
  3. Trap: q → q (dead state, always rejects)

Example:
  δ(q0, 'a') = q1
  δ(q0, 'b') = q0
  δ(q1, 'a') = q1
  δ(q1, 'b') = q1
""")

# 4. START STATE (q₀)
print("=== Start State (q₀) ===")
print("""
- Single, distinguished state
- Where processing begins
- Must be in Q
- Usually drawn with incoming arrow

Sometimes called:
  - Initial state
  - q0
  - Start
  - S
""")

# 5. ACCEPT STATES (F)
print("""
=== Accept States (F) ===

- Subset of Q (F ⊆ Q)
- Can be empty (accepts nothing)
- Can be all of Q (accepts everything)
- Also called:
  * Final states
  * Accepting states
  * Goal states

Convention:
  - Drawn with double circles
  - Or with special markers
  - Or highlighted in diagrams
""")

# VISUALIZE DFA
def visualize_dfa(Q, delta, q0, F, title="DFA"):
    """Visualize DFA using networkx."""
    G = nx.DiGraph()
    
    # Add nodes
    for state in Q:
        G.add_node(state)
    
    # Add edges
    for (src, symbol), dst in delta.items():
        if G.has_edge(src, dst):
            # Multiple transitions — combine labels
            G[src][dst]['label'] += f", {symbol}"
        else:
            G.add_edge(src, dst, label=symbol)
    
    # Layout
    pos = nx.spring_layout(G, seed=42)
    
    # Draw
    plt.figure(figsize=(10, 6))
    
    # Nodes
    nx.draw_networkx_nodes(G, pos, 
                           node_color=['lightgreen' if n in F else 'lightblue' 
                                       for n in G.nodes()],
                           node_size=2000)
    
    # Edges
    nx.draw_networkx_edges(G, pos, edge_color='gray', 
                           arrows=True, arrowsize=20)
    
    # Labels
    nx.draw_networkx_labels(G, pos, font_size=12)
    edge_labels = nx.get_edge_attributes(G, 'label')
    nx.draw_networkx_edge_labels(G, pos, edge_labels, font_size=10)
    
    plt.title(title)
    plt.axis('off')
    plt.tight_layout()
    plt.show()

# EXAMPLE: DFA for strings ending in "01"
Q = {'q0', 'q1', 'q2'}
delta = {
    ('q0', '0'): 'q1',
    ('q0', '1'): 'q0',
    ('q1', '0'): 'q1',
    ('q1', '1'): 'q2',
    ('q2', '0'): 'q1',
    ('q2', '1'): 'q0',
}
F = {'q2'}

# visualize_dfa(Q, delta, 'q0', F, "DFA: Strings ending in '01'")
print("\n=== Visualization available ===")
print("Uncomment the visualize_dfa call to see the diagram")

# DETAILED EXAMPLE
print("\n=== Detailed Example: Even Number of 0s ===")
print("""
Q = {Even, Odd}
Σ = {0, 1}
δ:
  (Even, 0) → Odd
  (Even, 1) → Even
  (Odd, 0) → Even
  (Odd, 1) → Odd
q₀ = Even
F = {Even}

Trace "0101":
  Start: Even
  Read 0 → Odd
  Read 1 → Odd
  Read 0 → Even
  Read 1 → Even
  Result: ACCEPT ✓

Trace "010":
  Start: Even
  Read 0 → Odd
  Read 1 → Odd
  Read 0 → Even
  Result: ACCEPT ✓

Trace "011":
  Start: Even
  Read 0 → Odd
  Read 1 → Odd
  Read 1 → Odd
  Result: REJECT ✗
""")

🔄 Transition Function

🎯 The Heart of DFA

The transition function δ: Q × Σ → Q defines how the DFA moves between states. It must be a total function — defined for every (state, symbol) pair.

Transition Types

Self-loop: δ(q, a) = q. Forward: δ(q1, a) = q2. Trap state: All symbols → itself. Total function: Every (q, a) has exactly one δ(q, a). Extended δ*: δ*(q, w) for strings. Trace: Sequence of states visited.

🔄 Self-loop➡️ Forward🕳️ Trap📊 Table

# Transition function — implementation and extensions
from typing import Dict, Tuple

# 1. BASIC TRANSITION FUNCTION
class TransitionFunction:
    """
    δ: Q × Σ → Q
    """
    def __init__(self, delta: Dict[Tuple[str, str], str]):
        self.delta = delta
    
    def __call__(self, state: str, symbol: str) -> str:
        """Apply δ to (state, symbol)."""
        if (state, symbol) not in self.delta:
            raise ValueError(f"δ({state}, {symbol}) undefined!")
        return self.delta[(state, symbol)]
    
    def extended(self, state: str, word: str) -> str:
        """
        Extended transition function δ*: Q × Σ* → Q
        """
        for symbol in word:
            state = self(state, symbol)
        return state

# Example
delta = TransitionFunction({
    ('q0', '0'): 'q1',
    ('q0', '1'): 'q0',
    ('q1', '0'): 'q1',
    ('q1', '1'): 'q2',
    ('q2', '0'): 'q1',
    ('q2', '1'): 'q0',
})

print("=== Basic Transitions ===")
print(f"δ(q0, 0) = {delta('q0', '0')}")
print(f"δ(q1, 1) = {delta('q1', '1')}")
print(f"δ*(q0, '0101') = {delta.extended('q0', '0101')}")

# 2. TRANSITION TABLE
def print_transition_table(states, alphabet, delta):
    """Print transition table."""
    header = "State".ljust(8) + "| " + " | ".join(alphabet)
    print(header)
    print("-" * len(header))
    
    for state in sorted(states):
        row = state.ljust(8) + "| "
        row += " | ".join(delta[(state, s)] for s in alphabet)
        print(row)

print("\n=== Transition Table ===")
print_transition_table(
    {'q0', 'q1', 'q2'}, 
    ['0', '1'], 
    delta.delta
)

# 3. TRAP STATE EXAMPLE
print("\n=== Trap State (Dead State) ===")
print("""
A trap state is a non-accepting state where:
- All transitions lead back to itself
- Once entered, never leaves
- Any string reaching trap is rejected

Example: DFA for strings starting with 'a'
  Q = {q0, q1, q_trap}
  Σ = {a, b}
  δ:
    (q0, 'a') → q1
    (q0, 'b') → q_trap
    (q1, 'a') → q1
    (q1, 'b') → q1
    (q_trap, 'a') → q_trap
    (q_trap, 'b') → q_trap
  q₀ = q0
  F = {q1}
  
Once in q_trap, always in q_trap → reject
""")

# 4. EXTENDED TRANSITION FUNCTION
print("=== Extended Transition δ* ===")
print("""
Definition:
  δ*(q, ε) = q                    (empty string)
  δ*(q, wa) = δ(δ*(q, w), a)     (recursive)

Properties:
  δ*(q, w·a) = δ(δ*(q, w), a)    (concatenation)
  δ*(q, a) = δ(q, a)              (single symbol)
  δ*(q, ε) = q                    (identity)

Uses:
  - Determine final state for any string
  - Define L(M) = {w | δ*(q₀, w) ∈ F}
  - Prove language properties

Example for DFA ending in '01':
  δ*(q0, '') = q0
  δ*(q0, '0') = q1
  δ*(q0, '01') = q2 ∈ F  ✓ Accept
  δ*(q0, '101') = q2 ∈ F  ✓ Accept
  δ*(q0, '10') = q0 ∉ F  ✗ Reject
""")

# 5. VISUALIZATION OF TRANSITIONS
print("\n=== Transition Visualization ===")
print("""
ASCII Diagram for DFA ending in '01':

        0           0
    ┌───┐       ┌───┐
    ↓   │       ↓   │
  →(q0)────0────→(q1)────1────→((q2))
    ↑              ↑              │
    └────1─────────┘              │
    │                             │
    └────────0,1──────────────────┘

Legend:
  (q)  = regular state
  ((q)) = accepting state
  →    = start state arrow
  ───  = transition (with symbol)
""")

# 6. VALIDATION
def validate_delta(Q, Sigma, delta):
    """Validate that delta is a total function."""
    expected_pairs = {(q, s) for q in Q for s in Sigma}
    actual_pairs = set(delta.keys())
    
    missing = expected_pairs - actual_pairs
    extra = actual_pairs - expected_pairs
    
    if missing:
        print(f"❌ Missing transitions: {missing}")
    if extra:
        print(f"❌ Extra transitions: {extra}")
    if not missing and not extra:
        print("✓ Transition function is valid (total)")

print("\n=== Validation ===")
validate_delta(
    {'q0', 'q1', 'q2'},
    {'0', '1'},
    delta.delta
)

# 7. COMMON PATTERNS
print("\n=== Common Transition Patterns ===")
print("""
1. KLEENE STAR (accepts any string)
   All transitions → same accepting state

2. EMPTY SET (accepts nothing)
   All states non-accepting
   Or missing accept states

3. CONCATENATION (accepts L1·L2)
   Final states of L1 → start state of L2

4. UNION (accepts L1 ∪ L2)
   New start state with ε-transitions
   (Or in DFA: Cartesian product)

5. INTERSECTION (accepts L1 ∩ L2)
   Product construction: Q = Q1 × Q2
   F = F1 × F2
""")

📊 Representations (Table/Diagram)

🎯 Ways to Represent DFAs

DFAs can be represented in multiple equivalent ways: state diagrams, transition tables, formal definitions, and code. Each is useful in different contexts.

Representation Types

Diagram: Visual, intuitive. Table: Compact, precise. Formal: Mathematical, unambiguous. Code: Executable, testable. JSON: Serializable, portable. Graph: Network analysis friendly.

🎨 Diagram📋 Table📐 Formal💻 Code

# Multiple representations of DFA
import json
from typing import Dict, Set, Tuple

# 1. TRANSITION TABLE REPRESENTATION
class DFATable:
    """DFA as transition table."""
    def __init__(self, states, alphabet, table, start, accept):
        self.states = states
        self.alphabet = alphabet
        self.table = table  # Dict[Tuple[state, symbol], next_state]
        self.start = start
        self.accept = accept
    
    def accepts(self, word):
        state = self.start
        for symbol in word:
            state = self.table[(state, symbol)]
        return state in self.accept
    
    def print_table(self):
        """Print as formatted table."""
        print("\nTransition Table:")
        header = "State".ljust(10) + "| " + " | ".join(self.alphabet)
        print(header)
        print("-" * len(header))
        
        for state in sorted(self.states):
            marker = "→" if state == self.start else " "
            marker += "*" if state in self.accept else " "
            row = f"{marker} {state}".ljust(10) + "| "
            row += " | ".join(self.table[(state, s)] for s in self.alphabet)
            print(row)

# Example
dfa = DFATable(
    states={'q0', 'q1', 'q2'},
    alphabet=['0', '1'],
    table={
        ('q0', '0'): 'q1',
        ('q0', '1'): 'q0',
        ('q1', '0'): 'q1',
        ('q1', '1'): 'q2',
        ('q2', '0'): 'q1',
        ('q2', '1'): 'q0',
    },
    start='q0',
    accept={'q2'}
)

dfa.print_table()

# 2. STATE DIAGRAM (ASCII)
def ascii_diagram():
    print("""
ASCII State Diagram for DFA ending in '01':

    ┌───────────────────────┐
    │                       │
    │   0                   1
    ↓   │                   │
  →(q0)┴────0───→(q1)───1──→((q2))
    ↑            ↑              │
    │            │              │
    └────1───────┘              │
    │                           │
    └─────────0, 1──────────────┘

Legend:
  →     : start state indicator
  ( )   : state
  (( )) : accepting state
  ───   : transition
  X, Y  : multiple symbols
""")

ascii_diagram()

# 3. FORMAL MATHEMATICAL REPRESENTATION
print("""
=== Formal Mathematical Representation ===

M = (Q, Σ, δ, q₀, F) where:
  Q = {q₀, q₁, q₂}
  Σ = {0, 1}
  δ = { 
    (q₀, 0) ↦ q₁,
    (q₀, 1) ↦ q₀,
    (q₁, 0) ↦ q₁,
    (q₁, 1) ↦ q₂,
    (q₂, 0) ↦ q₁,
    (q₂, 1) ↦ q₀
  }
  q₀ = q₀
  F = {q₂}

Language: L(M) = {w ∈ {0,1}* | w ends in '01'}
""")

# 4. JSON REPRESENTATION
def to_json(dfa):
    """Convert DFA to JSON."""
    return {
        'states': list(dfa.states),
        'alphabet': dfa.alphabet,
        'transitions': [
            {'from': q, 'symbol': s, 'to': q_next}
            for (q, s), q_next in dfa.table.items()
        ],
        'start_state': dfa.start,
        'accept_states': list(dfa.accept)
    }

json_repr = to_json(dfa)
print("=== JSON Representation ===")
print(json.dumps(json_repr, indent=2))

# 5. PYTHON DICTIONARY
def as_dict():
    return {
        'Q': {'q0', 'q1', 'q2'},
        'Sigma': {'0', '1'},
        'delta': {
            ('q0', '0'): 'q1',
            ('q0', '1'): 'q0',
            ('q1', '0'): 'q1',
            ('q1', '1'): 'q2',
            ('q2', '0'): 'q1',
            ('q2', '1'): 'q0',
        },
        'q0': 'q0',
        'F': {'q2'}
    }

# 6. REGEX REPRESENTATION
print("""
=== Regular Expression Equivalents ===

DFA for strings ending in "01":
  Regex: (0|1)*01

Other examples:
  Even number of 0s: (1*01*0)*1*
  Starts with 'a': a(a|b)*
  Even length: ((a|b)(a|b))*
  Contains "ab": (a|b)*ab(a|b)*
  Ends with "ba": (a|b)*ba
""")

# 7. COMPARISON
print("=== Representation Comparison ===")
print(f"{'Method':<15} {'Pros':<30} {'Cons':<30}")
print("-" * 75)
print(f"{'Diagram':<15} {'Intuitive, visual':<30} {'Hard to scale':<30}")
print(f"{'Table':<15} {'Compact, precise':<30} {'Less intuitive':<30}")
print(f"{'Formal':<15} {'Unambiguous':<30} {'Verbose':<30}")
print(f"{'Code':<15} {'Executable, testable':<30} {'Language-specific':<30}")
print(f"{'JSON':<15} {'Portable, standard':<30} {'Verbose':<30}")
print(f"{'Regex':<15} {'Compact':<30} {'Less explicit':<30}")

# 8. CONVERSION EXAMPLE
print("\n=== Converting Between Representations ===")
print("""
Table → Diagram:
  1. Draw circles for each state
  2. Mark start with arrow
  3. Mark accept with double circle
  4. Draw arrows for each transition

Diagram → Table:
  1. List all states as rows
  2. List all symbols as columns
  3. Fill in transitions from diagram

Formal → Code:
  1. Q → set of state names
  2. Σ → set of symbols
  3. δ → dictionary of (state, symbol) → state
  4. q₀ → start state string
  5. F → set of accept state names
""")

✅ String Acceptance

🎯 Does the DFA Accept This String?

String acceptance is determined by running the DFA on the input and checking if it ends in an accepting state. The language of a DFA is the set of all strings it accepts.

Acceptance Process

1. Start: Begin at q₀. 2. Read: Process symbols left to right. 3. Transition: δ(current, symbol). 4. End: Check if in F. Accept: Final state ∈ F. Reject: Final state ∉ F.

▶️ Start q₀📖 Read symbols✅ Check F🎯 L(M)

# String acceptance in detail
class DFA:
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def accepts(self, word):
        """Return True if DFA accepts word."""
        state = self.q0
        for symbol in word:
            if symbol not in self.Sigma:
                return False
            state = self.delta[(state, symbol)]
        return state in self.F
    
    def run_trace(self, word):
        """Return full execution trace."""
        state = self.q0
        trace = [('start', None, state)]
        
        for symbol in word:
            state = self.delta[(state, symbol)]
            trace.append(('read', symbol, state))
        
        accepted = state in self.F
        return trace, accepted

# Example: DFA ending in "01"
dfa = DFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'0', '1'},
    delta={
        ('q0', '0'): 'q1',
        ('q0', '1'): 'q0',
        ('q1', '0'): 'q1',
        ('q1', '1'): 'q2',
        ('q2', '0'): 'q1',
        ('q2', '1'): 'q0',
    },
    q0='q0',
    F={'q2'}
)

# 1. ACCEPTANCE TESTING
print("=== Acceptance Testing ===")
test_strings = ['', '0', '1', '01', '10', '11', '001', '101', '1101', '111']
for s in test_strings:
    result = "✓ ACCEPT" if dfa.accepts(s) else "✗ REJECT"
    print(f"'{s:6s}' → {result}")

# 2. STEP-BY-STEP TRACE
print("\n=== Step-by-Step Trace for '101' ===")
trace, accepted = dfa.run_trace('101')

print(f"{'Step':<6} {'Action':<8} {'Symbol':<8} {'State':<8}")
print("-" * 35)
for i, (action, symbol, state) in enumerate(trace):
    symbol_str = symbol if symbol else '—'
    print(f"{i:<6} {action:<8} {symbol_str:<8} {state:<8}")

print(f"\nFinal result: {'ACCEPT ✓' if accepted else 'REJECT ✗'}")

# 3. LANGUAGE OF A DFA
print("\n=== Language of a DFA ===")
print("""
L(M) = { w ∈ Σ* | δ*(q₀, w) ∈ F }

For DFA ending in "01":
  L(M) = { w ∈ {0,1}* | w ends in "01" }

Examples:
  ✓ Accepted: 01, 101, 001, 1101, 0101, 00001
  ✗ Rejected: 0, 1, 10, 11, 100, 011, 0111

Regular expression: (0|1)*01
""")

# 4. ENUMERATING ACCEPTED STRINGS
def enumerate_language(dfa, max_length):
    """Enumerate all accepted strings up to max_length."""
    from itertools import product
    
    accepted = []
    
    for length in range(max_length + 1):
        for symbols in product(dfa.Sigma, repeat=length):
            word = ''.join(symbols)
            if dfa.accepts(word):
                accepted.append(word)
    
    return accepted

print("\n=== Enumerating Language (up to length 4) ===")
accepted = enumerate_language(dfa, 4)
print(f"Total accepted strings (len ≤ 4): {len(accepted)}")
for s in accepted[:20]:
    print(f"  '{s}'")
if len(accepted) > 20:
    print(f"  ... and {len(accepted) - 20} more")

# 5. MEMBERSHIP VS NON-MEMBERSHIP
print("\n=== Membership Testing ===")
print("""
For ANY string w, exactly one of:
  1. w ∈ L(M) — accepted
  2. w ∉ L(M) — rejected

No ambiguity in DFA!

Verify for a specific string:
  w = '1101'
  
  q0 --1--> q0 --1--> q0 --0--> q1 --1--> q2
                                              ↑
                                          Accept state!
  
  So '1101' ∈ L(M) ✓
""")

# 6. PUMPING LEMMA INTRO
print("=== Pumping Lemma (Preview) ===")
print("""
For any regular language L, there exists n such that:
  Any string w ∈ L with |w| ≥ n
  Can be written as w = xyz where:
    - |y| ≥ 1
    - |xy| ≤ n
    - For all i ≥ 0: xyⁱz ∈ L

Application: Prove a language is NOT regular.

Example: L = {aⁿbⁿ | n ≥ 0} is NOT regular
  Proof by contradiction using pumping lemma.

(More on this in Formal Languages course)
""")

# 7. COMPLEXITY
print("=== Time Complexity ===")
print("""
For a DFA M and input string w:
  Time: O(|w|)   — one step per symbol
  Space: O(1)    — just current state

Very efficient!
  - Linear time
  - Constant space
  - Optimal for regular languages

Comparison:
  DFA: O(n) time, O(1) space
  NFA: O(n × |states|) time
  Regex (backtracking): exponential worst-case
  Regex (Thompson NFA): O(n × m) time
""")

🎨 Designing DFAs

🎯 Building DFAs for Languages

Designing DFAs is a skill. You need to identify what "memory" the machine needs and encode it in states. Here's a systematic approach.

Design Methodology

1. Understand: What language? 2. Identify memory: What must be remembered? 3. Choose states: Encode memory. 4. Define transitions: How does memory update? 5. Mark accept: Which states satisfy goal? 6. Test: Verify with examples.

🎯 Understand🧠 Memory📊 States🔄 Transitions

# Designing DFAs — systematic approach
print("=== DFA Design Template ===")
print("""
Step 1: WHAT is the language?
  - Describe in words
  - Identify the pattern
  - Consider edge cases

Step 2: WHAT must be remembered?
  - What properties of the prefix matter?
  - Examples: parity, last symbol, position mod k

Step 3: HOW MANY states?
  - Each distinct "memory configuration" = 1 state
  - n bits of memory → 2ⁿ states
  - Counter mod k → k states

Step 4: TRANSITIONS?
  - For each (state, symbol), determine new memory
  - Draw arrows

Step 5: START state?
  - Memory before reading any input
  - Usually "nothing seen yet"

Step 6: ACCEPT states?
  - Memory configurations that satisfy the goal

Step 7: TEST
  - Try positive and negative examples
  - Check edge cases (empty string, single symbol)
""")

# EXAMPLE 1: STRINGS ENDING IN "ab"
print("\n=== Example 1: Strings ending in 'ab' ===")
print("""
Step 1: Language
  L = {w ∈ {a,b}* | w ends in 'ab'}

Step 2: Memory needed
  Need to remember: how much of "ab" suffix is currently matched?
  - Nothing matched: no 'a' or 'b' suffix pending
  - 'a' matched: last symbol was 'a'
  - 'ab' matched: last two symbols were 'ab'
  → 3 memory configurations = 3 states

Step 3: States
  Q = {q0, qa, qab}
  - q0: no partial match
  - qa: last symbol was 'a' (waiting for 'b')
  - qab: last two symbols were 'ab' (accept!)

Step 4: Transitions
  δ(q0, 'a') = qa
  δ(q0, 'b') = q0
  δ(qa, 'a') = qa
  δ(qa, 'b') = qab
  δ(qab, 'a') = qa
  δ(qab, 'b') = q0

Step 5: Start state
  q0 = q0

Step 6: Accept states
  F = {qab}

Step 7: Test
  'ab' → q0 --a--> qa --b--> qab ∈ F ✓
  'aab' → q0 --a--> qa --a--> qa --b--> qab ✓
  'bab' → q0 --b--> q0 --a--> qa --b--> qab ✓
  'abb' → q0 --a--> qa --b--> qab --b--> q0 ✗
  'ba' → q0 --b--> q0 --a--> qa ∉ F ✗
  '' → q0 ∉ F ✗
""")

# Example 2: Divisible by 3
print("\n=== Example 2: Binary numbers divisible by 3 ===")
print("""
Step 1: Language
  L = {binary w | value(w) mod 3 == 0}

Step 2: Memory
  Remainder of current number mod 3
  → 3 possible remainders = 3 states

Step 3: States
  Q = {r0, r1, r2} where ri means "remainder is i"

Step 4: Transitions
  When reading bit b:
    new_remainder = (2 × old_remainder + b) mod 3
  δ(ri, b) = r_{(2i + b) mod 3}
  
  δ(r0, 0) = r0
  δ(r0, 1) = r1
  δ(r1, 0) = r2
  δ(r1, 1) = r0
  δ(r2, 0) = r1
  δ(r2, 1) = r2

Step 5: Start = r0

Step 6: Accept = {r0}

Step 7: Test
  '0'   = 0   → r0 ✓
  '11'  = 3   → r0 ✓
  '110' = 6   → r0 ✓
  '1001'= 9   → r0 ✓
  '1'   = 1   → r1 ✗
  '10'  = 2   → r2 ✗
  '100' = 4   → r1 ✗
""")

# Example 3: Contains "aa" or "bb"
print("\n=== Example 3: Contains 'aa' or 'bb' ===")
print("""
Language: L = {w | w contains 'aa' or 'bb'}

States (track last symbol):
  q0: no symbol seen yet (start)
  q1: last symbol was 'a', no 'aa'/'bb' yet
  q2: last symbol was 'b', no 'aa'/'bb' yet
  q3: found 'aa' or 'bb' (accept, trap here)

Transitions:
  δ(q0, 'a') = q1
  δ(q0, 'b') = q2
  δ(q1, 'a') = q3  (found 'aa')
  δ(q1, 'b') = q2
  δ(q2, 'a') = q1
  δ(q2, 'b') = q3  (found 'bb')
  δ(q3, 'a') = q3
  δ(q3, 'b') = q3

Accept = {q3}

Trace "abba":
  q0 --a--> q1 --b--> q2 --b--> q3 --a--> q3
  Result: ACCEPT ✓
""")

# DESIGN PATTERNS
print("\n=== Common Design Patterns ===")
print("""
1. MODULAR COUNTING
   - Count something mod k
   - k states (or k+1 with reset)
   - Example: length divisible by 3

2. PATTERN MATCHING
   - Pattern of length k → k+1 states
   - Track how much of pattern matched
   - Example: ends in "abc"

3. LAST SYMBOL
   - n symbols → n+1 states
   - Remember last symbol seen
   - Example: ends in 'a'

4. FLAG-BASED
   - Track boolean properties
   - 2ⁿ states for n flags
   - Example: contains both 'a' and 'b'

5. TWO-STEP MEMORY
   - Remember last two symbols
   - n² states
   - Example: ends in "01"

6. PARITY
   - Even/odd number of occurrences
   - 2 states
   - Example: even number of 0s
""")

# SYSTEMATIC CODE
def design_dfa_example():
    """Design DFA for binary numbers divisible by 5."""
    print("\n=== Design: Divisible by 5 ===")
    print("""
Language: binary strings whose value is divisible by 5

Memory: remainder mod 5 → 5 states

Transitions: δ(ri, b) = r_{(2i+b) mod 5}

Q = {r0, r1, r2, r3, r4}
Σ = {0, 1}
q0 = r0
F = {r0}

Transition table:
  State | 0  | 1
  ------|----|----
  →*r0  | r0 | r1
    r1  | r2 | r3
    r2  | r4 | r0
    r3  | r1 | r2
    r4  | r3 | r4

Test cases:
  '0'     = 0  → r0 ✓
  '101'   = 5  → r0 ✓
  '1010'  = 10 → r0 ✓
  '1111'  = 15 → r0 ✓
  '1'     = 1  → r1 ✗
  '11'    = 3  → r3 ✗
""")

design_dfa_example()

➕ Operations (Union, Intersection)

🎯 Combining DFAs

DFAs are closed under union, intersection, complement, and difference. We can combine DFAs using product construction and other techniques.

Closure Properties

Union: L1 ∪ L2. Intersection: L1 ∩ L2. Complement: Σ* \ L. Difference: L1 \ L2. Product: Q = Q1 × Q2. Regular: Closed under all these.

➕ Union∩ Intersection¬ Complement∖ Difference

# DFA operations — product construction
from itertools import product as cartesian_product
from typing import Set, Dict, Tuple

class DFA:
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def accepts(self, word):
        state = self.q0
        for symbol in word:
            if symbol not in self.Sigma:
                return False
            state = self.delta[(state, symbol)]
        return state in self.F
    
    def __repr__(self):
        return f"DFA({len(self.Q)} states, alphabet={self.Sigma})"


# 1. INTERSECTION (product construction)
def intersect(dfa1, dfa2):
    """
    L(M1 ∩ M2) = L(M1) ∩ L(M2)
    
    Q = Q1 × Q2
    F = F1 × F2
    δ((q1, q2), a) = (δ1(q1, a), δ2(q2, a))
    """
    new_states = set(cartesian_product(dfa1.Q, dfa2.Q))
    new_alphabet = dfa1.Sigma & dfa2.Sigma
    new_q0 = (dfa1.q0, dfa2.q0)
    new_F = {(q1, q2) for q1 in dfa1.F for q2 in dfa2.F}
    
    new_delta = {}
    for (q1, q2) in new_states:
        for symbol in new_alphabet:
            next_q1 = dfa1.delta[(q1, symbol)]
            next_q2 = dfa2.delta[(q2, symbol)]
            new_delta[((q1, q2), symbol)] = (next_q1, next_q2)
    
    return DFA(new_states, new_alphabet, new_delta, new_q0, new_F)


# 2. UNION
def union(dfa1, dfa2):
    """
    L(M1 ∪ M2) = L(M1) ∪ L(M2)
    
    Q = Q1 × Q2
    F = {(q1, q2) | q1 ∈ F1 or q2 ∈ F2}
    """
    new_states = set(cartesian_product(dfa1.Q, dfa2.Q))
    new_alphabet = dfa1.Sigma & dfa2.Sigma
    new_q0 = (dfa1.q0, dfa2.q0)
    new_F = {(q1, q2) for q1, q2 in new_states 
             if q1 in dfa1.F or q2 in dfa2.F}
    
    new_delta = {}
    for (q1, q2) in new_states:
        for symbol in new_alphabet:
            next_q1 = dfa1.delta[(q1, symbol)]
            next_q2 = dfa2.delta[(q2, symbol)]
            new_delta[((q1, q2), symbol)] = (next_q1, next_q2)
    
    return DFA(new_states, new_alphabet, new_delta, new_q0, new_F)


# 3. COMPLEMENT
def complement(dfa):
    """
    L(M') = Σ* \ L(M)
    
    Same structure, swap F with Q \ F
    """
    new_F = dfa.Q - dfa.F
    return DFA(dfa.Q, dfa.Sigma, dfa.delta.copy(), dfa.q0, new_F)


# 4. DIFFERENCE
def difference(dfa1, dfa2):
    """
    L(M1) \ L(M2) = L(M1) ∩ L(M2)^c
    """
    return intersect(dfa1, complement(dfa2))


# EXAMPLE
# DFA 1: strings ending in "01"
dfa1 = DFA(
    states={'a0', 'a1', 'a2'},
    alphabet={'0', '1'},
    delta={
        ('a0', '0'): 'a1',
        ('a0', '1'): 'a0',
        ('a1', '0'): 'a1',
        ('a1', '1'): 'a2',
        ('a2', '0'): 'a1',
        ('a2', '1'): 'a0',
    },
    q0='a0',
    F={'a2'}
)

# DFA 2: even number of 1s
dfa2 = DFA(
    states={'b0', 'b1'},
    alphabet={'0', '1'},
    delta={
        ('b0', '0'): 'b0',
        ('b0', '1'): 'b1',
        ('b1', '0'): 'b1',
        ('b1', '1'): 'b0',
    },
    q0='b0',
    F={'b0'}
)

# 5. TEST
print("=== DFA Operations ===")

# Intersection
dfa_int = intersect(dfa1, dfa2)
print(f"\nIntersection: {dfa_int}")
print(f"States: {dfa_int.Q}")
print(f"Accept: {dfa_int.F}")

# Union
dfa_uni = union(dfa1, dfa2)
print(f"\nUnion: {dfa_uni}")

# Complement
dfa_comp = complement(dfa1)
print(f"\nComplement of DFA1:")
print(f"Original F: {dfa1.F}")
print(f"New F: {dfa_comp.F}")

# Difference
dfa_diff = difference(dfa1, dfa2)
print(f"\nDifference (DFA1 \\ DFA2): {dfa_diff}")

# 6. TEST WITH STRINGS
print("\n=== Test Strings ===")
test_strings = ['01', '011', '0111', '0101', '0011', '111', '10101']

print(f"{'String':<10} {'DFA1':<8} {'DFA2':<8} {'Int':<8} {'Uni':<8} {'Diff':<8}")
print("-" * 55)

for s in test_strings:
    r1 = dfa1.accepts(s)
    r2 = dfa2.accepts(s)
    ri = dfa_int.accepts(s)
    ru = dfa_uni.accepts(s)
    rd = dfa_diff.accepts(s)
    
    print(f"{s:<10} {str(r1):<8} {str(r2):<8} {str(ri):<8} {str(ru):<8} {str(rd):<8}")

# 7. PRODUCT CONSTRUCTION VISUALIZATION
print("\n=== Product Construction State Count ===")
print(f"DFA1 states: {len(dfa1.Q)}")
print(f"DFA2 states: {len(dfa2.Q)}")
print(f"Product states: {len(dfa1.Q) * len(dfa2.Q)}")
print(f"Reachable states may be fewer!")

# 8. CLOSURE PROPERTIES
print("\n=== Closure Properties of Regular Languages ===")
print("""
Regular languages are closed under:

1. UNION: L1 ∪ L2 is regular
2. INTERSECTION: L1 ∩ L2 is regular
3. COMPLEMENT: Σ* \ L is regular
4. DIFFERENCE: L1 \ L2 is regular
5. CONCATENATION: L1 · L2 is regular
6. KLEENE STAR: L* is regular
7. REVERSAL: L^R is regular
8. HOMOMORPHISM: h(L) is regular
9. INVERSE HOMOMORPHISM: h⁻¹(L) is regular

Proof: Constructive — show how to build the DFA/NFA

Non-regular operations:
- Infinite union of regular may be non-regular
- Subset of regular may be non-regular
""")

📉 DFA Minimization

🎯 Finding the Smallest DFA

DFA minimization finds the smallest DFA that accepts the same language. The minimal DFA is unique up to isomorphism and has no redundant states.

Minimization Algorithm

1. Remove unreachable: States not reachable from q₀. 2. Remove dead: States that can't reach accept. 3. Partition refinement: Hopcroft's algorithm. 4. Merge equivalent: States with same behavior. Result: Minimal DFA, unique up to naming.

🔍 Unreachable💀 Dead📊 Partition✅ Unique

# DFA Minimization — Hopcroft's algorithm
from collections import defaultdict, deque
from typing import Set, Dict, Tuple, FrozenSet

class DFA:
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def accepts(self, word):
        state = self.q0
        for symbol in word:
            state = self.delta[(state, symbol)]
        return state in self.F


# 1. REMOVE UNREACHABLE STATES
def remove_unreachable(dfa):
    """Remove states not reachable from q0."""
    reachable = {dfa.q0}
    queue = deque([dfa.q0])
    
    while queue:
        state = queue.popleft()
        for symbol in dfa.Sigma:
            next_state = dfa.delta.get((state, symbol))
            if next_state is not None and next_state not in reachable:
                reachable.add(next_state)
                queue.append(next_state)
    
    new_delta = {
        (q, s): d
        for (q, s), d in dfa.delta.items()
        if q in reachable and d in reachable
    }
    
    return DFA(
        states=reachable,
        alphabet=dfa.Sigma,
        delta=new_delta,
        q0=dfa.q0,
        F=dfa.F & reachable
    )


# 2. REMOVE DEAD STATES
def remove_dead(dfa):
    """Remove states from which no accept state is reachable."""
    # Reverse transitions
    reverse = defaultdict(list)
    for (q, s), d in dfa.delta.items():
        reverse[d].append(q)
    
    # BFS from F backwards
    live = set(dfa.F)
    queue = deque(dfa.F)
    
    while queue:
        state = queue.popleft()
        for prev in reverse[state]:
            if prev not in live:
                live.add(prev)
                queue.append(prev)
    
    # Add q0 to keep structure (even if not "live")
    live.add(dfa.q0)
    
    new_delta = {
        (q, s): d
        for (q, s), d in dfa.delta.items()
        if q in live and d in live
    }
    
    return DFA(
        states=live,
        alphabet=dfa.Sigma,
        delta=new_delta,
        q0=dfa.q0,
        F=dfa.F & live
    )


# 3. HOPCROFT'S ALGORITHM (partition refinement)
def minimize_dfa(dfa):
    """
    Hopcroft's algorithm for DFA minimization.
    
    1. Remove unreachable and dead states
    2. Start with partition {F, Q\F}
    3. Refine partition until stable
    4. Merge states in same partition
    """
    # Clean up
    dfa = remove_unreachable(dfa)
    dfa = remove_dead(dfa)
    
    # Initial partition
    F = frozenset(dfa.F)
    non_F = frozenset(dfa.Q - dfa.F)
    
    partitions = []
    if F:
        partitions.append(F)
    if non_F:
        partitions.append(non_F)
    
    # Refinement loop
    changed = True
    while changed:
        changed = False
        new_partitions = []
        
        for group in partitions:
            # Try to split this group
            split = split_group(group, partitions, dfa)
            new_partitions.extend(split)
            if len(split) > 1:
                changed = True
        
        partitions = new_partitions
    
    # Build new DFA from partitions
    return build_minimal_dfa(dfa, partitions)


def split_group(group, partitions, dfa):
    """Split a group based on transitions to other partitions."""
    if len(group) <= 1:
        return [group]
    
    # Assign partition index to each group
    partition_of = {}
    for i, part in enumerate(partitions):
        for state in part:
            partition_of[state] = i
    
    # Signature of each state: which partition each symbol leads to
    signatures = defaultdict(list)
    for state in group:
        sig = tuple(
            partition_of.get(dfa.delta.get((state, s), state), -1)
            for s in sorted(dfa.Sigma)
        )
        signatures[sig].append(state)
    
    return [frozenset(states) for states in signatures.values()]


def build_minimal_dfa(dfa, partitions):
    """Build minimal DFA from partition refinement."""
    # Map state to its partition
    state_to_part = {}
    for i, part in enumerate(partitions):
        for state in part:
            state_to_part[state] = i
    
    # New states are partition indices
    new_Q = set(range(len(partitions)))
    new_q0 = state_to_part[dfa.q0]
    new_F = {state_to_part[s] for s in dfa.F}
    
    # New transitions
    new_delta = {}
    for state in dfa.Q:
        for symbol in dfa.Sigma:
            next_state = dfa.delta[(state, symbol)]
            new_delta[(state_to_part[state], symbol)] = state_to_part[next_state]
    
    return DFA(new_Q, dfa.Sigma, new_delta, new_q0, new_F)


# 4. EXAMPLE
print("=== Minimization Example ===")

# Non-minimal DFA for "ends in 01"
# Has redundant states
dfa_original = DFA(
    states={'q0', 'q1', 'q2', 'q3', 'q4'},
    alphabet={'0', '1'},
    delta={
        ('q0', '0'): 'q1',
        ('q0', '1'): 'q3',
        ('q1', '0'): 'q1',
        ('q1', '1'): 'q2',
        ('q2', '0'): 'q1',
        ('q2', '1'): 'q4',
        ('q3', '0'): 'q1',
        ('q3', '1'): 'q3',
        ('q4', '0'): 'q1',
        ('q4', '1'): 'q3',
    },
    q0='q0',
    F={'q2'}
)

print(f"Original: {len(dfa_original.Q)} states")

# Minimize
dfa_minimal = minimize_dfa(dfa_original)
print(f"Minimal:  {len(dfa_minimal.Q)} states")

# 5. VERIFY EQUIVALENCE
def test_equivalence(dfa1, dfa2, max_length=8):
    """Test if two DFAs accept same language."""
    from itertools import product
    
    for length in range(max_length + 1):
        for symbols in product(dfa1.Sigma, repeat=length):
            word = ''.join(symbols)
            r1 = dfa1.accepts(word)
            r2 = dfa2.accepts(word)
            if r1 != r2:
                return False, word, r1, r2
    
    return True, None, None, None

print("\n=== Equivalence Test ===")
equiv, counter, r1, r2 = test_equivalence(dfa_original, dfa_minimal, max_length=10)

if equiv:
    print("✓ DFAs are equivalent (up to length 10)")
else:
    print(f"✗ Differ on '{counter}': original={r1}, minimal={r2}")

# 6. MYHILL-NERODE THEOREM
print("\n=== Myhill-Nerode Theorem ===")
print("""
The minimal DFA is unique!

Theorem (Myhill-Nerode):
  A language L is regular iff
  L has finitely many equivalence classes
  under the relation:
    x ~ y iff for all z: (xz ∈ L) ↔ (yz ∈ L)

The number of states in the minimal DFA
equals the number of equivalence classes.

Implications:
  - Unique minimal DFA
  - Decidable: is L regular?
  - Characterizes regular languages

Example: L = strings ending in '01'
  Classes:
    [ε]     = {w : w doesn't end in 0 or 01}
    [0]     = {w : w ends in 0 but not 01}
    [01]    = {w : w ends in 01}
  
  So minimal DFA has exactly 3 states!
""")

# 7. WHY MINIMIZE
print("\n=== Why Minimize? ===")
print("""
1. EFFICIENCY
   - Fewer states → smaller memory
   - Faster implementation

2. UNDERSTANDING
   - Reveals true complexity
   - Structural insight

3. VERIFICATION
   - Canonical form
   - Easy comparison

4. THEORY
   - Myhill-Nerode theorem
   - Decision procedures

Applications:
  - Lexical analyzer optimization
  - Hardware circuit design
  - Protocol verification
""")

🟰 Equivalence & Testing

🎯 Are Two DFAs the Same?

Two DFAs are equivalent if they accept the same language. Testing equivalence is decidable and efficient — one of the key advantages of finite automata.

Equivalence Testing

Approach 1: Minimize both, check isomorphism. Approach 2: Product construction, check reachable F. Complexity: O(|Q1| × |Q2|). Decidable: Yes, always. Difference: Symmetric difference. Counterexample: Shortest distinguishing string.

🟰 Equivalence📊 Product🔍 Diff🎯 Counterexample

# DFA equivalence testing
from collections import deque
from typing import Optional, Tuple
from itertools import product

class DFA:
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def accepts(self, word):
        state = self.q0
        for symbol in word:
            state = self.delta[(state, symbol)]
        return state in self.F


# 1. PRODUCT CONSTRUCTION FOR EQUIVALENCE
def check_equivalence(dfa1, dfa2) -> Tuple[bool, Optional[str]]:
    """
    Check if two DFAs are equivalent.
    
    Returns:
      (True, None) if equivalent
      (False, counterexample) if not
    
    Method: BFS on product automaton.
    If we reach state (q1, q2) where q1 ∈ F1 XOR q2 ∈ F2,
    then the path to this state is a counterexample.
    """
    # Handle alphabet mismatch
    if dfa1.Sigma != dfa2.Sigma:
        return False, "Different alphabets"
    
    # BFS on product
    start = (dfa1.q0, dfa2.q0)
    queue = deque([(start, "")])  # (state pair, string so far)
    visited = {start}
    
    while queue:
        (q1, q2), word = queue.popleft()
        
        # Check if this is a distinguishing state
        in_F1 = q1 in dfa1.F
        in_F2 = q2 in dfa2.F
        
        if in_F1 != in_F2:
            # Found distinguishing string
            return False, word
        
        # Explore next states
        for symbol in dfa1.Sigma:
            next_q1 = dfa1.delta[(q1, symbol)]
            next_q2 = dfa2.delta[(q2, symbol)]
            next_state = (next_q1, next_q2)
            
            if next_state not in visited:
                visited.add(next_state)
                queue.append((next_state, word + symbol))
    
    # No distinguishing string found
    return True, None


# 2. TEST
print("=== DFA Equivalence Test ===")

# DFA 1: ends in "01"
dfa1 = DFA(
    states={'a0', 'a1', 'a2'},
    alphabet={'0', '1'},
    delta={
        ('a0', '0'): 'a1',
        ('a0', '1'): 'a0',
        ('a1', '0'): 'a1',
        ('a1', '1'): 'a2',
        ('a2', '0'): 'a1',
        ('a2', '1'): 'a0',
    },
    q0='a0',
    F={'a2'}
)

# DFA 2: equivalent but with more states
dfa2 = DFA(
    states={'b0', 'b1', 'b2', 'b3', 'b4'},
    alphabet={'0', '1'},
    delta={
        ('b0', '0'): 'b1',
        ('b0', '1'): 'b3',
        ('b1', '0'): 'b1',
        ('b1', '1'): 'b2',
        ('b2', '0'): 'b1',
        ('b2', '1'): 'b3',
        ('b3', '0'): 'b1',
        ('b3', '1'): 'b3',
        ('b4', '0'): 'b1',
        ('b4', '1'): 'b2',
    },
    q0='b0',
    F={'b2'}
)

# DFA 3: different language (ends in "10")
dfa3 = DFA(
    states={'c0', 'c1', 'c2'},
    alphabet={'0', '1'},
    delta={
        ('c0', '0'): 'c0',
        ('c0', '1'): 'c1',
        ('c1', '0'): 'c2',
        ('c1', '1'): 'c1',
        ('c2', '0'): 'c0',
        ('c2', '1'): 'c1',
    },
    q0='c0',
    F={'c2'}
)

# Test pairs
pairs = [
    ("DFA1 vs DFA2 (should be equivalent)", dfa1, dfa2),
    ("DFA1 vs DFA3 (should differ)", dfa1, dfa3),
]

for name, d1, d2 in pairs:
    print(f"\n{name}:")
    equiv, counter = check_equivalence(d1, d2)
    
    if equiv:
        print("  ✓ Equivalent (no distinguishing string)")
    else:
        print(f"  ✗ Not equivalent")
        print(f"  Counterexample: '{counter}'")
        print(f"    DFA1 accepts: {d1.accepts(counter)}")
        print(f"    DFA2 accepts: {d2.accepts(counter)}")


# 3. ISOMORPHISM CHECK
def are_isomorphic(dfa1, dfa2) -> bool:
    """
    Check if two DFAs are isomorphic (same structure).
    
    Must have same number of states.
    BFS from start states, matching structure.
    """
    if len(dfa1.Q) != len(dfa2.Q):
        return False
    
    # Map from dfa1 state to dfa2 state
    mapping = {dfa1.q0: dfa2.q0}
    queue = deque([(dfa1.q0, dfa2.q0)])
    
    while queue:
        q1, q2 = queue.popleft()
        
        # Check accepting status matches
        if (q1 in dfa1.F) != (q2 in dfa2.F):
            return False
        
        # Check transitions
        for symbol in dfa1.Sigma:
            next_q1 = dfa1.delta[(q1, symbol)]
            next_q2 = dfa2.delta[(q2, symbol)]
            
            if next_q1 in mapping:
                if mapping[next_q1] != next_q2:
                    return False
            else:
                mapping[next_q1] = next_q2
                queue.append((next_q1, next_q2))
    
    return True


# 4. SHORTEST DISTINGUISHING STRING
def shortest_distinguishing(dfa1, dfa2) -> Optional[str]:
    """
    Find shortest string accepted by exactly one DFA.
    
    BFS gives shortest automatically.
    """
    _, counter = check_equivalence(dfa1, dfa2)
    return counter


# 5. LANGUAGE OPERATIONS USING EQUIVALENCE
print("\n=== Language Operations ===")

def is_empty(dfa):
    """Check if DFA accepts empty language."""
    # Check if any accept state is reachable
    reachable = {dfa.q0}
    queue = deque([dfa.q0])
    
    while queue:
        state = queue.popleft()
        if state in dfa.F:
            return False
        for symbol in dfa.Sigma:
            next_state = dfa.delta[(state, symbol)]
            if next_state not in reachable:
                reachable.add(next_state)
                queue.append(next_state)
    
    return True

def is_universal(dfa):
    """Check if DFA accepts all strings."""
    # Complement should be empty
    F_complement = dfa.Q - dfa.F
    dfa_comp = DFA(dfa.Q, dfa.Sigma, dfa.delta, dfa.q0, F_complement)
    return is_empty(dfa_comp)

def is_subset(dfa1, dfa2):
    """Check if L(dfa1) ⊆ L(dfa2)."""
    # L1 \ L2 should be empty
    # = L1 ∩ complement(L2)
    return is_empty(difference(dfa1, dfa2))

def is_disjoint(dfa1, dfa2):
    """Check if L(dfa1) ∩ L(dfa2) = ∅."""
    return is_empty(intersect(dfa1, dfa2))

# Tests
print(f"\nDFA1 is empty: {is_empty(dfa1)}")
print(f"DFA1 is universal: {is_universal(dfa1)}")
print(f"DFA1 is disjoint from DFA3: {is_disjoint(dfa1, dfa3)}")


# 6. DECISION PROBLEMS
print("\n=== Decidable Problems for DFAs ===")
print("""
All these problems are DECIDABLE:

1. MEMBERSHIP
   "Is w ∈ L(M)?"
   → Simulate DFA, O(|w|)

2. EMPTINESS
   "Is L(M) = ∅?"
   → Check if any accept state reachable
   → BFS from start

3. UNIVERSALITY
   "Is L(M) = Σ*?"
   → Complement is empty
   → Decidable

4. EQUIVALENCE
   "Is L(M1) = L(M2)?"
   → Product construction
   → O(|Q1| × |Q2|)

5. INCLUSION
   "Is L(M1) ⊆ L(M2)?"
   → L(M1) ∩ L(M2)^c = ∅?

6. DISJOINTNESS
   "Is L(M1) ∩ L(M2) = ∅?"
   → Product construction

7. FINITENESS
   "Is L(M) finite?"
   → Detect cycles on paths to accept

All these are efficient and always terminate.
""")

# 7. FINITENESS CHECK
def is_finite(dfa):
    """Check if L(M) is finite."""
    # Detect cycle reachable from q0 that can reach F
    # DFS with colors
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {state: WHITE for state in dfa.Q}
    
    def can_reach_F(state):
        """Check if state can reach an accept state."""
        visited = {state}
        queue = deque([state])
        while queue:
            s = queue.popleft()
            if s in dfa.F:
                return True
            for symbol in dfa.Sigma:
                next_s = dfa.delta[(s, symbol)]
                if next_s not in visited:
                    visited.add(next_s)
                    queue.append(next_s)
        return False
    
    def dfs(state):
        """DFS to detect cycle leading to F."""
        if color[state] == GRAY:
            # Cycle detected
            return can_reach_F(state)
        if color[state] == BLACK:
            return False
        
        color[state] = GRAY
        
        for symbol in dfa.Sigma:
            next_state = dfa.delta[(state, symbol)]
            if dfs(next_state):
                return True
        
        color[state] = BLACK
        return False
    
    has_cycle = dfs(dfa.q0)
    return not has_cycle

print(f"\nDFA1 is finite: {is_finite(dfa1)}")
print(f"DFA1 is infinite: {not is_finite(dfa1)}")


# 8. SUMMARY
print("\n=== Summary ===")
print(f"{'Problem':<20} {'Complexity':<20} {'Method':<30}")
print("-" * 70)
print(f"{'Membership':<20} {'O(|w|)':<20} {'Simulate':<30}")
print(f"{'Emptiness':<20} {'O(|Q|)':<20} {'BFS from q0':<30}")
print(f"{'Universality':<20} {'O(|Q|)':<20} {'Complement + empty':<30}")
print(f"{'Equivalence':<20} {'O(|Q1|×|Q2|)':<20} {'Product':<30}")
print(f"{'Inclusion':<20} {'O(|Q1|×|Q2|)':<20} {'Product':<30}")
print(f"{'Finiteness':<20} {'O(|Q|)':<20} {'Cycle detection':<30}")

🔀 NFA vs DFA

🎯 Two Models, Same Power

NFAs (Nondeterministic Finite Automata) allow multiple transitions from a state on the same symbol, plus ε-transitions. They're easier to design but no more powerful than DFAs — every NFA has an equivalent DFA.

Key Differences

DFA: Exactly one transition per (state, symbol). NFA: Zero, one, or many transitions. ε-transitions: NFA only. Simulation: DFA easy, NFA requires subset construction. Power: Both recognize regular languages. Size: NFA can be exponentially smaller.

🎯 Deterministic🔀 Nondeterministicε Transitions📊 Subset

# NFA vs DFA — comparison and conversion
from collections import deque, defaultdict
from itertools import chain

# 1. NFA DEFINITION
class NFA:
    """
    Nondeterministic Finite Automaton.
    
    δ: Q × Σ → P(Q)      (set of states)
    Plus ε-transitions:  δ: Q × {ε} → P(Q)
    """
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta          # Dict[(state, symbol), set of states]
        self.q0 = q0
        self.F = F
    
    def epsilon_closure(self, states):
        """Compute ε-closure of a set of states."""
        closure = set(states)
        stack = list(states)
        
        while stack:
            state = stack.pop()
            for next_state in self.delta.get((state, 'ε'), set()):
                if next_state not in closure:
                    closure.add(next_state)
                    stack.append(next_state)
        
        return closure
    
    def accepts(self, word):
        """Simulate NFA (subset simulation)."""
        current = self.epsilon_closure({self.q0})
        
        for symbol in word:
            next_states = set()
            for state in current:
                next_states |= self.delta.get((state, symbol), set())
            current = self.epsilon_closure(next_states)
        
        return bool(current & self.F)


# 2. SUBSET CONSTRUCTION (NFA → DFA)
def nfa_to_dfa(nfa):
    """
    Convert NFA to DFA via subset construction.
    
    States: subsets of NFA states (P(Q))
    Start: ε-closure({q0})
    δ_D(S, a) = ε-closure(∪_{q ∈ S} δ_N(q, a))
    F_D = {S ⊆ Q | S ∩ F_N ≠ ∅}
    """
    # Start state
    start = frozenset(nfa.epsilon_closure({nfa.q0}))
    
    # BFS over subsets
    dfa_states = {start}
    queue = deque([start])
    dfa_delta = {}
    
    while queue:
        current_set = queue.popleft()
        
        for symbol in nfa.Sigma:
            # Compute next subset
            next_set = set()
            for state in current_set:
                next_set |= nfa.delta.get((state, symbol), set())
            
            next_set = frozenset(nfa.epsilon_closure(next_set))
            
            dfa_delta[(current_set, symbol)] = next_set
            
            if next_set not in dfa_states:
                dfa_states.add(next_set)
                queue.append(next_set)
    
    # Accept states: subsets containing an NFA accept state
    dfa_F = {s for s in dfa_states if s & nfa.F}
    
    return DFA_FromSubsets(dfa_states, nfa.Sigma, dfa_delta, start, dfa_F)


class DFA_FromSubsets:
    """DFA built from subset construction."""
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def accepts(self, word):
        state = self.q0
        for symbol in word:
            state = self.delta[(state, symbol)]
        return state in self.F
    
    def state_count(self):
        return len(self.Q)


# 3. EXAMPLE: NFA for strings ending in "01"
print("=== NFA Example ===")
print("""
NFA for "ends in 01":
  Q = {q0, q1, q2}
  Σ = {0, 1}
  δ:
    (q0, 0) → {q0, q1}
    (q0, 1) → {q0}
    (q1, 1) → {q2}
    (q2, 0) → {}  (dead)
    (q2, 1) → {}  (dead)
  q₀ = q0
  F = {q2}

Key: from q0 on '0', can stay OR advance to q1
""")

nfa = NFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'0', '1'},
    delta={
        ('q0', '0'): {'q0', 'q1'},
        ('q0', '1'): {'q0'},
        ('q1', '0'): set(),
        ('q1', '1'): {'q2'},
        ('q2', '0'): set(),
        ('q2', '1'): set(),
    },
    q0='q0',
    F={'q2'}
)

# Test NFA
test_strings = ['01', '101', '001', '10', '11', '1', '0', '']
print("NFA acceptance:")
for s in test_strings:
    result = "✓" if nfa.accepts(s) else "✗"
    print(f"  '{s}' → {result}")

# Convert to DFA
print("\n=== Subset Construction ===")
dfa = nfa_to_dfa(nfa)
print(f"NFA states: {len(nfa.Q)}")
print(f"DFA states: {dfa.state_count()}")

# 4. COMPARISON TABLE
print("\n=== NFA vs DFA Comparison ===")
print(f"{'Aspect':<30} {'DFA':<25} {'NFA':<25}")
print("-" * 80)
print(f"{'Transitions per (q, a)':<30} {'Exactly 1':<25} {'0, 1, or more':<25}")
print(f"{'ε-transitions':<30} {'No':<25} {'Yes':<25}")
print(f"{'State at any time':<30} {'Exactly 1':<25} {'Set of states':<25}")
print(f"{'Acceptance':<30} {'Unique path':<25} {'Any path accepts':<25}")
print(f"{'Simulation':<30} {'Easy':<25} {'Requires subsets':<25}")
print(f"{'Design ease':<30} {'Harder':<25} {'Easier':<25}")
print(f"{'Memory':<30} {'Small':<25} {'Same or smaller':<25}")
print(f"{'Expressive power':<30} {'Regular':<25} {'Regular (same)':<25}")

# 5. WHY NFAs ARE USEFUL
print("\n=== Why NFAs Are Useful ===")
print("""
1. EASIER TO DESIGN
   - Multiple choices are natural
   - "Guess" the right path
   - No need to combine transitions

2. CONCISE REPRESENTATION
   - Sometimes exponentially smaller
   - Example: strings with k-th symbol = 'a'
     - NFA: O(k) states
     - DFA: O(2^k) states

3. REGEX COMPILATION
   - Thompson's construction builds NFA from regex
   - Then subset construction to DFA
   - Standard compiler technique

4. PROOFS
   - Closure properties easier with NFA
   - Union, concatenation, star

5. SIMPLER CORRECTNESS
   - Design NFA first
   - Then convert to DFA
   - Easier to reason about
""")

# 6. ε-NFA EXAMPLE
print("\n=== ε-NFA Example ===")
print("""
ε-NFA: accepts strings of form a*b*

States: {q0, q1, q2}
  q0: initial (matches a*)
  q1: accepts b* (via ε from q0)
  q2: accepts b*

Transitions:
  (q0, 'a') → {q0}
  (q0, 'ε') → {q1}
  (q1, 'b') → {q1}
  q0 = q0
  F = {q0, q1}

This accepts: '', 'a', 'aa', 'b', 'bb', 'ab', 'aab', 'abb', 'aaabbb'
Rejects: 'ba', 'bab', 'aba' (a after b)
""")

# 7. PRACTICAL CONVERSION
print("\n=== Practical Conversion Example ===")
print("""
Convert ε-NFA to DFA:
  1. Compute ε-closure of start state → initial DFA state
  2. For each DFA state (subset of NFA states):
     - For each symbol: compute next subset
     - Apply ε-closure to result
     - Add new DFA state if not seen
  3. Repeat until all subsets processed
  4. Accept if subset contains NFA accept state

Result: DFA with at most 2^n states
        (but usually much fewer reachable)

Complexity:
  Worst case: exponential blowup
  Practical: usually manageable
  For regex: linear in pattern size (up to blowup)
""")

# 8. DECISION: WHICH TO USE
print("=== Which Model to Use? ===")
print("""
USE NFA WHEN:
  ✓ Designing a new automaton (easier)
  ✓ Working with regex
  ✓ Proving closure properties
  ✓ Theoretical arguments

USE DFA WHEN:
  ✓ Implementing (faster simulation)
  ✓ Optimization (lexer, pattern matching)
  ✓ Hardware design
  ✓ Need deterministic behavior

IN PRACTICE:
  - Design as NFA (easier)
  - Convert to DFA (subset construction)
  - Minimize DFA (Hopcroft)
  - Implement the minimized DFA
""")

🔤 Regular Expressions

🎯 Regex and DFAs Are Equivalent

Regular expressions and DFAs describe exactly the same class of languages. Kleene's theorem shows the equivalence: for every regex, there's a DFA, and vice versa.

Kleene's Theorem

→: Regex → NFA (Thompson construction). →: NFA → DFA (subset construction). →: DFA → Regex (state elimination). Equivalence: All describe regular languages. Practical: Regex in grep, sed, Python re. Implementation: Backtracking or NFA/DFA.

🔤 Regex⚙️ Thompson📊 Subset🎯 Equivalence

# Regular expressions and DFA conversion
import re
from typing import Set

# 1. REGEX SYNTAX
print("=== Regex Syntax ===")
print("""
BASIC OPERATIONS:
  a       — literal 'a'
  ε       — empty string
  ∅       — empty set (nothing)
  R|S     — union (R or S)
  RS      — concatenation (R followed by S)
  R*      — Kleene star (0 or more R's)
  R+      — 1 or more (R R*)
  R?      — 0 or 1 (R | ε)

CHARACTER CLASSES:
  [abc]   — a, b, or c
  [a-z]   — any lowercase
  [^abc]  — anything except a, b, c
  .       — any character

ANCHORS:
  ^       — start of string
  $       — end of string
  \\b      — word boundary

QUANTIFIERS:
  {n}     — exactly n
  {n,}    — n or more
  {n,m}   — between n and m

Precedence (highest to lowest):
  1. Parentheses ()
  2. Star *
  3. Concatenation
  4. Union |
""")

# 2. REGEX TO DFA (via NFA)
print("=== Regex → NFA → DFA ===")
print("""
Thompson's Construction (Regex → NFA):
  
  Base cases:
    a:    →(q0)--a--→(q1)
    ε:    →(q0)--ε--→(q1)
    ∅:    →(q0)  (no accept)
  
  Operations:
    R|S:  new start with ε to R's start and S's start
          both end states connect via ε to new accept
    
    RS:   connect R's accept to S's start via ε
    
    R*:   new start & accept with ε-loops
    
  Then: NFA → DFA via subset construction
""")

def regex_to_dfa(regex_pattern, alphabet):
    """
    Conceptual: convert regex to DFA.
    In practice, use libraries or implement Thompson's construction.
    """
    # Compile regex
    compiled = re.compile(regex_pattern)
    
    class RegexDFA:
        """Simple DFA-like wrapper around Python's re module."""
        def __init__(self, pattern):
            self.pattern = re.compile(pattern)
        
        def accepts(self, word):
            return bool(self.pattern.fullmatch(word))
    
    return RegexDFA(regex_pattern)


# 3. EXAMPLES
print("\n=== Regex Examples ===")

examples = [
    (r'(0|1)*01', 'ends in "01"'),
    (r'(0|1)*', 'any binary string'),
    (r'(00|11)*', 'even runs of 0s and 1s'),
    (r'0*1*', 'any number of 0s followed by 1s'),
    (r'(01)+', 'repeated "01" at least once'),
    (r'[a-z]+', 'one or more lowercase letters'),
    (r'a(b|c)*d', 'a, then any b/c, then d'),
    (r'(a|b)*abb', 'ends in "abb"'),
]

for pattern, description in examples:
    print(f"\n  {pattern:<20} — {description}")

# 4. USE WITH PYTHON re
print("\n=== Python re Module ===")

# Test a regex
pattern = r'(0|1)*01'
test_strings = ['01', '101', '001', '10', '11', '1', '0', '']

print(f"Pattern: {pattern}")
for s in test_strings:
    match = re.fullmatch(pattern, s)
    result = "✓" if match else "✗"
    print(f"  '{s}' → {result}")

# 5. REGEX OPERATIONS
print("\n=== Regex Operations ===")
print("""
UNION: R1 | R2
  Matches strings in R1 OR R2
  Corresponds to: L(R1) ∪ L(R2)

CONCATENATION: R1 R2
  Matches R1 followed by R2
  Corresponds to: L(R1) · L(R2)

KLEENE STAR: R*
  Zero or more repetitions
  Corresponds to: L(R)*

CLOSURE PROPERTIES:
  - Union is regular
  - Concatenation is regular
  - Star is regular
  - All regex are regular!
""")

# 6. NFA CONSTRUCTION FOR REGEX
print("\n=== Thompson's Construction Rules ===")
print("""
For each regex operator, we build a piece:

1. LITERAL a:
   ε → (q_start) --a--> (q_end) → ε

2. UNION R1|R2:
              ε    [R1]    ε
   →(q0) ──→ ┌─→(R1)→─┐ ──→ (q_accept)
              │        │
              ε   [R2]  ε
              └─→(R2)→─┘

3. CONCATENATION R1 R2:
   →(R1)→ε→(R2)→

4. STAR R*:
           ε ┌────→────┐
             │         │
   →(q0) ──→ (R) ──→ (qf)
       │              ↑
       └──────ε───────┘

5. PLUS R+ = R R*
6. OPTIONAL R? = R|ε

Each piece has:
  - Exactly one start state
  - Exactly one accept state
  - No transitions into start
  - No transitions out of accept
""")

# 7. STATE ELIMINATION (DFA → Regex)
print("\n=== DFA → Regex (State Elimination) ===")
print("""
Reverse direction: Convert DFA to Regex.

Algorithm:
  1. Add new start and accept states with ε-transitions
  2. Repeatedly eliminate states:
     - For each state q to eliminate:
       - For each pair (p, r) with p → q and q → r:
         - Add edge p → r with regex R(p,q) R(q,q)* R(q,r)
  3. Continue until only start and accept remain
  4. Result: single regex

Example:
  DFA ending in "01" → regex (0|1)*01
  
Complexity: Exponential in worst case
""")

# 8. PRACTICAL REGEX ENGINE
class SimpleRegexEngine:
    """
    Simple regex engine that compiles to DFA-like behavior.
    Educational — Python's re is much more powerful.
    """
    def __init__(self, pattern):
        self.pattern = re.compile(pattern)
    
    def match(self, text):
        return bool(self.pattern.fullmatch(text))
    
    def search(self, text):
        return self.pattern.search(text)


# 9. LIMITATIONS
print("\n=== Regex Limitations ===")
print("""
Regex CAN'T express (non-regular):
  ✗ Balanced parentheses: a^n b^n
  ✗ Palindromes: w = w^R
  ✗ Prime length strings
  ✗ Nested structures (JSON, HTML)

Why?
  These require unbounded memory
  DFAs have finite states → bounded memory

For these, need:
  - Context-free grammars (CFG)
  - Pushdown automata (PDA)
  - Turing machines (TM)
""")

# 10. PRACTICAL USE
print("\n=== Practical Regex Uses ===")
print("""
1. VALIDATION
   - Email addresses
   - Phone numbers
   - URLs
   - Dates

2. SEARCH & REPLACE
   - Find patterns in text
   - Substitution
   - Clean data

3. TOKENIZATION
   - Lexical analysis
   - Split into tokens
   - Language parsing

4. EXTRACTION
   - Extract emails from text
   - Parse logs
   - Scrape data

5. FILTERING
   - Match allowed patterns
   - Block suspicious input

Used in: grep, sed, awk, Python, JavaScript, 
         and every modern programming language
""")

# 11. COMPLEXITY
print("=== Regex Complexity ===")
print(f"{'Operation':<25} {'DFA-based':<20} {'Backtracking':<20}")
print("-" * 65)
print(f"{'Match':<25} {'O(n)':<20} {'O(2^n) worst':<20}")
print(f"{'Compile':<25} {'O(m × 2^m)':<20} {'O(m)':<20}")
print(f"{'Memory':<25} {'O(2^m)':<20} {'O(m × n)':<20}")
print(f"\nWhere m = pattern length, n = text length")

print("""
Note:
  - Python re uses backtracking (fast usually, slow worst case)
  - RE2, Rust regex use NFA/DFA (linear time)
  - For untrusted input, use RE2 or similar
""")

# 12. DEMONSTRATION
print("\n=== Complete Demonstration ===")

# A simple regex
pattern = r'[a-z]+@[a-z]+\.com'
regex_dfa = regex_to_dfa(pattern, set('abcdefghijklmnopqrstuvwxyz@.'))

emails = [
    "user@example.com",
    "test@domain.com",
    "invalid",
    "user@invalid.org",
    "a@b.com",
]

print(f"Pattern: {pattern}")
for email in emails:
    result = "✓ MATCH" if regex_dfa.accepts(email) else "✗ NO MATCH"
    print(f"  {email:<25} → {result}")

💼 Applications

🎯 DFAs in the Real World

DFAs aren't just theoretical — they power many real systems. From text editors to network protocols, DFAs are everywhere efficient pattern recognition is needed.

Application Domains

Compilers: Lexical analysis. Text editors: Search and replace. Network: Protocol parsing. Hardware: Digital circuits. Bioinformatics: DNA sequence matching. AI: Model checking, NLP.

💻 Compilers📝 Editors🌐 Network🔬 Science

# Applications of DFAs
import re
from collections import deque

# 1. LEXICAL ANALYSIS (Compiler Frontend)
print("=== Lexical Analysis ===")
print("""
Compilers use DFAs to tokenize source code:

Tokens:
  Keywords:  if, else, while, for, ...
  Identifiers: [a-zA-Z_][a-zA-Z0-9_]*
  Numbers:   [0-9]+(\\.[0-9]+)?
  Operators: +, -, *, /, ==, !=
  Delimiters: ( ) { } ; ,
  Whitespace: space, tab, newline

Each token type = one DFA
Combined DFA = scanner/lexer

Real examples:
  - Lex (original)
  - Flex (fast lex)
  - ANTLR lexers
  - Hand-written lexers
""")

# Simple lexer using DFA-like logic
class SimpleLexer:
    def __init__(self, source):
        self.source = source
        self.pos = 0
        self.tokens = []
    
    def tokenize(self):
        while self.pos < len(self.source):
            char = self.source[self.pos]
            
            if char.isspace():
                self.pos += 1
                continue
            
            if char.isdigit():
                self.tokens.append(('NUMBER', self.read_number()))
            elif char.isalpha() or char == '_':
                self.tokens.append(('IDENT', self.read_ident()))
            elif char in '+-*/()=':
                self.tokens.append(('OP', char))
                self.pos += 1
            else:
                self.pos += 1
        
        return self.tokens
    
    def read_number(self):
        start = self.pos
        while self.pos < len(self.source) and self.source[self.pos].isdigit():
            self.pos += 1
        return self.source[start:self.pos]
    
    def read_ident(self):
        start = self.pos
        while self.pos < len(self.source) and (self.source[self.pos].isalnum() or self.source[self.pos] == '_'):
            self.pos += 1
        return self.source[start:self.pos]

lexer = SimpleLexer("x = 10 + y * 3")
print(f"Tokens: {lexer.tokenize()}")

# 2. TEXT SEARCH (grep, editor find)
print("\n=== Text Search ===")
print("""
grep uses DFA-like matching:

  grep 'pattern' file     — find lines matching pattern
  sed 's/old/new/' file   — replace pattern

Editors:
  VS Code, Vim, Emacs — regex search
  Ctrl+F with regex

Implementation:
  - Simple patterns: DFA (fast)
  - Complex patterns (backreferences): backtracking
  - RE2/DFA: linear time, no backreferences
""")

def grep(pattern, text):
    """Simple grep using regex."""
    regex = re.compile(pattern)
    results = []
    for i, line in enumerate(text.split('\n'), 1):
        if regex.search(line):
            results.append((i, line))
    return results

text = """Hello World
Python is great
Programming is fun
Hello Python
Goodbye World"""

matches = grep('Hello', text)
for line_num, line in matches:
    print(f"  Line {line_num}: {line}")

# 3. NETWORK PROTOCOLS
print("\n=== Network Protocols ===")
print("""
State machines are used for:

TCP Connection:
  States: CLOSED, LISTEN, SYN_SENT, ESTABLISHED, ...
  Events: SYN, ACK, FIN, ...

HTTP Parsing:
  States: METHOD, URL, HEADERS, BODY
  Events: characters, CRLF

DNS Resolution:
  States: QUERY, RESPONSE, CACHE

WebSocket:
  States: CONNECTING, OPEN, CLOSING, CLOSED

Protocol Buffers:
  State machine for varint decoding
""")

# 4. DIGITAL CIRCUIT DESIGN
print("\n=== Digital Circuit Design ===")
print("""
DFAs map directly to hardware:

Sequential circuits:
  - States = flip-flop values
  - Transitions = combinational logic
  - Clock = input timing

Example: Traffic light controller
  States: RED, RED_YELLOW, GREEN, YELLOW
  Transitions: timed
  Outputs: which lights on

Used in:
  - FPGAs
  - ASICs
  - CPU control units
  - Protocol controllers
""")

# 5. BIOINFORMATICS
print("\n=== Bioinformatics ===")
print("""
DNA sequence analysis:

Pattern matching in DNA:
  - Motif finding
  - Restriction sites
  - Gene prediction

FASTA/FASTQ parsing:
  - Read sequence
  - Track state (header, sequence, quality)
  - DFA for parsing

Algorithms:
  - Aho-Corasick (multiple pattern matching)
  - Uses DFA for O(n) matching
""")

# 6. COMPILER OPTIMIZATION
print("\n=== Compiler Optimization ===")
print("""
DFA-based peephole optimization:

Patterns in assembly:
  mov R1, 0     →  xor R1, R1
  add R1, 0     →  (remove)
  mul R1, 1     →  (remove)
  jmp next      →  (remove)

Uses DFA to match patterns in instruction stream.
Then replaces with optimized version.

Also: Register allocation, dead code elimination
""")

# 7. WEB SECURITY
print("\n=== Web Security ===")
print("""
Input validation with DFA:

Email validation:
  Regex: ^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}$
  DFA: linear time matching

SQL injection prevention:
  Whitelist DFA for allowed characters

XSS prevention:
  DFA for safe HTML/JS

URL parsing:
  State machine for scheme, host, path, query, fragment
""")

# 8. AI AND NLP
print("\n=== AI and NLP ===")
print("""
Finite state transducers (FST):

Morphological analysis:
  "running" → run + ing
  "runs" → run + s

Speech recognition:
  Pronunciation dictionaries
  Finite state transducers

Information extraction:
  Pattern-based extraction
  Named entity recognition (partially)

Text normalization:
  Numbers → words
  Dates → ISO format
""")

# 9. HARDWARE AND EMBEDDED
print("\n=== Hardware and Embedded ===")
print("""
Embedded systems use DFAs for:

UART receiver:
  States: IDLE, START, DATA, PARITY, STOP
  Events: bit transitions

SPI/I2C protocols:
  State machines for transactions

Keyboard scanning:
  States: IDLE, DEBOUNCE, KEY_PRESSED, RELEASE

Motor control:
  States: STOPPED, ACCELERATING, CRUISING, DECELERATING

Advantages:
  - Predictable timing
  - Small memory footprint
  - No complex computation
""")

# 10. CASE STUDY: LEX/YACC
print("\n=== Case Study: Lex and Yacc ===")
print("""
Classic Unix tools:

LEX (Lexical Analyzer Generator):
  - Input: Regex patterns
  - Output: C code implementing DFA
  - Used by: Compilers, parsers

YACC (Yet Another Compiler Compiler):
  - Input: Grammar rules
  - Output: Parser (LALR)
  - Uses lexer output

Pipeline:
  Source → Lex → Tokens → Yacc → AST → Compiler

Modern equivalents:
  - Flex (fast lex)
  - Bison (GNU yacc)
  - ANTLR (Java-based, more powerful)
""")

# 11. PRODUCTION EXAMPLE
print("\n=== Production Example: Log Parser ===")
print("""
Parsing web server logs:

Log format:
  192.168.1.1 - - [01/Jan/2024:12:00:00 +0000] "GET /index.html HTTP/1.1" 200 1234

DFA states:
  - Reading IP
  - Reading timestamp
  - Reading request
  - Reading status
  - Reading size

Regex approach:
  r'(\\S+) - - \\[(.+?)\\] "(\\S+) (\\S+) (\\S+)" (\\d+) (\\d+)'

DFA approach:
  - Faster for high-volume logs
  - No backtracking
  - Constant memory per line

Use case:
  - Real-time monitoring
  - Alert on errors
  - Traffic analysis
  - Security audit
""")

# 12. SUMMARY TABLE
print("\n=== Application Summary ===")
print(f"{'Domain':<25} {'Use Case':<30} {'DFA Role':<25}")
print("-" * 80)
print(f"{'Compilers':<25} {'Lexical analysis':<30} {'Token recognition':<25}")
print(f"{'Text editors':<25} {'Find & replace':<30} {'Pattern matching':<25}")
print(f"{'Networking':<25} {'Protocol parsing':<30} {'State machines':<25}")
print(f"{'Hardware':<25} {'Control units':<30} {'Sequential logic':<25}")
print(f"{'Security':<25} {'Input validation':<30} {'Fast checking':<25}")
print(f"{'Bioinformatics':<25} {'DNA matching':<30} {'Sequence search':<25}")
print(f"{'Web':<25} {'URL parsing':<30} {'State transitions':<25}")

🚀 Future: DFA in Modern Computing

🎯 Where DFAs Are Going

DFAs remain fundamental but their implementations are evolving. Modern systems combine DFAs with hardware acceleration, SIMD, and hybrid approaches.

Future Directions

Hardware: FPGA/ASIC DFAs. SIMD: Parallel DFA simulation. GPUs: Massively parallel matching. Streaming: DFA on data streams. Quantum: Quantum automata. AI: Neural DFAs.

⚡ Hardware🔀 SIMD🎮 GPU🌊 Streaming

# Future of DFA in modern computing
import numpy as np

# 1. HARDWARE ACCELERATION
print("=== Hardware-Accelerated DFAs ===")
print("""
FPGA-Based DFA:
  - Compile DFA to hardware logic
  - Process multiple symbols per clock
  - 100x faster than software
  
Technologies:
  - Intel DFA (deep packet inspection)
  - Microsoft Catapult (Bing search)
  - Google TPU (partially)
  - NVIDIA regex (GPU)

Example Application:
  Network intrusion detection:
    - 10+ Gbps throughput
    - Multiple rules in parallel
    - Low latency (<1 μs)

ASIC Implementation:
  - Custom silicon
  - Highest speed/watt ratio
  - Used in high-end routers
""")

# 2. SIMD AND PARALLEL DFA
print("\n=== SIMD and Parallel DFAs ===")
print("""
SIMD (Single Instruction Multiple Data):

Idea: Process multiple DFAs in parallel.

Application:
  - Multiple regex patterns simultaneously
  - Same pattern on multiple strings

Techniques:
  - Bit-parallel NFA simulation
  - 8/16/32 DFAs per instruction
  - AVX-512 (Intel)
  - NEON (ARM)

Example: Hyperscan (Intel)
  - Multiple patterns
  - SIMD optimized
  - Used in: Snort, Suricata (IDS)

Performance:
  - 100+ GB/s on modern CPUs
  - Linear scaling with SIMD width
""")

# 3. GPU-ACCELERATED DFA
print("\n=== GPU-Accelerated DFA ===")
print("""
DFA simulation on GPUs:

Challenge:
  - DFAs are sequential (state dependency)
  - GPUs excel at parallel work

Solution:
  - Bit-parallel simulation
  - One thread per DFA
  - One warp per regex
  - Matrix representation

Libraries:
  - NVIDIA cuDF (regex support)
  - RAPIDS (data science)
  - Custom CUDA kernels

Applications:
  - Log analysis at scale
  - Genomics (DNA matching)
  - Network traffic analysis
""")

# 4. STREAMING AND ONLINE DFAs
print("\n=== Streaming DFAs ===")
print("""
Process data as it arrives:

Properties:
  - No need to store all input
  - Constant memory
  - O(1) per symbol
  - Can handle infinite streams

Applications:
  - Network traffic monitoring
  - IoT sensor data
  - Real-time log analysis
  - Financial tickers

Techniques:
  - Sliding window DFA
  - Match multiple patterns
  - Handle out-of-order data

Frameworks:
  - Apache Flink
  - Apache Storm
  - Kafka Streams
  - Apache Beam
""")

# 5. QUANTUM FINITE AUTOMATA
print("\n=== Quantum Finite Automata ===")
print("""
Quantum Computing meets Automata Theory:

Types:
  1. Measure-Once QFA
     - Quantum until final measurement
  
  2. Measure-Many QFA
     - Quantum measurement at each step

  3. Latvian QFA
     - Complex amplitudes

Properties:
  - Some languages require exponentially fewer states
  - Can recognize certain non-regular languages (with measurement)
  - Still an active research area

Challenges:
  - Decoherence
  - Error correction
  - Small scale (currently)
""")

# 6. NEURAL NETWORKS AND AUTOMATA
print("\n=== Neural Automata ===")
print("""
Neural Networks that learn DFAs:

Approaches:
  1. Neural Turing Machines
     - RNN + external memory
  
  2. Differentiable Automata
     - Soft versions of DFA
     - End-to-end trainable
  
  3. Neural State Machines
     - Learn state transitions
     - Discrete or continuous

Applications:
  - Program synthesis
  - Language understanding
  - Robotics (control)
  - Reinforcement learning

Libraries:
  - PyTorch
  - TensorFlow
  - JAX
""")

# 7. VERIFICATION AND MODEL CHECKING
print("\n=== Verification and Model Checking ===")
print("""
DFA-based verification:

1. HARDWARE VERIFICATION
   - Model circuits as automata
   - Check properties (safety, liveness)
   - Tools: NuSMV, SPIN

2. PROTOCOL VERIFICATION
   - Model protocols as state machines
   - Verify correctness
   - Tools: UPPAAL, PRISM

3. SOFTWARE VERIFICATION
   - Abstract programs to automata
   - Check reachability
   - Tools: CBMC, SLAM

4. SECURITY ANALYSIS
   - Model attacks as automata
   - Verify defenses
   - Tools: ProVerif, Tamarin
""")

# 8. BIG DATA AND ANALYTICS
print("\n=== Big Data and Analytics ===")
print("""
DFAs for massive scale:

Applications:
  - Log analysis (petabytes/day)
  - Security event correlation
  - Fraud detection
  - Real-time analytics

Techniques:
  - Distributed DFA (Spark)
  - MapReduce for matching
  - Stream processing
  - Compressed DFAs

Performance:
  - 10+ TB/s aggregate throughput
  - Linear scaling with cluster size
  - Fault-tolerant
""")

# 9. DOMAIN-SPECIFIC LANGUAGES (DSL)
print("\n=== Domain-Specific Languages ===")
print("""
DFAs are core to DSL implementation:

DSLs using DFAs:
  - Regex engines
  - Template engines
  - Configuration languages
  - Protocol buffers

Examples:
  - Terraform (HCL)
  - Ansible (YAML)
  - Kubernetes (YAML)
  - GraphQL (schema)

Approach:
  1. Define grammar (CFG)
  2. Tokenize with DFA (lexer)
  3. Parse with PDA/parser
  4. Generate code/AST
""")

# 10. FPGA-BASED DFA EXAMPLE
print("\n=== FPGA-Based DFA Implementation ===")
print("""
Concrete example: Hardware DFA

1. DFA states → registers
2. Transitions → combinational logic
3. Input → character stream

Optimization:
  - Multiple characters per cycle
  - Parallel DFAs for multiple patterns
  - Pipeline stages for long patterns

Use Case: Real-time packet filtering
  - 100 Gbps Ethernet
  - <1 μs latency
  - Line-rate processing

FPGA vendors:
  - Intel (Altera)
  - AMD (Xilinx)
  - Lattice
  - Microchip
""")

# 11. FUTURE OUTLOOK
print("\n=== Future Outlook ===")
print("""
DFAs will continue to be foundational:

Short term (1-5 years):
  - Better SIMD implementations
  - More GPU acceleration
  - Wider adoption in ML
  - Streaming-native

Medium term (5-10 years):
  - Quantum DFA applications
  - Neural DFA hybrid models
  - Program synthesis with DFAs
  - Hardware-software co-design

Long term (10+ years):
  - Brain-inspired automata
  - Photonic DFA
  - Molecular computing
  - New computational models

Key trends:
  1. Hardware acceleration
  2. Parallelism everywhere
  3. Integration with ML
  4. Streaming-first design
  5. Formal verification
""")

# 12. RECOMMENDATIONS
print("\n=== Recommendations ===")
print("""
For practitioners:
  1. Master DFA fundamentals
  2. Learn regex deeply
  3. Use libraries (RE2, Hyperscan)
  4. Consider hardware for scale
  5. Profile before optimizing

For researchers:
  1. Quantum automata
  2. Neural DFA models
  3. Hardware implementations
  4. Verification techniques
  5. New applications

For students:
  1. Understand theory
  2. Implement DFAs from scratch
  3. Study real systems
  4. Practice with tools
  5. Explore applications

Resources:
  - "Introduction to Automata Theory" (Hopcroft)
  - "Compilers: Principles, Techniques, and Tools" (Dragon Book)
  - Online courses (Coursera, edX)
  - Research papers (DLT, ICALP)
""")

# 13. FINAL THOUGHTS
print("\n=== Final Thoughts ===")
print("""
DFAs are the simplest model of computation:

1930s-1950s: Theoretical foundations
  - Turing machines
  - Finite automata
  - Regular languages

1960s-1980s: Practical applications
  - Lexical analysis (Lex)
  - Pattern matching (grep)
  - Text processing (sed)

1990s-2010s: High-performance
  - Hardware DFAs
  - Network security
  - Regular expression engines

2020s+: Modern revival
  - SIMD acceleration
  - GPU computing
  - ML integration
  - Quantum automata

Why DFAs matter:
  - Simplest computation model
  - Efficient and predictable
  - Foundation of formal languages
  - Ubiquitous in practice

You now understand:
  - Formal definition
  - How DFAs work
  - Design methodology
  - Minimization
  - Equivalence testing
  - Relationship to regex
  - Real-world applications
  - Future directions

"DFAs are the building blocks
of all computation."
  — Anonymous

Go build efficient systems!
""")