🧠 NFA Fundamentals

🎯 What is an NFA?

A Nondeterministic Finite Automaton (NFA) is a theoretical machine that generalizes the DFA. For a given state and input symbol, an NFA can have zero, one, or multiple possible next states. It can also have ε-transitions (spontaneous moves without reading input). Despite this flexibility, NFAs recognize exactly the same class of languages as DFAs — the regular languages.

Why NFAs Matter

Design ease: Multiple choices are natural. Concise: Often exponentially smaller than DFA. Regex: Thompson construction builds NFA from regex. Closure proofs: Union, concat, star are trivial. Same power: Equivalent to DFA. Guessing: "Guess" the right path.

📌 Multiple next states📌 ε-transitions📌 Same power as DFA📌 Regex compilation

# NFA — the big picture
# An NFA is like a DFA that can "guess" or "branch"

# REAL-LIFE EXAMPLE: Coin-operated turnstile with choices
# States: Locked, Unlocked, Broken
# Inputs: Push, Coin

class TurnstileNFA:
    """
    Turnstile NFA (nondeterministic):
      States: {Locked, Unlocked, Broken}
      Alphabet: {Push, Coin}
      Start: Locked
      Accept: Unlocked
      
      Nondeterminism:
        - From Locked, a Coin can go to Unlocked OR Broken (fault)
        - From Unlocked, a Push can go to Locked OR stay (jammed)
    """
    def __init__(self):
        self.states = {'Locked', 'Unlocked', 'Broken'}
        self.alphabet = {'Push', 'Coin'}
        self.start = 'Locked'
        self.accept = {'Unlocked'}
        # NFA transitions: (state, symbol) -> set of next states
        self.transitions = {
            ('Locked', 'Push'): {'Locked'},
            ('Locked', 'Coin'): {'Unlocked', 'Broken'},  # nondeterministic!
            ('Unlocked', 'Push'): {'Locked', 'Unlocked'}, # nondeterministic!
            ('Unlocked', 'Coin'): {'Unlocked'},
            ('Broken', 'Push'): {'Broken'},
            ('Broken', 'Coin'): {'Broken'},
        }
    
    def accepts(self, inputs):
        """Simulate NFA — track set of possible states."""
        current = {self.start}
        for symbol in inputs:
            next_states = set()
            for state in current:
                next_states |= self.transitions.get((state, symbol), set())
            current = next_states
        return bool(current & self.accept)

# Test
turnstile = TurnstileNFA()
print("Turnstile NFA simulation:")
for seq in [['Coin'], ['Coin', 'Push'], ['Push'], ['Coin', 'Coin'], ['Push', 'Coin']]:
    result = turnstile.accepts(seq)
    print(f"  {seq} → {'ACCEPT' if result else 'REJECT'}")

# KEY PROPERTIES OF NFA
print("""
=== NFA Key Properties ===

1. NONDETERMINISM
   - Zero, one, or multiple next states
   - No single "correct" path
   - Accepts if ANY path accepts

2. ε-TRANSITIONS
   - Move without reading input
   - Spontaneous state changes
   - Optional in NFA definition

3. INPUT PROCESSING
   - Read input left to right
   - Can branch to multiple states
   - Can take ε-moves anytime

4. ACCEPTANCE
   - Accept if ANY possible path ends in accept
   - Reject if ALL paths fail to accept
   - Input consumed entirely

5. COMPLEXITY
   - Simulation: O(n × |Q|) — track state sets
   - Subset construction: O(2^|Q|) worst case
   - Often much smaller than equivalent DFA

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

📐 Formal Definition

🎯 The 5-Tuple

An NFA is formally defined as a 5-tuple M = (Q, Σ, δ, q₀, F), where δ maps to sets of states rather than single states.

The Components

Q: Finite set of states. Σ: Input alphabet. δ: Transition function Q × (Σ ∪ {ε}) → P(Q). q₀: Start state (q₀ ∈ Q). F: Set of accepting states (F ⊆ Q). Recognition: String w accepted if some path from q₀ on w ends in F.

Q StatesΣ Alphabetδ → P(Q)q₀ StartF Accept

# Formal definition of NFA in code
from dataclasses import dataclass
from typing import Set, Dict, Tuple, FrozenSet
from collections import deque

@dataclass
class NFA:
    """
    Formal NFA as 5-tuple M = (Q, Σ, δ, q₀, F)
    where δ: Q × (Σ ∪ {ε}) → P(Q)
    """
    Q: FrozenSet[str]                          # States
    Sigma: FrozenSet[str]                      # Alphabet (no ε)
    delta: Dict[Tuple[str, str], FrozenSet[str]]  # Transitions
    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), next_set in self.delta.items():
            assert q in self.Q, f"State {q} not in Q"
            assert s in self.Sigma or s == 'ε', f"Symbol {s} not valid"
            assert next_set.issubset(self.Q), f"Next states not in Q"
    
    def epsilon_closure(self, states: FrozenSet[str]) -> FrozenSet[str]:
        """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, 'ε'), frozenset()):
                if next_state not in closure:
                    closure.add(next_state)
                    stack.append(next_state)
        
        return frozenset(closure)
    
    def accepts(self, input_string: str) -> bool:
        """Check if NFA accepts input_string."""
        current = self.epsilon_closure(frozenset({self.q0}))
        
        for symbol in input_string:
            if symbol not in self.Sigma:
                return False  # Invalid symbol
            next_states = set()
            for state in current:
                next_states |= self.delta.get((state, symbol), frozenset())
            current = self.epsilon_closure(frozenset(next_states))
        
        return bool(current & self.F)
    
    def trace(self, input_string: str) -> list:
        """Trace execution step by step (showing state sets)."""
        current = self.epsilon_closure(frozenset({self.q0}))
        trace = [f"Start ε-closure: {sorted(current)}"]
        
        for symbol in input_string:
            next_states = set()
            for state in current:
                next_states |= self.delta.get((state, symbol), frozenset())
            current = self.epsilon_closure(frozenset(next_states))
            trace.append(f"Read '{symbol}' → {sorted(current)}")
        
        result = "ACCEPT" if (current & self.F) else "REJECT"
        trace.append(f"Result: {result}")
        return trace


# EXAMPLE: NFA for strings ending in "01"
nfa_ends_01 = NFA(
    Q=frozenset({'q0', 'q1', 'q2'}),
    Sigma=frozenset({'0', '1'}),
    delta={
        ('q0', '0'): frozenset({'q0', 'q1'}),  # nondeterministic choice!
        ('q0', '1'): frozenset({'q0'}),
        ('q1', '0'): frozenset(),
        ('q1', '1'): frozenset({'q2'}),
        ('q2', '0'): frozenset(),
        ('q2', '1'): frozenset(),
    },
    q0='q0',
    F=frozenset({'q2'})
)

# Test
print("NFA for strings ending in '01':")
for s in ['01', '101', '001', '10', '11', '1', '0', '']:
    result = nfa_ends_01.accepts(s)
    print(f"  '{s}' → {result}")

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

# ε-NFA EXAMPLE
print("\n=== ε-NFA Example: a*b* ===")
nfa_astar_bstar = NFA(
    Q=frozenset({'q0', 'q1'}),
    Sigma=frozenset({'a', 'b'}),
    delta={
        ('q0', 'a'): frozenset({'q0'}),
        ('q0', 'ε'): frozenset({'q1'}),   # ε-transition!
        ('q1', 'b'): frozenset({'q1'}),
    },
    q0='q0',
    F=frozenset({'q0', 'q1'})
)

print("Accepts strings of form a*b*:")
for s in ['', 'a', 'b', 'ab', 'aabb', 'aa', 'bb', 'ba', 'aba']:
    result = nfa_astar_bstar.accepts(s)
    print(f"  '{s}' → {result}")

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

Example 1: Strings containing "ab"
  Q = {q0, q1, q2}
  Σ = {a, b}
  δ: (q0,a)→{q0,q1}, (q0,b)→{q0}
     (q1,b)→{q2}
     (q2,a)→{q2}, (q2,b)→{q2}
  q₀ = q0
  F = {q2}

Example 2: Strings with even 0s OR even 1s
  Q = {q0, q1, q2, q3}
  Σ = {0, 1}
  δ: (q0,0)→{q1}, (q0,1)→{q2}
     (q1,0)→{q0}, (q1,1)→{q1}
     (q2,0)→{q2}, (q2,1)→{q0}
     (q3,·)→{q3}
  q₀ = q0
  F = {q0}
  
  But wait — this is deterministic. NFA can guess.

Example 3: Strings of length divisible by 3 or ending in "ab"
  (Union via NFA with ε-transitions)
""")

🔀 Nondeterminism

🎯 The Power of Choice

Nondeterminism means the machine can have multiple possible next states for the same input. Think of it as "guessing" or "branching" — the NFA accepts if any branch leads to acceptance.

Understanding Nondeterminism

Guessing: "Guess" the correct path. Branching: Explore all paths in parallel. Existential: Accept if ANY path accepts. No cost: Branching is free (theoretical). Simulation: Track set of possible states. Power: Same as DFA for regular languages.

🔀 Branching🤔 Guessing📊 State sets✅ Any path

# Nondeterminism in detail
print("=== Understanding Nondeterminism ===")
print("""
DFA vs NFA transitions:

DFA: δ(q, a) = q'        (exactly one next state)
NFA: δ(q, a) = {q1, q2}  (set of next states)

NFA can also have:
  δ(q, a) = {}           (no transition — dead)
  δ(q, a) = {q}          (self-loop)
  δ(q, a) = {q1, q2, q3} (multiple choices)

INTUITION: "Guessing"
  Think of NFA as magically guessing the right path.
  If there EXISTS a path to accept, it accepts.
  This is like "parallel exploration" of all paths.

IMPORTANT: Nondeterminism does NOT add power!
  - NFA recognizes exactly regular languages
  - Any NFA can be converted to equivalent DFA
  - But NFA can be exponentially smaller
""")

# 1. SIMULATING NFA: TRACKING SETS
class NFASimulator:
    """
    Simulate an NFA by tracking the set of all possible states.
    This is the "subset simulation" — basis of subset construction.
    """
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta  # (state, symbol) -> set of states
        self.q0 = q0
        self.F = F
    
    def simulate(self, word):
        """Return set of states after reading word."""
        current = {self.q0}
        
        # Apply epsilon closure initially
        current = self.epsilon_closure(current)
        
        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 current
    
    def epsilon_closure(self, states):
        """Compute ε-closure."""
        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):
        final_states = self.simulate(word)
        return bool(final_states & self.F)

# Example: NFA for (a|b)*abb
nfa = NFASimulator(
    states={'q0', 'q1', 'q2', 'q3'},
    alphabet={'a', 'b'},
    delta={
        ('q0', 'a'): {'q0', 'q1'},
        ('q0', 'b'): {'q0'},
        ('q1', 'b'): {'q2'},
        ('q2', 'b'): {'q3'},
        ('q3', 'a'): {'q3'},
        ('q3', 'b'): {'q3'},
    },
    q0='q0',
    F={'q3'}
)

print("=== NFA Simulation: (a|b)*abb ===")
for s in ['abb', 'aabb', 'babb', 'abab', 'ab', 'abbb', 'bb']:
    states = nfa.simulate(s)
    result = nfa.accepts(s)
    print(f"  '{s:6s}' → states={sorted(states)} → {'ACCEPT' if result else 'REJECT'}")

# 2. NONDETERMINISM AS PARALLELISM
print("\n=== Nondeterminism as Parallelism ===")
print("""
Visualize NFA execution for 'aab' on (a|b)*abb:

Start: {q0}

Read 'a':
  q0 --a--> q0, q1
  So: {q0, q1}

Read 'a':
  q0 --a--> q0, q1
  q1 --a--> (none)
  So: {q0, q1}

