মাইহিল-নেরোড থিওরেম

def even_ones_language(s):
    return s.count('1') % 2 == 0   # L06-এর "even number of 1s" ভাষা


def are_equivalent(x, y, in_L, test_suffixes):
    # প্রতিনিধিত্বশীল suffix-সেট দিয়ে x =_L y পরীক্ষা -- একটি distinguishing suffix পেলেই non-equivalent
    for z in test_suffixes:
        if in_L(x + z) != in_L(y + z):
            return False, z
    return True, None


def count_equivalence_classes(in_L, test_strings, test_suffixes):
    classes = []   # প্রতিটি এন্ট্রি একটি ইকুইভ্যালেন্স ক্লাসের স্ট্রিং-লিস্ট
    for s in test_strings:
        placed = False
        for cls in classes:
            equiv, _ = are_equivalent(s, cls[0], in_L, test_suffixes)
            if equiv:
                cls.append(s)
                placed = True
                break
        if not placed:
            classes.append([s])
    return classes


test_suffixes = ["", "0", "1", "00", "01", "10", "11", "010", "101", "111"]

eq1, w1 = are_equivalent("0", "00", even_ones_language, test_suffixes)
print(f"'0' equiv_L '00' ? {eq1}  (উভয়েরই 1-সংখ্যা even, তাই যেকোনো suffix উভয়কেই একইভাবে প্রভাবিত করে)")

eq2, w2 = are_equivalent("0", "1", even_ones_language, test_suffixes)
print(f"'0' equiv_L '1' ? {eq2}  distinguishing suffix z={w2!r}")
print(f"    L('0'+z) = {even_ones_language('0'+w2)},  L('1'+z) = {even_ones_language('1'+w2)}")

test_strings = ["", "0", "1", "00", "01", "10", "11", "000", "001", "010", "011",
                 "100", "101", "110", "111", "0000", "1111", "0101010"]

classes = count_equivalence_classes(even_ones_language, test_strings, test_suffixes)
print()
print(f"{len(test_strings)}টি টেস্ট স্ট্রিং, {len(classes)}টি ইকুইভ্যালেন্স ক্লাসে ভাগ হলো:")
for i, cls in enumerate(classes):
    print(f"  ক্লাস {i}: {cls}")

known_minimal_dfa_size = 2   # L06-এর "even number of 1s" DFA-র পরিচিত, ন্যূনতম স্টেট সংখ্যা
print()
print(f"পরিচিত মিনিমাল DFA-র স্টেট সংখ্যা: {known_minimal_dfa_size}")
print(f"গণনা করা ক্লাস-সংখ্যা মিলছে কি না: {len(classes) == known_minimal_dfa_size}")