NFA & Regular Expressions

NFA (Nondeterministic Finite Automaton) — same as DFA but with two key differences:
① For a given (state, symbol), there can be ZERO, ONE, or MANY possible next states
② Epsilon (ε) transitions: the NFA can change state without reading any input

An NFA accepts a string if there EXISTS at least one path through the transitions that leads to an accept state. It's like the machine "guesses" the right path.

NFAs vs DFAs — power and equivalence:
- NFAs are NOT more powerful than DFAs in terms of what languages they recognize
- Every NFA can be converted to an equivalent DFA (subset construction algorithm)
- But NFAs can be EXPONENTIALLY more concise — an NFA with n states may need a DFA with 2ⁿ states
- NFAs are easier to BUILD (especially from regex), DFAs are easier to RUN (deterministic)

Subset Construction (NFA → DFA):
- Each DFA state = a SET of NFA states (the set of states the NFA could possibly be in)
- Start DFA state = ε-closure(q0) (all states reachable from start via ε transitions)
- DFA has at most 2^|Q_NFA| states

ε-closure: the set of all states reachable from a given state via ε transitions alone (including the state itself).

Regular Expressions → NFA (Thompson's Construction):
Every regex can be mechanically converted to an NFA:
- Single symbol a: two states, one transition
- Concatenation r·s: connect NFA(r) end to NFA(s) start via ε
- Union r|s: new start with ε to both NFA(r) and NFA(s) starts, both ends ε to new accept
- Kleene star r*: new start/accept, ε loop back, ε to skip
Then convert NFA → DFA (subset construction) → minimize DFA.
This is EXACTLY what Python's re module does when you compile a regex!

Regular Expression operators:
- a — literal character a
- . — any single character
- * — zero or more (Kleene star)
- + — one or more (= rr*)
- ? — zero or one
- | — alternation (union)
- [] — character class
- ^ — start anchor / negation in class
- $ — end anchor
- () — grouping

Languages defined by regex = Regular Languages. They are EXACTLY the class of languages DFAs/NFAs recognize. This is the Kleene theorem.

1import re
2from collections import defaultdict
3
4# ── NFA implementation ─────────────────────────────────
5class NFA:
6    def __init__(self, states, alphabet, transitions, start, accept):
7        """
8        transitions: dict {(state, symbol_or_eps): set_of_next_states}
9        Use None for epsilon transitions
10        """
11        self.states      = states
12        self.alphabet    = alphabet
13        self.transitions = transitions
14        self.start       = start
15        self.accept      = accept
16
17    def epsilon_closure(self, states):
18        """All states reachable via epsilon transitions"""
19        closure = set(states)
20        stack   = list(states)
21        while stack:
22            state = stack.pop()
23            for next_s in self.transitions.get((state, None), set()):
24                if next_s not in closure:
25                    closure.add(next_s)
26                    stack.append(next_s)
27        return frozenset(closure)
28
29    def move(self, states, symbol):
30        """All states reachable from 'states' on 'symbol'"""
31        result = set()
32        for state in states:
33            result |= self.transitions.get((state, symbol), set())
34        return result
35
36    def accepts(self, string):
37        current = self.epsilon_closure({self.start})
38        for symbol in string:
39            current = self.epsilon_closure(self.move(current, symbol))
40        return bool(current & self.accept)
41
42    def to_dfa_states(self):
43        """Subset construction — returns DFA transition table"""
44        start_set = self.epsilon_closure({self.start})
45        dfa_trans = {}
46        visited   = set()
47        queue     = [start_set]
48
49        while queue:
50            current = queue.pop(0)
51            if current in visited:
52                continue
53            visited.add(current)
54            for symbol in self.alphabet:
55                next_set = self.epsilon_closure(self.move(current, symbol))
56                dfa_trans[(current, symbol)] = next_set
57                if next_set not in visited:
58                    queue.append(next_set)
59
60        return dfa_trans, start_set, {s for s in visited if s & self.accept}
61
62
63# ── NFA for strings ending in "ab" ────────────────────
64nfa = NFA(
65    states     = {0, 1, 2},
66    alphabet   = {"a", "b"},
67    transitions = {
68        (0,"a"): {0, 1},   # nondeterminism: stay OR go to q1
69        (0,"b"): {0},
70        (1,"b"): {2},
71    },
72    start  = 0,
73    accept = {2},
74)
75
76print("NFA: strings ending in 'ab'")
77tests = ["ab", "aab", "bab", "aba", "b", "abab", "cab"]
78for s in tests:
79    r = nfa.accepts(s)
80    expected = s.endswith("ab")
81    check = "✓" if r == expected else "BUG"
82    print(f"  '{s}' → {'ACCEPT' if r else 'REJECT'} {check}")
83
84# ── Regular Expressions in Python ─────────────────────
85print("
86Regex = Regular Language in action:")
87
88patterns = [
89    (r"^[a-zA-Z_][a-zA-Z0-9_]*$",  "Valid Python identifier"),
90    (r"^d{1,3}(.d{1,3}){3}$",   "IPv4 address"),
91    (r"^[^@]+@[^@]+.[^@]+$",      "Email (simplified)"),
92    (r"^(0|[1-9][0-9]*)$",         "Non-negative integer"),
93    (r"^#[0-9a-fA-F]{6}$",         "Hex color code"),
94]
95
96test_strings = [
97    "my_var", "123abc", "192.168.1.1", "999.999.999.999",
98    "k@nii.ac.in", "notanemail", "42", "007", "#FF5733", "#GGGGGG"
99]
100
101for pattern, desc in patterns:
102    print(f"
103  Pattern: {desc}")
104    compiled = re.compile(pattern)
105    for s in test_strings:
106        if compiled.match(s):
107            print(f"    '{s}' ✓")
108
109# ── Regex internals: compiled to NFA then DFA ─────────
110import re
111p = re.compile(r"(a|b)*ab")
112print(f"
113re.compile('(a|b)*ab'):")
114print(f"  pattern: {p.pattern}")
115print(f"  flags:   {p.flags}")
116print(f"  groups:  {p.groups}")
117# Python's re module uses a backtracking NFA simulation
118# re2 (used by Google) converts to DFA for guaranteed O(n)