ফাইনাইট অটোমাটা — NFA থেকে DFA

# a*b -এর NFA (Thompson's construction অনুসরণ করে হাতে বানানো)
# ট্রানজিশন: (from, symbol_or_None, to) -- None মানে epsilon
NFA = {
    'states': {0, 1, 2, 3, 4, 5},
    'alphabet': {'a', 'b'},
    'transitions': [
        (0, None, 1), (0, None, 3),   # শূন্যবার 'a' নেওয়ার সুযোগ
        (1, 'a', 2),                  # একটি 'a' পড়া
        (2, None, 1), (2, None, 3),   # লুপে ফিরে যাওয়া বা বের হওয়া
        (3, None, 4),                 # 'b' অংশে প্রবেশ
        (4, 'b', 5),                  # চূড়ান্ত 'b'
    ],
    'start': 0,
    'accept': {5},
}

def epsilon_closure(nfa, states):
    stack = list(states)
    closure = set(states)
    while stack:
        s = stack.pop()
        for (frm, sym, to) in nfa['transitions']:
            if frm == s and sym is None and to not in closure:
                closure.add(to)
                stack.append(to)
    return frozenset(closure)

def move(nfa, states, symbol):
    return {to for (frm, sym, to) in nfa['transitions'] if frm in states and sym == symbol}

def subset_construction(nfa):
    alphabet = sorted(nfa['alphabet'])
    start_set = epsilon_closure(nfa, {nfa['start']})
    dfa_states = {start_set}
    unmarked = [start_set]
    dfa_transitions = {}
    while unmarked:
        current = unmarked.pop()
        for symbol in alphabet:
            target = epsilon_closure(nfa, move(nfa, current, symbol))
            dfa_transitions[(current, symbol)] = target
            if target not in dfa_states:
                dfa_states.add(target)
                unmarked.append(target)
    dfa_accept = {s for s in dfa_states if s & nfa['accept']}
    return {'states': dfa_states, 'alphabet': alphabet, 'transitions': dfa_transitions,
            'start': start_set, 'accept': dfa_accept}

DFA = subset_construction(NFA)
print(f"subset construction থেকে পাওয়া DFA স্টেট সংখ্যা: {len(DFA['states'])}")
for st in sorted(DFA['states'], key=lambda s: sorted(s)):
    tag = "ACCEPT" if st in DFA['accept'] else ""
    print(f"  DFA স্টেট {sorted(st)} {tag}")

def run_dfa(dfa, s):
    state = dfa['start']
    for ch in s:
        state = dfa['transitions'].get((state, ch), frozenset())
    return state in dfa['accept']

print("\naccept হওয়া উচিত:")
for s in ["b", "ab", "aab", "aaab"]:
    print(f"  run_dfa({s!r}) = {'accept' if run_dfa(DFA, s) else 'reject'}")

print("\nreject হওয়া উচিত:")
for s in ["a", "ba", ""]:
    label = "(empty string)" if s == "" else ""
    print(f"  run_dfa({s!r}) = {'accept' if run_dfa(DFA, s) else 'reject'} {label}")