Read 'b':
  q0 --b--> q0
  q1 --b--> q2
  So: {q0, q2}

Read 'b':
  q0 --b--> q0
  q2 --b--> q3
  So: {q0, q3}  ← contains accept state q3!
  
Result: ACCEPT ✓

The NFA "guessed" to follow q1→q2→q3 path.
""")

# 3. WHY NONDETERMINISM IS USEFUL
print("=== Why Nondeterminism is Useful ===")
print("""
1. EASIER DESIGN
   Problem: strings containing "ab" as substring
   
   DFA: Need to track how much of "ab" matched
   NFA: Just "guess" where "ab" starts!
   
   NFA for "contains ab":
     q0 --a--> q0, q1
     q0 --b--> q0
     q1 --b--> q2 (accept)
     q2 --a,b--> q2
   
   Much simpler than DFA!

2. CONCISE REPRESENTATION
   Some languages need exponentially more DFA states.
   
   Example: L = {w | k-th symbol from end is 'a'}
   - DFA: 2^k states
   - NFA: k+1 states

3. CLOSURE PROPERTIES
   Union: NFA with new start and ε-transitions
   Concatenation: connect via ε-transitions
   Star: ε-loops

4. REGEX COMPILATION
   Thompson's construction builds NFA from regex.
   Then convert to DFA for implementation.
""")

# 4. DEMONSTRATION: WHY NFA IS CONCISE
print("=== NFA vs DFA Size ===")
print("""
Language: Strings where the 3rd symbol from the end is 'a'
  Σ = {a, b}

DFA approach: Need to remember last 3 symbols
  States = 2^3 = 8 states (all possible 3-symbol suffixes)

NFA approach: Guess where 3rd-from-last 'a' is
  States = 4 states (q0, q1, q2, q3)
  
  q0: initial, can stay or guess
  q1: seen 'a' (3rd from end)
  q2: seen 'a' + one symbol
  q3: seen 'a' + two symbols (accept)

NFA transitions:
  q0 --a--> q0, q1
  q0 --b--> q0
  q1 --a,b--> q2
  q2 --a,b--> q3
  q3 --a,b--> q3
  
  F = {q3}

For k=10:
  DFA: 2^10 = 1024 states
  NFA: 11 states
  
  Exponential difference!
""")

# 5. PROVING NFA CORRECTNESS
print("\n=== Proving NFA Correctness ===")
print("""
To prove an NFA M accepts language L:

Part 1: L ⊆ L(M)
  For every w ∈ L, show there exists an accepting path.
  → Constructive: describe the path the NFA takes.

Part 2: L(M) ⊆ L
  For every accepting path in M, show w ∈ L.
  → Show every accepting path implies w has property.

Example: NFA for "contains ab"
  Part 1: If w contains "ab" at position i,
          NFA guesses i, follows q0→q1→q2, accepts.
  Part 2: If NFA accepts, path must be:
          q0* → q1 → q2 → q2*
          So w contains "ab". ∎
""")

# 6. COMMON NFA PATTERNS
print("=== Common NFA Patterns ===")
print("""
1. CONTAINS PATTERN
   "Guess" where pattern starts
   → Initial state loops, non-deterministically enters pattern

2. ENDS WITH PATTERN
   Reverse of contains — pattern must reach end
   → States track pattern progress, accept only at end

3. UNION (R1 | R2)
   → New start state with ε-transitions to R1 and R2

4. CONCATENATION (R1 R2)
   → ε-transitions from R1 accept states to R2 start

5. KLEENE STAR (R*)
   → ε-loop from accept back to start
   → New start/accept with ε-transitions

6. OPTIONAL (R?)
   → R | ε

7. REPETITION (R+)
   → R R*
""")

# 7. BOUNDED VS UNBOUNDED NONDETERMINISM
print("\n=== Types of Nondeterminism ===")
print("""
1. FINITE BRANCHING
   Each (state, symbol) has finitely many next states.
   → Standard NFA.
   
2. ε-TRANSITIONS
   Additional nondeterminism: move without input.
   → ε-NFA. Equivalent to NFA.

3. UNBOUNDED NONDETERMINISM
   Not allowed in NFA!
   Each transition has a finite set of next states.
   (This would be a different model — e.g., 
    nondeterministic Turing machine)

NFA always has:
  - Finite states
  - Finite alphabet
  - Finite transitions (each δ(q,a) is finite set)

So NFA computation always terminates.
""")

ε Epsilon Transitions

🎯 Spontaneous Moves

An ε-transition allows an NFA to change state without reading any input. This adds convenience but no extra power — every ε-NFA can be converted to an equivalent NFA (and then DFA).

Understanding ε-Transitions

Free move: Change state without consuming input. ε-closure: All states reachable via ε-moves. Convenience: Simplify design (union, concat, star). Optional: Can always be eliminated. Closure: Must compute ε-closure after every step. No power: Equivalent to regular NFA.

ε Moveε-closureFree transitionOptional

# Epsilon transitions — theory and implementation
from collections import defaultdict, deque

# 1. WHAT IS ε-CLOSURE?
print("=== ε-Closure Definition ===")
print("""
For a state q, ε-closure(q) = set of all states reachable
from q using ONLY ε-transitions (zero or more).

Formal definition:
  ε-closure(q) = {q} ∪ {p | q →ε→ ... →ε→ p}

For a set S of states:
  ε-closure(S) = ∪_{q ∈ S} ε-closure(q)

Computing ε-closure:
  BFS/DFS from q following only ε-transitions.
""")

class EpsilonNFA:
    """ε-NFA implementation."""
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta  # (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."""
        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)
    
    def trace(self, word):
        """Trace with ε-closures."""
        current = self.epsilon_closure({self.q0})
        trace = [f"Start ε-closure: {sorted(current)}"]
        
        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)
            trace.append(f"Read '{symbol}' → {sorted(current)}")
        
        result = "ACCEPT" if (current & self.F) else "REJECT"
        trace.append(f"Result: {result}")
        return trace

# 2. EXAMPLE: ε-NFA FOR a*b*
print("=== Example: ε-NFA for a*b* ===")
print("""
States: {q0, q1, q2}
  q0: reading a's
  q1: transitioning (via ε) to b's
  q2: reading b's

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

Accepts: '', 'a', 'aa', 'b', 'bb', 'ab', 'aab', 'abb', 'aaabbb'
Rejects: 'ba', 'bab', 'aba'
""")

nfa_astar_bstar = EpsilonNFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'a', 'b'},
    delta={
        ('q0', 'a'): {'q0'},
        ('q0', 'ε'): {'q1'},
        ('q1', 'b'): {'q1'},
        ('q1', 'ε'): {'q2'},
    },
    q0='q0',
    F={'q0', 'q1', 'q2'}
)

print("ε-NFA for a*b*:")
for s in ['', 'a', 'b', 'ab', 'aabb', 'ba', 'aba', 'aa']:
    result = nfa_astar_bstar.accepts(s)
    print(f"  '{s}' → {result}")

# 3. ε-CLOSURE COMPUTATION
print("\n=== ε-Closure Computation ===")

def compute_epsilon_closures(nfa):
    """Compute ε-closure for every state."""
    closures = {}
    for state in nfa.Q:
        closures[state] = nfa.epsilon_closure({state})
    return closures

closures = compute_epsilon_closures(nfa_astar_bstar)
for state, closure in sorted(closures.items()):
    print(f"  ε-closure({state}) = {sorted(closure)}")

# 4. ε-NFA SIMULATION DETAIL
print("\n=== ε-NFA Simulation: 'aab' ===")
for line in nfa_astar_bstar.trace('aab'):
    print(f"  {line}")

# 5. ELIMINATING ε-TRANSITIONS
print("\n=== Eliminating ε-Transitions ===")
print("""
Convert ε-NFA to NFA (without ε):

Method:
  1. For each state q and symbol a:
     δ'(q, a) = ε-closure( ∪_{p ∈ ε-closure(q)} δ(p, a) )
  
  2. New accept states:
     F' = {q | ε-closure(q) ∩ F ≠ ∅}
  
  3. Start state: ε-closure(q0) — but keep q0 as start
  
  4. Remove all ε-transitions.

Result: Equivalent NFA without ε-transitions.

Complexity: O(|Q|² × |Σ|) worst case.
""")

def eliminate_epsilon(nfa):
    """Convert ε-NFA to NFA without ε-transitions."""
    # Compute ε-closures
    closures = {state: nfa.epsilon_closure({state}) for state in nfa.Q}
    
    # New transitions
    new_delta = {}
    for q in nfa.Q:
        for a in nfa.Sigma:
            next_states = set()
            # From all states in ε-closure(q)
            for p in closures[q]:
                next_states |= nfa.delta.get((p, a), set())
            # Apply ε-closure to result
            next_states = nfa.epsilon_closure(next_states)
            
            if next_states:
                new_delta[(q, a)] = new_states
    
    # New accept states
    new_F = {q for q in nfa.Q if closures[q] & nfa.F}
    
    return NFA_NoEps(nfa.Q, nfa.Sigma, new_delta, nfa.q0, new_F)


class NFA_NoEps:
    """NFA without ε-transitions."""
    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):
        current = {self.q0}
        for symbol in word:
            next_states = set()
            for state in current:
                next_states |= self.delta.get((state, symbol), set())
            current = next_states
        return bool(current & self.F)

# Convert
nfa_no_eps = eliminate_epsilon(nfa_astar_bstar)

print("After eliminating ε-transitions:")
for s in ['', 'a', 'b', 'ab', 'aabb', 'ba']:
    r1 = nfa_astar_bstar.accepts(s)
    r2 = nfa_no_eps.accepts(s)
    match = "✓" if r1 == r2 else "✗"
    print(f"  '{s:6s}' ε-NFA={r1}, NFA={r2} {match}")

# 6. WHY ε-TRANSITIONS ARE USEFUL
print("\n=== Why ε-Transitions Are Useful ===")
print("""
1. UNION (R1 | R2)
   New start state with ε to both starts:
   
   →(q_new) --ε--> start(R1)
            --ε--> start(R2)

2. CONCATENATION (R1 R2)
   ε from R1 accept to R2 start:
   
   accept(R1) --ε--> start(R2)

3. KLEENE STAR (R*)
   ε from accept back to start:
   
   accept(R) --ε--> start(R)
   Plus new start/accept states

4. OPTIONAL (R?)
   R | ε — use ε-transition

5. SIMPLIFICATION
   Avoids complex transition combinations.
   Makes proofs and constructions cleaner.

All these can be done without ε,
but ε makes the construction trivial.
""")

# 7. PRACTICAL NOTE
print("=== Practical Note ===")
print("""
In practice:
  - Design with ε (easier)
  - Eliminate ε (or go directly to DFA via subset construction)
  - Minimize DFA
  - Implement

Subset construction handles ε directly:
  - DFA state = ε-closure of subset of NFA states
  - δ_DFA(S, a) = ε-closure(∪_{q∈S} δ_NFA(q, a))

This is the standard pipeline:
  Regex → ε-NFA → NFA → DFA → Minimal DFA
""")

✅ String Acceptance

🎯 Does the NFA Accept This String?

An NFA accepts a string if there exists at least one path from the start state to an accept state that consumes the entire input. The language of an NFA is the set of all strings it accepts.

Acceptance Process

1. Start: ε-closure({q₀}). 2. Read: For each symbol, compute next state set. 3. ε-closure: Apply after each step. 4. End: Check if set contains accept state. Accept: Any accept state in final set. Reject: No accept state in final set.

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

