DFA মিনিমাইজেশন ও ডিসিশন প্রপার্টি

from collections import deque

class DFA:
    def __init__(self, states, alphabet, transitions, start, accept_states):
        self.states = set(states)
        self.alphabet = set(alphabet)
        self.transitions = transitions
        self.start = start
        self.accept_states = set(accept_states)
        for q in self.states:
            for a in self.alphabet:
                assert (q, a) in self.transitions

    def run(self, s):
        state = self.start
        for ch in s:
            state = self.transitions[(state, ch)]
        return state

    def accepts(self, s):
        return self.run(s) in self.accept_states


def is_empty(dfa):
    # L(dfa) খালি <=> start থেকে BFS-এ কোনো accept state-এ পৌঁছানো যায় না (../dsa/-স্টাইল গ্রাফ রিচেবিলিটি)
    visited = {dfa.start}
    queue = deque([dfa.start])
    while queue:
        q = queue.popleft()
        if q in dfa.accept_states:
            return False
        for a in dfa.alphabet:
            nxt = dfa.transitions[(q, a)]
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)
    return True


def symmetric_difference_dfa(dfa1, dfa2):
    # L12-এর প্রোডাক্ট-কনস্ট্রাকশন স্টাইল -- accept হয় ঠিক তখনই যখন দুই DFA-এর সিদ্ধান্ত ভিন্ন (XOR)
    assert dfa1.alphabet == dfa2.alphabet
    states = [(q1, q2) for q1 in dfa1.states for q2 in dfa2.states]
    transitions = {}
    for (q1, q2) in states:
        for a in dfa1.alphabet:
            transitions[((q1, q2), a)] = (dfa1.transitions[(q1, a)], dfa2.transitions[(q2, a)])
    start = (dfa1.start, dfa2.start)
    accept_states = [(q1, q2) for (q1, q2) in states
                      if (q1 in dfa1.accept_states) != (q2 in dfa2.accept_states)]
    return DFA(states, dfa1.alphabet, transitions, start, accept_states)


def are_equivalent(dfa1, dfa2):
    # L(dfa1) == L(dfa2) <=> তাদের সিমেট্রিক ডিফারেন্স খালি
    return is_empty(symmetric_difference_dfa(dfa1, dfa2))


# --- is_empty টেস্ট ---
reachable_accept = DFA(
    states={"s0", "s1"}, alphabet={"0", "1"},
    transitions={("s0","0"):"s1", ("s0","1"):"s1", ("s1","0"):"s1", ("s1","1"):"s1"},
    start="s0", accept_states={"s1"},
)
print("স্বাভাবিক DFA (accept state reachable) is_empty:", is_empty(reachable_accept), " (প্রত্যাশিত False)")

unreachable_accept = DFA(
    states={"s0", "s1", "dead"}, alphabet={"0", "1"},
    transitions={("s0","0"):"s0", ("s0","1"):"s0", ("s1","0"):"s1", ("s1","1"):"s1",
                 ("dead","0"):"dead", ("dead","1"):"dead"},
    start="s0", accept_states={"dead"},   # s0 চিরকাল সেল্ফ-লুপ করে, dead/s1 কখনো পৌঁছানো যায় না
)
print("ইচ্ছাকৃতভাবে-অপ্রাপ্য-accept DFA is_empty:", is_empty(unreachable_accept), " (প্রত্যাশিত True)")

# --- are_equivalent টেস্ট ---
minimal_even_ones = DFA(
    states=["q0", "q1"], alphabet={"0", "1"},
    transitions={("q0","0"):"q0", ("q0","1"):"q1", ("q1","0"):"q1", ("q1","1"):"q0"},
    start="q0", accept_states={"q0"},
)

def flip(x):
    return "B" if x == "A" else "A"

# একই ভাষার একটি রিডানডেন্ট ৪-স্টেট DFA -- একটি অপ্রয়োজনীয় "extra" বিট ট্র্যাক করে যা accept-এ প্রভাব ফেলে না
redundant_states = [(p, e) for p in (0, 1) for e in ("A", "B")]
redundant_trans = {}
for (p, e) in redundant_states:
    for c in ("0", "1"):
        redundant_trans[((p, e), c)] = (p ^ (1 if c == "1" else 0), flip(e))
redundant_even_ones = DFA(
    states=redundant_states, alphabet={"0", "1"}, transitions=redundant_trans,
    start=(0, "A"), accept_states=[(0, "A"), (0, "B")],
)

odd_ones = DFA(
    states=["r0", "r1"], alphabet={"0", "1"},
    transitions={("r0","0"):"r0", ("r0","1"):"r1", ("r1","0"):"r1", ("r1","1"):"r0"},
    start="r0", accept_states={"r1"},
)

# প্রথমে সরাসরি নিশ্চিত করা -- রিডানডেন্ট DFA সত্যিই একই ভাষা recognize করে কি না
test_strings = ["", "0", "1", "00", "01", "10", "11", "000", "111", "0101010", "110011"]
for s in test_strings:
    assert minimal_even_ones.accepts(s) == redundant_even_ones.accepts(s)
print()
print("রিডানডেন্ট ৪-স্টেট DFA সব টেস্ট স্ট্রিং-এ মিনিমাল ২-স্টেট DFA-র সাথে একমত: OK")

print("minimal(2-state) vs redundant(4-state), একই ভাষা, are_equivalent:",
      are_equivalent(minimal_even_ones, redundant_even_ones), " (প্রত্যাশিত True)")
print("minimal(even-1s) vs odd-1s DFA, ভিন্ন ভাষা, are_equivalent:",
      are_equivalent(minimal_even_ones, odd_ones), " (প্রত্যাশিত False)")