টুরিং মেশিন রিকগনাইজার ও ডিসাইডার হিসেবে

import itertools

ALPHABET = ['0', '1']

class DFA:
    def __init__(self, states, alphabet, trans, start, accept):
        self.states, self.alphabet = states, alphabet
        self.trans, self.start, self.accept = trans, start, accept

    def accepts(self, s):
        state = self.start
        for ch in s:
            state = self.trans[(state, ch)]
        return state in self.accept

def dfa_contains_11():           # L(A) = "1" এর পরপর দুটি আছে
    trans = {('q0','0'):'q0', ('q0','1'):'q1',
             ('q1','0'):'q0', ('q1','1'):'q2',
             ('q2','0'):'q2', ('q2','1'):'q2'}
    return DFA({'q0','q1','q2'}, ALPHABET, trans, 'q0', {'q2'})

def dfa_even_length():           # L(B) = জোড় দৈর্ঘ্যের স্ট্রিং
    trans = {('e','0'):'o', ('e','1'):'o', ('o','0'):'e', ('o','1'):'e'}
    return DFA({'e','o'}, ALPHABET, trans, 'e', {'e'})

# --- রিকগনাইজার-স্টাইল: bounded search, হ্যাঁ পেলে সাথে সাথে হল্ট করে ---
def recognizer_for_nonempty_intersection(dfa_a, dfa_b, max_length=6):
    checked = 0
    for length in range(max_length + 1):
        for bits in itertools.product(ALPHABET, repeat=length):
            checked += 1
            s = ''.join(bits)
            if dfa_a.accepts(s) and dfa_b.accepts(s):
                return True, s, checked          # witness পেয়ে গেলে সাথে সাথে accept/halt
    return None, None, checked                  # সত্যিকারের মডেলে: চিরকাল খুঁজতেই থাকত

# --- ডিসাইডার-স্টাইল (M3/L12-এর product construction পুনর্ব্যবহার): সবসময় হল্ট করে ---
def product_dfa_intersection(dfa_a, dfa_b):
    states = {(p, q) for p in dfa_a.states for q in dfa_b.states}
    trans = {}
    for p in dfa_a.states:
        for q in dfa_b.states:
            for a in ALPHABET:
                trans[((p, q), a)] = (dfa_a.trans[(p, a)], dfa_b.trans[(q, a)])
    accept = {(p, q) for p in dfa_a.accept for q in dfa_b.accept}
    return DFA(states, ALPHABET, trans, (dfa_a.start, dfa_b.start), accept)

def is_empty(dfa):                       # BFS reachability -- সবসময় হল্ট করে
    seen, frontier, visited = {dfa.start}, [dfa.start], 0
    while frontier:
        state = frontier.pop()
        visited += 1
        if state in dfa.accept:
            return False, visited
        for a in dfa.alphabet:
            nxt = dfa.trans[(state, a)]
            if nxt not in seen:
                seen.add(nxt); frontier.append(nxt)
    return True, visited

A, Bd = dfa_contains_11(), dfa_even_length()

found, witness, checked = recognizer_for_nonempty_intersection(A, Bd)
print("রিকগনাইজার:", found, "witness =", repr(witness), "| checked", checked, "স্ট্রিং")

prod = product_dfa_intersection(A, Bd)
empty, visited = is_empty(prod)
print("ডিসাইডার is_empty:", empty, "| visited", visited, "states -- সবসময় হল্ট করে")

assert found is True and A.accepts(witness) and Bd.accepts(witness)
assert empty is False   # nonempty, রিকগনাইজারের ফলাফলের সাথে সামঞ্জস্যপূর্ণ