NFA থেকে DFA ইকুইভ্যালেন্স — সাবসেট কনস্ট্রাকশন

from collections import deque
from itertools import product


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)


class DFA:
    def __init__(self, states, alphabet, transition, start, accept_states):
        self.states = states
        self.alphabet = alphabet
        self.transition = transition   # dict: (state, symbol) -> state
        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)


states = {"q0", "q1", "q2"}
alphabet = {"0", "1"}
transition = {
    ("q0", "0"): {"q0", "q1"},
    ("q0", "1"): {"q0"},
    ("q1", "0"): {"q1"},
    ("q1", "1"): {"q2"},
    ("q2", "0"): {"q2"},
    ("q2", "1"): {"q2"},
}
nfa = NFA(states, alphabet, transition, "q0", {"q2"})
dfa = subset_construction(nfa)

print(f"NFA states: {len(nfa.states)} | subset-construction DFA states: {len(dfa.states)}")

mismatches = 0
total = 0
for length in range(0, 7):
    for combo in product("01", repeat=length):
        s = "".join(combo)
        total += 1
        n_res = nfa.accepts(s)
        d_res = dfa.accepts(s)
        if n_res != d_res:
            mismatches += 1
            print("MISMATCH on", repr(s), n_res, d_res)

print(f"মোট টেস্ট স্ট্রিং: {total}, mismatch: {mismatches}")
assert mismatches == 0
print("সব স্ট্রিং-এ NFA ও DFA-এর ফলাফল অভিন্ন -- subset construction সঠিকভাবে কাজ করছে।")