রিডাকশন ও আনডিসাইডেবিলিটি প্রুফ

BLANK = '_'

class TuringMachine:
    """L32/L37-এর ধাঁচের একটি জেনেরিক TM।"""
    def __init__(self, transitions, start, accept, reject, blank=BLANK):
        self.transitions = transitions
        self.start, self.accept, self.reject, self.blank = start, accept, reject, blank

    def run(self, input_string, max_steps=3000):
        tape = {i: c for i, c in enumerate(input_string)}
        head, state, steps = 0, self.start, 0
        while state != self.accept and state != self.reject and steps < max_steps:
            symbol = tape.get(head, self.blank)
            key = (state, symbol)
            if key not in self.transitions:
                return 'reject', steps
            new_state, write_symbol, direction = self.transitions[key]
            tape[head] = write_symbol
            head += 1 if direction == 'R' else -1
            state = new_state
            steps += 1
        if state == self.accept:
            return 'accept', steps
        elif state == self.reject:
            return 'reject', steps
        else:
            return 'timeout', steps


# L37-এর M -- L = {0^n 1^n : n >= 0}
zn_transitions = {
    ('q_find0', 'X'): ('q_find0', 'X', 'R'), ('q_find0', 'Y'): ('q_find0', 'Y', 'R'),
    ('q_find0', '0'): ('q_goright', 'X', 'R'), ('q_find0', '1'): ('q_reject', '1', 'R'),
    ('q_find0', BLANK): ('q_accept', BLANK, 'R'),
    ('q_goright', '0'): ('q_goright', '0', 'R'), ('q_goright', '1'): ('q_goright', '1', 'R'),
    ('q_goright', 'X'): ('q_goright', 'X', 'R'), ('q_goright', 'Y'): ('q_goright', 'Y', 'R'),
    ('q_goright', BLANK): ('q_findlast', BLANK, 'L'),
    ('q_findlast', 'X'): ('q_findlast', 'X', 'L'), ('q_findlast', 'Y'): ('q_findlast', 'Y', 'L'),
    ('q_findlast', '1'): ('q_gohome', 'Y', 'L'), ('q_findlast', '0'): ('q_reject', '0', 'L'),
    ('q_findlast', BLANK): ('q_reject', BLANK, 'L'),
    ('q_gohome', '0'): ('q_gohome', '0', 'L'), ('q_gohome', '1'): ('q_gohome', '1', 'L'),
    ('q_gohome', 'X'): ('q_gohome', 'X', 'L'), ('q_gohome', 'Y'): ('q_gohome', 'Y', 'L'),
    ('q_gohome', BLANK): ('q_find0', BLANK, 'R'),
}
M = TuringMachine(zn_transitions, 'q_find0', 'q_accept', 'q_reject')


class TMEncoder:
    """L37-এর এনকোডার -- একটি TM-কে একটি স্ট্রিং-এ এনকোড করে।"""
    SEP_FIELD, SEP_RULE, SEP_PARTS, SEP_ARROW = ';;', '|', ',', '>'

    @staticmethod
    def encode(tm):
        parts = ['START=' + tm.start, 'ACCEPT=' + tm.accept,
                 'REJECT=' + tm.reject, 'BLANK=' + tm.blank]
        rules = []
        for (state, symbol), (ns, ws, d) in tm.transitions.items():
            lhs = TMEncoder.SEP_PARTS.join([state, symbol])
            rhs = TMEncoder.SEP_PARTS.join([ns, ws, d])
            rules.append(lhs + TMEncoder.SEP_ARROW + rhs)
        parts.append('TRANS=' + TMEncoder.SEP_RULE.join(rules))
        return TMEncoder.SEP_FIELD.join(parts)

    @staticmethod
    def decode(encoded):
        fields = dict(f.split('=', 1) for f in encoded.split(TMEncoder.SEP_FIELD))
        transitions = {}
        if fields['TRANS']:
            for rule in fields['TRANS'].split(TMEncoder.SEP_RULE):
                lhs, rhs = rule.split(TMEncoder.SEP_ARROW)
                state, symbol = lhs.split(TMEncoder.SEP_PARTS)
                ns, ws, d = rhs.split(TMEncoder.SEP_PARTS)
                transitions[(state, symbol)] = (ns, ws, d)
        return transitions, fields['START'], fields['ACCEPT'], fields['REJECT'], fields['BLANK']


