সরাসরি পর্বে যান
পর্ব ৮২ · ৮৫-এর মধ্যে · মডিউল ১৪

MCQ প্রশ্নব্যাংক — গণনার তত্ত্ব

Theory of Computation MCQ Bank — Module-wise Questions with Every Option Explained

Taught in Bangla, this practice page offers 90 multiple-choice questions in course order: 80 across modules 1 to 13, from finite automata and regex to grammars, Turing machines, computability and complexity, plus a 10-question timed mixed set. Every option opens an explanation with the lesson to revisit, and an in-page Python (Pyodide) block after each part checks every number, trace and table by brute force. It also teaches elimination, twelve common traps and keeping proven and open inclusions apart.

এই পর্বে যা করবেন

  • বাদ দেওয়ার পদ্ধতিতে উত্তর বের করা, আর প্রতিটি distractor-এর পেছনের ভুল ধারণা চেনা
  • DFA, NFA, regex, grammar, PDA আর Turing machine পড়ে ছোট trace আর state-সংখ্যা দ্রুত বের করা
  • Closure আর decidability-র টেবিল থেকে ঠিক অপশন বাছা, শর্তসহ
  • Reduction-এর দিক কখনো উল্টো না করা: জানা-কঠিন সমস্যা সবসময় বাঁয়ে
  • Complexity class-এর কোন অন্তর্ভুক্তি প্রমাণিত আর কোনটি খোলা, তা আলাদা রাখা
  • ঘড়ি ধরে মিশ্র মহড়া দিয়ে নিজের প্রস্তুতি মাপা আর দুর্বল মডিউলে ফেরা

১ · কীভাবে অনুশীলন করবেন — প্রশ্নের ধরন, বাদ দেওয়া আর সময়

এই পাতা বিশ্ববিদ্যালয়ের Theory of Computation বা Automata Theory কোর্সের পরীক্ষা, IT ও প্রোগ্রামার পদের লিখিত পরীক্ষা, software ইন্টারভিউ আর নিজে নিজে শেখার ঝালাইয়ের জন্য। গণনার তত্ত্বের MCQ-তে নম্বর সবচেয়ে বেশি হারায় তিন জায়গায়: শর্ত বাদ পড়া (“complete DFA”, “f(n) ≥ log n”, “non-trivial”), দিক উল্টে যাওয়া (A ≤m B পড়ে B-এর বদলে A-কে কঠিন বলা), আর “প্রমাণিত” ও “খোলা” গুলিয়ে ফেলা।

প্রশ্নের চার ছাঁচ

ধরনউদাহরণকৌশল
সংজ্ঞাPumping lemma-র শর্ত, NP-র সংজ্ঞা, Church–Turing thesisসব quantifier আর শর্তসহ বলুন
যুক্তিReduction-এর দিক, Rice খাটে কি না, closureপ্রতিটি অপশনে একটি নিয়ম বা counterexample
Machine পড়াDFA-র state, CYK-এর ঘর, TM-এর configurationখাতায় ধাপে ধাপে trace
গোনাSubset-এর সংখ্যা, Thompson-এর state, parse treeআগে সূত্র, তারপর ছোট ক্ষেত্রে মিলিয়ে দেখা

কোন মডিউলে কতটি প্রশ্ন

Questions per module, roughly in proportion to the number of lessons; 10 more in the mixed mock

মডিউলভিত্তিক প্রশ্নের সংখ্যা তেরোটি অনুভূমিক bar. মডিউল ১ থেকে ১৩-এ প্রশ্নের সংখ্যা যথাক্রমে ৬, ৬, ৮, ৪, ৮, ৬, ৫, ৭, ৭, ৭, ৬, ৫ আর ৫, মোট ৮০; মিশ্র মহড়ায় আরও ১০টি। M1 ভিত্তি৬ M2 FA৬ M3 regular৮ M4 regex বাস্তবে৪ M5 CFG৮ M6 PDA৬ M7 parsing৫ M8 TM৭ M9 computability৭ M10 P, NP৭ M11 উন্নত৬ M12 দিগন্ত৫ M13 প্রয়োগ৫ মিশ্র মহড়া১০

কৌশল ১ · বাদ দেওয়ার পদ্ধতি — একটি minimal DFA-র প্রশ্ন ধাপে ধাপে

“কয়টি state” ধরনের প্রশ্নে দুই দিক থেকে কাটুন: জোড়ায় জোড়ায় আলাদা করা যায় এমন string একটি নিম্নসীমা দেয় (পর্ব ১৮), আর একটি কাজের DFA একটি ওপরের সীমা দেয়।

  1. প্রশ্নকয়টি state?চারটি অপশন
  2. নিম্নসীমা২ বাদε, a, ab আলাদা
  3. ওপরের সীমা৪, ৫ বাদ৩-state DFA আছে
  4. উত্তর৩dead state নেই
  5. যাচাই২০৪৭ stringbrute force
প্রশ্ন (মাঝারি)চার অপশন
L = {w ∈ {a, b}* : w ab দিয়ে শেষ}
minimal DFA-তে কয়টি state?

ক) ২   খ) ৩
গ) ৪   ঘ) ৫
ধাপ ২ক কাটুন
ε বনাম a : z = b
  b ∉ L, ab ∈ L
ε বনাম ab: z = ε
a বনাম ab: z = ε
→ অন্তত ৩টি state
ধাপ ৩গ, ঘ কাটুন
0: কিছু মেলেনি
1: শেষে a
2: শেষে ab (accept)
a → 1 সবখান থেকে
b: 0→0, 1→2, 2→0
ধাপ ৪উত্তর খ
dead state লাগে না:
যেকোনো string-এর পরে
ab জুড়লেই গ্রহণ
→ ঠিক ৩টি state
ধাপ ৫কোডে যাচাই
suffix-আচরণে দল: ৩
DFA বনাম সংজ্ঞা:
দৈর্ঘ্য 0–10-এর
সব 2047 string-এ মেলে
  1. আগে প্রশ্নটি নিজের ভাষায় বলুন। শেষ দুটি চিহ্ন ab কি না, শুধু সেটুকু মনে রাখতে হবে। কতটুকু অতীত লাগে, সেটিই state-সংখ্যা ঠিক করে।
  2. নিম্নসীমা দিয়ে কাটুন। ε, a আর ab জোড়ায় জোড়ায় আলাদা: প্রতিটি জোড়ার জন্য একটি z আছে, যা একটিকে L-এ নেয়, অন্যটিকে নয়। Myhill–Nerode অনুযায়ী তাই অন্তত ৩টি state; ক বাদ।
  3. ওপরের সীমা দিয়ে কাটুন। “কিছু মেলেনি”, “শেষে a”, “শেষে ab” এই তিন state-এর একটি সম্পূর্ণ DFA কাজ করে, তাই ৩-এর বেশি লাগে না; গ আর ঘ বাদ।
  4. ফাঁদটি চিনুন। “Dead state যোগ করুন” অভ্যাসে অনেকে ৪ বলেন। কিন্তু এখানে কোনো string থেকে আর ফেরা অসম্ভব নয়, তাই dead state নেই। উত্তর খ, ৩।
  5. সন্দেহ থাকলে কোডে যাচাই। নিচের block suffix পরীক্ষায় দল গোনে (নিম্নসীমা) আর ৩-state DFA-কে দৈর্ঘ্য ১০ পর্যন্ত সব string-এ সংজ্ঞার সঙ্গে মেলায় (ওপরের সীমা)।

প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে; এই পাতার সব block শুধু Python-এর standard library ব্যবহার করে।

from itertools import product
from fractions import Fraction as F

L = lambda w: w.endswith("ab")            # প্রশ্নের language
words = lambda n: ["".join(p) for k in range(n + 1) for p in product("ab", repeat=k)]
# Myhill–Nerode: দৈর্ঘ্য ≤ 3-এর সব suffix z-এ একই আচরণ ⇒ একই দলে
sig = {}
for w in words(4):
    sig.setdefault(tuple(L(w + z) for z in words(3)), w)
print("আলাদা দল:", len(sig), "| প্রতিনিধি:", sorted(sig.values(), key=len))

# ৩-state DFA: 0 = কিছু মেলেনি, 1 = শেষে a, 2 = শেষে ab
d = {(0, "a"): 1, (0, "b"): 0, (1, "a"): 1, (1, "b"): 2, (2, "a"): 1, (2, "b"): 0}
def accepts(w):
    q = 0
    for c in w:
        q = d[q, c]
    return q == 2
test = words(10)
print("৩-state DFA সব", len(test), "string-এ মেলে:", all(accepts(w) == L(w) for w in test))

# negative marking: ঠিক +1, ভুল −1/4, চারটি অপশন
for cut in range(3):
    k = 4 - cut
    ev = F(1, k) - F(k - 1, k) * F(1, 4)
    print(f"{cut}টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর {ev} ≈ {float(ev):.3f}")

আসল আউটপুট:

আলাদা দল: 3 | প্রতিনিধি: ['', 'a', 'ab']
৩-state DFA সব 2047 string-এ মেলে: True
0টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর 1/16 ≈ 0.062
1টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর 1/6 ≈ 0.167
2টি বাদ দিয়ে আন্দাজ: প্রত্যাশিত নম্বর 3/8 ≈ 0.375

দৈর্ঘ্য ≤ ৩-এর suffix দিয়ে মাত্র তিনটি দল পাওয়া গেছে, প্রতিনিধি ε, a আর ab; আর ৩-state DFA দৈর্ঘ্য ০ থেকে ১০-এর সব ২০৪৭টি string-এ সংজ্ঞার সঙ্গে মেলে। দুই সীমা মিলে উত্তর ৩। শেষ তিন লাইন negative marking-এর হিসাব: ঠিক হলে +১ আর ভুলে −০.২৫ ধরলে অন্ধ আন্দাজের প্রত্যাশিত লাভ মাত্র ১/১৬, একটি অপশন নিশ্চিত কাটলে ১/৬, দুটি কাটলে ৩/৮. কত কাটে বা আদৌ কাটে কি না, তা পরীক্ষাভেদে আলাদা; নিজের পরীক্ষার নিয়ম দেখে নিন।

কৌশল ২ · ছোট ক্ষেত্রে মিলিয়ে দেখা আর সময় ভাগ

সূত্র মনে না পড়লে n = 1, 2, 3 বসিয়ে অপশন কাটুন: “CNF-এ derivation 2n − 1 ধাপ” দাবিটি একটি অক্ষরের string-এ (S → a, এক ধাপ) সঙ্গে সঙ্গে মেলানো যায়। প্রথম দফায় সংজ্ঞা আর যুক্তির প্রশ্ন, দ্বিতীয় দফায় trace আর গোনা, খাতায় প্রতিটি ধাপ লিখে।

বারোটি বড় ফাঁদ

ফাঁদভুল ধারণাসঠিক কথা
ফাঁকা string“∅ = {ε}”∅-এ কিছু নেই, {ε}-এ একটি string; ∅∗ = {ε} (পর্ব ০৩)
Complement“F অদলবদল করলেই হলো”আগে complete DFA; NFA-তে এভাবে হয় না (পর্ব ০৮)
Pumping lemma“বিভাজন আমি বাছব”বিভাজন প্রতিপক্ষের; lemma শুধু প্রয়োজনীয় শর্ত (পর্ব ১৭)
CFL-এর ছেদ“CFL ∩ CFL = CFL”Closed শুধু regular-এর সঙ্গে ছেদে (পর্ব ৩৭)
Ambiguity“দুটি derivation মানেই ambiguous”লাগে দুটি parse tree বা দুটি leftmost derivation (পর্ব ২৭)
DPDA“DCFL = CFL”wwR CFL কিন্তু DCFL নয় (পর্ব ৩৫)
Decider“Recognizer মানেই decider”Decider সব input-এ থামে (পর্ব ৫০)
Reduction-এর দিক“A ≤m B, A কঠিন, তাই A-ই প্রমাণিত”জানা-কঠিন সমস্যা বাঁয়ে; কঠিনতা যায় ডানে, B-তে (পর্ব ৫২)
Rice-এর theorem“Program নিয়ে সব প্রশ্ন undecidable”শুধু language-এর non-trivial ধর্ম; state গোনা decidable (পর্ব ৫৩)
NP“NP মানে non-polynomial”Nondeterministic polynomial: polynomial সময়ের verifier (পর্ব ৫৮)
Pseudo-polynomial“O(nt) DP, তাই P-তে”t binary-তে log t bit; দৈর্ঘ্যে exponential (পর্ব ৬১)
খোলা প্রশ্ন“P ⊊ PSPACE প্রমাণিত”প্রমাণিত কঠোর শুধু NL ⊊ PSPACE আর P ⊊ EXP (পর্ব ৬৪)