# String acceptance for NFAs
class NFA:
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def epsilon_closure(self, states):
        """Compute ε-closure."""
        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):
        """Return True if NFA accepts word."""
        current = self.epsilon_closure({self.q0})
        
        for symbol in word:
            if symbol not in self.Sigma:
                return False
            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)
    
    def run_trace(self, word):
        """Return detailed execution trace."""
        current = self.epsilon_closure({self.q0})
        trace = [('start', None, frozenset(current))]
        
        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)
            trace.append(('read', symbol, frozenset(current)))
        
        accepted = bool(current & self.F)
        return trace, accepted

# Example: NFA for strings ending in "01"
nfa = NFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'0', '1'},
    delta={
        ('q0', '0'): {'q0', 'q1'},
        ('q0', '1'): {'q0'},
        ('q1', '1'): {'q2'},
    },
    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 nfa.accepts(s) else "✗ REJECT"
    print(f"'{s:6s}' → {result}")

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

print(f"{'Step':<6} {'Action':<8} {'Symbol':<8} {'State Set':<30}")
print("-" * 60)
for i, (action, symbol, state_set) in enumerate(trace):
    symbol_str = symbol if symbol else '—'
    states_str = '{' + ', '.join(sorted(state_set)) + '}'
    print(f"{i:<6} {action:<8} {symbol_str:<8} {states_str:<30}")

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

# 3. NFA ACCEPTANCE IS EXISTENTIAL
print("\n=== NFA Acceptance is Existential ===")
print("""
Key insight: NFA accepts if ANY path accepts.

For string '001' on NFA ending in '01':

Possible paths:
  Path 1: q0 --0--> q0 --0--> q0 --1--> q0    ✗ (q0 not accept)
  Path 2: q0 --0--> q1 --0--> (dead)          ✗
  Path 3: q0 --0--> q0 --0--> q1 --1--> q2    ✓ ACCEPT!
  Path 4: q0 --0--> q1 --0--> (dead)          ✗

Since Path 3 accepts, the NFA accepts '001'.

The NFA "guessed" to take the transition q0→q1
on the second '0' (not the first).
""")

# 4. LANGUAGE OF AN NFA
print("=== Language of an NFA ===")
print("""
L(M) = { w ∈ Σ* | there exists a path from q₀ to some q ∈ F
                  that consumes all of w }

For NFA 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
Same language as the DFA!
""")