class UniversalSimulator:
    """L37-এর UTM -- এনকোডেড TM ডিকোড করে জেনেরিকভাবে সিমুলেট করে।"""
    def __init__(self, encoded_tm):
        (self.transitions, self.start, self.accept,
         self.reject, self.blank) = TMEncoder.decode(encoded_tm)

    def run(self, input_string, max_steps=3000):
        tape = {i: c for i, c in enumerate(input_string)}
        head, state, steps = 0, self.start, 0
        while state != self.accept and state != self.reject and steps < max_steps:
            symbol = tape.get(head, self.blank)
            key = (state, symbol)
            if key not in self.transitions:
                return 'reject', steps
            ns, ws, d = self.transitions[key]
            tape[head] = ws
            head += 1 if d == 'R' else -1
            state = ns
            steps += 1
        if state == self.accept:
            return 'accept', steps
        elif state == self.reject:
            return 'reject', steps
        else:
            return 'timeout', steps


def build_Mw(m_encoded, w, buffer=60):
    """L40-এর রিডাকশন কনস্ট্রাকশন: ⟨M⟩ + ফিক্সড w নিয়ে ⟨M_w⟩ বানায় -- M_w তার নিজের
    ইনপুট x সম্পূর্ণ ignore করে (নিরাপদে টেপের অনেক বাঁ-দিকে সরে গিয়ে, x-এর এলাকা কখনো
    স্পর্শ না করে), সেখানে w লিখে M-কে সেই w-এর উপর চালায়।
    L(M_w) = সব স্ট্রিং (M যদি w-এর উপর accept করে), অথবা ফাঁকা (যদি না করে)।"""
    transitions, start, accept, reject, blank = TMEncoder.decode(m_encoded)
    new_transitions = dict(transitions)

    seek_len = buffer + max(len(w), 1)   # x-এর এলাকা এড়াতে যথেষ্ট বাঁ-দিকে সরে যাওয়া
    for i in range(seek_len):
        cur = f'mw_seek_{i}'
        nxt = f'mw_seek_{i+1}' if i + 1 < seek_len else 'mw_write_0'
        for sym in ('0', '1', blank):
            new_transitions[(cur, sym)] = (nxt, sym, 'L')   # x যা-ই থাকুক, স্পর্শ না করেই টপকে যাই

    if len(w) == 0:
        for sym in ('0', '1', blank):
            new_transitions[('mw_write_0', sym)] = ('mw_return_0', sym, 'R')
    else:
        for i, ch in enumerate(w):
            cur = f'mw_write_{i}'
            nxt = f'mw_write_{i+1}' if i + 1 < len(w) else 'mw_return_0'
            for sym in ('0', '1', blank):
                new_transitions[(cur, sym)] = (nxt, ch, 'R')   # w-এর ক্যারেক্টার একে একে লেখা

    return_len = max(len(w), 1)
    for i in range(return_len):
        cur = f'mw_return_{i}'
        nxt = f'mw_return_{i+1}' if i + 1 < return_len else start   # শেষে M-এর নিজের start-এ প্রবেশ
        for sym in ('0', '1', blank):
            new_transitions[(cur, sym)] = (nxt, sym, 'L')

    mw_tm = TuringMachine(new_transitions, 'mw_seek_0', accept, reject, blank)
    return TMEncoder.encode(mw_tm)


# --- যাচাই: দুটো (M, w) জোড়া -- একটির জন্য M(w) accept করে, আরেকটির জন্য reject করে ---
m_encoded = TMEncoder.encode(M)
known_cases = [("0011", "accept"), ("01001", "reject")]   # সরাসরি M চালিয়ে যাচাইযোগ্য
test_xs = ["", "0", "1111", "0101", "111000"]              # M_w-এর নিজস্ব ইনপুট -- ignored হওয়ার কথা

for w, expected in known_cases:
    direct, _ = M.run(w)
    assert direct == expected, "M(w)-এর সরাসরি ফলাফল প্রত্যাশার সাথে মেলেনি"
    mw_encoded = build_Mw(m_encoded, w)
    sim = UniversalSimulator(mw_encoded)
    print(f"M({w!r}) সরাসরি = {direct}  =>  M_w = build_Mw(M, {w!r})")
    results = []
    for x in test_xs:
        r, steps = sim.run(x, max_steps=3000)
        results.append(r)
        print(f"  M_w({x!r}) = {r} (steps={steps})")
    same = all(r == results[0] for r in results)
    matches_expected = all(r == expected for r in results)
    print(f"  সব x-এ একই ফলাফল (L(M_w) হয় সবকিছু, নয় ফাঁকা): {same}")
    print(f"  M(w)-এর সাথে মিলছে (L(M_w) সঠিক): {matches_expected}\n")
    assert same and matches_expected

print("রিডাকশন কনস্ট্রাকশন যাচাই সফল -- build_Mw ঠিক দাবিকৃত ভাষাই তৈরি করে।")