এপসিলন-NFA ও এপসিলন-ক্লোজার

from itertools import product

EPSILON = None  # sentinel representing an epsilon-transition


class EpsilonNFA:
    def __init__(self, states, alphabet, transition, start, accept_states):
        self.states = states
        self.alphabet = alphabet
        self.transition = transition   # dict: (state, symbol_or_EPSILON) -> set(states)
        self.start = start
        self.accept_states = accept_states

    def accepts(self, string):
        current = epsilon_closure(self, self.start)
        for ch in string:
            raw = set()
            for q in current:
                raw |= self.transition.get((q, ch), set())
            nxt = set()
            for s in raw:
                nxt |= epsilon_closure(self, s)
            current = nxt
            if not current:
                break
        return bool(current & self.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)


# sub-machine A: accepts exactly "a"  (s0 --a--> s1)
# sub-machine B: accepts exactly "b"  (t0 --b--> t1)
# joined at a new start q0 via epsilon-transitions to s0 and t0
states = {"q0", "s0", "s1", "t0", "t1"}
alphabet = {"a", "b"}
transition = {
    ("q0", EPSILON): {"s0", "t0"},
    ("s0", "a"): {"s1"},
    ("t0", "b"): {"t1"},
}
enfa = EpsilonNFA(states, alphabet, transition, "q0", {"s1", "t1"})

# hand-verify epsilon-closures
print("ECLOSE(q0) =", sorted(epsilon_closure(enfa, "q0")))
print("ECLOSE(s0) =", sorted(epsilon_closure(enfa, "s0")))
print("ECLOSE(s1) =", sorted(epsilon_closure(enfa, "s1")))
assert epsilon_closure(enfa, "q0") == frozenset({"q0", "s0", "t0"})
assert epsilon_closure(enfa, "s0") == frozenset({"s0"})

plain_nfa = remove_epsilon_transitions(enfa)
print("plain NFA transitions:")
for k, v in sorted(plain_nfa.transition.items(), key=lambda kv: (kv[0][0], kv[0][1] or "")):
    print(" ", k, "->", sorted(v))
print("plain NFA accept states:", sorted(plain_nfa.accept_states))

mismatches = 0
total = 0
for length in range(0, 4):
    for combo in product("ab", repeat=length):
        s = "".join(combo)
        total += 1
        r1 = enfa.accepts(s)
        r2 = plain_nfa.accepts(s)
        expected = s in ("a", "b")
        if not (r1 == r2 == expected):
            mismatches += 1
            print("MISMATCH", repr(s), r1, r2, expected)

print(f"total={total} mismatches={mismatches}")
assert mismatches == 0
print("epsilon-NFA ও epsilon-transition-remove করা NFA উভয়ই অভিন্ন ফলাফল দেয়।")