# 5. ENUMERATING ACCEPTED STRINGS
def enumerate_language(nfa, 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(nfa.Sigma, repeat=length):
            word = ''.join(symbols)
            if nfa.accepts(word):
                accepted.append(word)
    return accepted

print("\n=== Enumerating Language (up to length 4) ===")
accepted = enumerate_language(nfa, 4)
print(f"Total accepted strings (len ≤ 4): {len(accepted)}")
for s in accepted:
    print(f"  '{s}'")

# 6. COMPLEXITY
print("\n=== Time Complexity ===")
print("""
For an NFA M and input string w:
  Simulation: O(|w| × |Q|²)
    - At each step, compute next state set
    - Each state set can have up to |Q| states
    - Transitions from each state: O(|Q|)
  
  Space: O(|Q|) — store current state set

Subset construction (to DFA):
  Worst case: O(2^|Q|) states
  Then simulate DFA: O(|w|) time

Trade-off:
  - NFA: compact, slower simulation
  - DFA: larger, faster simulation

In practice:
  - Use NFA for design
  - Convert to DFA for implementation
""")

# 7. NFA ACCEPTANCE VS DFA ACCEPTANCE
print("\n=== NFA vs DFA Acceptance ===")
print(f"{'Aspect':<30} {'DFA':<25} {'NFA':<25}")
print("-" * 80)
print(f"{'States after input':<30} {'1 state':<25} {'Set of states':<25}")
print(f"{'Acceptance condition':<30} {'In F':<25} {'Intersects F':<25}")
print(f"{'Path uniqueness':<30} {'Unique path':<25} {'Many paths':<25}")
print(f"{'Simulation time':<30} {'O(n)':<25} {'O(n × |Q|²)':<25}")
print(f"{'Space':<30} {'O(1)':<25} {'O(|Q|)':<25}")

# 8. PROVING EQUIVALENCE
print("\n=== Proving NFA = DFA ===")
print("""
Theorem: For every NFA, there exists an equivalent DFA.

Proof: Subset construction.

Let N = (Q_N, Σ, δ_N, q0_N, F_N) be an NFA.
Construct DFA D = (Q_D, Σ, δ_D, q0_D, F_D):

  Q_D = P(Q_N)  (all subsets of Q_N)
  q0_D = ε-closure({q0_N})
  F_D = { S ∈ Q_D | S ∩ F_N ≠ ∅ }
  δ_D(S, a) = ε-closure( ∪_{q ∈ S} δ_N(q, a) )

Claim: L(D) = L(N).

Proof:
  δ_D*(q0_D, w) = ε-closure( δ_N*(q0_N, w) )  (by induction)
  
  w ∈ L(N)
  ↔ δ_N*(q0_N, w) ∩ F_N ≠ ∅
  ↔ δ_D*(q0_D, w) ∩ F_N ≠ ∅
  ↔ δ_D*(q0_D, w) ∈ F_D
  ↔ w ∈ L(D)  ∎

Note: We only need REACHABLE subsets.
      In practice, |Q_D| << 2^|Q_N|.
""")

🎨 Designing NFAs

🎯 Building NFAs for Languages

Designing NFAs is often easier than designing DFAs because you can use nondeterminism to "guess" the right path. Here's a systematic approach.

Design Methodology

1. Understand: What language? 2. Decompose: Can it be built from simpler languages? 3. Guess: What can the NFA guess? 4. Use ε: Combine pieces with ε-transitions. 5. Mark accept: Which states accept? 6. Test: Verify with examples.

🎯 Understand🔀 Guessε Combine✅ Test

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

Step 2: WHAT can the NFA guess?
  - Where does the pattern start/end?
  - Which branch to take?
  - When to use ε-transitions?

Step 3: HOW MANY states?
  - Usually fewer than DFA
  - One state per "pattern position"
  - Plus initial and accept states

Step 4: TRANSITIONS?
  - Use nondeterminism freely
  - Use ε-transitions to combine
  - Don't worry about "missing" transitions

Step 5: START state?
  - Usually a new initial state
  - Can ε-transition to sub-NFAs

Step 6: ACCEPT states?
  - States that complete the pattern
  - Can be multiple

Step 7: TEST
  - Try positive and negative examples
  - Trace to verify
""")

# EXAMPLE 1: CONTAINS "ab"
print("\n=== Example 1: Contains 'ab' ===")
print("""
Step 1: Language
  L = {w ∈ {a,b}* | w contains 'ab' as substring}

Step 2: Guess
  Guess WHERE the "ab" starts.

Step 3: States
  q0: initial — haven't guessed yet
  q1: guessed 'a' (waiting for 'b')
  q2: found 'ab' (accept)

Step 4: Transitions
  q0 --a--> q0 (stay), q1 (guess!)
  q0 --b--> q0
  q1 --b--> q2
  q2 --a,b--> q2

Step 5: Start = q0

Step 6: Accept = {q2}

Step 7: Test
  'ab'   → q0 --a--> {q0,q1} --b--> {q0,q2} ✓
  'aab'  → guess on 2nd a, then b → ✓
  'aba'  → ✓
  'ba'   → q0 --b--> q0 --a--> {q0,q1} ∉ F ✗
  'bb'   → q0 --b--> q0 --b--> q0 ∉ F ✗

Much simpler than DFA!
DFA would need to track how much of "ab" matched.
""")

# EXAMPLE 2: UNION OF LANGUAGES
print("\n=== Example 2: Union (ends in 'ab' OR contains 'bb') ===")
print("""
Step 1: Language
  L = {w | w ends in 'ab'} ∪ {w | w contains 'bb'}

Step 2: Decompose
  Build NFA for each part, combine with ε.

Step 3-6: Build NFA for each part:

NFA1 (ends in 'ab'):
  States: {p0, p1, p2}
  p0 --a--> p1
  p0 --b--> p0
  p1 --a--> p1, p0 --b--> p2
  p1 --b--> p2
  p2 --a--> p1, p2 --b--> p0

NFA2 (contains 'bb'):
  States: {r0, r1, r2}
  r0 --a--> r0, r0 --b--> r0, r1
  r1 --b--> r2
  r2 --a,b--> r2

Combine with new start state s:
  s --ε--> p0
  s --ε--> r0
  F = {p2, r2}

Result: NFA accepts if either branch accepts.
""")

# EXAMPLE 3: CONCATENATION
print("\n=== Example 3: Concatenation (starts with 'a' then ends with 'b') ===")
print("""
Step 1: L = {w | w starts with 'a' and ends with 'b'}

Step 2: Decompose into L1 · L2
  L1 = {w | starts with 'a'} = a(a|b)*
  L2 = {w | ends with 'b'} = (a|b)*b

Step 3: Build NFA for L1:
  q0 --a--> q1
  q1 --a,b--> q1
  F1 = {q1}

NFA for L2:
  p0 --a,b--> p0, p1 (guess end)
  p1 --b--> p2
  F2 = {p2}

Concatenate:
  q1 --ε--> p0
  F = {p2}

Accepts: strings starting with 'a' AND ending with 'b'
  'ab', 'aab', 'abb', 'aabb', 'abab', ...
Rejects: 'a', 'b', 'ba', 'aba', 'bab'
""")

# DESIGN PATTERNS
print("\n=== Common NFA Design Patterns ===")
print("""
1. CONTAINS PATTERN (P)
   q0 --a--> q0, q1 (guess start)
   ... pattern states ...
   accept state loops on all symbols

2. ENDS WITH PATTERN (P)
   ... pattern states ...
   accept state must be final
   No loops out of accept

3. STARTS WITH PATTERN (P)
   initial state only allows pattern
   Then free transitions

4. UNION (R1 | R2)
   New start with ε to R1 and R2 starts
   Accept = union of accepts

5. CONCATENATION (R1 R2)
   ε from R1 accepts to R2 start

6. KLEENE STAR (R*)
   New start/accept
   ε from start to R start and accept
   ε from R accept back to R start and accept

7. OPTIONAL (R?)
   R | ε

8. REPETITION (R+)
   R R* — at least one R
""")

# SYSTEMATIC CODE
def design_nfa_contains_ab():
    """Design NFA for strings containing 'ab'."""
    print("\n=== Design: Contains 'ab' ===")
    print("""
NFA for L = {w | w contains 'ab'}

Q = {q0, q1, q2}
Σ = {a, b}
q0 = q0
F = {q2}

δ:
  (q0, 'a') → {q0, q1}   ← guess: stay OR start matching
  (q0, 'b') → {q0}
  (q1, 'b') → {q2}
  (q2, 'a') → {q2}
  (q2, 'b') → {q2}

Test:
  'ab'   → {q0,q1} --b--> {q0,q2} ✓
  'aab'  → {q0,q1} --a--> {q0,q1} --b--> {q0,q2} ✓
  'ba'   → {q0} --b--> {q0} --a--> {q0,q1} ✗
  'bb'   → {q0} --b--> {q0} --b--> {q0} ✗
""")

design_nfa_contains_ab()

def design_nfa_even_ab():
    """Design NFA for strings with even number of 'ab'."""
    print("\n=== Design: Even number of 'ab' occurrences ===")
    print("""
L = {w | number of occurrences of 'ab' is even}

This is actually easier as DFA, but NFA works too.

States: {Even, Odd}
  Even: even number of "ab" seen
  Odd: odd number of "ab" seen

Transitions:
  (Even, 'a') → {Even} (if next isn't b)
  ... wait, this needs lookahead!

NFA solution: guess the occurrences.

Actually, this is a regular language.
The DFA has states:
  q0: even ab, last wasn't 'a'
  q1: even ab, last was 'a'
  q2: odd ab, last wasn't 'a'
  q3: odd ab, last was 'a'
  
F = {q0, q1}

NFA can just track parity — but needs to detect "ab".
Since "ab" detection is local (needs 1 symbol memory),
NFA doesn't help much here. DFA is natural.

Lesson: NFAs are most useful when "guessing" helps.
""")

design_nfa_even_ab()

📊 Subset Construction (NFA→DFA)

🎯 Converting NFA to DFA

The subset construction (also called powerset construction) converts any NFA into an equivalent DFA. The resulting DFA's states are sets of NFA states.

Subset Construction Algorithm

1. Start: ε-closure({q₀_N}). 2. For each subset: δ_D(S, a) = ε-closure(∪ δ_N(q, a)). 3. Repeat: Until all reachable subsets found. 4. Accept: Subsets containing NFA accept state. 5. Result: DFA equivalent to NFA. Worst case: 2^|Q_N| states.

📊 Powersetε-closureReachable subsetsEquivalent DFA

# Subset Construction — NFA to DFA conversion
from collections import deque
from itertools import product

class NFA:
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def epsilon_closure(self, states):
        """Compute ε-closure."""
        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):
        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)


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
    
    def __repr__(self):
        return f"DFA({len(self.Q)} states, alphabet={self.Sigma})"


# SUBSET CONSTRUCTION
def subset_construction(nfa):
    """
    Convert NFA to DFA.
    
    States of DFA are subsets of NFA states.
    Start: ε-closure({q0_NFA})
    δ_D(S, a) = ε-closure(∪_{q∈S} δ_N(q, a))
    F_D = {S | S ∩ F_NFA ≠ ∅}
    """
    # Initial DFA state
    start = frozenset(nfa.epsilon_closure({nfa.q0}))
    
    # BFS over reachable subsets
    dfa_states = {start}
    queue = deque([start])
    dfa_delta = {}
    
    while queue:
        current = queue.popleft()
        
        for symbol in nfa.Sigma:
            # Compute next state set
            next_set = set()
            for state in current:
                next_set |= nfa.delta.get((state, symbol), set())
            
            next_set = frozenset(nfa.epsilon_closure(next_set))
            dfa_delta[(current, symbol)] = next_set
            
            if next_set not in dfa_states:
                dfa_states.add(next_set)
                queue.append(next_set)
    
    # Accept states: subsets containing NFA accept state
    dfa_F = {s for s in dfa_states if s & nfa.F}
    
    return DFA(dfa_states, nfa.Sigma, dfa_delta, start, dfa_F)


# EXAMPLE 1: SIMPLE NFA
print("=== Example 1: NFA for strings ending in '01' ===")

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

# Convert
dfa1 = subset_construction(nfa1)

print(f"NFA states: {len(nfa1.Q)}")
print(f"DFA states: {len(dfa1.Q)}")
print(f"\nDFA states (as sets):")
for state in dfa1.Q:
    marker = " (accept)" if state in dfa1.F else ""
    print(f"  {set(state)}{marker}")

# Test equivalence
print("\n=== Equivalence Test ===")
test_strings = ['01', '101', '001', '10', '11', '1', '0', '']
print(f"{'String':<10} {'NFA':<8} {'DFA':<8} {'Match':<8}")
print("-" * 40)
for s in test_strings:
    r_nfa = nfa1.accepts(s)
    r_dfa = dfa1.accepts(s)
    match = "✓" if r_nfa == r_dfa else "✗"
    print(f"'{s:6s}' {str(r_nfa):<8} {str(r_dfa):<8} {match:<8}")

# EXAMPLE 2: NFA WITH ε-TRANSITIONS
print("\n=== Example 2: ε-NFA for a*b* ===")

nfa2 = NFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'a', 'b'},
    delta={
        ('q0', 'a'): {'q0'},
        ('q0', 'ε'): {'q1'},
        ('q1', 'b'): {'q1'},
        ('q1', 'ε'): {'q2'},
    },
    q0='q0',
    F={'q0', 'q1', 'q2'}
)

dfa2 = subset_construction(nfa2)

print(f"NFA states: {len(nfa2.Q)}")
print(f"DFA states: {len(dfa2.Q)}")
print(f"\nDFA states:")
for state in dfa2.Q:
    marker = " (accept)" if state in dfa2.F else ""
    print(f"  {set(state)}{marker}")

# Test
print("\nEquivalence test:")
for s in ['', 'a', 'b', 'ab', 'aabb', 'ba', 'aba', 'aa', 'bb']:
    r_nfa = nfa2.accepts(s)
    r_dfa = dfa2.accepts(s)
    match = "✓" if r_nfa == r_dfa else "✗"
    print(f"  '{s:6s}' NFA={r_nfa}, DFA={r_dfa} {match}")

# EXAMPLE 3: ONLY REACHABLE STATES
print("\n=== Only Reachable States ===")
print("""
Subset construction only creates REACHABLE subsets.
This is crucial — otherwise we'd have 2^|Q| states!

For most practical NFAs, the number of reachable
subsets is much smaller than 2^|Q|.

Example: NFA with 10 states
  Worst case: 2^10 = 1024 DFA states
  Typical: 10-50 DFA states

The BFS approach automatically avoids unreachable states.
""")

# VISUALIZATION OF SUBSET CONSTRUCTION
print("=== Subset Construction Trace ===")
print("""
NFA for "ends in 01":
  q0 --0--> {q0, q1}
  q0 --1--> {q0}
  q1 --1--> {q2}

Subset construction:

Start: ε-closure({q0}) = {q0}
  Call this DFA state A = {q0}

From A on '0': {q0, q1} → call this B
From A on '1': {q0} → A (self-loop)

From B on '0': {q0, q1} → B
From B on '1': {q0, q2} → call this C

From C on '0': {q0, q1} → B
From C on '1': {q0} → A

DFA states: A, B, C
  A = {q0}
  B = {q0, q1}
  C = {q0, q2} ← contains q2 (accept!)

F_DFA = {C}

This matches the DFA we designed directly!
""")

# COMPLEXITY
print("=== Complexity of Subset Construction ===")
print("""
Time: O(2^|Q_N| × |Σ|)
  - At most 2^|Q_N| subsets
  - For each subset, |Σ| symbols
  - For each symbol, compute union and ε-closure

Space: O(2^|Q_N|)
  - Store DFA states (subsets)

Worst case: Exponential blowup
  - Some NFAs require 2^n DFA states
  - Example: L = {w | k-th symbol from end is 'a'}
    NFA: k+1 states
    DFA: 2^k states

In practice:
  - Usually much smaller
  - Many subsets unreachable
  - Use BFS to avoid unreachable states

Optimization:
  - Lazy construction (only when needed)
  - On-the-fly subset construction
  - Used in regex engines (RE2)
""")

# PRACTICAL APPLICATION
print("=== Practical Application: Regex Engine ===")
print("""
Modern regex engines use subset construction:

1. Parse regex → AST
2. Thompson construction → ε-NFA
3. Subset construction → DFA (on-the-fly)
4. Minimize DFA (Hopcroft)
5. Simulate DFA (linear time)

On-the-fly subset construction:
  - Don't precompute all DFA states
  - Compute transitions lazily as needed
  - Cache results for performance
  - Used in RE2, Rust regex

Benefits:
  - No exponential blowup in practice
  - Linear time matching
  - No catastrophic backtracking
""")

➕ Operations (Union, Concat, Star)

🎯 Combining NFAs

NFAs make it easy to prove closure properties. Union, concatenation, and Kleene star all have simple NFA constructions using ε-transitions.

NFA Closure Constructions

Union: New start with ε to both. Concat: ε from R1 accept to R2 start. Star: ε-loop back to start. Complement: Harder (need DFA). Intersection: Product construction. Closure: All regular languages.

➕ Union· Concat* Starε Combine

# NFA operations — closure properties
from collections import deque

class NFA:
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def epsilon_closure(self, 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):
        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)


# 1. UNION
def union(nfa1, nfa2):
    """
    L(M1 ∪ M2) = L(M1) ∪ L(M2)
    
    New start state with ε to both starts.
    Accept = F1 ∪ F2.
    """
    # Create new start state
    new_start = 'q_union_start'
    
    # New states: all states from both + new start
    new_Q = nfa1.Q | nfa2.Q | {new_start}
    
    # New transitions
    new_delta = dict(nfa1.delta)
    for (q, s), next_set in nfa2.delta.items():
        new_delta[(q, s)] = next_set
    
    # Add ε-transitions from new start
    new_delta[(new_start, 'ε')] = {nfa1.q0, nfa2.q0}
    
    # Accept states: union
    new_F = nfa1.F | nfa2.F
    
    return NFA(new_Q, nfa1.Sigma | nfa2.Sigma, new_delta, new_start, new_F)


# 2. CONCATENATION
def concatenate(nfa1, nfa2):
    """
    L(M1 · M2) = L(M1) · L(M2)
    
    ε-transitions from M1 accept states to M2 start.
    Accept = F2.
    """
    new_Q = nfa1.Q | nfa2.Q
    
    new_delta = dict(nfa1.delta)
    for (q, s), next_set in nfa2.delta.items():
        new_delta[(q, s)] = next_set
    
    # Add ε from M1 accepts to M2 start
    for accept_state in nfa1.F:
        new_delta[(accept_state, 'ε')] = {nfa2.q0}
    
    return NFA(new_Q, nfa1.Sigma | nfa2.Sigma, new_delta, nfa1.q0, nfa2.F)


# 3. KLEENE STAR
def kleene_star(nfa):
    """
    L(M*) = (L(M))*
    
    New start/accept with ε-transitions.
    ε from new start to old start.
    ε from old accepts back to old start.
    ε from old accepts to new accept.
    """
    new_start = 'q_star_start'
    new_accept = 'q_star_accept'
    
    new_Q = nfa.Q | {new_start, new_accept}
    
    new_delta = dict(nfa.delta)
    
    # New start ε to old start and new accept
    new_delta[(new_start, 'ε')] = {nfa.q0, new_accept}
    
    # Old accepts ε to old start and new accept
    for accept_state in nfa.F:
        if (accept_state, 'ε') in new_delta:
            new_delta[(accept_state, 'ε')] |= {nfa.q0, new_accept}
        else:
            new_delta[(accept_state, 'ε')] = {nfa.q0, new_accept}
    
    # New accept
    new_F = {new_accept}
    
    return NFA(new_Q, nfa.Sigma, new_delta, new_start, new_F)


# 4. PLUS (R+)
def plus(nfa):
    """L(M+) = L(M) · L(M)*"""
    return concatenate(nfa, kleene_star(nfa))


# 5. OPTIONAL (R?)
def optional(nfa):
    """L(M?) = L(M) ∪ {ε}"""
    # Add ε-transition from start to a new accept state
    new_accept = 'q_opt_accept'
    new_Q = nfa.Q | {new_accept}
    new_delta = dict(nfa.delta)
    new_delta[(nfa.q0, 'ε')] = {new_accept}
    new_F = nfa.F | {new_accept}
    return NFA(new_Q, nfa.Sigma, new_delta, nfa.q0, new_F)


# EXAMPLE
print("=== NFA Operations Demo ===")

# NFA for strings ending in "ab"
nfa_ab = NFA(
    states={'a0', 'a1', 'a2'},
    alphabet={'a', 'b'},
    delta={
        ('a0', 'a'): {'a1'},
        ('a0', 'b'): {'a0'},
        ('a1', 'b'): {'a2'},
        ('a1', 'a'): {'a1'},
        ('a2', 'a'): {'a1'},
        ('a2', 'b'): {'a0'},
    },
    q0='a0',
    F={'a2'}
)

# NFA for strings with even length
nfa_even = NFA(
    states={'b0', 'b1'},
    alphabet={'a', 'b'},
    delta={
        ('b0', 'a'): {'b1'},
        ('b0', 'b'): {'b1'},
        ('b1', 'a'): {'b0'},
        ('b1', 'b'): {'b0'},
    },
    q0='b0',
    F={'b0'}
)

# Union
nfa_union = union(nfa_ab, nfa_even)
print(f"\nUnion NFA states: {len(nfa_union.Q)}")

# Concatenation
nfa_concat = concatenate(nfa_ab, nfa_even)
print(f"Concat NFA states: {len(nfa_concat.Q)}")

# Star
nfa_star = kleene_star(nfa_ab)
print(f"Star NFA states: {len(nfa_star.Q)}")

# Test
print("\n=== Testing Union (ends in 'ab' OR even length) ===")
for s in ['ab', 'aabb', 'abab', 'a', 'b', 'aa', 'bb', 'aba', 'ba']:
    r1 = nfa_ab.accepts(s)
    r2 = nfa_even.accepts(s)
    r_union = nfa_union.accepts(s)
    expected = r1 or r2
    match = "✓" if r_union == expected else "✗"
    print(f"  '{s:6s}' ab={r1}, even={r2}, union={r_union} {match}")

print("\n=== Testing Concatenation (ends in 'ab' · even length) ===")
for s in ['ab', 'abab', 'abaa', 'abbb', 'aabb', 'abba']:
    r_concat = nfa_concat.accepts(s)
    print(f"  '{s:6s}' → {r_concat}")

print("\n=== Testing Star ((ends in 'ab')*) ===")
for s in ['', 'ab', 'abab', 'ababab', 'a', 'ababa', 'ba']:
    r_star = nfa_star.accepts(s)
    print(f"  '{s:6s}' → {r_star}")

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

✓ UNION: L1 ∪ L2
  Construction: New start with ε to both

✓ CONCATENATION: L1 · L2
  Construction: ε from L1 accepts to L2 start

✓ KLEENE STAR: L*
  Construction: ε-loops

✓ COMPLEMENT: Σ* \ L
  Construction: Swap F with Q\F (need DFA)

✓ INTERSECTION: L1 ∩ L2
  Construction: Product (need DFA)

✓ DIFFERENCE: L1 \ L2
  Construction: L1 ∩ complement(L2)

✓ REVERSAL: L^R
  Construction: Reverse all transitions

✓ HOMOMORPHISM: h(L)
  Construction: Replace symbols

All these preserve regularity!
NFA makes union, concat, star trivial.
""")

# 7. REVERSAL
def reverse(nfa):
    """
    L(M^R) = {w^R | w ∈ L(M)}
    
    1. Reverse all transitions
    2. New start state with ε to all old accepts
    3. Old start becomes accept
    """
    new_start = 'q_rev_start'
    
    # Reverse transitions
    new_delta = {}
    for (q, s), next_set in nfa.delta.items():
        for next_state in next_set:
            if (next_state, s) not in new_delta:
                new_delta[(next_state, s)] = set()
            new_delta[(next_state, s)].add(q)
    
    # New start ε to old accepts
    new_delta[(new_start, 'ε')] = set(nfa.F)
    
    # Old start becomes accept
    new_F = {nfa.q0}
    
    return NFA(nfa.Q | {new_start}, nfa.Sigma, new_delta, new_start, new_F)

# Test reversal
nfa_rev = reverse(nfa_ab)
print("\n=== Testing Reversal (reverse of 'ends in ab') ===")
print("Original: ends in 'ab' → 'ab', 'aab', 'bab'")
print("Reversed: starts with 'ba' → 'ba', 'baa', 'bab'")
for s in ['ba', 'baa', 'bab', 'ab', 'b', 'a', 'bba']:
    r_orig = nfa_ab.accepts(s)
    r_rev = nfa_rev.accepts(s)
    print(f"  '{s:6s}' original={r_orig}, reversed={r_rev}")

🟰 Equivalence & Testing

🎯 Are Two NFAs the Same?

Two NFAs are equivalent if they accept the same language. This is decidable — convert both to DFAs and test DFA equivalence.

Equivalence Testing for NFAs

Approach: NFA1 → DFA1, NFA2 → DFA2. Then: Test DFA equivalence. Alternative: Product construction on NFAs. Complexity: O(2^|Q1| × 2^|Q2|). Decidable: Yes, always. Counterexample: Shortest distinguishing string.

🟰 Equivalence📊 Subset first🔍 Product🎯 Counterexample

# NFA equivalence testing
from collections import deque
from itertools import product as cartesian_product

class NFA:
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def epsilon_closure(self, 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):
        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)


