DFA মিনিমাইজেশন

# রিডানড্যান্ট DFA: "অন্তত একটি 1 আছে" -- qB ও qC ইচ্ছাকৃতভাবে সমতুল্য কিন্তু আলাদা
states = {'q0', 'qB', 'qC', 'qF'}
alphabet = ['0', '1']
delta = {
    ('q0', '0'): 'qB', ('q0', '1'): 'qC',
    ('qB', '0'): 'qB', ('qB', '1'): 'qF',
    ('qC', '0'): 'qC', ('qC', '1'): 'qF',
    ('qF', '0'): 'qF', ('qF', '1'): 'qF',
}
start = 'q0'
accept = {'qF'}

def run_dfa(states, delta, start, accept, s):
    state = start
    for ch in s:
        state = delta[(state, ch)]
    return state in accept

def group_index(partition, state):
    for i, g in enumerate(partition):
        if state in g:
            return i
    raise ValueError("স্টেট কোনো গ্রুপে নেই")

def minimize_dfa(states, alphabet, delta, start, accept):
    non_accept = states - accept
    partition = [g for g in [set(accept), set(non_accept)] if g]
    changed = True
    while changed:
        changed = False
        new_partition = []
        for group in partition:
            buckets = {}
            for state in group:
                # প্রতিটি সিম্বলে এই স্টেট কোন গ্রুপে যায় তার "স্বাক্ষর"
                sig = tuple(group_index(partition, delta[(state, sym)]) for sym in alphabet)
                buckets.setdefault(sig, set()).add(state)
            if len(buckets) > 1:
                changed = True
            new_partition.extend(buckets.values())
        partition = new_partition

    # প্রতিটি গ্রুপকে একটি নতুন মিনিমাইজড স্টেট নাম দাও
    group_name = {i: "G" + str(i) + "_" + "_".join(sorted(g)) for i, g in enumerate(partition)}
    rep = {s: group_name[i] for i, g in enumerate(partition) for s in g}
    new_states = set(group_name.values())
    new_delta = {}
    for i, g in enumerate(partition):
        any_state = next(iter(g))
        for sym in alphabet:
            new_delta[(group_name[i], sym)] = rep[delta[(any_state, sym)]]
    new_start = rep[start]
    new_accept = {group_name[i] for i, g in enumerate(partition) if g & accept}
    return new_states, new_delta, new_start, new_accept, partition

print(f"মূল DFA-র স্টেট সংখ্যা: {len(states)}")
new_states, new_delta, new_start, new_accept, partition = minimize_dfa(states, alphabet, delta, start, accept)
print(f"মিনিমাইজড DFA-র স্টেট সংখ্যা: {len(new_states)}")
print("চূড়ান্ত গ্রুপ:")
for g in partition:
    print(f"  {sorted(g)}")

test_strings = ["", "0", "1", "00", "01", "10", "11", "000", "010", "101", "0101", "0000"]
all_match = True
print("\nমূল বনাম মিনিমাইজড DFA -- সব টেস্ট স্ট্রিং:")
for s in test_strings:
    orig = run_dfa(states, delta, start, accept, s)
    minim = run_dfa(new_states, new_delta, new_start, new_accept, s)
    ok = orig == minim
    all_match = all_match and ok
    print(f"  {s!r:8s} মূল={orig!s:5s} মিনিমাইজড={minim!s:5s} {'ঠিক আছে' if ok else 'গরমিল!'}")
print(f"\nসব ফলাফল হুবহু মিলেছে: {all_match}")