ক্লিনির থিওরেম — রেগেক্স ও ফাইনাইট অটোমাটার ইকুইভ্যালেন্স

from collections import deque
from itertools import product

EPSILON = None


# ---------- L09-style epsilon-NFA machinery ----------
class EpsilonNFA:
    def __init__(self, states, alphabet, transition, start, accept_states):
        self.states = states
        self.alphabet = alphabet
        self.transition = transition
        self.start = start
        self.accept_states = accept_states


def epsilon_closure(enfa, state):
    closure = {state}
    frontier = [state]
    while frontier:
        q = frontier.pop()
        for nxt in enfa.transition.get((q, EPSILON), set()):
            if nxt not in closure:
                closure.add(nxt)
                frontier.append(nxt)
    return frozenset(closure)


class NFA:
    def __init__(self, states, alphabet, transition, start, accept_states):
        self.states = states
        self.alphabet = alphabet
        self.transition = transition
        self.start = start
        self.accept_states = accept_states

    def accepts(self, string):
        current = {self.start}
        for ch in string:
            nxt = set()
            for q in current:
                nxt |= self.transition.get((q, ch), set())
            current = nxt
            if not current:
                break
        return bool(current & self.accept_states)


def remove_epsilon_transitions(enfa):
    new_transition = {}
    for q in enfa.states:
        closure_q = epsilon_closure(enfa, q)
        for a in enfa.alphabet:
            raw = set()
            for p in closure_q:
                raw |= enfa.transition.get((p, a), set())
            dest = set()
            for r in raw:
                dest |= epsilon_closure(enfa, r)
            if dest:
                new_transition[(q, a)] = dest
    new_accept = {q for q in enfa.states if epsilon_closure(enfa, q) & enfa.accept_states}
    return NFA(enfa.states, enfa.alphabet, new_transition, enfa.start, new_accept)


# ---------- L08-style subset construction ----------
class DFA:
    def __init__(self, states, alphabet, transition, start, accept_states):
        self.states = states
        self.alphabet = alphabet
        self.transition = transition
        self.start = start
        self.accept_states = accept_states

    def accepts(self, string):
        state = self.start
        for ch in string:
            state = self.transition[(state, ch)]
        return state in self.accept_states


def subset_construction(nfa):
    start_set = frozenset({nfa.start})
    dfa_states = {start_set}
    dfa_transition = {}
    queue = deque([start_set])
    while queue:
        current = queue.popleft()
        for a in nfa.alphabet:
            nxt = frozenset().union(*(nfa.transition.get((q, a), set()) for q in current)) if current else frozenset()
            dfa_transition[(current, a)] = nxt
            if nxt not in dfa_states:
                dfa_states.add(nxt)
                queue.append(nxt)
    accept_states = {S for S in dfa_states if S & nfa.accept_states}
    return DFA(dfa_states, nfa.alphabet, dfa_transition, start_set, accept_states)


# ---------- L10-style set-based regex language generator ----------
def language_of(node, max_length):
    kind = node[0]
    if kind == "empty":
        return set()
    if kind == "eps":
        return {""}
    if kind == "sym":
        a = node[1]
        return {a} if len(a) <= max_length else set()
    if kind == "union":
        _, R, S = node
        return language_of(R, max_length) | language_of(S, max_length)
    if kind == "concat":
        _, R, S = node
        LR = language_of(R, max_length)
        LS = language_of(S, max_length)
        return {x + y for x in LR for y in LS if len(x) + len(y) <= max_length}
    if kind == "star":
        _, R = node
        LR = {w for w in language_of(R, max_length) if w != ""}
        result = {""}
        frontier = {""}
        while frontier:
            new = set()
            for s in frontier:
                for r in LR:
                    cand = s + r
                    if len(cand) <= max_length and cand not in result:
                        new.add(cand)
            result |= new
            frontier = new
        return result
    raise ValueError(node)


# ---------- L11: regex -> epsilon-NFA, recursively, following regex structure (Thompson construction) ----------
def merge_transitions(a, b):
    result = {}
    for d in (a, b):
        for k, v in d.items():
            result.setdefault(k, set()).update(v)
    return result


def regex_to_fragment(node, counter):
    kind = node[0]

    def fresh():
        counter[0] += 1
        return f"n{counter[0]}"

    if kind == "empty":
        q = fresh()
        return {"states": {q}, "transition": {}, "start": q, "accept": set()}

    if kind == "eps":
        q = fresh()
        return {"states": {q}, "transition": {}, "start": q, "accept": {q}}

    if kind == "sym":
        a = node[1]
        s, t = fresh(), fresh()
        return {"states": {s, t}, "transition": {(s, a): {t}}, "start": s, "accept": {t}}

    if kind == "union":
        _, R, S = node
        r = regex_to_fragment(R, counter)
        s = regex_to_fragment(S, counter)
        q0 = fresh()
        transition = merge_transitions(r["transition"], s["transition"])
        transition.setdefault((q0, EPSILON), set()).update({r["start"], s["start"]})
        return {
            "states": r["states"] | s["states"] | {q0},
            "transition": transition,
            "start": q0,
            "accept": r["accept"] | s["accept"],
        }

    if kind == "concat":
        _, R, S = node
        r = regex_to_fragment(R, counter)
        s = regex_to_fragment(S, counter)
        transition = merge_transitions(r["transition"], s["transition"])
        for acc in r["accept"]:
            transition.setdefault((acc, EPSILON), set()).add(s["start"])
        return {
            "states": r["states"] | s["states"],
            "transition": transition,
            "start": r["start"],
            "accept": s["accept"],
        }

    if kind == "star":
        _, R = node
        r = regex_to_fragment(R, counter)
        q0, qf = fresh(), fresh()
        transition = {k: set(v) for k, v in r["transition"].items()}
        transition.setdefault((q0, EPSILON), set()).update({r["start"], qf})
        for acc in r["accept"]:
            transition.setdefault((acc, EPSILON), set()).update({r["start"], qf})
        return {
            "states": r["states"] | {q0, qf},
            "transition": transition,
            "start": q0,
            "accept": {qf},
        }

    raise ValueError(f"unknown regex node: {node}")


def regex_to_nfa(regex_ast, alphabet):
    counter = [0]
    frag = regex_to_fragment(regex_ast, counter)
    return EpsilonNFA(frag["states"], alphabet, frag["transition"], frag["start"], frag["accept"])


# ---------- run it on (a U b)* a ----------
regex = ("concat",
         ("star", ("union", ("sym", "a"), ("sym", "b"))),
         ("sym", "a"))
alphabet = {"a", "b"}

enfa = regex_to_nfa(regex, alphabet)
print(f"regex_to_nfa: {len(enfa.states)} states (Thompson construction)")

plain_nfa = remove_epsilon_transitions(enfa)
dfa = subset_construction(plain_nfa)
print(f"epsilon-transition বাদ দেওয়ার পর NFA states: {len(plain_nfa.states)}, subset-construction DFA states: {len(dfa.states)}")

MAX_LEN = 5
lang = language_of(regex, MAX_LEN)

mismatches = 0
total = 0
for length in range(0, MAX_LEN + 1):
    for combo in product("ab", repeat=length):
        s = "".join(combo)
        total += 1
        expected = s in lang
        got = dfa.accepts(s)
        if expected != got:
            mismatches += 1
            print("MISMATCH", repr(s), "expected", expected, "got", got)

print(f"total={total} mismatches={mismatches}")
assert mismatches == 0
print("regex_to_nfa -> subset_construction দিয়ে বানানো DFA, এবং L10-এর সেট-বেসড language_of -- length<=5 পর্যন্ত সব স্ট্রিং-এ হুবহু মিলেছে -- Kleene's theorem-এর একটি concrete, code-verified confirmation।")