# 1. NFA → DFA (subset construction)
def nfa_to_dfa(nfa):
    """Convert NFA to DFA using subset construction."""
    start = frozenset(nfa.epsilon_closure({nfa.q0}))
    dfa_states = {start}
    queue = deque([start])
    dfa_delta = {}
    
    while queue:
        current = queue.popleft()
        for symbol in nfa.Sigma:
            next_set = set()
            for state in current:
                next_set |= nfa.delta.get((state, symbol), set())
            next_set = frozenset(nfa.epsilon_closure(next_set))
            dfa_delta[(current, symbol)] = next_set
            if next_set not in dfa_states:
                dfa_states.add(next_set)
                queue.append(next_set)
    
    dfa_F = {s for s in dfa_states if s & nfa.F}
    
    class DFA:
        def __init__(self, Q, Sigma, delta, q0, F):
            self.Q = Q
            self.Sigma = Sigma
            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
    
    return DFA(dfa_states, nfa.Sigma, dfa_delta, start, dfa_F)


# 2. DFA EQUIVALENCE (product construction)
def check_equivalence(dfa1, dfa2):
    """
    Check if two DFAs are equivalent.
    Returns (True, None) or (False, counterexample).
    """
    start = (dfa1.q0, dfa2.q0)
    queue = deque([(start, "")])
    visited = {start}
    
    while queue:
        (q1, q2), word = queue.popleft()
        
        if (q1 in dfa1.F) != (q2 in dfa2.F):
            return False, word
        
        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))
    
    return True, None


# 3. NFA EQUIVALENCE
def nfa_equivalent(nfa1, nfa2):
    """Check if two NFAs are equivalent."""
    dfa1 = nfa_to_dfa(nfa1)
    dfa2 = nfa_to_dfa(nfa2)
    return check_equivalence(dfa1, dfa2)


# EXAMPLE
print("=== NFA Equivalence Testing ===")

# NFA 1: ends in "01"
nfa1 = NFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'0', '1'},
    delta={
        ('q0', '0'): {'q0', 'q1'},
        ('q0', '1'): {'q0'},
        ('q1', '1'): {'q2'},
    },
    q0='q0',
    F={'q2'}
)

# NFA 2: equivalent, different design
nfa2 = NFA(
    states={'r0', 'r1', 'r2'},
    alphabet={'0', '1'},
    delta={
        ('r0', '0'): {'r1'},
        ('r0', '1'): {'r2'},
        ('r1', '0'): {'r1'},
        ('r1', '1'): {'r3'},
        ('r2', '0'): {'r1'},
        ('r2', '1'): {'r2'},
        ('r3', '0'): {'r1'},
        ('r3', '1'): {'r2'},
    },
    q0='r0',
    F={'r3'}
)

# NFA 3: different language
nfa3 = NFA(
    states={'s0', 's1', 's2'},
    alphabet={'0', '1'},
    delta={
        ('s0', '0'): {'s0'},
        ('s0', '1'): {'s0', 's1'},
        ('s1', '0'): {'s2'},
    },
    q0='s0',
    F={'s2'}
)

# Test pairs
print("\n1. NFA1 vs NFA2 (should be equivalent):")
equiv, counter = nfa_equivalent(nfa1, nfa2)
if equiv:
    print("   ✓ Equivalent")
else:
    print(f"   ✗ Differ on '{counter}'")

print("\n2. NFA1 vs NFA3 (should differ):")
equiv, counter = nfa_equivalent(nfa1, nfa3)
if equiv:
    print("   ✓ Equivalent")
else:
    print(f"   ✗ Differ on '{counter}'")
    print(f"     NFA1 accepts: {nfa1.accepts(counter)}")
    print(f"     NFA3 accepts: {nfa3.accepts(counter)}")

# 4. DECISION PROBLEMS
print("\n=== Decidable Problems for NFAs ===")
print("""
All decidable (via conversion to DFA):

1. MEMBERSHIP
   "Is w ∈ L(N)?"
   → Simulate NFA, O(|w| × |Q|²)

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

3. UNIVERSALITY
   "Is L(N) = Σ*?"
   → Convert to DFA, check complement empty

4. EQUIVALENCE
   "Is L(N1) = L(N2)?"
   → Convert both to DFA, test equivalence

5. INCLUSION
   "Is L(N1) ⊆ L(N2)?"
   → Convert to DFA, test L1 \ L2 = ∅

6. DISJOINTNESS
   "Is L(N1) ∩ L(N2) = ∅?"
   → Convert to DFA, product construction

7. FINITENESS
   "Is L(N) finite?"
   → Convert to DFA, check cycle

All efficient after DFA conversion.
""")

# 5. EMPTINESS CHECK
def is_empty(nfa):
    """Check if NFA accepts empty language."""
    reachable = nfa.epsilon_closure({nfa.q0})
    queue = deque(reachable)
    visited = set(reachable)
    
    while queue:
        state = queue.popleft()
        if state in nfa.F:
            return False
        for symbol in nfa.Sigma:
            for next_state in nfa.delta.get((state, symbol), set()):
                if next_state not in visited:
                    visited.add(next_state)
                    queue.append(next_state)
    
    return True

print(f"\nnfa1 is empty: {is_empty(nfa1)}")
print(f"nfa2 is empty: {is_empty(nfa2)}")
print(f"nfa3 is empty: {is_empty(nfa3)}")

# 6. SUMMARY
print("\n=== Summary: NFA Decision Problems ===")
print(f"{'Problem':<20} {'Method':<30} {'Complexity':<20}")
print("-" * 70)
print(f"{'Membership':<20} {'Simulate NFA':<30} {'O(n × |Q|²)':<20}")
print(f"{'Emptiness':<20} {'Reachability':<30} {'O(|Q| × |Σ|)':<20}")
print(f"{'Equivalence':<20} {'Subset + DFA product':<30} {'O(2^|Q1| × 2^|Q2|)':<20}")
print(f"{'Inclusion':<20} {'Subset + DFA product':<30} {'Exponential':<20}")
print(f"{'Finiteness':<20} {'Cycle detection':<30} {'O(|Q|)':<20}")

# 7. PRACTICAL NOTE
print("\n=== Practical Note ===")
print("""
In practice:
  - Direct NFA simulation is often faster than subset construction
    (especially if NFA is small)
  - For repeated queries, convert to DFA once
  - For equivalence, always go through DFA

Tools:
  - Python: automata-lib
  - Java: dk.brics.automaton
  - C++: RE2, OpenFST
  - Rust: rust-automata

Remember:
  - NFA simulation tracks sets of states
  - Subset construction may blow up
  - But resulting DFA is fast to simulate
""")

📉 NFA Minimization

🎯 Finding the Smallest NFA

Unlike DFAs, minimal NFAs are not unique. Finding the smallest NFA for a language is computationally hard (PSPACE-complete). However, we can still reduce NFA size using various techniques.

NFA Reduction Techniques

1. Remove unreachable: States not reachable from q₀. 2. Remove dead: States that can't reach accept. 3. ε-elimination: Remove ε-transitions. 4. Merge equivalent: States with same behavior. 5. Convert to DFA: Then minimize DFA. Not unique: Different minimal NFAs possible.

🔍 Unreachable💀 Deadε Eliminate📊 DFA minimize

# NFA minimization and reduction
from collections import deque, defaultdict

class NFA:
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def epsilon_closure(self, 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):
        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)


# 1. REMOVE UNREACHABLE STATES
def remove_unreachable(nfa):
    """Remove states not reachable from q0."""
    reachable = nfa.epsilon_closure({nfa.q0})
    queue = deque(reachable)
    
    while queue:
        state = queue.popleft()
        for symbol in nfa.Sigma:
            for next_state in nfa.delta.get((state, symbol), set()):
                if next_state not in reachable:
                    reachable.add(next_state)
                    queue.append(next_state)
        # Also follow ε-transitions
        for next_state in nfa.delta.get((state, 'ε'), set()):
            if next_state not in reachable:
                reachable.add(next_state)
                queue.append(next_state)
    
    new_delta = {
        (q, s): {d for d in next_set if d in reachable}
        for (q, s), next_set in nfa.delta.items()
        if q in reachable    }
    
    return NFA(
        states=reachable,
        alphabet=nfa.Sigma,
        delta=new_delta,
        q0=nfa.q0,
        F=nfa.F & reachable
    )


# 2. REMOVE DEAD STATES
def remove_dead(nfa):
    """Remove states from which no accept state is reachable."""
    # Reverse transitions (including ε)
    reverse = defaultdict(set)
    for (q, s), next_set in nfa.delta.items():
        for d in next_set:
            reverse[d].add(q)
    
    # BFS from accept states backwards
    live = set(nfa.F)
    queue = deque(nfa.F)
    
    while queue:
        state = queue.popleft()
        for prev in reverse[state]:
            if prev not in live:
                live.add(prev)
                queue.append(prev)
    
    live.add(nfa.q0)  # Keep start state
    
    new_delta = {
        (q, s): {d for d in next_set if d in live}
        for (q, s), next_set in nfa.delta.items()
        if q in live
    }
    
    return NFA(
        states=live,
        alphabet=nfa.Sigma,
        delta=new_delta,
        q0=nfa.q0,
        F=nfa.F & live
    )


# 3. ELIMINATE ε-TRANSITIONS
def eliminate_epsilon(nfa):
    """Remove ε-transitions from NFA."""
    # Compute ε-closures
    closures = {state: nfa.epsilon_closure({state}) for state in nfa.Q}
    
    new_delta = {}
    for q in nfa.Q:
        for a in nfa.Sigma:
            next_states = set()
            for p in closures[q]:
                next_states |= nfa.delta.get((p, a), set())
            next_states = nfa.epsilon_closure(next_states)
            if next_states:
                new_delta[(q, a)] = next_states
    
    new_F = {q for q in nfa.Q if closures[q] & nfa.F}
    
    return NFA(nfa.Q, nfa.Sigma, new_delta, nfa.q0, new_F)


# 4. MERGE EQUIVALENT STATES (simple heuristic)
def merge_equivalent(nfa):
    """
    Merge states with identical transition behavior.
    This is a heuristic — not guaranteed to find minimal NFA.
    """
    # Compute signature for each state
    signatures = {}
    for q in nfa.Q:
        sig = []
        for a in sorted(nfa.Sigma):
            sig.append(tuple(sorted(nfa.delta.get((q, a), set()))))
        sig.append(q in nfa.F)
        signatures[q] = tuple(sig)
    
    # Group states with same signature
    groups = defaultdict(set)
    for q, sig in signatures.items():
        groups[sig].add(q)
    
    # Create mapping from old states to group representatives
    mapping = {}
    for sig, group in groups.items():
        rep = min(group)  # choose representative
        for q in group:
            mapping[q] = rep
    
    # Build new NFA
    new_Q = set(mapping.values())
    new_delta = {}
    for (q, a), next_set in nfa.delta.items():
        new_q = mapping[q]
        new_next = {mapping[d] for d in next_set}
        if (new_q, a) in new_delta:
            new_delta[(new_q, a)] |= new_next
        else:
            new_delta[(new_q, a)] = new_next
    
    new_F = {mapping[q] for q in nfa.F}
    
    return NFA(new_Q, nfa.Sigma, new_delta, mapping[nfa.q0], new_F)


# 5. FULL REDUCTION PIPELINE
def reduce_nfa(nfa):
    """Apply all reduction techniques."""
    nfa = remove_unreachable(nfa)
    nfa = remove_dead(nfa)
    nfa = eliminate_epsilon(nfa)
    nfa = merge_equivalent(nfa)
    nfa = remove_unreachable(nfa)  # again after merge
    return nfa


# EXAMPLE
print("=== NFA Reduction Example ===")

# Create a non-minimal NFA
nfa = NFA(
    states={'q0', 'q1', 'q2', 'q3', 'q4', 'q5'},
    alphabet={'a', 'b'},
    delta={
        ('q0', 'a'): {'q1', 'q2'},
        ('q0', 'b'): {'q3'},
        ('q1', 'a'): {'q1'},
        ('q1', 'b'): {'q4'},
        ('q2', 'a'): {'q2'},
        ('q2', 'b'): {'q4'},
        ('q3', 'a'): {'q3'},
        ('q3', 'b'): {'q3'},
        ('q4', 'a'): {'q4'},
        ('q4', 'b'): {'q4'},
        ('q5', 'a'): {'q5'},  # unreachable
        ('q5', 'b'): {'q5'},
    },
    q0='q0',
    F={'q4', 'q5'}
)

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

# Apply reductions
nfa_unreach = remove_unreachable(nfa)
print(f"After removing unreachable: {len(nfa_unreach.Q)} states")

nfa_dead = remove_dead(nfa_unreach)
print(f"After removing dead: {len(nfa_dead.Q)} states")

nfa_no_eps = eliminate_epsilon(nfa_dead)
print(f"After eliminating ε: {len(nfa_no_eps.Q)} states")

nfa_merged = merge_equivalent(nfa_no_eps)
print(f"After merging equivalent: {len(nfa_merged.Q)} states")

nfa_final = reduce_nfa(nfa)
print(f"After full reduction: {len(nfa_final.Q)} states")

# Test equivalence
print("\nEquivalence test after reduction:")
for s in ['', 'a', 'b', 'ab', 'ba', 'aab', 'abb', 'abab', 'bb']:
    r_orig = nfa.accepts(s)
    r_reduced = nfa_final.accepts(s)
    match = "✓" if r_orig == r_reduced else "✗"
    print(f"  '{s:6s}' orig={r_orig}, reduced={r_reduced} {match}")

# 6. WHY NFA MINIMIZATION IS HARD
print("\n=== Why NFA Minimization is Hard ===")
print("""
Complexity:
  - Finding minimal NFA is PSPACE-complete
  - Finding minimal DFA is polynomial (Hopcroft)
  - This is a fundamental difference

Intuition:
  - DFA minimal is unique (Myhill-Nerode)
  - NFA minimal is NOT unique
  - Choosing where to use nondeterminism is combinatorial

Practical approach:
  1. Reduce using heuristics
  2. Convert to DFA
  3. Minimize DFA (optimal for DFA)
  4. Optionally try to reduce further

In practice:
  - NFA minimization is rarely needed
  - NFA is usually a design tool
  - Convert to DFA for implementation
  - Minimize the DFA
""")

# 7. NFA VS DFA MINIMIZATION
print("\n=== NFA vs DFA Minimization ===")
print(f"{'Aspect':<30} {'DFA':<25} {'NFA':<25}")
print("-" * 80)
print(f"{'Minimal unique?':<30} {'Yes (Myhill-Nerode)':<25} {'No':<25}")
print(f"{'Complexity':<30} {'Polynomial':<25} {'PSPACE-complete':<25}")
print(f"{'Algorithm':<30} {'Hopcroft':<25} {'Heuristics':<25}")
print(f"{'Practical':<30} {'Always optimal':<25} {'Rarely needed':<25}")
print(f"{'Approach':<30} {'Partition refinement':<25} {'Reduce + convert':<25}")

# 8. REDUCTION TECHNIQUES SUMMARY
print("\n=== NFA Reduction Techniques ===")
print("""
1. UNREACHABLE REMOVAL
   - BFS from start
   - Remove states not visited
   - O(|Q| × |Σ|)

2. DEAD STATE REMOVAL
   - Backward BFS from accepts
   - Remove states that can't reach accept
   - O(|Q| × |Σ|)

3. ε-TRANSITION ELIMINATION
   - Compute ε-closures
   - Build new transitions
   - O(|Q|² × |Σ|)

4. EQUIVALENT STATE MERGING
   - Compare transition signatures
   - Merge identical states
   - O(|Q|² × |Σ|) — heuristic

5. DIRECT DFA CONSTRUCTION
   - Skip NFA reduction
   - Subset construction
   - Minimize resulting DFA
   - Often best approach
""")

🔤 Regular Expressions & Thompson

🎯 Regex to NFA: Thompson's Construction

Thompson's construction converts any regular expression into an equivalent ε-NFA. This is the foundation of modern regex engines.

Thompson's Construction

Literal: ε → q0 --a--> q1 → ε. Union: New start/accept with ε. Concat: ε from R1 accept to R2 start. Star: ε-loops. Result: ε-NFA with one start, one accept. Then: Subset construction → DFA.

🔤 Regex⚙️ Thompsonε-NFA📊 Subset

# Thompson's Construction: Regex → ε-NFA
from dataclasses import dataclass
from typing import Set, Dict, Tuple, FrozenSet, Optional
import re

# 1. AST FOR REGEX
@dataclass
class RegexNode:
    """Abstract syntax tree node for regex."""
    type: str  # 'literal', 'concat', 'union', 'star', 'plus', 'optional', 'epsilon'
    value: Optional[str] = None
    left: Optional['RegexNode'] = None
    right: Optional['RegexNode'] = None


def parse_regex(pattern: str) -> RegexNode:
    """Simple regex parser (supports |, *, +, ?, concat, parentheses, literals)."""
    # This is a simplified parser — production regex is more complex
    pattern = pattern.replace(' ', '')
    
    def parse_union(s):
        parts = split_top_level(s, '|')
        if len(parts) == 1:
            return parse_concat(parts[0])
        node = RegexNode('union')
        current = node
        for i, part in enumerate(parts):
            if i == 0:
                node.left = parse_concat(part)
            else:
                new_node = RegexNode('union')
                new_node.left = current.right
                new_node.right = parse_concat(part)
                current.right = new_node
                current = new_node
        return node
    
    def parse_concat(s):
        parts = split_concat(s)
        if len(parts) == 1:
            return parse_postfix(parts[0])
        node = RegexNode('concat')
        node.left = parse_postfix(parts[0])
        if len(parts) > 1:
            node.right = parse_concat(''.join(parts[1:]))
        return node
    
    def parse_postfix(s):
        if len(s) == 1:
            return RegexNode('literal', value=s)
        if s.endswith('*'):
            return RegexNode('star', left=parse_postfix(s[:-1]))
        if s.endswith('+'):
            return RegexNode('plus', left=parse_postfix(s[:-1]))
        if s.endswith('?'):
            return RegexNode('optional', left=parse_postfix(s[:-1]))
        # Handle parentheses
        if s.startswith('(') and s.endswith(')'):
            return parse_union(s[1:-1])
        # Handle literals and escapes
        if len(s) > 1:
            return RegexNode('concat', 
                           left=RegexNode('literal', value=s[0]),
                           right=parse_postfix(s[1:]))
        return RegexNode('literal', value=s)
    
    def split_top_level(s, op):
        """Split by op at top level (not inside parentheses)."""
        parts = []
        depth = 0
        current = ''
        for c in s:
            if c == '(':
                depth += 1
                current += c
            elif c == ')':
                depth -= 1
                current += c
            elif c == op and depth == 0:
                parts.append(current)
                current = ''
            else:
                current += c
        parts.append(current)
        return parts
    
    def split_concat(s):
        """Split concatenation into parts."""
        parts = []
        current = ''
        depth = 0
        for c in s:
            if c == '(':
                depth += 1
                current += c
            elif c == ')':
                depth -= 1
                current += c
            elif c in '*+?' and depth == 0:
                current += c
            else:
                if depth == 0 and current and current[-1] not in '*+?':
                    parts.append(current)
                    current = c
                else:
                    current += c
        if current:
            parts.append(current)
        return parts
    
    return parse_union(pattern)


# 2. THOMPSON'S CONSTRUCTION
class EpsilonNFA:
    """ε-NFA for Thompson construction."""
    _counter = 0
    
    def __init__(self, start, accept, transitions):
        self.start = start
        self.accept = accept
        self.transitions = transitions  # (state, symbol) -> set of states
    
    @classmethod
    def new_state(cls):
        cls._counter += 1
        return f"q{cls._counter}"
    
    @classmethod
    def from_literal(cls, char):
        """Build NFA for a single literal."""
        s0 = cls.new_state()
        s1 = cls.new_state()
        return cls(s0, s1, {(s0, char): {s1}})
    
    @classmethod
    def from_epsilon(cls):
        """Build NFA for ε."""
        s0 = cls.new_state()
        s1 = cls.new_state()
        return cls(s0, s1, {(s0, 'ε'): {s1}})
    
    @classmethod
    def union(cls, nfa1, nfa2):
        """Build NFA for R1 | R2."""
        s0 = cls.new_state()
        s1 = cls.new_state()
        
        transitions = {}
        # Copy transitions
        for (q, a), next_set in {**nfa1.transitions, **nfa2.transitions}.items():
            transitions[(q, a)] = set(next_set)
        
        # New start ε to both starts
        transitions[(s0, 'ε')] = {nfa1.start, nfa2.start}
        
        # Both accepts ε to new accept
        transitions[(nfa1.accept, 'ε')] = transitions.get((nfa1.accept, 'ε'), set()) | {s1}
        transitions[(nfa2.accept, 'ε')] = transitions.get((nfa2.accept, 'ε'), set()) | {s1}
        
        return cls(s0, s1, transitions)
    
    @classmethod
    def concat(cls, nfa1, nfa2):
        """Build NFA for R1 R2."""
        transitions = {}
        for (q, a), next_set in {**nfa1.transitions, **nfa2.transitions}.items():
            transitions[(q, a)] = set(next_set)
        
        # nfa1 accept ε to nfa2 start
        transitions[(nfa1.accept, 'ε')] = transitions.get((nfa1.accept, 'ε'), set()) | {nfa2.start}
        
        return cls(nfa1.start, nfa2.accept, transitions)
    
    @classmethod
    def star(cls, nfa):
        """Build NFA for R*."""
        s0 = cls.new_state()
        s1 = cls.new_state()
        
        transitions = {}
        for (q, a), next_set in nfa.transitions.items():
            transitions[(q, a)] = set(next_set)
        
        # New start ε to old start and new accept
        transitions[(s0, 'ε')] = {nfa.start, s1}
        
        # Old accept ε back to old start and to new accept
        transitions[(nfa.accept, 'ε')] = transitions.get((nfa.accept, 'ε'), set()) | {nfa.start, s1}
        
        return cls(s0, s1, transitions)
    
    @classmethod
    def plus(cls, nfa):
        """Build NFA for R+ = R R*."""
        return cls.concat(nfa, cls.star(nfa))
    
    @classmethod
    def optional(cls, nfa):
        """Build NFA for R? = R | ε."""
        return cls.union(nfa, cls.from_epsilon())
    
    def to_nfa_dict(self):
        """Convert to standard NFA format."""
        states = set()
        for (q, a), next_set in self.transitions.items():
            states.add(q)
            states.update(next_set)
        states.add(self.start)
        states.add(self.accept)
        
        return {
            'states': states,
            'alphabet': {a for (q, a) in self.transitions if a != 'ε'},
            'delta': self.transitions,
            'start': self.start,
            'accept': {self.accept}
        }


def thompson_construction(regex_node: RegexNode) -> EpsilonNFA:
    """Build ε-NFA from regex AST using Thompson's construction."""
    if regex_node.type == 'literal':
        return EpsilonNFA.from_literal(regex_node.value)
    elif regex_node.type == 'epsilon':
        return EpsilonNFA.from_epsilon()
    elif regex_node.type == 'concat':
        left = thompson_construction(regex_node.left)
        right = thompson_construction(regex_node.right)
        return EpsilonNFA.concat(left, right)
    elif regex_node.type == 'union':
        left = thompson_construction(regex_node.left)
        right = thompson_construction(regex_node.right)
        return EpsilonNFA.union(left, right)
    elif regex_node.type == 'star':
        inner = thompson_construction(regex_node.left)
        return EpsilonNFA.star(inner)
    elif regex_node.type == 'plus':
        inner = thompson_construction(regex_node.left)
        return EpsilonNFA.plus(inner)
    elif regex_node.type == 'optional':
        inner = thompson_construction(regex_node.left)
        return EpsilonNFA.optional(inner)
    else:
        raise ValueError(f"Unknown node type: {regex_node.type}")


# 3. DEMONSTRATION
print("=== Thompson's Construction Demo ===")

test_regexes = [
    ('a', 'literal a'),
    ('ab', 'concatenation'),
    ('a|b', 'union'),
    ('a*', 'Kleene star'),
    ('a+', 'plus'),
    ('a?', 'optional'),
    ('(a|b)*abb', 'complex regex'),
]

for pattern, desc in test_regexes:
    try:
        ast = parse_regex(pattern)
        enfa = thompson_construction(ast)
        nfa_dict = enfa.to_nfa_dict()
        print(f"\nRegex: {pattern} ({desc})")
        print(f"  States: {len(nfa_dict['states'])}")
        print(f"  Start: {nfa_dict['start']}")
        print(f"  Accept: {nfa_dict['accept']}")
        print(f"  Transitions: {len(nfa_dict['delta'])}")
    except Exception as e:
        print(f"\nRegex: {pattern} ({desc})")
        print(f"  Error: {e}")

# 4. TEST MATCHING
print("\n=== Testing Regex Matching ===")

def test_regex_match(pattern, strings):
    """Test if regex matches strings."""
    try:
        ast = parse_regex(pattern)
        enfa = thompson_construction(ast)
        nfa_dict = enfa.to_nfa_dict()
        
        # Create NFA object for simulation
        class NFA:
            def __init__(self, d):
                self.Q = d['states']
                self.Sigma = d['alphabet']
                self.delta = d['delta']
                self.q0 = d['start']
                self.F = d['accept']
            def epsilon_closure(self, states):
                closure = set(states)
                stack = list(states)
                while stack:
                    state = stack.pop()
                    for ns in self.delta.get((state, 'ε'), set()):
                        if ns not in closure:
                            closure.add(ns)
                            stack.append(ns)
                return closure
            def accepts(self, word):
                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)
        
        nfa = NFA(nfa_dict)
        
        print(f"\nPattern: {pattern}")
        for s in strings:
            result = "✓" if nfa.accepts(s) else "✗"
            print(f"  '{s}' → {result}")
    except Exception as e:
        print(f"\nPattern: {pattern}")
        print(f"  Error: {e}")

test_regex_match('(a|b)*abb', ['abb', 'aabb', 'babb', 'abab', 'ab', 'b', ''])
test_regex_match('a*b*', ['', 'a', 'b', 'ab', 'aabb', 'aa', 'bb', 'ba'])

# 5. PRACTICAL REGEX ENGINE PIPELINE
print("\n=== Practical Regex Engine Pipeline ===")
print("""
1. PARSE
   Input: regex string like "(a|b)*abb"
   Output: AST (Abstract Syntax Tree)

2. THOMPSON CONSTRUCTION
   Input: AST
   Output: ε-NFA
   - Each regex operator has a construction rule
   - Result: NFA with single start and accept

3. SUBSET CONSTRUCTION
   Input: ε-NFA
   Output: DFA
   - States are subsets of NFA states
   - May be exponential in worst case

4. DFA MINIMIZATION
   Input: DFA
   Output: Minimal DFA
   - Hopcroft's algorithm
   - Unique minimal DFA

5. SIMULATION
   Input: Minimal DFA + text
   Output: Match/no match
   - O(n) time
   - O(1) space

This is how RE2, Rust regex, and others work.
""")

# 6. COMPARISON WITH BACKTRACKING
print("\n=== Thompson NFA vs Backtracking ===")
print(f"{'Aspect':<25} {'Thompson NFA':<25} {'Backtracking':<25}")
print("-" * 75)
print(f"{'Time (worst)':<25} {'O(n × m)':<25} {'O(2^n)':<25}")
print(f"{'Space':<25} {'O(2^m)':<25} {'O(m × n)':<25}")
print(f"{'Features':<25} {'Regular only':<25} {'Backrefs, lookahead':<25}")
print(f"{'Implementation':<25} {'Complex':<25} {'Simple':<25}")
print(f"{'Used in':<25} {'RE2, Rust':<25} {'Python, Java, JS':<25}")

print("""
Key insight:
  - Thompson NFA guarantees linear time
  - But doesn't support backreferences
  - Backtracking supports more features
  - But can be exponential

For untrusted input: use Thompson NFA
For feature-rich regex: use backtracking (carefully)
""")

# 7. LIMITATIONS
print("\n=== Regex Limitations (Regular Languages) ===")
print("""
Regex (and thus NFA/DFA) CANNOT express:

✗ Balanced parentheses: a^n b^n
✗ Palindromes: w = w^R
✗ Prime length strings
✗ Nested structures (JSON, HTML)
✗ Backreferences: (a+)b\\1

Why?
  These require unbounded memory.
  Finite automata have finite states.

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

Note: Many "regex" implementations add features
      (backrefs, lookahead) that go beyond
      regular languages.
""")

💼 Applications

🎯 NFAs in the Real World

NFAs are the design tool of choice for pattern matching. They're used in compilers, text editors, network security, and anywhere regex is needed.

Application Domains

Compilers: Lexical analysis. Regex engines: Thompson construction. Text editors: Search and replace. Network: Intrusion detection. Bioinformatics: DNA matching. Verification: Model checking.

💻 Compilers🔤 Regex🌐 Network🔬 Science

# Applications of NFAs
import re
from collections import deque

# 1. LEXICAL ANALYSIS (Compiler Frontend)
print("=== Lexical Analysis ===")
print("""
Compilers use NFAs to build lexers:

Pipeline:
  Regex patterns → NFA (Thompson) → DFA (subset) → Scanner

Each token type is a regex:
  Keywords:  if|else|while|for|return
  Identifiers: [a-zA-Z_][a-zA-Z0-9_]*
  Numbers:   [0-9]+(\\.[0-9]+)?
  Operators: \\+|-|\\*|/|==|!=|<=|>=
  Delimiters: \\(|\\)|\\{|\\}|;|,

Combined NFA: union of all token NFAs
Then: subset construction → single DFA
Scanner: runs DFA on input, emits tokens

Tools:
  - Lex (original)
  - Flex (fast lex)
  - ANTLR lexers
  - Hand-written (recursive descent)
""")

# Simple NFA-based lexer
class NFALexer:
    """Lexer using NFA simulation (via regex)."""
    def __init__(self):
        self.token_patterns = [
            ('NUMBER', re.compile(r'\d+(\.\d+)?')),
            ('IDENT', re.compile(r'[a-zA-Z_][a-zA-Z0-9_]*')),
            ('OP', re.compile(r'[+\-*/=<>!]+')),
            ('DELIM', re.compile(r'[(){};,\.]')),
        ]
    
    def tokenize(self, text):
        tokens = []
        pos = 0
        
        while pos < len(text):
            if text[pos].isspace():
                pos += 1
                continue
            
            matched = False
            for token_type, pattern in self.token_patterns:
                match = pattern.match(text, pos)
                if match:
                    tokens.append((token_type, match.group()))
                    pos = match.end()
                    matched = True
                    break
            
            if not matched:
                tokens.append(('UNKNOWN', text[pos]))
                pos += 1
        
        return tokens