এই পাতার প্রশ্নগুলো সম্পর্কে: প্রশ্নগুলো এই কোর্সের পর্বগুলো থেকে নতুন করে লেখা, এ ধরনের প্রশ্ন প্রায়ই আসে এমন ধারণা থেকে। কোনোটিই কোনো নির্দিষ্ট পরীক্ষা, বিশ্ববিদ্যালয় বা প্রতিষ্ঠানের আসল প্রশ্ন নয়। “বাজারঘর” একটি কাল্পনিক অনলাইন দোকান।

২ · মডিউল ১ ও ২ — ভিত্তি আর finite automaton (১২টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ০১–১২

মডিউল ১ — ভিত্তি (৬টি প্রশ্ন)

(সহজ) নিচের কোনটি সঠিক?

  • ∅ = {ε}
  • ∅∗ = ∅
  • |{ε}| = 1 আর |∅| = 0
  • যেকোনো L-এর জন্য ∅L = L

(সহজ) Σ = {0, 1}. দৈর্ঘ্য ঠিক ৩-এর string কয়টি, আর দৈর্ঘ্য বড়জোর ৩-এর কয়টি?

  • ৮ আর ১৫
  • ৮ আর ১৪
  • ৬ আর ১৪
  • ৯ আর ১৩

(মাঝারি) L = {a, aa}. L2 = LL-এ কয়টি আলাদা string আছে?

  • ৪
  • ৩
  • ২
  • ৬

(মাঝারি) Σ = {0, 1}. কোন সেটটি uncountable?

  • Σ∗
  • সব DFA-র সেট
  • সব Turing machine-এর সেট
  • P(Σ∗), অর্থাৎ সব language-এর সেট

(মাঝারি) PRIME-এর input একটি সংখ্যা n, binary-তে b bit. √n পর্যন্ত trial division-এর ধাপ b-এর সাপেক্ষে কেমন?

  • O(b), কারণ √n ছোট
  • প্রায় 2b/2, অর্থাৎ input-এর দৈর্ঘ্যে exponential
  • O(b2)
  • n = 1000-এ মাত্র ১০ ধাপ, তাই polynomial

(মাঝারি) Language-শ্রেণির ক্রম নিয়ে কোনটি সঠিক?

  • Type 0 grammar ঠিক decidable language দেয়
  • Context-sensitive = decidable
  • REG ⊊ CFL ⊊ CSL ⊊ decidable ⊊ recognizable
  • Decidable language-গুলোই Type 1

মডিউল ২ — finite automaton (৬টি প্রশ্ন)

(সহজ) Binary সংখ্যা বাঁ থেকে পড়ে ভাগশেষ রাখে এমন DFA: δ(r, b) = (2r + b) mod 3, শুরু r = 0. Input 1101 পড়ার পর কোন state?

  • r = 0
  • r = 2
  • r = 3
  • r = 1

(সহজ) ৩-state mod-3 DFA আর “1-এর সংখ্যা জোড়” চেনা ২-state DFA থেকে ∩-এর product DFA বানালে সর্বোচ্চ কয়টি state?

  • ৫
  • ৬
  • ৮
  • ৯

(মাঝারি) একটি partial DFA-তে কিছু transition নেই (সেখানে string আটকে বর্জিত হয়). শুধু F আর Q ∖ F অদলবদল করলে কী হয়?

  • আটকে যাওয়া string দুই যন্ত্রেই বর্জিত হয়, তাই ফল complement নয়
  • সঠিক complement পাওয়া যায়
  • ফল একটি NFA হয়ে যায়
  • Language একটুও বদলায় না

(মাঝারি) L3 = {w ∈ {0, 1}∗ : শেষ থেকে তৃতীয় চিহ্ন 1}. এর ৪-state NFA থেকে subset construction-এ কয়টি reachable subset পাওয়া যায়?

  • ৪
  • ১৬
  • ৮
  • ৬

(মাঝারি) একটি ε-NFA-তে ε-তীর q0 → q1, q1 → q2, q2 → q0, আর q1 থেকে a পড়ে q3. ECLOSE(q0) কোনটি?

  • {q1, q2}
  • {q0, q1, q2}
  • {q0, q1, q2, q3}
  • {q0, q1}

(কঠিন) Overlap-সহ 101 detector-এর ৩-state Mealy machine: state 0, 1, 2 = এ পর্যন্ত কতটা মিলেছে; output 1 শুধু state 2 থেকে 1 পড়লে. Moore-এ রূপান্তরে state হয় (q, শেষ output). কয়টি জোড়া reachable?

  • ৩
  • ৬
  • ৫
  • ৪

সব প্রশ্ন শেষ হলে নিচের block-এ ওপরের হিসাবগুলো মিলিয়ে নিন।

from itertools import product
L = {"a", "aa"}
print("L² =", sorted({x + y for x in L for y in L}, key=len))
print("দৈর্ঘ্য 3:", 2 ** 3, "| ≤ 3:", sum(2 ** k for k in range(4)), "| 1000-এর binary:", len(bin(1000)) - 2, "bit")
r, path = 0, [0]
for b in "1101":
    r = (2 * r + int(b)) % 3
    path.append(r)
ws = ["".join(p) for k in range(7) for p in product("01", repeat=k)]
pairs = {(int(w or "0", 2) % 3, w.count("1") % 2) for w in ws}
print("mod-3 পথ 1101-এ:", path, "| product-এর reachable জোড়া:", len(pairs))
nfa = {("q0", "0"): {"q0"}, ("q0", "1"): {"q0", "q1"}}   # L3: শেষ থেকে তৃতীয় চিহ্ন 1
for i in (1, 2):
    for a in "01":
        nfa[f"q{i}", a] = {f"q{i + 1}"}
seen, todo = {frozenset({"q0"})}, [frozenset({"q0"})]
for S in todo:                      # todo বাড়তে থাকে, সব reachable subset ঘোরে
    for a in "01":
        T = frozenset(set().union(*[nfa.get((q, a), set()) for q in S]))
        if T not in seen:
            seen.add(T); todo.append(T)
print("L3-এর reachable subset:", len(seen))
eps = {"q0": ["q1"], "q1": ["q2"], "q2": ["q0"], "q3": []}
clo, todo = {"q0"}, ["q0"]
for q in todo:
    clo.update(eps[q]); todo += [t for t in eps[q] if t not in todo]
print("ECLOSE(q0) =", sorted(clo))
me = {(0, "0"): (0, 0), (0, "1"): (1, 0), (1, "0"): (2, 0),   # overlap-সহ 101 (Mealy)
      (1, "1"): (1, 0), (2, "0"): (0, 0), (2, "1"): (1, 1)}
print("Moore-এর (state, output):", sorted({(0, 0)} | set(me.values())))

আসল আউটপুট:

L² = ['aa', 'aaa', 'aaaa']
দৈর্ঘ্য 3: 8 | ≤ 3: 15 | 1000-এর binary: 10 bit
mod-3 পথ 1101-এ: [0, 1, 0, 0, 1] | product-এর reachable জোড়া: 6
L3-এর reachable subset: 8
ECLOSE(q0) = ['q0', 'q1', 'q2']
Moore-এর (state, output): [(0, 0), (1, 0), (1, 1), (2, 0)]

L2-এ তিনটি string, কারণ aaa দুইভাবে এলেও একবারই গোনা হয়। mod-3 পথ শেষ হয় 1-এ, product-এ ছয়টি জোড়াই reachable. L3-এর subset ঠিক ৮টি, ECLOSE(q0)-এ q0 নিজেসহ তিনটি state, আর Moore রূপান্তরে চারটি (state, output) জোড়া। গোনাগুলো সসীম পরিসরে, কিন্তু প্রতিটির পেছনে পর্বের প্রমাণ আছে।

৩ · মডিউল ৩ ও ৪ — regular language আর বাস্তবের regex (১২টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ১৩–২৪

মডিউল ৩ — regular expression আর regular language (৮টি প্রশ্ন)

(সহজ) কোন string (a ∪ b)a∗-এ আছে কিন্তু a ∪ ba∗-এ নেই?

  • ba
  • aa
  • a
  • b

(মাঝারি) R আর S যেকোনো regular expression. কোন “অভেদ” সাধারণভাবে মিথ্যা?

  • (R∗)∗ = R∗
  • (R ∪ S)∗ = (R∗S∗)∗
  • (RS)∗ = R∗S∗
  • R∅ = ∅

(মাঝারি) Thompson construction-এ প্রতিটি পাতায় ২টি state, union আর star-এ +২, concatenation-এ নতুন state নেই. (a ∪ b)∗abb-এর ε-NFA-তে মোট কয়টি state?

  • ১৪
  • ১০
  • ২২
  • ৮

(মাঝারি) Regular language নিচের কোনটিতে closed নয়?

  • Reversal
  • Inverse homomorphism
  • যেকোনো language M দিয়ে right quotient
  • অসীম union

(মাঝারি) {anbn}-এর pumping প্রমাণে প্রতিপক্ষ p = 4 বেছেছেন, আপনি s = a4b4. |xy| ≤ p আর |y| ≥ 1 মানে এমন কয়টি বিভাজন (x, y, z) আপনাকে সামলাতে হবে?

  • ৪
  • ১০
  • ১৬
  • ১টি, কারণ প্রতিপক্ষ একটিই বাছেন

(মাঝারি) L = {w ∈ {a, b}∗ : ডান থেকে দ্বিতীয় চিহ্ন a}. ≡L-এর class কয়টি, অর্থাৎ minimal DFA-তে কয়টি state?

  • ২
  • ৩
  • ৪
  • ৮

(মাঝারি) DFA, Σ = {0, 1}, শুরু A, F = {C, E}. A, B আর D প্রত্যেকে 0-তে B-তে আর 1-এ C-তে যায়; C আর E প্রত্যেকে 0-তে D-তে আর 1-এ E-তে যায়. Minimal DFA-তে কয়টি state?

  • ২
  • ৩
  • ৫
  • ৪

(কঠিন) Input একটি NFA N. L(N) = Σ∗ কি না (universality), প্রশ্নটি কেমন?

  • Undecidable
  • Polynomial, কারণ NFA থেকে DFA বানিয়ে দেখা যায়
  • PSPACE-complete
  • সবসময় O(|N|) সময়ে

এখানে প্রথম যাচাই block; মডিউল ৪-এর পরে দ্বিতীয়টি।

import re
from itertools import product
ws = ["".join(p) for k in range(5) for p in product("ab", repeat=k)]
m = lambda r, w: re.fullmatch(r, w) is not None
only1 = [w for w in ws if m("(a|b)a*", w) and not m("a|ba*", w)]
print("শুধু (a∪b)a*-এ, দৈর্ঘ্য ≤ 4:", only1[:4])
wit = next(w for w in ws if m("(ab)*", w) != m("a*b*", w))
print("(ab)* বনাম a*b*-এর প্রথম পার্থক্য:", wit)
# Thompson: পাতা 2 state, union ও star +2, concatenation +0
def states(t):
    if isinstance(t, str): return 2
    op, *kids = t
    return sum(map(states, kids)) + (0 if op == "cat" else 2)
R = ("cat", ("star", ("or", "a", "b")), "a", "b", "b")
print("(a∪b)*abb-এর Thompson state:", states(R))
# pumping: p = 4, s = a^4 b^4; বৈধ (|x|, |y|) জোড়া, প্রতিটিতে i = 0
p, s = 4, "aaaabbbb"
inL = lambda w: w == "a" * (len(w) // 2) + "b" * (len(w) // 2)
splits = [(x, y) for x in range(p) for y in range(1, p - x + 1)]
fail0 = all(not inL(s[:x] + s[x + y:]) for x, y in splits)
print("বৈধ বিভাজন:", len(splits), "| সবগুলো i = 0-এ L-এর বাইরে:", fail0)

আসল আউটপুট:

শুধু (a∪b)a*-এ, দৈর্ঘ্য ≤ 4: ['aa', 'aaa', 'aaaa']
(ab)* বনাম a*b*-এর প্রথম পার্থক্য: a
(a∪b)*abb-এর Thompson state: 14
বৈধ বিভাজন: 10 | সবগুলো i = 0-এ L-এর বাইরে: True

Python-এর re.fullmatch দিয়ে দেখা গেল aa, aaa, aaaa শুধু প্রথম regex-এ। (ab)∗ আর a∗b∗-এর প্রথম পার্থক্য একটিমাত্র a. Thompson-এর হিসাব ১৪, আর a4b4-এর দশটি বৈধ বিভাজনের প্রতিটি i = 0-এ language-এর বাইরে যায়।

মডিউল ৪ — বাস্তবে automaton আর regex (৪টি প্রশ্ন)

(মাঝারি) Backtracking engine-এ pattern ^(a+)+$, input a10b (দশটি a, তারপর b). (a+)+ যতভাবে a-গুলোর কোনো prefix মেলাতে পারে, প্রতিবার $ পরীক্ষা হয়. মোট কতবার?

  • ১০
  • ৫৫
  • ১০২৪
  • ১০২৩

(সহজ) Token-তালিকা {>=, ==, >, =}. Maximal munch নিয়মে lexer input >== কীভাবে ভাঙে?

  • > তারপর ==
  • >= তারপর =
  • > তারপর = তারপর =
  • Lexical error

(মাঝারি) ধাঁচ ABABAC-এর failure function π (প্রতিটি prefix-এর সবচেয়ে লম্বা proper border-এর দৈর্ঘ্য) কোনটি?

  • 0 0 1 2 3 0
  • 0 0 1 2 3 1
  • 1 2 3 4 5 6
  • 0 0 0 1 2 0

(মাঝারি) বাজারঘরের checkout বোতামের state idle, loading, success, error. Loading অবস্থায় আবার click এলে কোন নকশা double order ঠেকায়?

  • আরেকটি request পাঠানো, যেটি আগে ফেরে সেটি নেওয়া
  • সরাসরি error state-এ যাওয়া
  • Click উপেক্ষা (self-loop), আর request id দিয়ে দেরিতে আসা উত্তর বাদ
  • isLoading আর isError দুটি Boolean flag দিয়ে সামলানো
from itertools import product
ws = lambda n: ["".join(p) for k in range(n + 1) for p in product("ab", repeat=k)]
L = lambda w: len(w) >= 2 and w[-2] == "a"            # ডান থেকে দ্বিতীয় চিহ্ন a
print("Myhill–Nerode দল:", len({tuple(L(w + z) for z in ws(3)) for w in ws(5)}))
# পাঁচ state-এর DFA, F = {C, E}; Moore refinement
d = {"A": "BC", "B": "BC", "C": "DE", "D": "BC", "E": "DE"}   # (0-তে, 1-এ)
part = {q: q in "CE" for q in d}
for _ in range(5):
    part = {q: (part[q], part[d[q][0]], part[d[q][1]]) for q in d}
print("minimal DFA-র state:", len(set(part.values())))
def ways(n, i=0):                  # (a+)+ কত উপায়ে a^n-এর একটি prefix মেলায়
    return sum(1 + ways(n, j) for j in range(i + 1, n + 1))
print("^(a+)+$ আর a^10 b: $ পরীক্ষা", ways(10))
toks = [">=", "==", ">", "="]
def munch(s):
    out = []
    for _ in range(len(s)):
        if not s: break
        t = max((t for t in toks if s.startswith(t)), key=len)
        out.append(t); s = s[len(t):]
    return out
print('">==" →', munch(">=="))
P, pi = "ABABAC", [0] * 6
for q in range(1, 6):
    k = pi[q - 1]
    for _ in range(q):
        if k == 0 or P[k] == P[q]: break
        k = pi[k - 1]
    pi[q] = k + (P[k] == P[q])
print("π(ABABAC) =", pi)

আসল আউটপুট:

Myhill–Nerode দল: 4
minimal DFA-র state: 2
^(a+)+$ আর a^10 b: $ পরীক্ষা 1023
">==" → ['>=', '=']
π(ABABAC) = [0, 0, 1, 2, 3, 0]

দৈর্ঘ্য ≤ ৩-এর suffix দিয়ে চারটি দল পাওয়া গেছে; এটি নিম্নসীমা, আর শেষ দুই চিহ্ন মনে রাখা ৪-state DFA ওপরের সীমা। Moore-ধাঁচের refinement পাঁচ state-কে দুই দলে নামায়। ways function ঠিক backtracking-এর মতো প্রতিটি ভাগ একবার গোনে: ১০২৩. শেষ দুই লাইন maximal munch আর KMP-র π.

৪ · মডিউল ৫ ও ৬ — context-free grammar আর pushdown automaton (১৪টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ২৫–৩৭

মডিউল ৫ — context-free grammar (৮টি প্রশ্ন)

(সহজ) Grammar E → E+E ∣ E∗E ∣ id-এ id+id∗id-এর কয়টি parse tree আছে?

  • ১
  • ২
  • ৩
  • ৫

(মাঝারি) Grammar E → E+E ∣ id-এ id+id+id+id (তিনটি +)-এর কয়টি parse tree?

  • ৩
  • ৬
  • ১৪
  • ৫

(মাঝারি) Unambiguous grammar E → E+T ∣ T, T → T∗F ∣ F, F → (E) ∣ id. id+id∗id-এর parse tree-র root-এ কোন নিয়ম বসে?

  • E → E+T
  • E → T
  • T → T∗F
  • F → (E)

(মাঝারি) Grammar S → AB ∣ c, A → aA ∣ ε, B → bB ∣ A. কোন variable-গুলো nullable?

  • {A}
  • {A, B}
  • {A, B, S}
  • {S}

(মাঝারি) Grammar S → AB ∣ a, A → b; B-এর কোনো নিয়ম নেই. সঠিক ক্রমে (আগে non-generating, পরে unreachable) useless symbol সরালে কী থাকে?

  • S → a আর A → b
  • শুধু S → a
  • S → AB ∣ a আর A → b
  • কিছুই না, কারণ L(G) = ∅

(সহজ) Chomsky normal form-এ একটি grammar. দৈর্ঘ্য ৬-এর একটি string-এর যেকোনো derivation-এ কত ধাপ?

  • ৬
  • ১২
  • ১৭
  • ১১

(মাঝারি) A → Aα ∣ β (β A দিয়ে শুরু নয়) থেকে immediate left recursion দূর করলে কোনটি পাওয়া যায়?

  • A → βA′, A′ → αA′ ∣ ε
  • A → αA′, A′ → βA′ ∣ ε
  • A → A′α, A′ → β
  • A → β ∣ αA

(কঠিন) CNF grammar S → AB ∣ BC, A → BA ∣ a, B → CC ∣ b, C → AB ∣ a. Input baaba-র CYK টেবিলের চূড়ার ঘরে (পুরো string) কী আছে?

  • ∅, তাই বর্জিত
  • শুধু {S}, তাই গৃহীত
  • {S, A, C}, তাই গৃহীত
  • {A, C}, S নেই বলে বর্জিত

Grammar-এর হিসাবগুলো মিলিয়ে নিন।

from functools import cache
@cache
def trees(t):                      # E → E+E ∣ E∗E ∣ id-এ token-সারির parse tree
    n = (t == ("id",)) * 1
    for k in range(1, len(t) - 1):
        if t[k] in "+*": n += trees(t[:k]) * trees(t[k + 1:])
    return n
print("id+id+id+id:", trees(tuple("id + id + id + id".split())),
      "| id+id*id:", trees(tuple("id + id * id".split())))
def fix(G, ok):                    # nullable বা generating: কিছু না বাড়া পর্যন্ত
    S = set()
    for _ in G: S |= {X for X, rhs in G.items() if any(all(ok(c, S) for c in r) for r in rhs)}
    return S
G = {"S": ["AB", "c"], "A": ["aA", ""], "B": ["bB", "A"]}
print("nullable:", sorted(fix(G, lambda c, S: c in S)))
H = {"S": ["AB", "a"], "A": ["b"], "B": []}     # B-এর কোনো নিয়ম নেই
gen = fix(H, lambda c, S: c.islower() or c in S)
H2 = {X: [r for r in H[X] if all(c.islower() or c in gen for c in r)] for X in gen}
reach = {"S"}
for _ in H2: reach |= {c for X in reach for r in H2[X] for c in r if c.isupper()}
print("ঠিক ক্রমে বাকি:", {X: H2[X] for X in reach}, "| উল্টো ক্রমে বাকি:", H2)
R = {"S": ["AB", "BC"], "A": ["BA", "a"], "B": ["CC", "b"], "C": ["AB", "a"]}
w = "baaba"; n = len(w)
T = {(i, 1): {X for X in R if w[i] in R[X]} for i in range(n)}
for l in range(2, n + 1):
    for i in range(n - l + 1):
        T[i, l] = {X for X in R for r in R[X] if len(r) == 2 for k in range(1, l)
                   if r[0] in T[i, k] and r[1] in T[i + k, l - k]}
print("CYK চূড়া T[0,5] =", sorted(T[0, n]))

আসল আউটপুট:

id+id+id+id: 5 | id+id*id: 2
nullable: ['A', 'B', 'S']
ঠিক ক্রমে বাকি: {'S': ['a']} | উল্টো ক্রমে বাকি: {'S': ['a'], 'A': ['b']}
CYK চূড়া T[0,5] = ['A', 'C', 'S']

Parse tree গোনা হয়েছে প্রতিটি operator-এ ভাঙার জায়গা ধরে: তিনটি +-এ ৫, id+id∗id-এ ২. Nullable আর generating দুটিই একই fixpoint ছাঁচে। “উল্টো ক্রমে বাকি” লাইনটি দেখায়, আগে reachability নিলে কিছু সরে না, আর B সরানোর পরে A → b useless হয়েও থেকে যায়। CYK-এর চূড়া {A, C, S}.

মডিউল ৬ — pushdown automaton আর CFL (৬টি প্রশ্ন)

(সহজ) PDA-র transition “a, x → y”-এর মানে কী?

  • a পড়ে x push, তারপর y pop
  • a পড়ে stack-এর ওপর থেকে x তোলে আর y রাখে
  • x পড়ে a তোলে আর y রাখে
  • ওপরে a থাকলে x পড়ে y state-এ যায়

(মাঝারি) {anbn}-এর PDA: প্রথমে ε, ε → $; প্রতিটি a-তে a push; প্রতিটি b-তে একটি a pop. aaabbb-এর প্রথম চার চিহ্ন aaab পড়ার পর stack (ওপর বাঁয়ে)?

  • a$
  • $
  • aa$
  • aaa$

(মাঝারি) কোন language deterministic CFL নয়?

  • {wwR : w ∈ {a, b}∗}
  • {wcwR : w ∈ {a, b}∗}
  • {anbn : n ≥ 0}
  • সুষম বন্ধনীর language

(মাঝারি) {anbncm : n, m ≥ 0} ∩ {ambncn : n, m ≥ 0} কী, আর এটি কী দেখায়?

  • ∅; কিছুই দেখায় না
  • a∗b∗c∗; CFL ∩ CFL regular হয়
  • {anbn}; CFL ∩-এ closed
  • {anbncn}, যা CFL নয়; তাই CFL ∩-এ closed নয়

(কঠিন) L = {anbncn}, s = apbpcp. CFL pumping lemma-র যেকোনো বৈধ বিভাজন uvxyz সম্পর্কে কোনটি নিশ্চিত?

  • vxy সবসময় a-ব্লকের ভেতরে
  • vxy বড়জোর দুই রকম চিহ্ন ছোঁয়, তাই i = 2-এ তিন সংখ্যা সমান থাকে না
  • v আর y দুটিই অ-ফাঁকা
  • u = ε ধরে নেওয়া যায়

(মাঝারি) Context-free grammar-এর জন্য কোন প্রশ্নটি decidable?

  • L(G) = Σ∗ কি না
  • L(G1) = L(G2) কি না
  • L(G) = ∅ কি না
  • G ambiguous কি না
import re
from itertools import product
def pda(w):                        # aⁿbⁿ: ε,ε→$; a,ε→a; b,a→ε (q2); শেষে ε,$→ε
    q, st, trace = "q1", "$", []   # stack-এর ওপর বাঁয়ে
    for c in w:
        if c == "a" and q == "q1": st = "a" + st
        elif c == "b" and st[0] == "a": q, st = "q2", st[1:]
        else: return trace + ["আটকে গেল"]
        trace.append(f"{c}:{st}")
    return trace
print("aaab পড়ার পর:", pda("aaab"))
ws = ["".join(p) for k in range(10) for p in product("abc", repeat=k)]
def blocks(w):                     # w = aⁱbʲcᵏ হলে (i, j, k), নইলে None
    m = re.fullmatch("(a*)(b*)(c*)", w)
    return tuple(map(len, m.groups())) if m else None
L1 = {w for w in ws if (b := blocks(w)) and b[0] == b[1]}       # aⁿbⁿcᵐ
L2 = {w for w in ws if (b := blocks(w)) and b[1] == b[2]}       # aᵐbⁿcⁿ
print("L1 ∩ L2, দৈর্ঘ্য ≤ 9:", sorted(L1 & L2, key=len))
p, s, bad, kinds = 3, "aaabbbccc", [], set()
inL = lambda w: (b := blocks(w)) is not None and b[0] == b[1] == b[2]
for u in range(len(s) + 1):
    for vxy in range(1, min(p, len(s) - u) + 1):
        for v in range(vxy + 1):
            for x in range(vxy - v + 1):
                y = vxy - v - x
                if v + y == 0: continue
                kinds.add(len(set(s[u:u + vxy])))
                V, X, Y, Z = s[u:u+v], s[u+v:u+v+x], s[u+v+x:u+vxy], s[u+vxy:]
                if inL(s[:u] + V * 2 + X + Y * 2 + Z): bad.append((u, v, x, y))
print("vxy-তে আলাদা চিহ্ন:", sorted(kinds), "| i = 2-এ L-এ থেকে যায়:", bad)

আসল আউটপুট:

aaab পড়ার পর: ['a:a$', 'a:aa$', 'a:aaa$', 'b:aa$']
L1 ∩ L2, দৈর্ঘ্য ≤ 9: ['', 'abc', 'aabbcc', 'aaabbbccc']
vxy-তে আলাদা চিহ্ন: [1, 2] | i = 2-এ L-এ থেকে যায়: []

PDA-র trace-এ প্রতি চিহ্নের পরে stack দেখা যায়: চতুর্থ চিহ্ন b-এর পরে aa$. দৈর্ঘ্য ৯ পর্যন্ত দুই language-এর ছেদে ঠিক ε, abc, aabbcc আর aaabbbccc. শেষ লাইন p = 3-এ সব বৈধ uvxyz বিভাজন ঘুরে দেখায়: vxy কখনো দুই রকমের বেশি চিহ্ন ছোঁয় না, আর i = 2-এ একটিও L-এ থাকে না।

৫ · মডিউল ৭ ও ৮ — parsing আর Turing machine (১২টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ৩৮–৪৯

মডিউল ৭ — বাস্তবে parsing (৫টি প্রশ্ন)

(মাঝারি) Grammar E → TE′, E′ → +TE′ ∣ ε, T → FT′, T′ → ∗FT′ ∣ ε, F → (E) ∣ id. FOLLOW(T) কোনটি?

  • {+, ), $}
  • {+, $}
  • {∗, +, ), $}
  • {id, (}

(সহজ) A → ab ∣ ac নিয়ম দুটি LL(1) নয় কেন, আর প্রতিকার কী?

  • Ambiguous বলে; precedence লাগে
  • Left-recursive বলে; A′ দিয়ে recursion সরাতে হবে
  • ε-নিয়ম আছে বলে
  • দুটিই a দিয়ে শুরু; left factoring: A → aA′, A′ → b ∣ c

(মাঝারি) LR(1) item set-এর একই core মিলিয়ে LALR(1) table বানালে কোন নতুন conflict আসতে পারে?

  • Shift/reduce
  • শুধু reduce/reduce
  • দুই ধরনেরই
  • কোনোটিই নয়

(মাঝারি) PEG নিয়ম A ← a / ab (ordered choice). পুরো input ab-কে A দিয়ে মেলাতে চাইলে কী হয়?

  • ab মেলে, কারণ / মানে union
  • দুই বিকল্প চেষ্টা করে লম্বাটি নেয়
  • A শুধু a নেয়; b বাকি থাকে বলে parse ব্যর্থ
  • Infinite loop

(মাঝারি) Earley parser সম্পর্কে কোনটি সঠিক?

  • Left-recursive grammar-এ loop করে
  • শুধু LL(1) grammar-এ চলে
  • সবসময় O(n) সময়ে চলে
  • যেকোনো CFG-এ চলে; সবচেয়ে খারাপ O(n3), unambiguous grammar-এ O(n2)

মডিউল ৮ — Turing machine (৭টি প্রশ্ন)

(সহজ) একটি Turing machine M সম্পর্কে কোনটি সঠিক?

  • M সবসময় থামে
  • একটি input-এ তিন ফল: গ্রহণ, বর্জন বা loop; সব input-এ থামলে M decider
  • M-এর tape সসীম
  • বর্জন আর loop একই কথা

(মাঝারি) একটি TM-এর configuration ab q3 ba (tape abba, head তৃতীয় ঘরে), আর δ(q3, b) = (q5, x, L). পরের configuration কোনটি?

  • a q5 bxa
  • abx q5 a
  • ab q5 xa
  • a q5 xba

(মাঝারি) t(n) ≥ n সময়ের একটি k-tape TM-কে এক-tape TM দিয়ে নকল করলে সময় কত লাগে?

  • O(t(n))
  • O(k · t(n))
  • O(t(n)2)
  • 2O(t(n))

(মাঝারি) Nondeterministic TM-কে deterministic ভাবে নকল করতে computation tree-তে DFS কেন যথেষ্ট নয়?

  • DFS বেশি জায়গা নেয়
  • DFS গ্রহণকারী শাখা পেলেও চিনতে পারে না
  • প্রতিটি node-এ অসীম সংখ্যক সন্তান
  • একটি অসীম শাখায় আটকে যেতে পারে, অথচ অন্য শাখা গ্রহণ করত

(সহজ) Church–Turing thesis-এর অবস্থান কী?

  • এটি একটি thesis: অনানুষ্ঠানিক ধারণার কারণে প্রমাণযোগ্য নয়, তবে প্রবল সাক্ষ্য আছে
  • ১৯৩৬ সালে Turing এটি প্রমাণ করেন
  • Quantum computer এটি ভেঙে দিয়েছে
  • এটি বলে সব সমস্যা polynomial সময়ে সমাধানযোগ্য

(মাঝারি) Church numeral-এ n মানে “f-কে n বার প্রয়োগ”, আর EXP = λm.λn. n m. EXP 2 3 কোন সংখ্যা?

  • ৬
  • ৯
  • ৮
  • ৫

(মাঝারি) Universal Turing machine U সম্পর্কে কোনটি সঠিক?

  • U একটি decider
  • L(U) = ATM; M loop করলে U-ও loop করে
  • প্রতিটি M-এর জন্য আলাদা U লাগে
  • U-এর state-সংখ্যা M-এর আকারের সঙ্গে বাড়ে
G = {"E": [["T", "E'"]], "E'": [["+", "T", "E'"], []], "T": [["F", "T'"]],
     "T'": [["*", "F", "T'"], []], "F": [["(", "E", ")"], ["id"]]}
FIRST = {X: set() for X in G}; FOLLOW = {X: set() for X in G}; FOLLOW["E"].add("$")
def first(seq):                    # ε-কে "" দিয়ে লেখা
    out = set()
    for s in seq:
        f = FIRST[s] if s in G else {s}
        out |= f - {""}
        if "" not in f: return out
    return out | {""}
for _ in range(10):                # fixpoint: কয়েক পাকেই স্থির হয়
    for A, rules in G.items():
        for r in rules:
            FIRST[A] |= first(r)
            for i, B in enumerate(r):
                if B in G:
                    f = first(r[i + 1:])
                    FOLLOW[B] |= (f - {""}) | (FOLLOW[A] if "" in f else set())
print("FOLLOW(T) =", sorted(FOLLOW["T"]), "| FOLLOW(E') =", sorted(FOLLOW["E'"]))
def peg_A(s, i):                   # A ← a / ab : ordered choice
    for alt in ("a", "ab"):
        if s.startswith(alt, i): return i + len(alt)
    return None
print("A মেলায়:", repr("ab"[:peg_A("ab", 0)]), "| পুরো input মিলেছে:", peg_A("ab", 0) == 2)
u, q, v = "ab", "q3", "ba"         # configuration ab q3 ba; δ(q3, b) = (q5, x, L)
tape = u + "x" + v[1:]
print("পরের configuration:", tape[:len(u) - 1], "q5", tape[len(u) - 1:])
church = lambda n: lambda f: lambda x: x if n == 0 else f(church(n - 1)(f)(x))
EXP = lambda m: lambda n: n(m)     # EXP = λm.λn. n m
print("EXP 2 3 =", EXP(church(2))(church(3))(lambda k: k + 1)(0))

আসল আউটপুট:

FOLLOW(T) = ['$', ')', '+'] | FOLLOW(E') = ['$', ')']
A মেলায়: 'a' | পুরো input মিলেছে: False
পরের configuration: a q5 bxa
EXP 2 3 = 8

FIRST আর FOLLOW একসঙ্গে fixpoint পর্যন্ত বাড়ানো হয়েছে: FOLLOW(T) = {$, ), +}. PEG-এর লাইন দেখায় ordered choice প্রথম সফল বিকল্পেই থামে। Configuration-এর লাইন u q v নিয়ম মেনে বানানো, আর Church numeral সত্যিকারের Python lambda দিয়ে চালিয়ে EXP 2 3 = 8.

৬ · মডিউল ৯ — computability (৭টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ৫০–৫৬

(সহজ) কোন বক্তব্যটি সঠিক?

  • প্রতিটি recognizable language decidable
  • L recognizable হলে L̄-ও recognizable
  • Decider কিছু input-এ loop করতে পারে
  • L decidable ⇔ L আর L̄ দুটিই recognizable

(মাঝারি) ATM-এর complement সম্পর্কে কোনটি সঠিক?

  • Decidable
  • Recognizable নয়
  • Recognizable কিন্তু undecidable
  • Regular

(মাঝারি) A ≤m B, আর জানা যে A undecidable. কোনটি নিশ্চিতভাবে বলা যায়?

  • B undecidable
  • B decidable
  • A recognizable
  • B ≤m A

(মাঝারি) কোন প্রশ্নের undecidability সরাসরি Rice-এর theorem থেকে আসে?

  • M-এর state ৫টির বেশি কি না
  • M input ε-তে ১০০ ধাপের মধ্যে থামে কি না
  • L(M) সসীম কি না
  • L(M) recognizable কি না

(মাঝারি) PCP-র ডমিনো (ওপর/নিচ): ১ = [b/ca], ২ = [a/ab], ৩ = [ca/a], ৪ = [abc/c]. কোন ক্রমটি একটি match?

  • ১, ২, ৩, ৪
  • ২, ১, ৩, ৪
  • ৪, ৩, ২, ১
  • ২, ১, ৩, ২, ৪

(মাঝারি) Busy Beaver function S(n) (n-state থামা যন্ত্রের সর্বোচ্চ ধাপ) সম্পর্কে কোনটি সঠিক?

  • S(n) computable, শুধু খুব দ্রুত বাড়ে
  • S(2) = 6, S(4) = 107, S(5) = 47,176,870 জানা, তবু S computable নয়
  • S(5) এখনো অজানা
  • যথেষ্ট বড় একটি computable timeout সব n-state যন্ত্রের halting decide করে

(মাঝারি) Binary alphabet-এ দৈর্ঘ্য ১০-এর চেয়ে ছোট program কয়টি, আর এ থেকে কী নিশ্চিত হয়?

  • ১০২৩টি, অথচ string ১০২৪টি; তাই অন্তত একটির K(x) ≥ ১০
  • ১০২৪টি; তাই সব string সংকোচনযোগ্য
  • ১০টি; তাই বেশিরভাগ সংকোচনযোগ্য
  • K(x) computable, তাই গুনে দেখা যায়
from itertools import product
D = {1: ("b", "ca"), 2: ("a", "ab"), 3: ("ca", "a"), 4: ("abc", "c")}   # [ওপর/নিচ]
def text(seq):
    return "".join(D[i][0] for i in seq), "".join(D[i][1] for i in seq)
for seq in [(1, 2, 3, 4), (2, 1, 3, 4), (4, 3, 2, 1), (2, 1, 3, 2, 4)]:
    t, b = text(seq)
    print(seq, t, b, "match" if t == b else "নয়")
short = next((n, s) for n in range(1, 7) for s in product(D, repeat=n)
             if text(s)[0] == text(s)[1])
print("সবচেয়ে ছোট match (দৈর্ঘ্য ≤ 6-এ খুঁজে):", short)
# ২-state Busy Beaver champion: (state, পড়া) → (লেখা, দিক, পরের state)
bb = {("A", 0): (1, 1, "B"), ("A", 1): (1, -1, "B"),
      ("B", 0): (1, -1, "A"), ("B", 1): (1, 1, "H")}
tape, pos, q, steps = {}, 0, "A", 0
for _ in range(100):               # step cap
    if q == "H": break
    w, mv, q = bb[q, tape.get(pos, 0)]
    tape[pos] = w; pos += mv; steps += 1
print("BB(2) champion: ধাপ", steps, "| 1-এর সংখ্যা", sum(tape.values()))
n = 10
print(f"দৈর্ঘ্য < {n}-এর program:", sum(2 ** i for i in range(n)), f"| দৈর্ঘ্য {n}-এর string:", 2 ** n)

আসল আউটপুট:

(1, 2, 3, 4) bacaabc caabac নয়
(2, 1, 3, 4) abcaabc abcaac নয়
(4, 3, 2, 1) abccaab caabca নয়
(2, 1, 3, 2, 4) abcaaabc abcaaabc match
সবচেয়ে ছোট match (দৈর্ঘ্য ≤ 6-এ খুঁজে): (5, (2, 1, 3, 2, 4))
BB(2) champion: ধাপ 6 | 1-এর সংখ্যা 4
দৈর্ঘ্য < 10-এর program: 1023 | দৈর্ঘ্য 10-এর string: 1024

দৈর্ঘ্য ৬ পর্যন্ত সব ক্রম খুঁজে সবচেয়ে ছোট match (২, ১, ৩, ২, ৪). মনে রাখুন, এই খোঁজ একটি নির্দিষ্ট instance-এর জন্য; PCP সাধারণভাবে undecidable, আর “সীমার মধ্যে পাওয়া যায়নি” কোনো রায় নয়। ২-state champion step cap-এর মধ্যে ৬ ধাপে থামে, চারটি 1 লিখে। শেষ লাইন Kolmogorov-এর গোনার যুক্তি।

৭ · মডিউল ১০ ও ১১ — P, NP আর উন্নত complexity (১৩টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ৫৭–৭০

মডিউল ১০ — P, NP আর NP-completeness (৭টি প্রশ্ন)

(সহজ) NP-এর সংজ্ঞায় কোনটি সঠিক?

  • NP মানে non-polynomial
  • NP-এর প্রতিটি সমস্যা P-এর বাইরে
  • Polynomial দৈর্ঘ্যের certificate আর polynomial সময়ের verifier আছে
  • প্রতিটি “না” উত্তরের ছোট প্রমাণ আছে

(মাঝারি) নতুন সমস্যা X NP-hard দেখাতে কোন reduction লাগে?

  • X ≤p 3SAT
  • 3SAT ≤p X
  • X-এর একটি polynomial verifier
  • X-এর একটি exponential algorithm

(মাঝারি) ৪টি clause-এর একটি 3CNF সূত্র φ থেকে 3SAT ≤p CLIQUE reduction-এ graph-এ কয়টি node, আর k কত?

  • ৪ আর ৪
  • ১২ আর ৩
  • ৩ (চলক) আর ৪
  • ১২ আর ৪

(মাঝারি) 3SAT ≤p VERTEX-COVER-এ (চলক-প্রতি একটি edge, clause-প্রতি একটি ত্রিভুজ) l = 3 চলক আর m = 2 clause হলে k কত?

  • ৭
  • ৫
  • ৯
  • ১২

(মাঝারি) একটি ৫-literal clause-কে তিন-literal clause-এ ভাঙলে কয়টি clause আর কয়টি নতুন চলক লাগে?

  • ৫ আর ৫
  • ২ আর ১
  • ৩ আর ২
  • ৪ আর ৩

(মাঝারি) কোনটি NP-hard কিন্তু NP-তে নেই?

  • 3SAT
  • HALTTM
  • 2SAT
  • CLIQUE

(সহজ) নিচের কোনটি প্রমাণিত?

  • P ≠ NP
  • NP = coNP
  • P = NP
  • P ⊆ NP আর P ⊊ EXP

মডিউল ১১ — উন্নত complexity (৬টি প্রশ্ন)

(মাঝারি) Savitch-এর theorem কী বলে?

  • f(n) ≥ log n হলে NSPACE(f(n)) ⊆ SPACE(f(n)2), তাই PSPACE = NPSPACE
  • NTIME(t) ⊆ TIME(t2)
  • NSPACE(f) = SPACE(f)
  • যেকোনো f-এ, কোনো শর্ত ছাড়াই

(মাঝারি) L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP. কোন কঠোর অন্তর্ভুক্তি (⊊) প্রমাণিত?

  • P ⊊ NP
  • L ⊊ NL
  • NL ⊊ PSPACE
  • NP ⊊ PSPACE

(মাঝারি) L আর NL নিয়ে কোনটি সঠিক?

  • L = NL প্রমাণিত
  • NL = coNL প্রমাণিত, কিন্তু L = NL খোলা
  • NL = P প্রমাণিত
  • NL ⊊ P প্রমাণিত

(মাঝারি) φ1 = ∀x ∃y (x ⊕ y) আর φ2 = ∃y ∀x (x ⊕ y), x আর y Boolean. কোনটি সঠিক?

  • দুটিই সত্য
  • দুটিই মিথ্যা
  • φ1 মিথ্যা, φ2 সত্য
  • φ1 সত্য, φ2 মিথ্যা

(মাঝারি) একটি RP algorithm “না” instance-এ কখনো গ্রহণ করে না, আর “হ্যাঁ” instance-এ অন্তত 1/2 সম্ভাবনায় গ্রহণ করে. স্বাধীনভাবে ১০ বার চালিয়ে একবার গ্রহণ করলেই “হ্যাঁ” বললে, “হ্যাঁ” instance-এ ভুলের সম্ভাবনা সর্বোচ্চ কত?

  • 1/1024
  • 1/10
  • 1/20
  • (1/3)10

(মাঝারি) Circuit complexity-তে কোনটি প্রমাণিত?

  • NP-এর কোনো সমস্যার superpolynomial circuit lower bound
  • P/poly-তে শুধু decidable language আছে
  • PARITY ∉ AC0, আর প্রায় সব n-bit function-এর Ω(2n/n) gate লাগে
  • P = P/poly
from itertools import product, combinations
from fractions import Fraction as F
phi = [(1, 2, 3), (-1, -2, 3), (1, -3, 2), (-1, 2, -3)]      # 4টি clause, চলক x1..x3
V = [(c, lit) for c, cl in enumerate(phi) for lit in cl]       # clause-প্রতি তিন node
E = {(u, v) for u, v in combinations(V, 2) if u[0] != v[0] and u[1] != -v[1]}
k = len(phi)
sat = any(all(any((l > 0) == a[abs(l) - 1] for l in cl) for cl in phi)
          for a in product([False, True], repeat=3))
clq = any(all((u, v) in E for u, v in combinations(S, 2)) for S in combinations(V, k))
print("node:", len(V), "| k:", k, "| satisfiable:", sat, "| k-clique:", clq)
l, m = 3, 2
print("3SAT → VC: node", 2 * l + 3 * m, "| k =", l + 2 * m)
big = [1, 2, 3, 4, 5]                                         # ৫-literal clause
new = [(1, 2, 6), (-6, 3, 7), (-7, 4, 5)]                      # y1 = 6, y2 = 7
ok = lambda cls, a: all(any((x > 0) == a[abs(x) - 1] for x in c) for c in cls)
same = all(ok([big], a) == any(ok(new, a + y) for y in product([False, True], repeat=2))
           for a in product([False, True], repeat=5))
print("clause:", len(new), "| নতুন চলক: 2 | equisatisfiable:", same)
xor = lambda x, y: x != y
print("∀x∃y (x⊕y):", all(any(xor(x, y) for y in (0, 1)) for x in (0, 1)),
      "| ∃y∀x (x⊕y):", any(all(xor(x, y) for x in (0, 1)) for y in (0, 1)))
print("RP, 10 বার চালালে ভুলের সর্বোচ্চ সম্ভাবনা:", F(1, 2) ** 10)

আসল আউটপুট:

node: 12 | k: 4 | satisfiable: True | k-clique: True
3SAT → VC: node 12 | k = 7
clause: 3 | নতুন চলক: 2 | equisatisfiable: True
∀x∃y (x⊕y): True | ∃y∀x (x⊕y): False
RP, 10 বার চালালে ভুলের সর্বোচ্চ সম্ভাবনা: 1/1024

চার clause-এর একটি নমুনা সূত্র থেকে graph বানিয়ে দেখা গেল: ১২টি node, আর সূত্র satisfiable হওয়ার সঙ্গে ৪-clique থাকা মিলে যায়। পাঁচ-literal clause ভাঙার পর সব ৩২টি মান-নির্ধারণে equisatisfiable. শেষ দুই লাইন quantifier-এর ক্রম আর RP-র পুনরাবৃত্তি। একটি নমুনায় মিল প্রমাণ নয়; reduction-এর প্রমাণ “⇔”-এর দুই দিকেই লাগে।

৮ · মডিউল ১২ ও ১৩ — নতুন দিগন্ত আর প্রয়োগ (১০টি প্রশ্ন)

যে পর্বগুলো ঝালিয়ে নেবেন · পর্ব ৭১–৮০

মডিউল ১২ — কঠিন সমস্যার মোকাবিলা আর নতুন দিগন্ত (৫টি প্রশ্ন)

(মাঝারি) পথ a–b–c–d–e-এর edge-গুলো (a,b), (b,c), (c,d), (d,e) ক্রমে ঘুরে maximal matching নিলে (দুই প্রান্তই খালি থাকলে edge নিন, দুই প্রান্তই cover-এ), cover-এর আকার আর OPT কত?

  • ২ আর ২
  • ৪ আর ২
  • ৫ আর ২
  • ৪ আর ৩

(মাঝারি) Vertex cover-এর Buss kernel (degree > k হলে vertex নিন, একাকী vertex মুছুন). k = 4 হলে “হ্যাঁ” instance-এর kernel-এ edge আর vertex বড়জোর কত?

  • ৪ আর ৮
  • ৮ আর ১৬
  • ১৬ আর ১৬
  • ১৬ আর ২০

(মাঝারি) CDCL SAT solver সম্পর্কে কোনটি সঠিক?

  • এর UNSAT run একটি resolution প্রমাণ
  • WalkSAT-এর মতো এটিও UNSAT প্রমাণ করতে পারে না
  • সব 3SAT instance polynomial সময়ে সমাধান করে
  • শেখা clause কিছু সমাধান বাদ দিয়ে ফেলতে পারে

(মাঝারি) N = 220 উপাদানের অগোছালো তালিকায় একটি চিহ্নিত উপাদান খুঁজতে Grover-এর algorithm প্রায় কতটি query নেয়?

  • ২০
  • 220
  • প্রায় ৮০৪
  • ১০২৪

(মাঝারি) One-way function (OWF) আর P বনাম NP সম্পর্কে কোনটি সঠিক?

  • P ≠ NP হলে one-way function আছে
  • One-way function থাকলে P ≠ NP; উল্টো দিক অজানা
  • Factoring one-way বলে প্রমাণিত
  • দুটির মধ্যে কোনো সম্পর্ক নেই

মডিউল ১৩ — প্রয়োগ আর ক্যাপস্টোন (৫টি প্রশ্ন)

(সহজ) বাজারঘরের system-এর কোন ধর্মটি liveness?

  • দুটি process কখনো একসঙ্গে critical section-এ নয়
  • Stock কখনো ঋণাত্মক হয় না
  • Cancelled অর্ডার কখনো shipped হয় না
  • প্রতিটি অর্ডার শেষমেশ পৌঁছায়

(মাঝারি) Büchi automaton: q0 –a→ q1, q1 –b→ q2, q2 –a→ q1; শুরু q0, accepting শুধু q0. L(A) কী?

  • ∅, কারণ q0 কোনো চক্রে নেই
  • শুধু a(ba)ω
  • {a}
  • (ba)ω

(মাঝারি) সসীম precision-এর একটি RNN-এর পৌঁছানো hidden state সসীম হলে সেটি সর্বোচ্চ কোন শ্রেণির language চিনতে পারে?

  • সব context-free language, যেমন সীমাহীন গভীরতার Dyck
  • সব decidable language
  • কোনো language নয়
  • শুধু regular language

(মাঝারি) বাজারঘরের toolkit-এ তিন কাজ: order-code যাচাই (BG- আর ৪টি অঙ্ক), order-query-র বন্ধনী মেলানো, আর একটি Turing-complete plug-in “কখনো ভুল ছাড় দেয় কি না” যাচাই. সবচেয়ে দুর্বল যথেষ্ট মডেল আর প্রশ্নের অবস্থা কী?

  • DFA; CFG বা PDA; plug-in-এর প্রশ্ন undecidable
  • তিনটিতেই regex যথেষ্ট
  • তিনটিতেই Turing machine, আর সব প্রশ্ন decidable
  • DFA; DFA; decidable

(মাঝারি) x = 0; while cond: x = x + 1 (cond সম্পর্কে কিছু জানা নেই). Interval analysis-এ widening ছাড়া loop-এর মাথায় x-এর interval কী হয়, আর widening কী দেয়?

  • [0, 0]-এ স্থির; widening লাগে না
  • [0, 0], [0, 1], [0, 2], … থামে না; widening [0, +∞] দেয়
  • [0, 1]-এ স্থির
  • Widening সবচেয়ে ছোট fixpoint ঠিক ঠিক দেয়
from itertools import combinations
from math import pi, sqrt
E = [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e")]          # পথ a–b–c–d–e
cover = set()
for u, v in E:                     # maximal matching: দুই প্রান্তই খালি হলে নিন
    if u not in cover and v not in cover: cover |= {u, v}
opt = min(len(S) for r in range(6) for S in combinations("abcde", r)
          if all(u in S or v in S for u, v in E))
print("matching cover:", sorted(cover), "| OPT:", opt)
k = 4
print("Buss kernel, k = 4: edge ≤", k * k, "| vertex ≤", k * k + k)
N = 2 ** 20
print("Grover, N = 2^20: প্রায়", round(pi / 4 * sqrt(N)), "query | ক্লাসিক্যাল সবচেয়ে খারাপ:", N)
# Büchi: q0 -a-> q1, q1 -b-> q2, q2 -a-> q1; accepting = {q0}
nxt = {"q0": ["q1"], "q1": ["q2"], "q2": ["q1"]}
def reach(s):
    seen, todo = set(), list(nxt[s])
    for q in todo:
        if q not in seen: seen.add(q); todo += nxt[q]
    return seen
acc = {"q0"}
print("কোনো accepting state চক্রে:", any(q in reach(q) for q in acc))
lo, hi, hist = 0, 0, []            # x = 0; loop-এ x = x + 1; interval [lo, hi]
for it in range(4):
    hist.append((lo, hi)); lo, hi = min(0, lo + 1), max(0, hi + 1)   # [0,0] ⊔ (x + 1)
print("widening ছাড়া:", hist, "… থামে না")
w = (0, float("inf"))              # নড়া ওপরের সীমা → +∞
print("widening-এর পর:", w, "| পরের পাকে বদলায় না:", (min(0, w[0] + 1), max(0, w[1] + 1)) == w)

আসল আউটপুট:

matching cover: ['a', 'b', 'c', 'd'] | OPT: 2
Buss kernel, k = 4: edge ≤ 16 | vertex ≤ 20
Grover, N = 2^20: প্রায় 804 query | ক্লাসিক্যাল সবচেয়ে খারাপ: 1048576
কোনো accepting state চক্রে: False
widening ছাড়া: [(0, 0), (0, 1), (0, 2), (0, 3)] … থামে না
widening-এর পর: (0, inf) | পরের পাকে বদলায় না: True

Matching-এর cover চার vertex, আর সব subset খুঁজে OPT দুই: ratio ঠিক ২. Grover-এর হিসাব প্রায় ৮০৪টি query, ক্লাসিক্যাল সবচেয়ে খারাপ ক্ষেত্রে দশ লাখের বেশি। Büchi-র লাইন দেখায় q0 নিজের কাছে ফেরে না, তাই L(A) = ∅. শেষ দুই লাইনে widening ছাড়া interval বাড়তেই থাকে, আর [0, ∞]-এ পরের পাক কিছু বদলায় না।

৯ · মিশ্র মহড়া — ঘড়ি ধরে ১০টি প্রশ্ন, সব মডিউল থেকে

সব ভাগ শেষ হলে এই অংশটি একটি ছোট মহড়া পরীক্ষা হিসেবে করুন। প্রশ্নগুলো ইচ্ছা করে এলোমেলো, কারণ আসল পরীক্ষায় 2SAT-এর পরেই regex engine, তারপর parse tree আসতে পারে। ওপরের প্রশ্ন থেকে এগুলো আলাদা।

মহড়ার নিয়ম · ১০টি প্রশ্ন, ১৫ মিনিট
  • ঘড়ি ধরুন: ১৫ মিনিটের টাইমার চালু করুন; প্রতি প্রশ্নে গড়ে দেড় মিনিট।
  • আগে খাতায়: ১ থেকে ১০ নম্বরের পাশে অপশন আর এক লাইনের কারণ লিখুন; সময় শেষ হলে তবেই অপশন চাপুন।
  • ফল পড়ুন এভাবে: ৮ বা বেশি ঠিক হলে প্রস্তুতি ভালো; ৫ থেকে ৭ হলে ভুল প্রশ্নের পর্বগুলো ঝালিয়ে নিন; ৪ বা কম হলে আগে মডিউলের ভাগগুলো আবার করুন। এই সীমা শুধু অনুশীলনের সুবিধার জন্য ধরা, কোনো পরীক্ষার মান নয়।

(সহজ) নিচের কোন সমস্যা P-তে আছে বলে জানা?

  • 3SAT
  • HAMPATH
  • 2SAT
  • 3-COLOR

(মাঝারি) EQTM = {⟨M1, M2⟩ : L(M1) = L(M2)} সম্পর্কে কোনটি সঠিক?

  • Recognizable-ও নয়, co-recognizable-ও নয়
  • Decidable
  • Recognizable কিন্তু undecidable
  • Co-recognizable কিন্তু recognizable নয়

(মাঝারি) SUBSET-SUM-এর O(n · t) সময়ের DP থাকা সত্ত্বেও এটি P-তে আছে বলে প্রমাণিত নয় কেন?

  • DP কিছু ক্ষেত্রে ভুল উত্তর দেয়
  • n বড় হলে DP চলে না
  • SUBSET-SUM undecidable
  • t binary-তে log t bit, তাই n · t দৈর্ঘ্যে exponential হতে পারে

(সহজ) কোন ধরনের regex engine backreference সমর্থন করে না, কিন্তু input-দৈর্ঘ্যে রৈখিক সময়ের নিশ্চয়তা দেয়?

  • Python-এর re
  • RE2-ধাঁচের automaton-ভিত্তিক engine
  • JavaScript-এর RegExp
  • PCRE

(মাঝারি) Deterministic PDA-তে empty-stack acceptance কেন মানক রীতি নয়?

  • DPDA-তে stack থাকে না
  • Empty stack বেশি শক্তিশালী
  • Empty stack-এ শুধু prefix-free DCFL চেনা যায়
  • দুই রীতি সমান, তাই পার্থক্য নেই

(মাঝারি) Interactive proof-এর শ্রেণি IP সম্পর্কে কোনটি প্রমাণিত?

  • IP = PSPACE
  • IP = NP
  • IP ⊆ BPP
  • IP = EXP

(মাঝারি) P = NP প্রমাণিত হলে polynomial hierarchy-র কী হতো?

  • PH = PSPACE
  • PH অসীম প্রমাণ হতো
  • PH = EXP
  • PH = P, পুরো hierarchy ধসে পড়ত

(কঠিন) একটি BPP algorithm প্রতিটি run-এ ঠিক 1/3 সম্ভাবনায় ভুল করে, run-গুলো স্বাধীন. ৫ বার চালিয়ে সংখ্যাগরিষ্ঠ উত্তর নিলে ভুলের সম্ভাবনা কত?

  • 1/243
  • 17/81 ≈ 0.21
  • 1/3
  • 1/27

(মাঝারি) {a, b}-এর ওপর দৈর্ঘ্য ঠিক ৪-এর কতগুলো string-এ aa substring হিসেবে আছে?

  • ৮
  • ১২
  • ৩
  • ৫

(মাঝারি) Chomsky normal form-এ দৈর্ঘ্য ৫-এর একটি string-এর parse tree-তে পাতাসহ মোট কয়টি node?

  • ৯
  • ১০
  • ১৪
  • ১৫

মহড়া শেষ করে, নম্বর লিখে তবেই নিচের block চালান।

from itertools import product
from fractions import Fraction as F
from math import comb
w4 = ["".join(p) for p in product("ab", repeat=4)]
print("দৈর্ঘ্য 4-এ 'aa' আছে:", sum("aa" in w for w in w4), "| নেই:", sum("aa" not in w for w in w4))
def trees(n):                      # S → SS ∣ a-তে aⁿ-এর সব parse tree: (ধাপ, node)
    if n == 1: return [(1, 2)]     # S → a: ১ ধাপ, node S আর a
    return [(1 + s1 + s2, 1 + n1 + n2) for k in range(1, n)
            for s1, n1 in trees(k) for s2, n2 in trees(n - k)]
for n in (5, 6):
    t = trees(n)
    print(f"n = {n}: গাছ {len(t)}টি, ধাপ {set(s for s, _ in t)}, node {set(x for _, x in t)}")
p = F(1, 3)
err = sum(comb(5, i) * p ** i * (1 - p) ** (5 - i) for i in range(3, 6))
print("৫ run-এর সংখ্যাগরিষ্ঠে ভুল:", err, "≈", round(float(err), 4), "| (1/3)^5 =", p ** 5)

আসল আউটপুট:

দৈর্ঘ্য 4-এ 'aa' আছে: 8 | নেই: 8
n = 5: গাছ 14টি, ধাপ {9}, node {14}
n = 6: গাছ 42টি, ধাপ {11}, node {17}
৫ run-এর সংখ্যাগরিষ্ঠে ভুল: 17/81 ≈ 0.2099 | (1/3)^5 = 1/243

দৈর্ঘ্য ৪-এর ১৬টি string সমান দুই ভাগে পড়ে। S → SS ∣ a grammar-টি CNF-এ, আর a5-এর ১৪টি গাছের (Catalan C4) প্রতিটিতে ধাপ ৯ আর node ১৪; a6-এ ১১ আর ১৭. গাছের আকার বদলালেও এই দুই সংখ্যা বদলায় না, CNF-এর মূল ধর্ম এটিই। শেষ লাইন BPP-র সংখ্যাগরিষ্ঠ ভোটের সঠিক সম্ভাবনা।

AI-এর যুগে — AI দিয়ে আরও MCQ বানান, কিন্তু উত্তর নিজে যাচাই করুন

AI assistant মুহূর্তে শত শত প্রশ্ন বানাতে পারে, কিন্তু গণনার তত্ত্বে সে প্রায়ই ভুল language-এর automaton দেয় (গোনায় off-by-one, ε বা dead state বাদ), pumping-এর “প্রমাণে” বিভাজন নিজে বাছে, decidable আর recognizable গুলিয়ে ফেলে, reduction উল্টো দিকে করে, উপপাদ্য শর্ত ছাড়া বলে, খোলা প্রশ্নকে মীমাংসিত বলে, আর বানানো উৎস দেয়। তাই AI-এর প্রশ্ন অনুশীলনের কাঁচামাল, উত্তরপত্র নয়।

AI-এর প্রচলিত ভুলউদাহরণকীভাবে ধরবেন
ভুল machine“ঠিক দুটি a”-এর DFA-তে ε বা dead state বাদদৈর্ঘ্য ১০ পর্যন্ত সব string-এ সংজ্ঞার সঙ্গে তুলনা
উল্টো reduction“X ≤p SAT, তাই X NP-hard”জানা-কঠিন সমস্যা বাঁয়ে আছে কি না দেখুন
শর্তহীন উপপাদ্যSavitch-এ f(n) ≥ log n বাদ, Rice syntactic ধর্মেপ্রতিটি উপপাদ্যের শর্ত জিজ্ঞেস করুন
খোলাকে মীমাংসিত বলা“L ≠ NL প্রমাণিত”, “BQP ⊇ NP”বিশ্বস্ত পাঠ্যবইয়ে মিলিয়ে নিন
বানানো উৎস“অমুক পরীক্ষায় এসেছিল”উৎস দেখাতে না পারলে দাবি বাদ

নিচের প্রম্পটটি AI-কে প্রশ্ন বানাতে বলে, আর যাচাইয়ের উপায়ও চায়। উত্তর পেলে প্রতিটি machine বা সংখ্যা এই পাতার Python block-এর মতো একটি ছোট কোডে মিলিয়ে নিন।

আমি Theory of Computation-এর MCQ পরীক্ষার প্রস্তুতি নিচ্ছি। বিষয়: [যেমন: subset construction / CFL closure / Rice-এর theorem / NP-completeness reduction / Savitch] কঠিনতা: [সহজ / মাঝারি / কঠিন] ৮টি MCQ বানাও। প্রতিটির জন্য: ১. ঠিক ৪টি অপশন, শুধু একটি সঠিক। দরকারি machine বা grammar প্রশ্নেই থাকবে। ২. গোনা বা trace-এর প্রশ্নে একটি ছোট Python কোড দাও, যা brute force দিয়ে উত্তর মেলায়। ৩. কোনো উপপাদ্য ব্যবহার করলে তার সব শর্ত লেখো; reduction থাকলে দিক স্পষ্ট লেখো। ৪. খোলা প্রশ্ন (P বনাম NP, L বনাম NL ইত্যাদি) কখনো মীমাংসিত বলবে না। ৫. নিশ্চিত না হলে “নিশ্চিত নই” লেখো; কোনো প্রশ্নকে কোনো নির্দিষ্ট পরীক্ষার আসল প্রশ্ন বলে দাবি করবে না।

যাচাইয়ের চেকলিস্ট

কেন এই উত্তর ভুল? — রিভিশনের কৌশল আর বড় ধারণা

আগে নিজে ভাবুন, তারপর খুলে দেখুন।

প্র ০১Reduction-এর দিক এত বেশি MCQ-তে ফাঁদ হয় কেন?

কারণ “A ≤ B” চিহ্নটি পড়লে মনে হয় A নিয়ে কিছু প্রমাণ হচ্ছে, অথচ নতুন তথ্য যায় B-এর দিকে। চিহ্নের মানে “A, B-এর চেয়ে কঠিন নয়”: B-এর একটি সমাধান থাকলে A-ও সমাধান হয়। তাই A কঠিন জানা থাকলে কঠিনতা ডানে B-তে যায়, আর B সহজ জানা থাকলে সহজতা বাঁয়ে A-তে আসে।

  • ইতিহাস: Alan Turing ১৯৩৬ সালে halting-এর ধাঁচের প্রথম undecidable প্রশ্ন দেন; Emil Post ১৯৪৪ সালের একটি প্রভাবশালী প্রবন্ধে reducibility-কে নিজস্ব বিষয় হিসেবে দাঁড় করান। একই ধারণা polynomial সময়ে আসে Stephen Cook (১৯৭১) আর Leonid Levin (১৯৭৩)-এর হাতে, আর Richard Karp ১৯৭২ সালে ২১টি সমস্যাকে একে একে NP-complete দেখান (পর্ব ৫২, ৫৯, ৬১)।
  • দুই কাজ, দুই দিক: কঠিনতা প্রমাণে 3SAT ≤p X; বাস্তবে সমাধানের জন্য উল্টো, X ≤p SAT, যাতে একটি SAT solver কাজে লাগে (পর্ব ৭৩)।
  • শর্ত: mapping reduction-এ f সব input-এ থামে আর w ∈ A ⇔ f(w) ∈ B, দুই দিকেই; শুধু এক দিক দেখালে প্রমাণ অসম্পূর্ণ।

রিভিশনে প্রতিটি reduction-এর পাশে লিখুন: “কোনটি জানা, কোনটি নতুন?” জানা-কঠিন সমস্যা সবসময় বাঁয়ে। MCQ-এ যে অপশন বাঁয়ের সমস্যা সম্পর্কে নতুন সিদ্ধান্ত টানে, সেটি সাধারণত distractor.

একটি চেনা উদাহরণে নিয়মটি দেখুন। ATM ≤m HALTTM: ⟨M, w⟩ থেকে এমন ⟨M′, w⟩ লেখা হয়, যেখানে M′ চালায় M-কে আর বর্জনের বদলে loop করে; তাই M′ থামে ⇔ M গ্রহণ করে। ATM undecidable জানা, তাই সিদ্ধান্ত HALTTM-এর ওপর (পর্ব ৫১, ৫২)। উল্টো দিকে HALTTM ≤m ATM সত্য হলেও তা থেকে নতুন কিছু জানা যায় না। আরও দুটি সহায়ক তথ্য: একই f দিয়ে Ā ≤m B̄ হয়, আর ≤m transitive, তাই reduction-এর শিকল বানিয়ে একটি জানা সমস্যা থেকে দূরের সমস্যায় পৌঁছানো যায়। Turing reduction (oracle) বেশি সাধারণ, কিন্তু recognizability বহন করে না; সেজন্য co-recognizable প্রশ্নে mapping reduction লাগে।

মূল উপলব্ধি: ≤ চিহ্নের ডানে যে বসে, তার ওপরই নতুন রায়।

প্র ০২“প্রয়োজনীয়” আর “যথেষ্ট” শর্ত: pumping lemma দিয়ে regularity প্রমাণ করা যায় না কেন?

Pumping lemma বলে “regular ⇒ pump করে”; উল্টো দিক মিথ্যা। তাই lemma দিয়ে শুধু non-regularity প্রমাণ হয়: একটি s আর প্রতিটি বৈধ বিভাজনে একটি খারাপ i দেখালে। কোনো language pump করলেও তা regular হওয়ার প্রমাণ নয়; {aibjck : i = 0 বা j = k} pump করে, অথচ non-regular (পর্ব ১৭)।

  • ইতিহাস: pumping-এর ধারণা সাধারণত ১৯৬১ সালের Bar-Hillel, Perles আর Shamir-এর প্রবন্ধের সঙ্গে যুক্ত করা হয়, যেখানে context-free রূপটিও আছে (পর্ব ৩৬)। William Ogden ১৯৬৮ সালে চিহ্নিত অবস্থানের শক্তিশালী রূপ দেন।
  • “যদি এবং কেবল যদি” হাতিয়ার: Myhill (১৯৫৭) আর Nerode (১৯৫৮)-এর theorem বলে L regular ⇔ ≡L-এর class সসীম। এটি দুই দিকেই কাজ করে, তাই pumping যেখানে ব্যর্থ, সেখানে fooling set কাজে আসে (পর্ব ১৮)।
  • Closure-এর দিকও এক-মুখী: regular থেকে regular, কিন্তু “ফল regular, তাই উপাদান regular” সত্য নয় (পর্ব ১৬)।

MCQ-তে “L pump করে, তাই L regular” বা “pumping lemma-র শর্ত পূরণ হলে CFL” ধরনের অপশন সবসময় সন্দেহ করুন। কোনো উপপাদ্য পড়ার সময় তীরের দিক আলাদা করে লিখুন: ⇒ না ⇔?

একটি ছোট তুলনা দেখুন। {anbn}-এ s = apbp নিলে প্রতিটি বৈধ বিভাজনে y শুধু a, তাই i = 0-এ string ভাঙে: lemma কাজ করে। কিন্তু {aibjck : i = 0 বা j = k}-এ প্রতিপক্ষ সবসময় y-কে প্রথম অক্ষরে রাখতে পারেন, আর pump করার পরও string ভাষায় থাকে; তখন L ∩ ab∗c∗ দিয়ে ছেঁকে {abjcj} পাওয়া যায়, আর closure-এর যুক্তিতে non-regularity আসে। Context-free দিকেও একই কথা: unary ভাষায় CFL আর regular একই শ্রেণি (Parikh), তাই সেখানে aⁿ² ধাঁচের প্রশ্নে pumping-এর সঙ্গে গোনার যুক্তিও মেলানো দরকার। Pumping খেলার ক্রমটিও মনে রাখুন: প্রতিপক্ষ p দেন, আপনি |s| ≥ p-এর একটি s বাছেন, প্রতিপক্ষ বিভাজন দেন, আর আপনি একটি i দেখান। ক্রম উল্টে নিজে বিভাজন বাছলে প্রমাণ বাতিল, যদিও উত্তর হয়তো ঠিক ছিল (পর্ব ১৭, ৩৬)।

মূল উপলব্ধি: প্রয়োজনীয় শর্ত দিয়ে শুধু “না” প্রমাণ হয়; “হ্যাঁ” প্রমাণে লাগে যথেষ্ট শর্ত বা একটি নির্মাণ।

প্র ০৩Decidable, recognizable আর co-recognizable: চার ঘরের মানচিত্র কীভাবে মনে রাখবেন?

প্রতিটি language চার ঘরের একটিতে পড়ে: decidable (L আর L̄ দুটিই recognizable), শুধু recognizable, শুধু co-recognizable, আর কোনোটিই নয়। মূল সেতু একটি theorem: L decidable ⇔ L আর L̄ দুটিই recognizable (পর্ব ৫০)।

  • শুধু recognizable: ATM, HALTTM, PCP, আর ETM-এর complement. Turing ১৯৩৬ সালে diagonalization দিয়ে প্রথম এমন সীমা দেখান (পর্ব ৫১, ৫৪)।
  • শুধু co-recognizable: ETM আর ATM-এর complement; এদের “না” উত্তর খোঁজে পাওয়া যায়।
  • কোনোটিই নয়: EQTM, কারণ ATM দুই দিকেই এতে reduce হয় (পর্ব ৫২)।
  • Rice: Henry Rice-এর ১৯৫৩ সালে প্রকাশিত theorem বলে, recognizable language-এর প্রতিটি non-trivial ধর্ম undecidable (পর্ব ৫৩)।

গণিতের বাইরেও এই মানচিত্র দেখা যায়: Hilbert-এর দশম সমস্যা (পূর্ণসংখ্যার polynomial সমীকরণের সমাধান আছে কি না) recognizable কিন্তু undecidable; Davis, Putnam আর Robinson-এর কাজের ওপর দাঁড়িয়ে Matiyasevich ১৯৭০ সালে প্রমাণ শেষ করেন (পর্ব ৫৫)। “হ্যাঁ” দিকটি খোঁজে পাওয়া যায়, “না”-এর সাধারণ পদ্ধতি নেই।

প্রতিটি ঘরের পেছনে একটি কৌশল আছে। ETM-এর complement recognizable, কারণ dovetailing-এ round i-তে প্রথম i টি string-এ i ধাপ করে চালালে কোনো গৃহীত string থাকলে তা একসময় ধরা পড়ে (পর্ব ৫০)। Closure-এ পার্থক্য: decidable শ্রেণি complement-এ বদ্ধ, recognizable শ্রেণি বদ্ধ নয়; তাই একটি ভাষা recognizable আর তার complement-ও recognizable হলে সেটি সরাসরি decidable ঘরে চলে আসে। বাস্তবে এর মানে, PCP-এর মতো সমস্যায় খোঁজ একটি সমাধান পেলে থামে, কিন্তু “সমাধান নেই” বলার কোনো সাধারণ সীমা নেই; step cap-এ থামা তাই রায় নয়, শুধু “এখনো পাওয়া যায়নি”। দুর্বল মডেলে ছবিটি বদলে যায়: DFA-তে emptiness, equivalence সবই decidable, CFG-তে emptiness decidable কিন্তু equivalence নয়, আর TM-এ emptiness-ও undecidable (পর্ব ২০, ৩৭, ৫৩)। তাই প্রশ্নে কোন মডেল দেওয়া আছে, তা আগে দেখুন; একই প্রশ্ন DFA-তে সহজ আর TM-এ অসম্ভব হতে পারে।

মূল উপলব্ধি: কোন দিকের উত্তর খুঁজে পাওয়া যায়, তা জিজ্ঞেস করলেই ঘর ঠিক হয়।

প্র ০৪Complexity-র অন্তর্ভুক্তি: কোনটি প্রমাণিত, কোনটি খোলা, কোনটি শুধু বিশ্বাস?

শৃঙ্খলটি L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP পুরোটাই প্রমাণিত, কিন্তু কোন একক ধাপ কঠোর, তা প্রায় কোথাও জানা নেই। প্রমাণিত কঠোর শুধু দূরের জোড়া: P ⊊ EXP আর NL ⊊ PSPACE, hierarchy theorem থেকে। Juris Hartmanis আর Richard Stearns ১৯৬৫ সালে time hierarchy-র ভিত্তি দেন (পর্ব ৬৭)।

  • প্রমাণিত সমতা: Walter Savitch ১৯৭০ সালে দেখান PSPACE = NPSPACE (পর্ব ৬৪); Neil Immerman আর Róbert Szelepcsényi ১৯৮৭–৮৮ সালে আলাদাভাবে দেখান NL = coNL (পর্ব ৬৬)। ২০০২ সালে AKS দেখায় PRIMES ∈ P (পর্ব ৫৭)।
  • খোলা: P বনাম NP, NP বনাম coNP, L বনাম NL, P বনাম PSPACE, BPP বনাম P (P = BPP অনেকে বিশ্বাস করেন, প্রমাণ নেই), আর BQP বনাম NP-এর সম্পর্ক।
  • বাধা: Baker, Gill আর Solovay ১৯৭৫ সালে দেখান কিছু oracle-এ P = NP, কিছুতে নয়; তাই relativize করা কৌশল একা প্রশ্নটি মেটাতে পারে না। পরে natural proofs (১৯৯৪) আর algebrization (২০০৮) আরও দুই বাধা চিহ্নিত করে (পর্ব ৬৩)।

MCQ-তে “প্রমাণিত” শব্দটি দেখলেই মনের তালিকা মেলান। “বেশিরভাগ গবেষক মনে করেন” আর “প্রমাণিত” আলাদা দাবি; বাধাগুলোও অসম্ভবতার প্রমাণ নয়, শুধু কিছু কৌশলের সীমা।

প্রমাণিত ফলগুলোর অনুসিদ্ধান্তও MCQ-তে আসে। P = NP হলে NP = coNP আর PH = P হতো; কোনো NP-complete সমস্যা coNP-তে থাকলে NP = coNP; NP ⊆ P/poly হলে PH দ্বিতীয় স্তরে ধসে পড়ে (Karp–Lipton) (পর্ব ৬২, ৬৮, ৭০)। এগুলো সবই শর্তসাপেক্ষ বাক্য: “যদি … তবে …”, তাই শর্তটি নিজে প্রমাণিত না হলে সিদ্ধান্তও প্রমাণিত নয়। আরেকটি ফাঁদ: P ⊊ EXP প্রমাণিত বলে শৃঙ্খলের অন্তত একটি ধাপ কঠোর, কিন্তু কোনটি, তা অজানা। একইভাবে NL ⊊ PSPACE বলে L, NL, P, NP-এর অন্তত একটি PSPACE থেকে আলাদা, তবু নির্দিষ্ট কোনো জোড়ার কথা বলা যায় না। Randomness-এর দিকেও একই সতর্কতা: P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PSPACE প্রমাণিত, কিন্তু BPP-কে P-এর সমান বলা এখনো অনুমান, যদিও derandomization-এর ফলগুলো সেদিকে ইঙ্গিত করে (পর্ব ৬৯)।

মূল উপলব্ধি: প্রমাণিত কঠোরতা আসে একই সম্পদের বড় ফাঁক থেকে; পাশাপাশি দুই শ্রেণির পার্থক্য প্রায় সবই খোলা।

প্র ০৫গোনা আর trace-এর প্রশ্নে ছোট ক্ষেত্রে brute force কেন সবচেয়ে নির্ভরযোগ্য পাহারা?

গণনার তত্ত্বের সংখ্যা প্রায়ই সূত্র থেকে আসে: 2n subset, 2(পাতা + union + star) Thompson state, 2n − 1 ধাপ, Catalan সংখ্যা। Distractor বানানো হয় সূত্রের একটি অংশ বাদ দিয়ে: ε ভুলে যাওয়া, −1 বাদ, “proper” শর্ত বাদ। ছোট n-এ সব কিছু তালিকা করলে এমন ভুল সঙ্গে সঙ্গে ধরা পড়ে।

  • ইতিহাস: Michael Rabin আর Dana Scott ১৯৫৯ সালে NFA আর subset construction-এর ভিত্তি দেন, পরে Turing Award পান (পর্ব ১০)। Ken Thompson ১৯৬৮ সালে regex থেকে NFA বানিয়ে খোঁজার পদ্ধতি প্রকাশ করেন (পর্ব ১৪)। দুটিই এখনো এই পাতার মতো ছোট উদাহরণে হাতে যাচাই করা যায়।
  • যন্ত্র-যাচাই প্রমাণ: ২০২৪ সালে bbchallenge-এর সহযোগীরা S(5) = 47,176,870 প্রমাণ করেন, আর প্রমাণটি proof assistant-এ যাচাই করা হয় (পর্ব ৫৫)। বড় গোনার দাবিও এখন কোডে মেলানো হয়।
  • সীমা মনে রাখুন: সসীম পরীক্ষা ভুল ধরে, সব n-এ সত্যতা প্রমাণ করে না। Suffix পরীক্ষা Myhill–Nerode class-এর শুধু নিম্নসীমা দেয়, আর step cap-এ না থামা মানে “কখনো থামবে না” নয় (পর্ব ১৮, ৪৪)।

রিভিশনে প্রতিটি গোনার প্রশ্নে আগে সূত্র, তারপর n = 1, 2, 3-এ হাতে বা কোডে তালিকা। দুটি না মিললে সূত্রের কোন অংশ ভুল, সেটিই আসল শিক্ষা।

এই পাতাতেই কয়েকটি distractor এভাবে বানানো: ১০২৪ বনাম ১০২৩ (−1 বাদ), ৮ আর ১৫-এর বদলে ৮ আর ১৪ (ε বাদ), Thompson-এ ২২ (concatenation-কেও নতুন state ধরা), parse tree-র ১৭ বনাম ধাপের ১১ (পাতা গোনা)। প্রতিটি ক্ষেত্রে দৈর্ঘ্য ১ বা ২-এর একটি উদাহরণ হাতে লিখলেই ভুল অংশটি ধরা পড়ে। কোডে যাচাইয়ের সময় তিনটি অভ্যাস রাখুন: সংজ্ঞাটি আলাদা একটি সরল function-এ লিখুন, machine-এর ফল তার সঙ্গে সব ছোট string-এ মেলান, আর কোন দৈর্ঘ্য পর্যন্ত পরীক্ষা হলো তা আউটপুটেই ছাপুন, যাতে সীমাটি ভুলে না যান।

মূল উপলব্ধি: প্রমাণ সত্য প্রতিষ্ঠা করে, brute force ভুল ধরে; MCQ-তে দুটিই লাগে।

শেষ ধাপ — ক্রম সাজান আর স্কোর দেখুন

উপরের সব MCQ শেষ করলে নিচে আপনার মোট স্কোর দেখাবে।

ক্রমনতুন সমস্যা X NP-complete প্রমাণের ছয় ধাপ। আগে থেকে পরে সাজান (▲▼ চেপে সরান)

  1. X-এর decision রূপ লেখা, একটি bound k-সহ
  2. Polynomial verifier দিয়ে X ∈ NP দেখানো
  3. একটি জানা NP-complete সমস্যা বাছা, যেমন 3SAT
  4. Polynomial সময়ের f: 3SAT-এর instance থেকে X-এর instance
  5. φ satisfiable ⇔ f(φ) ∈ X, দুই দিকেই প্রমাণ
  6. উপসংহার: X NP-hard আর NP-তে, তাই NP-complete

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:

মনে রাখুন

  1. কারণসহ উত্তর: চাপার আগে খাতায় অপশন আর এক লাইনের কারণ; ভুলের খাতায় প্রশ্ন নয়, নিয়ম লিখুন।
  2. দুই সীমা: state-সংখ্যার প্রশ্নে distinguishable string নিম্নসীমা, একটি কাজের machine ওপরের সীমা।
  3. শর্ত আগে: complete DFA, |vxy| ≤ p, f(n) ≥ log n, non-trivial semantic ধর্ম: শর্ত না মিললে সিদ্ধান্ত নেই।
  4. দিক: A ≤ B-তে জানা-কঠিন A বাঁয়ে, নতুন রায় B-এর ওপর।
  5. প্রমাণিত বনাম খোলা: P ⊆ NP, P ⊊ EXP, NL ⊊ PSPACE, PSPACE = NPSPACE, NL = coNL প্রমাণিত; P বনাম NP, L বনাম NL খোলা।

পরের পর্বে: পর্ব ৮৩ “লিখিত ও মৌখিক (ভাইভা) প্রশ্ন — গণনার তত্ত্ব”: MCQ চেনায় কোনটি সঠিক, লিখিত পরীক্ষা আর ভাইভা চায় কেন সঠিক; সেখানে তুলনা আর ব্যাখ্যার আদর্শ উত্তর।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান