নন-ডিটারমিনিস্টিক টুরিং মেশিন ও ইকুইভ্যালেন্স

def ntm_recognize(s, pattern="101"):
    """সব সম্ভাব্য (position, match_progress) কনফিগারেশন একসাথে সেটে ট্র্যাক করে --
    প্রতিটি ধাপে দুটি 'পছন্দ' সমান্তরালে ট্র্যাক করা হয়: (ক) নতুন করে ম্যাচ শুরুর guess,
    (খ) চলমান ম্যাচ চালিয়ে যাওয়া -- ঠিক NTM/NFA নন-ডিটারমিনিজম সিমুলেশনের স্ট্যান্ডার্ড কৌশল।"""
    m, n = len(pattern), len(s)
    configs = {(0, 0)}
    branch_count = 0
    for step in range(n + 1):
        branch_count += len(configs)          # সমান্তরালে যত কনফিগারেশন বিদ্যমান
        if any(progress == m for _, progress in configs):
            return True, branch_count
        if step == n:
            break
        ch = s[step]
        new_configs = set()
        for (pos, progress) in configs:
            new_configs.add((pos, 1 if ch == pattern[0] else 0))   # নতুন attempt-এর guess
            if progress < m and ch == pattern[progress]:
                new_configs.add((pos, progress + 1))               # চলমান ম্যাচ চালিয়ে যাওয়া
        configs = new_configs
    return any(p == m for _, p in configs), branch_count

def deterministic_bfs_recognize(s, pattern="101"):
    """ডিটারমিনিস্টিক সংস্করণ -- প্রতিটি সম্ভাব্য শুরু-অবস্থান একে একে, sequentially চেষ্টা করে,
    ঠিক একই কাজ করছে, কিন্তু কোনো সমান্তরাল ট্র্যাকিং ছাড়া।"""
    n, m = len(s), len(pattern)
    branch_count = 0
    for start in range(max(0, n - m + 1)):
        branch_count += 1
        match = True
        for offset in range(m):
            branch_count += 1
            if s[start + offset] != pattern[offset]:
                match = False
                break
        if match:
            return True, branch_count
    return False, branch_count

tests = ["101", "1101", "0101100", "111000111", "100110", "000000", "1"*15]
for s in tests:
    nt_result, nt_branches = ntm_recognize(s)
    det_result, det_branches = deterministic_bfs_recognize(s)
    match = "IDENTICAL" if nt_result == det_result else "MISMATCH"
    print(f"{s!r:14s} NTM={nt_result!s:5s}(branch={nt_branches:3d})  "
          f"DET-BFS={det_result!s:5s}(branch={det_branches:3d})  [{match}]")