lexer = NFALexer()
source = "x = 10 + y * 3.14"
print(f"Source: {source}")
print(f"Tokens: {lexer.tokenize(source)}")

# 2. REGEX ENGINES
print("\n=== Regex Engines ===")
print("""
Modern regex engines use Thompson NFA:

Pipeline:
  1. Parse regex → AST
  2. Thompson construction → ε-NFA
  3. Subset construction → DFA (on-the-fly)
  4. Simulate DFA

Advantages:
  - Linear time: O(n × m)
  - No catastrophic backtracking
  - Predictable performance

Implementations:
  - RE2 (Google) — C++
  - Rust regex — Rust
  - Hyperscan (Intel) — SIMD accelerated
  - Go regexp — Go (uses Thompson NFA)

Comparison:
  - Thompson NFA: O(n × m), no backrefs
  - Backtracking: O(2^n) worst, full features
  - Use Thompson for untrusted input
""")

# NFA-based regex engine (simplified)
def nfa_regex_match(pattern, text):
    """Simple NFA-based regex matcher."""
    try:
        compiled = re.compile(pattern)
        return bool(compiled.fullmatch(text))
    except:
        return False

test_cases = [
    (r'(a|b)*abb', 'aabb', True),
    (r'(a|b)*abb', 'abab', False),
    (r'a*b*', 'aaabbb', True),
    (r'a*b*', 'ba', False),
]

print("NFA-based regex matching:")
for pattern, text, expected in test_cases:
    result = nfa_regex_match(pattern, text)
    match = "✓" if result == expected else "✗"
    print(f"  '{pattern}' on '{text}': {result} {match}")

# 3. NETWORK INTRUSION DETECTION
print("\n=== Network Intrusion Detection ===")
print("""
NFAs for deep packet inspection:

Approach:
  - Compile attack signatures to NFA
  - Run NFA on network packets
  - Alert on match

Signatures:
  - SQL injection patterns
  - XSS patterns
  - Malware signatures
  - Protocol violations

Tools:
  - Snort (NFA/DFA based)
  - Suricata
  - Bro/Zeek

Performance:
  - 10+ Gbps throughput
  - Multiple signatures in parallel
  - Hardware acceleration (FPGA, GPU)

Example: Hyperscan (Intel)
  - 100+ GB/s on modern CPUs
  - SIMD optimized
  - Multiple patterns simultaneously
""")

# 4. TEXT SEARCH AND REPLACE
print("\n=== Text Search and Replace ===")
print("""
grep, sed, and text editors use NFA-based matching:

grep:
  - Pattern → NFA → DFA
  - Linear time matching
  - Efficient for large files

sed:
  - Pattern → NFA
  - Substitution
  - Streaming processing

Editors:
  - Find/replace with regex
  - Syntax highlighting (NFA for tokens)
  - Auto-completion

Example: Syntax highlighting
  - Keywords: NFA for keyword set
  - Strings: NFA for quoted strings
  - Comments: NFA for comment syntax
  - Numbers: NFA for number formats
""")

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

Patterns:
  - Motifs: short conserved sequences
  - Restriction sites: EcoRI = GAATTC
  - Promoters: TATA box
  - Splice sites

Approach:
  - Compile patterns to NFA
  - Search sequences
  - Handle mutations (IUPAC codes)

Example: IUPAC ambiguity codes
  A = A
  R = A or G (purine)
  Y = C or T (pyrimidine)
  N = any base

Tools:
  - Aho-Corasick (multiple patterns)
  - BLAST (heuristic)
  - Pattern matching libraries

Performance:
  - Human genome: 3 billion base pairs
  - Need linear time matching
  - NFAs/DFAs ideal
""")

# 6. COMPILER OPTIMIZATION
print("\n=== Compiler Optimization ===")
print("""
NFA/DFA for peephole optimization:

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

Approach:
  - Compile patterns to NFA
  - Run on instruction stream
  - Replace matched patterns

Also:
  - Register allocation
  - Dead code elimination
  - Loop optimization
""")

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

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

SQL injection prevention:
  NFA for allowed SQL patterns
  Block suspicious input

XSS prevention:
  NFA for safe HTML/JS
  Sanitize input

URL parsing:
  NFA for scheme, host, path, query, fragment

Performance:
  - O(n) validation
  - Constant memory
  - No ReDoS vulnerability
""")

# 8. CASE STUDY: SNORT IDS
print("\n=== Case Study: Snort IDS ===")
print("""
Snort — Network Intrusion Detection System

Architecture:
  1. Rules: patterns for attacks
  2. Compile rules → NFA/DFA
  3. Run on network packets
  4. Alert on match

Rule example:
  alert tcp any any -> any 80 (
    content: "GET";
    content: "/etc/passwd";
    msg: "Possible path traversal";
  )

Implementation:
  - Multi-pattern matching
  - Aho-Corasick + NFA
  - Hardware acceleration

Performance:
  - 10+ Gbps
  - Millions of rules
  - Low latency
""")

# 9. SUMMARY TABLE
print("\n=== Application Summary ===")
print(f"{'Domain':<25} {'Use Case':<30} {'NFA Role':<25}")
print("-" * 80)
print(f"{'Compilers':<25} {'Lexical analysis':<30} {'Pattern → NFA → DFA':<25}")
print(f"{'Regex engines':<25} {'Pattern matching':<30} {'Thompson construction':<25}")
print(f"{'Text editors':<25} {'Find & replace':<30} {'NFA simulation':<25}")
print(f"{'Networking':<25} {'Intrusion detection':<30} {'Multi-pattern NFA':<25}")
print(f"{'Bioinformatics':<25} {'DNA matching':<30} {'Motif NFA':<25}")
print(f"{'Security':<25} {'Input validation':<30} {'Fast NFA matching':<25}")

# 10. 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

Approach:
  1. Compile log format to NFA
  2. Run on each log line
  3. Extract fields

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

NFA advantage:
  - Linear time
  - No backtracking
  - Constant memory

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

🚀 Future: NFA in Modern Computing

🎯 Where NFAs Are Going

NFAs remain fundamental as a design tool, while their implementations evolve with hardware acceleration, parallelism, and integration with machine learning.

Future Directions

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

⚡ Hardware🔀 SIMD🎮 GPU🌊 Streaming

# Future of NFA in modern computing
print("=== Future Directions ===")
print("""
1. HARDWARE ACCELERATION
   - FPGA-based NFA
   - ASIC for regex
   - Network processors
   - 100+ Gbps throughput

2. SIMD PARALLELISM
   - Bit-parallel NFA simulation
   - 64 states in parallel (64-bit word)
   - AVX-512: 512 bits parallel
   - Intel Hyperscan

3. GPU ACCELERATION
   - Massively parallel NFA
   - Thousands of patterns
   - Thousands of strings
   - NVIDIA, AMD

4. STREAMING AND ONLINE
   - NFA on infinite streams
   - Sliding window matching
   - Real-time monitoring
   - IoT and edge computing

5. QUANTUM AUTOMATA
   - Quantum NFA
   - Superposition of states
   - Potentially more compact
   - Still theoretical

6. NEURAL AUTOMATA
   - Differentiable NFA
   - Learned state transitions
   - Hybrid models
   - Program synthesis
""")

# 1. BIT-PARALLEL NFA SIMULATION
print("\n=== Bit-Parallel NFA Simulation ===")
print("""
Idea: Represent set of NFA states as a bit vector.

For NFA with ≤ 64 states:
  - State set = 64-bit integer
  - Transition = bitwise operations
  - Very fast

Algorithm:
  current = 1 << q0  (start state)
  for each symbol:
    next = 0
    for each state in current:
      next |= transition[state][symbol]
    current = next

Optimization:
  - Precompute transition masks
  - Use bitwise OR
  - SIMD for multiple strings

Performance:
  - 64 states per operation
  - 10-100x faster than set-based
  - Used in production regex engines
""")

# 2. FPGA-BASED NFA
print("\n=== FPGA-Based NFA ===")
print("""
FPGA implementation:

Mapping:
  - NFA state → flip-flop
  - Transition → logic gate
  - Input → character stream

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

Example: Snort on FPGA
  - 100 Gbps throughput
  - Millions of rules
  - <1 μs latency

Vendors:
  - Intel (Altera)
  - AMD (Xilinx)
  - Lattice
  - Microchip
""")

# 3. GPU-ACCELERATED NFA
print("\n=== GPU-Accelerated NFA ===")
print("""
GPU for NFA simulation:

Challenge:
  - NFA is sequential (state set)
  - GPU is parallel

Solutions:
  1. Multiple strings in parallel
  2. Multiple patterns in parallel
  3. Bit-parallel + GPU

Libraries:
  - NVIDIA cuDF (regex)
  - RAPIDS
  - Custom CUDA

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

Performance:
  - 100+ GB/s aggregate
  - Millions of matches per second
""")

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

Properties:
  - Constant memory
  - O(1) per symbol
  - Infinite streams
  - Real-time matching

Applications:
  - Network traffic monitoring
  - IoT sensor data
  - Financial tickers
  - Social media feeds

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

Techniques:
  - Sliding window
  - Multiple patterns
  - Out-of-order handling
""")

# 5. QUANTUM FINITE AUTOMATA
print("\n=== Quantum Finite Automata ===")
print("""
Quantum NFA (QFA):

Types:
  1. Measure-Once QFA
  2. Measure-Many QFA
  3. Latvian QFA

Properties:
  - Superposition of states
  - Potentially fewer states
  - Some languages need exponentially fewer

Challenges:
  - Decoherence
  - Error correction
  - Small scale

Status:
  - Active research
  - Theoretical mostly
  - Future possibility
""")

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

Approaches:
  1. Neural Turing Machines
     - RNN + external memory
  2. Differentiable Automata
     - Soft DFA/NFA
     - End-to-end trainable
  3. Neural State Machines
     - Learned 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("""
NFA-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
print("\n=== Big Data and Analytics ===")
print("""
NFA for massive scale:

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

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

Performance:
  - 10+ TB/s aggregate
  - Linear scaling
  - Fault-tolerant

Libraries:
  - Apache Spark (regex)
  - Flink (CEP)
  - Kafka Streams
  - Beam
""")

# 9. DOMAIN-SPECIFIC LANGUAGES
print("\n=== Domain-Specific Languages ===")
print("""
NFAs for DSL implementation:

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

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

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

# 10. FUTURE OUTLOOK
print("\n=== Future Outlook ===")
print("""
NFA 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 NFA applications
  - Neural NFA hybrid models
  - Program synthesis with NFA
  - Hardware-software co-design

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

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

# 11. RECOMMENDATIONS
print("\n=== Recommendations ===")
print("""
For practitioners:
  1. Master NFA 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 NFA models
  3. Hardware implementations
  4. Verification techniques
  5. New applications

For students:
  1. Understand theory
  2. Implement NFA 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)
""")

# 12. FINAL THOUGHTS
print("\n=== Final Thoughts ===")
print("""
NFAs are the design tool of choice:

1930s-1950s: Theoretical foundations
  - Nondeterminism introduced
  - Finite automata theory

1960s-1980s: Practical applications
  - Thompson construction
  - Lexical analysis (Lex)
  - Pattern matching (grep)

1990s-2010s: High-performance
  - Hardware NFAs
  - Network security
  - Regex engines

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

Why NFAs matter:
  - Easier to design than DFA
  - Same expressive power
  - Foundation of regex
  - Ubiquitous in practice

You now understand:
  - Formal definition
  - Nondeterminism and ε-transitions
  - Subset construction
  - Thompson construction
  - Equivalence testing
  - Real-world applications
  - Future directions

"NFAs: where guessing is free
and power is equivalent."
  — Automata Theory

Go build efficient systems!
""")