সমস্যাকে ল্যাঙ্গুয়েজ হিসেবে দেখা — ডিসিশন প্রবলেম

১ · ডিসিশন প্রবলেম কী

একটি ডিসিশন প্রবলেমDecision Problemএমন একটি প্রশ্ন যার উত্তর প্রতিটি সম্ভাব্য ইনপুট ইনস্ট্যান্সের জন্য YES বা NO। হলো এমন একটি প্রশ্ন যার উত্তর প্রতিটি সম্ভাব্য ইনপুট ইনস্ট্যান্স-এর জন্য YES অথবা NO — যেমন "এই গ্রাফ কি connected?" বা "এই সংখ্যা কি ৩ দ্বারা বিভাজ্য?" প্রতিটি ইনপুটের জন্য একটি নির্দিষ্ট, দ্ব্যর্থহীন উত্তর থাকে — "মাঝামাঝি" কোনো উত্তর নেই।

২ · সমস্যা থেকে ল্যাঙ্গুয়েজ — মূল রিফ্রেমিং

এই কোর্সের সবচেয়ে গুরুত্বপূর্ণ প্রাথমিক ট্রিকগুলোর একটি — যেকোনো ডিসিশন প্রবলেম একটি ল্যাঙ্গুয়েজ হিসেবে এনকোড করা যায়। কীভাবে? প্রতিটি সম্ভাব্য ইনপুটকে একটি স্ট্রিং হিসেবে এনকোড করে, ল্যাঙ্গুয়েজ $L$ সংজ্ঞায়িত করা হয় — ঠিক সেই সব ইনপুট-এনকোডিং-এর সেট যাদের উত্তর YES:

$$L = \{w \in \Sigma^* : w\text{-এর এনকোড করা ইনপুটের উত্তর YES}\}$$

এই সংজ্ঞা অনুযায়ী, "সমস্যা সমাধান করা" এখন হুবহু "ল্যাঙ্গুয়েজ membership যাচাই করা"-এর সমতুল্য — একটি নির্দিষ্ট $w$ ইনপুটের জন্য উত্তর YES কি না, তা জানতে শুধু জিজ্ঞাসা করতে হয়: $w \in L$ কি না? এই একটিমাত্র, একীভূত গাণিতিক কাঠামো (ল্যাঙ্গুয়েজ ও অটোমাটা) দিয়েই তাই সব ডিসিশন প্রবলেম পড়ানো সম্ভব — এটিই এই কোর্স কেন M2 থেকে M9 পর্যন্ত ক্রমাগত "ল্যাঙ্গুয়েজ" নিয়ে কথা বলবে, "সমস্যা" নয়, তার সরাসরি, স্পষ্ট প্রেরণা।

৩ · এনকোডিং — জটিল বস্তুও স্ট্রিং হতে পারে

সংখ্যার মতো "স্বাভাবিকভাবে স্ট্রিং-আকৃতির" ইনপুট ছাড়াও, আরও জটিল বস্তু — গ্রাফ, এমনকি (M9-এ দেখা যাবে) অন্য একটি টুরিং মেশিনের সম্পূর্ণ বর্ণনা — সবই একটি ফিক্সড আলফাবেটের উপর স্ট্রিং হিসেবে এনকোড করা যায়। যেমন একটি গ্রাফকে তার adjacency matrix-কে সারি-বাই-সারি একটি ফ্ল্যাট স্ট্রিং-এ রূপান্তর করে এনকোড করা যায়। এই এনকোডিং-ক্ষমতাই নিশ্চিত করে যে "ল্যাঙ্গুয়েজ" ফ্রেমওয়ার্কটি সত্যিই সাধারণ (general) — শুধু সংখ্যা/টেক্সট-জাতীয় সমস্যায় সীমাবদ্ধ নয়।

৪ · Python-এ ডিসিশন প্রবলেম ও এনকোডিং

নিচের কোড সেলে দুটি জিনিস দেখা যাচ্ছে — প্রথমত, "বাইনারি সংখ্যা ৩ দ্বারা বিভাজ্য কি না" প্রশ্নের একটি real, DFA-স্টাইল অ্যালগরিদম (প্রতিটি বিট প্রসেস করে remainder ট্র্যাক করা — M2-এর DFA formalism-এর সরাসরি পূর্বাভাস), Python-এর নেটিভ int(w,2)%3-এর বিপরীতে ক্রস-চেক করা; দ্বিতীয়ত, একটি গ্রাফকে (adjacency matrix হিসেবে) স্ট্রিং-এ এনকোড করার একটি সাধারণ ফাংশন।

def is_divisible_by_3(w):
    """w ekti binary string -- w-ke binary shonkha hisebe porle ta 3 dara bivajjo kina, ekti real
    bit-by-bit remainder-tracking algorithm diye (M2-er DFA-r purbabhash)"""
    remainder = 0
    for bit in w:
        remainder = (remainder * 2 + int(bit)) % 3
    return remainder == 0

test_strings = ["0", "11", "110", "1001", "1100", "111111", "101"]
print(f"{'w':10s} | {'int(w,2)':10s} | remainder-ট্রেস | int(w,2)%3==0 | মিলছে?")
print("-" * 65)
for w in test_strings:
    value = int(w, 2)
    trace_result = is_divisible_by_3(w)
    native_result = (value % 3 == 0)
    match = trace_result == native_result
    print(f"{w:10s} | {value:10d} | {str(trace_result):15s} | {str(native_result):13s} | {'হ্যাঁ' if match else 'না'}")

def encode_graph_as_string(adjacency_matrix):
    """n x n adjacency matrix (0/1 entry) -ke ekti flat string-e encode kore --
    protita sari ekshathe jora, sarir majhe '|' diye alada"""
    rows = []
    for row in adjacency_matrix:
        rows.append(''.join(str(bit) for bit in row))
    return '|'.join(rows)

triangle_graph = [
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0],
]

print()
print("গ্রাফ (adjacency matrix, ৩টি vertex, প্রতিটি জোড়ার মধ্যে edge):")
for row in triangle_graph:
    print(" ", row)
encoded = encode_graph_as_string(triangle_graph)
print("এনকোড করা স্ট্রিং:", encoded)
print("এই এনকোডিং একটি ফিক্সড আলফাবেট {0,1,|} -এর উপর একটি স্ট্রিং -- L(graph-properties)-এর মতো ল্যাঙ্গুয়েজে সরাসরি ব্যবহারযোগ্য")