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

প্রমাণ লেখার অনুশীলন — pumping lemma, reduction আর diagonalization

Proof-Writing Practice in Theory of Computation — Closure Constructions, Pumping Lemmas, Myhill–Nerode, Decidability, Diagonalization, Mapping Reductions, Rice's Theorem and NP-Completeness, with Marking Rubrics and Flawed Proofs

Taught in Bangla, this practice page lays out proofs as written on paper: numbered steps with reasons and a marking rubric. It gives 30 model proofs in six groups, from closure constructions and pumping-lemma arguments to Myhill–Nerode, decidability, diagonalization, mapping reductions, Rice's theorem, NP-completeness and Savitch, plus six flawed proofs to correct. Ten in-page Python (Pyodide) blocks check each construction and pumping argument by brute force on small cases (brute force is not proof).

এই পর্বে যা শিখবেন

  • দাবির আকার দেখে হাতিয়ার বাছা: নির্মাণ, pumping, Myhill–Nerode, closure, diagonalization, reduction না Rice
  • Closure নির্মাণ আর grammar-এর সঠিকতা দুই দিকের inclusion দিয়ে লেখা
  • Pumping lemma-র প্রমাণ প্রতিপক্ষের খেলার ছকে, প্রতিটি ক্ষেত্রসহ, লেখা
  • Decider, recognizer আর mapping reduction-এর প্রমাণে দিক আর computability ঠিক রাখা
  • NP-completeness-এর দুই অংশ (NP-তে আছে, NP-hard) আর reduction-এর “⇔” দুই দিকেই প্রমাণ করা

১ · ToC প্রমাণের কাঠামো — দাবি পড়া, হাতিয়ার বাছা, লেখা, যাচাই

ক্রিকেটে DRS রিভিউয়ে তৃতীয় আম্পায়ার প্রতিটি ফ্রেম আলাদা করে দেখেন; একটি ফ্রেম বাদ পড়লে সিদ্ধান্ত টেকে না। পরীক্ষক আপনার প্রমাণও এভাবে পড়েন। গণনার তত্ত্বের প্রমাণে আরেকটি বাড়তি দিক আছে: অনেক প্রমাণ আসলে একজন প্রতিপক্ষের বিরুদ্ধে খেলা: pumping-এ প্রতিপক্ষ p আর বিভাজন বাছেন, diagonalization-এ “সব যন্ত্র” একসঙ্গে হারাতে হয়। তাই “একটি উদাহরণে মিলেছে” কখনো যথেষ্ট নয়। প্রমাণের ধরনগুলো পর্ব ০৪-এ শেখানো হয়েছে; এখানে সেগুলো খাতায় লেখার অনুশীলন।

চার ধাপের কাঠামো
পড়া (কোন শ্রেণি, কোন quantifier) → হাতিয়ার বাছাই → কারণসহ ধাপ, ∎ পর্যন্ত → ছোট ক্ষেত্রে যাচাই
  1. পড়া: দাবিটি কোন ধরনের? “L regular” (অস্তিত্ব: একটি যন্ত্র দেখান), “L regular নয়” (সব যন্ত্রের বিরুদ্ধে), “X undecidable” (কোনো decider নেই), “X NP-complete” (দুটি আলাদা দাবি)।
  2. হাতিয়ার: নিচের ছবির সংকেত দেখে বাছুন, আর প্রথম লাইনেই লিখুন: “বিরোধের জন্য ধরি L regular” বা “ATM ≤m X দেখাব”।
  3. লেখা: প্রতিটি লাইনের পাশে কারণ: সংজ্ঞা, lemma-র কোন শর্ত, কোন পর্বের উপপাদ্য। নির্মাণ থাকলে আগে নির্মাণ, তারপর আলাদা করে সঠিকতা।
  4. যাচাই: খসড়ায় ছোট p, ছোট string বা ছোট সূত্রে মেলান। মিলে গেলেও তা প্রমাণ নয়; না মিললে দাবি বা যুক্তি ভুল।

ছবি ৮৪.১ — দাবির আকার থেকে প্রমাণের হাতিয়ার

বাঁয়ে প্রশ্নে যা দেখবেন, ডানে প্রথমে যে হাতিয়ার চেষ্টা করবেন

From the shape of a claim to a proof tool L regular L regular নয় L context-freeনয় L(G) = L L decidable L undecidable L recognizableনয় L NP-complete যন্ত্র বা regex নির্মাণ+ সঠিকতার যুক্তি pumping (খেলা),Myhill–Nerode, closure CFL pumping, বাregular-এর সঙ্গে ছেদ ⊆ আর ⊇ আলাদা,দুটিতেই induction সবসময় থামে এমনdecider + সঠিকতা diagonalization, বাজানা A ≤m L L̄ recognizable আরL undecidable L ∈ NP, আর3SAT ≤p L দিকের নিয়ম: জানা-কঠিন বাঁয়ে, নতুন সমস্যা ডানে

ছবিটি প্রথম চেষ্টার দিক, নিয়ম নয়। একই দাবির একাধিক প্রমাণ থাকে: {0n1m : n ≠ m} সরাসরি pumping-এ কঠিন, কিন্তু closure দিয়ে তিন লাইনে হয় (৩.২)। নিচের stepper-এ একটি ১০ নম্বরের pumping উত্তর শুরু থেকে ∎ পর্যন্ত গড়া হয়েছে, প্রতিটি ধাপে জমা নম্বরসহ।

প্রতিটি ধাপের পর (উদাহরণে p = 4)
ধাপ
খাতায় যা লিখলেন
উদাহরণের string
জমা নম্বর
  1. অনুমান — ১ নম্বর। p-এর মান আপনি জানেন না, আর জানার দরকারও নেই। p = 4 শুধু উদাহরণ দেখানোর জন্য; খাতায় সব যুক্তি p দিয়ে।
  2. s বাছাই — আরও ২। s-কে L-এর সদস্য হতে হবে: apbp নিলে a আর b সমান, তাই s ∉ L, আর পুরো প্রমাণ অচল। এক বাড়তি a সমস্যাটি মেটায়।
  3. বিভাজন — নম্বর নেই। প্রতিপক্ষের চাল। উদাহরণের বিভাজনটি তাঁর একটি সম্ভাব্য চাল মাত্র; আপনি এটি বাছেননি, তাই পরের ধাপে সব বিভাজন একসঙ্গে ধরতে হবে।
  4. সাধারণ রূপ — আরও ৩। |xy| ≤ p থেকে y শুধু a. এই এক লাইনেই প্রতিপক্ষের সব চাল ধরা পড়ে; নম্বরের বড় অংশ এখানেই।
  5. i বাছাই — আরও ৩। Pump up (i = 2) a বাড়ায়, তাতে i > j আরও শক্ত হয়, string L-এই থাকে। তাই pump down (i = 0): a কমে বড়জোর p, আর b = p, তাই i > j ভাঙে।
  6. উপসংহার — শেষ ১। “প্রতিটি বৈধ বিভাজনে” কথাটি লিখুন, আর lemma-র কোন শর্তের সঙ্গে বিরোধ, তা বলুন। অংশ ৩-এর চেকার দেখায়: p = 1 থেকে 7-এর প্রতিটি বিভাজনে i = 2 string-কে L-এই রাখে, i = 0 প্রতিবার বাইরে পাঠায়।
প্রশ্নের ধরনপড়া ও হাতিয়ারনির্মাণ বা মূল চালসঠিকতা (সব ক্ষেত্র, দুই দিক)উপসংহার
৫ নম্বর১২১১
১০ নম্বর১–২৩–৪৩–৪১
অংশপ্রমাণের ধরনমূল পর্বপ্রশ্ন
২Closure নির্মাণ, grammar-এর সঠিকতা, CFG থেকে PDA০৮, ১০, ১৬, ২৫, ৩৪২.১–২.৫
৩Regular নয়: pumping, closure, Myhill–Nerode১৬–১৮৩.১–৩.৫
৪Context-free নয়: CFL pumping, closure৩৬, ৩৭৪.১–৪.৪
৫TM simulation, decidability৪৫, ৪৬, ৫০৫.১–৫.৫
৬Diagonalization, mapping reduction, Rice৫১–৫৩৬.১–৬.৬
৭NP-তে থাকা, NP-hardness, Savitch৫৮, ৫৯, ৬১, ৬৪৭.১–৭.৫
৮ভুল প্রমাণ ধরা আর সংশোধন১৭, ৩৬, ৫২, ৫৯৮.১–৮.৬

এই পাতার কোনো প্রশ্ন কোনো নির্দিষ্ট পরীক্ষা, বিশ্ববিদ্যালয় বা প্রতিষ্ঠান থেকে নেওয়া নয়; এ ধরনের প্রমাণ বিশ্ববিদ্যালয়ের কোর্সে, চাকরির লিখিত পরীক্ষায় আর গবেষণামুখী ইন্টারভিউতে প্রায়ই আসে। নম্বর-ভাগ শুধু অনুশীলনের জন্য। প্রতিটি প্রশ্ন আগে নিজে লিখুন, তারপর খুলে মেলান। নকশার সমস্যা (DFA, CFG, PDA, TM বানানো) পর্ব ৮১-এ; MCQ পর্ব ৮২-এ, লিখিত তুলনা ও ভাইভা পর্ব ৮৩-এ, আর ইন্টারভিউর প্রশ্ন পর্ব ৮৫-এ।



২ · অংশ ক — Closure নির্মাণ আর grammar-এর সঠিকতা

ঝালিয়ে নিন: পর্ব ০৮ · DFA নকশা (product construction), পর্ব ১০ · NFA থেকে DFA, পর্ব ১৬ · Closure property, পর্ব ২৫ · CFG, পর্ব ৩৪ · PDA আর CFG-এর সমতা. এই দলের প্রতিটি উত্তরে দুটি অংশ: আগে নির্মাণ (construction proof), তারপর আলাদা করে “কেন ঠিক”।

২.১প্রমাণ করুন: L regular হলে L̄ = Σ∗ ∖ L-ও regular. NFA-তে accepting আর non-accepting state অদলবদল করলে কেন একই যুক্তি চলে না, একটি উদাহরণ দিন। — ৫ নম্বর (সহজ)
  1. L regular, তাই L চেনে এমন একটি সম্পূর্ণ DFA M = (Q, Σ, δ, q0, F) আছে (NFA থেকে subset construction, দরকারে dead state যোগ করে)। — পর্ব ১০
  2. M′ = (Q, Σ, δ, q0, Q ∖ F) নিন: শুধু accepting state-এর সেট উল্টানো। — নির্মাণ
  3. M সম্পূর্ণ আর deterministic, তাই প্রতিটি w-এ δ̂(q0, w) ঠিক একটি state, আর M ও M′-এ সেটি একই। তাই w ∈ L(M′) ⇔ δ̂(q0, w) ∉ F ⇔ w ∉ L. — একই run, ভিন্ন F
  4. অতএব L(M′) = L̄, আর L̄ regular. ∎

NFA-তে কেন নয়: N-এ p থেকে a, b-তে p-তে ফেরা, আর a-তে f-এও যাওয়া; F = {f}. N চেনে “শেষ চিহ্ন a”. F উল্টে {p} করলে “a”-ও গৃহীত হয় (p → p পথে), অথচ “a” মূল language-এ আছে। NFA একটি string-এ অনেক পথ রাখে; একটি পথ accept আর আরেকটি reject করলে উল্টানো যন্ত্রও accept করে। নিচের চেকার এমন চারটি string দেখায়।

নম্বর-ভাগ: সম্পূর্ণ DFA-র উল্লেখ (১), নির্মাণ (১), “একটিই run” যুক্তি (২), NFA উদাহরণ (১)। যেখানে নম্বর কাটে: dead state বাদ দেওয়া partial DFA-তে F উল্টানো; তখন যে string dead state-এ পড়ত, সেগুলো দুই যন্ত্রেই বর্জিত হয়।

২.২Product construction দিয়ে প্রমাণ করুন: L1 আর L2 regular হলে L1 ∩ L2 regular. নির্মাণের সঠিকতা induction দিয়ে দেখান। — ১০ নম্বর (মাঝারি)
  1. M1 = (Q1, Σ, δ1, q1, F1) আর M2 = (Q2, Σ, δ2, q2, F2) সম্পূর্ণ DFA, L(Mi) = Li. — অনুমান
  2. M = (Q1 × Q2, Σ, δ, (q1, q2), F1 × F2), যেখানে δ((r, s), a) = (δ1(r, a), δ2(s, a)). — product construction
  3. দাবি: সব w-এ δ̂((q1, q2), w) = (δ̂1(q1, w), δ̂2(q2, w)). ভিত্তি w = ε: দুই দিকই (q1, q2). — |w|-এর ওপর induction
  4. ধাপ w = ua: δ̂(…, ua) = δ(δ̂(…, u), a) = δ((δ̂1(q1, u), δ̂2(q2, u)), a) = (δ̂1(q1, ua), δ̂2(q2, ua)). — hypothesis, তারপর δ-র সংজ্ঞা
  5. তাই w ∈ L(M) ⇔ δ̂1(q1, w) ∈ F1 আর δ̂2(q2, w) ∈ F2 ⇔ w ∈ L1 ∩ L2. ∎ — F = F1 × F2

নম্বর-ভাগ: পূর্ণ tuple (২), δ-র সংজ্ঞা (২), invariant আর তার induction (৪), “⇔” উপসংহার (২)। যেখানে নম্বর কাটে: invariant না লিখে “দুই যন্ত্র একসঙ্গে চলে, তাই ঠিক” লেখা; ∪-এর প্রশ্নে F = F1 × F2 লেখা (∪-এ লাগে (F1 × Q2) ∪ (Q1 × F2), আর তখন দুটি DFA-ই সম্পূর্ণ হতে হয়)।

২.৩প্রমাণ করুন: L regular হলে LR = {wR : w ∈ L} regular. — ১০ নম্বর (মাঝারি)

নির্মাণ: L-এর DFA M = (Q, Σ, δ, q0, F) থেকে ε-NFA N = (Q ∪ {s}, Σ, δR, s, {q0}); s থেকে F-এর প্রতিটি state-এ ε-তীর, আর δR(p, a) = {q : δ(q, a) = p}, অর্থাৎ প্রতিটি তীর উল্টো।

  1. (⇒) w = a1⋯an ∈ L হলে M-এর run r0 = q0, r1, …, rn ∈ F আছে, যেখানে δ(ri−1, ai) = ri. — DFA-র গ্রহণ
  2. δR-এর সংজ্ঞায় ri−1 ∈ δR(ri, ai). তাই N-এ পথ s → rn → rn−1 → ⋯ → r0 = q0, যা an⋯a1 = wR পড়ে accepting state-এ থামে। — পথ উল্টো পড়া
  3. (⇐) N v = b1⋯bn গ্রহণ করলে একটি পথ s → t0 ∈ F → t1 → ⋯ → tn = q0 আছে, যেখানে δ(ti, bi) = ti−1. উল্টো ক্রমে এটি M-এর একটি run: q0 থেকে bn⋯b1 = vR পড়ে t0 ∈ F-এ। তাই vR ∈ L, অর্থাৎ v ∈ LR. — একই সংজ্ঞা, উল্টো দিকে
  4. L(N) = LR, আর NFA-র language regular. ∎ — subset construction

নম্বর-ভাগ: নির্মাণ (৩), ⇒ (৩), ⇐ (৩), উপসংহার (১)। যেখানে নম্বর কাটে: “উল্টানো যন্ত্রটি DFA” লেখা (একটি state-এ একই চিহ্নের অনেক তীর ঢুকতে পারে, উল্টালে তা nondeterminism); |F| > 1 হলেও একটিমাত্র শুরু ধরা; শুধু ⇒ দিক লেখা। Regex পথেও প্রমাণ হয়: R-এর গঠনের ওপর structural induction, (R1R2)R = R2RR1R.

from itertools import product
W = lambda n: ["".join(t) for k in range(n + 1) for t in product("ab", repeat=k)]
def nfa_accepts(d, starts, F, w):          # d[(state, symbol)] -> set of states
    cur = set(starts)
    for c in w: cur = {r for q in cur for r in d.get((q, c), ())}
    return bool(cur & F)
# 2.1: NFA for "ends with a": p loops on a, b and also guesses p -a-> f
N = {("p", "a"): {"p", "f"}, ("p", "b"): {"p"}}
flip = [w for w in W(6) if nfa_accepts(N, {"p"}, {"p"}, w) != (not w.endswith("a"))]
print("2.1 NFA with F flipped, wrong on:", flip[:4])
# 2.2: product DFA for (#a even) AND (ends with b)
D1 = {(e, c): e ^ (c == "a") for e in (0, 1) for c in "ab"}       # 0 = even
D2 = {(s, c): int(c == "b") for s in (0, 1) for c in "ab"}       # 1 = last is b
P = {((e, s), c): (D1[(e, c)], D2[(s, c)]) for e in (0, 1) for s in (0, 1) for c in "ab"}
def run(d, q, w):
    for c in w: q = d[(q, c)]
    return q
bad = [w for w in W(10) if (run(P, (0, 0), w) == (0, 1)) != (w.count("a") % 2 == 0 and w.endswith("b"))]
print("2.2 product mismatches up to length 10:", bad)
# 2.3: reverse every arrow of a DFA for "contains ab"; start = old F, F = {old start}
C = {(0, "a"): 1, (0, "b"): 0, (1, "a"): 1, (1, "b"): 2, (2, "a"): 2, (2, "b"): 2}
R = {}
for (q, c), r in C.items(): R.setdefault((r, c), set()).add(q)
bad = [w for w in W(10) if nfa_accepts(R, {2}, {0}, w) != ("ab" in w[::-1])]
print("2.3 reversal mismatches up to length 10:", bad)

আসল আউটপুট (ব্রাউজারের Python):

2.1 NFA with F flipped, wrong on: ['a', 'aa', 'ba', 'aaa']
2.2 product mismatches up to length 10: []
2.3 reversal mismatches up to length 10: []

প্রথম লাইন ২.১-এর সাবধানবাণী: NFA-র F উল্টানোর পরেও “a”, “aa”, “ba”, “aaa” গৃহীত হয়, অথচ এগুলো a দিয়ে শেষ, তাই complement-এ থাকার কথা নয়। দ্বিতীয় লাইনে product যন্ত্র দৈর্ঘ্য ১০ পর্যন্ত সব string-এ “a জোড় সংখ্যক আর শেষে b” সংজ্ঞার সঙ্গে মেলে (অমিল [])। তৃতীয় লাইনে “ab আছে”-র DFA-র তীর উল্টে পাওয়া NFA ঠিক সেই string নেয়, যাদের reversal-এ ab আছে।

২.৪G: S → aSb ∣ aS ∣ ε. প্রমাণ করুন: L(G) = {aibj : i ≥ j ≥ 0}. — ১০ নম্বর (মাঝারি)

দুটি set সমান দেখাতে দুই দিকের inclusion (double inclusion).

  1. (⊆) দাবি: S থেকে আসা প্রতিটি sentential form হয় aiSbj, নয় aibj, যেখানে i ≥ j. Derivation-এর ধাপের ওপর induction; ভিত্তি: S = a0Sb0. — invariant
  2. ধাপ: একটিমাত্র variable S, তার তিন নিয়ম। aiSbj থেকে S → aSb দেয় ai+1Sbj+1, S → aS দেয় ai+1Sbj, S → ε দেয় aibj; তিনটিতেই i ≥ j টিকে থাকে। — নিয়ম গুনে দেখা
  3. L(G)-এর string-এ variable নেই, তাই তা aibj, i ≥ j: L(G) ⊆ L. — invariant-এর ফল
  4. (⊇) aibj, i ≥ j দেওয়া। S → aS নিয়ম i − j বার: S ⇒∗ ai−jS; তারপর S → aSb j বার: ⇒∗ ai−jajSbj; শেষে S → ε: aibj. তাই L ⊆ L(G). ∎ — স্পষ্ট derivation

নম্বর-ভাগ: দুই দিকের ঘোষণা (১), invariant আর induction (৪), ⊆-এর উপসংহার (১), ⊇-এর derivation (৩), সমতা (১)। যেখানে নম্বর কাটে: কয়েকটি ছোট string উৎপন্ন করে দেখানো (উদাহরণ প্রমাণ নয়); শুধু ⊇ দিক লেখা, যা বলে না grammar বাড়তি কিছু তৈরি করে কি না।

২.৫প্রমাণের রূপরেখা দিন: প্রতিটি context-free language কোনো PDA চেনে। ২.৪-এর G থেকে PDA-র নিয়মগুলো লিখুন। — ১০ নম্বর (কঠিন)

CFG থেকে PDA (Sipser-এর তিন-state রূপ): qstart → qloop: “ε, ε → S$” (প্রথমে $, তার ওপরে S); qloop-এ প্রতিটি নিয়ম A → w-এর জন্য “ε, A → w”, প্রতিটি terminal a-এর জন্য “a, a → ε”; qloop → qaccept: “ε, $ → ε”.

  1. G-এর জন্য qloop-এর নিয়ম: ε, S → aSb; ε, S → aS; ε, S → ε; a, a → ε; b, b → ε. — নির্মাণ
  2. Invariant: input-এর u অংশ পড়া হয়েছে আর stack-এ γ$ (ওপর বাঁয়ে) থাকলে, S ⇒∗ uγ একটি leftmost derivation-এ। — stack = sentential form-এর বাকি অংশ
  3. Variable ওপরে থাকলে PDA একটি নিয়ম অনুমান করে (leftmost derivation-এর এক ধাপ); terminal ওপরে থাকলে input-এর পরের চিহ্নের সঙ্গে মেলায়। — nondeterminism অনুমানের কাজ করে
  4. $ ওপরে এলে আর input শেষ হলে γ = ε, তাই S ⇒∗ w: গৃহীত string L(G)-এ। উল্টো দিকে w-এর যেকোনো leftmost derivation ধাপে ধাপে অনুসরণ করা যায়, তাই L(G)-এর প্রতিটি w গৃহীত। ∎ — দুই দিক

নম্বর-ভাগ: তিন ধরনের নিয়ম (৩), G-এর নিয়ম (২), invariant (৩), দুই দিকের উপসংহার (২)। যেখানে নম্বর কাটে: শুরুতে $ না রাখা (তখন খালি stack পরীক্ষা করা যায় না); terminal মেলানোর নিয়ম ভুলে যাওয়া; যন্ত্রটিকে deterministic বলা। উল্টো দিক (PDA থেকে CFG, Apq variable) পর্ব ৩৪-এ।

from itertools import product
G = {"S": ["aSb", "aS", ""]}                # 2.4: S -> aSb | aS | eps
N = 8
ALL = ["".join(t) for k in range(N + 1) for t in product("ab", repeat=k)]
L = {w for w in ALL if w == "a" * w.count("a") + "b" * w.count("b") and w.count("a") >= w.count("b")}
def generate(G, n):                         # terminal strings of length <= n
    seen, todo, out = {"S"}, ["S"], set()
    while todo:
        f = todo.pop()
        i = next((k for k, c in enumerate(f) if c in G), None)
        if i is None: out.add(f); continue
        for rhs in G[f[i]]:                 # expand the leftmost variable
            g = f[:i] + rhs + f[i + 1:]
            if len(g) <= n + 1 and g not in seen: seen.add(g); todo.append(g)
    return out
gen = generate(G, N)
print("2.4 |L(G)| =", len(gen), "| |L| =", len(L), "| equal:", gen == L)
def pda_accepts(w):                         # 2.5: the loop state of the PDA, stack top = left
    todo, seen = [(0, "S")], set()
    while todo:
        i, st = todo.pop()
        if (i, st) in seen or len(st) > len(w) + 1: continue
        seen.add((i, st))
        if not st:
            if i == len(w): return True
        elif st[0] in G: todo += [(i, rhs + st[1:]) for rhs in G[st[0]]]
        elif i < len(w) and w[i] == st[0]: todo.append((i + 1, st[1:]))
    return False
print("2.5 PDA == L on all", len(ALL), "strings:", all(pda_accepts(w) == (w in L) for w in ALL))

আসল আউটপুট (ব্রাউজারের Python):

2.4 |L(G)| = 25 | |L| = 25 | equal: True
2.5 PDA == L on all 511 strings: True

দৈর্ঘ্য ৮ পর্যন্ত G ঠিক ২৫টি string তৈরি করে, আর সংজ্ঞা থেকে গোনা L-এও ২৫টি (j = 0 থেকে 4: 9 + 7 + 5 + 3 + 1), দুটি set হুবহু এক। দ্বিতীয় লাইনে ২.৫-এর এক-লুপের PDA (stack-এর ওপর বাঁয়ে) {a, b}-এর দৈর্ঘ্য ৮ পর্যন্ত সব ৫১১টি string-এ L-এর সঙ্গে মেলে। এগুলো ভুল ধরার জাল; সাধারণ প্রমাণ ওপরের induction.

৩ · অংশ খ — Regular নয়: pumping, closure আর Myhill–Nerode

ঝালিয়ে নিন: পর্ব ১৭ · Pumping lemma, পর্ব ১৮ · Myhill–Nerode, পর্ব ১৬-এর অংশ ৭. Pumping lemma শুধু প্রয়োজনীয় শর্ত; তাই এটি দিয়ে কেবল “regular নয়” প্রমাণ হয়, কখনো “regular” নয়। প্রমাণ সবসময় প্রতিপক্ষের খেলা: p আর বিভাজন প্রতিপক্ষের, s আর i আপনার।

৩.১Pumping lemma দিয়ে প্রমাণ করুন: L = {aibj : i > j ≥ 0} regular নয়। — ১০ নম্বর (মাঝারি)
  1. বিরোধের জন্য ধরি L regular; lemma একটি pumping length p দেয়। — contradiction
  2. s = ap+1bp নিন: p + 1 > p, তাই s ∈ L; |s| = 2p + 1 ≥ p. — s আপনার চাল
  3. যেকোনো বিভাজন s = xyz, |xy| ≤ p, |y| ≥ 1. s-এর প্রথম p চিহ্ন a, তাই y = ak, 1 ≤ k ≤ p. — সব বিভাজন একসঙ্গে
  4. i = 0: xz = ap+1−kbp. k ≥ 1, তাই a-র সংখ্যা ≤ p = b-র সংখ্যা: xz ∉ L. — pump down
  5. প্রতিটি বৈধ বিভাজনে lemma-র শর্ত ৩ ভাঙে, তাই L regular নয়। ∎

নম্বর-ভাগ: অনুমান (১), s আর s ∈ L (২), y-এর সাধারণ রূপ (৩), i = 0 আর কারণ (৩), উপসংহার (১)। যেখানে নম্বর কাটে: i = 2 নেওয়া: a বাড়লে i > j আরও সত্য হয়, তাই কোনো বিরোধ নেই (চেকার সব বিভাজনে তা দেখায়); s = apbp নেওয়া, যা L-এই নেই।

৩.২Closure property দিয়ে প্রমাণ করুন: L = {0n1m : n ≠ m} regular নয়। — ৫ নম্বর (মাঝারি)
  1. বিরোধের জন্য ধরি L regular. — অনুমান
  2. Regular language complement (২.১) আর ছেদে (২.২) বদ্ধ, আর 0∗1∗ regular; তাই L̄ ∩ 0∗1∗ regular. — closure
  3. L̄-এ 0∗1∗ আকারের বাইরের সব string আর 0n1n; ছেদ নিলে বাইরের অংশ বাদ যায়: L̄ ∩ 0∗1∗ = {0n1n : n ≥ 0}. — set-এর হিসাব
  4. কিন্তু {0n1n} regular নয় (পর্ব ১৭)। বিরোধ; L regular নয়। ∎

নম্বর-ভাগ: কোন closure কেন (২), ছেদের হিসাব (২), উপসংহার (১)। সরাসরি pumping এখানে কঠিন; closure পথটি নিরাপদ।

৩.৩Myhill–Nerode দিয়ে প্রমাণ করুন: PAL = {w ∈ {a, b}∗ : w = wR} regular নয়। S = {ai : i ≥ 0} নিলে z = ai কেন কাজ করে না, আর কোন z করে, তাও বলুন। — ১০ নম্বর (মাঝারি)
  1. S = {aib : i ≥ 0} নিন; S অসীম। — fooling set
  2. i ≠ j হলে z = ai নিন। aibai palindrome, তাই ∈ PAL. — সরাসরি
  3. ajbai-এ ঠিক একটি b; palindrome হলে b-টি মাঝখানে থাকত আর দুই পাশে সমান a থাকত। j ≠ i, তাই ∉ PAL. — একমাত্র b-এর অবস্থান
  4. S-এর প্রতিটি জোড়া distinguishable, তাই ≡PAL-এর class অসীম, আর Myhill–Nerode theorem অনুযায়ী PAL regular নয়। ∎

{ai} নিলে: z = ai বা অন্য কোনো শুধু-a z চলে না, কারণ ai+i আর aj+i দুটিই palindrome. তবে z = bai নিলে aibai ∈ PAL কিন্তু ajbai ∉ PAL, তাই {ai}-ও বৈধ fooling set; b-টি একটি “দেয়াল” বসায়, যার দুই পাশ মেলাতে হয়। নম্বর-ভাগ: S (২), z (২), দুই সদস্যতা কারণসহ (৪), উপপাদ্যের নাম আর উপসংহার (২)।

৩.৪k ≥ 1. Lk = {w ∈ {0, 1}∗ : |w| ≥ k আর শেষ থেকে k-তম চিহ্ন 1}. প্রমাণ করুন: Lk চেনে এমন প্রতিটি DFA-তে অন্তত 2kটি state লাগে। — ১০ নম্বর (কঠিন)
  1. S = {0, 1}k, দৈর্ঘ্য k-এর সব string; |S| = 2k. — প্রার্থী সেট
  2. x ≠ y ∈ S নিন; i = প্রথম অবস্থান যেখানে তারা আলাদা (1 ≤ i ≤ k). সাধারণতা না হারিয়ে xi = 1, yi = 0. — নামকরণ
  3. z = 0i−1. |xz| = k + i − 1, তাই xz-এর শেষ থেকে k-তম চিহ্ন অবস্থান (k + i − 1) − k + 1 = i-তে: xi = 1, অর্থাৎ xz ∈ Lk; একইভাবে yz-এ সেখানে 0, তাই yz ∉ Lk. — অবস্থান গোনা
  4. S-এর সব জোড়া distinguishable. কোনো DFA-তে 2k-এর কম state থাকলে pigeonhole নীতিতে S-এর দুটি string একই state-এ থামত, আর তাদের z-এ একই উত্তর দিত: ভুল। ∎

নম্বর-ভাগ: S (২), i আর z-এর বাছাই (৩), অবস্থানের হিসাব (৩), pigeonhole উপসংহার (২)। অথচ “শেষ থেকে k-তম 1” অনুমান করা NFA-তে k + 1টি state যথেষ্ট; NFA থেকে DFA-তে সূচকীয় ফাঁক যে সত্যিই আসতে পারে, এটিই তার প্রমাণ (পর্ব ১০)।

৩.৫দাবি: “L = {anbn : 0 ≤ n ≤ 1000} regular নয়, কারণ anbn regular নয়।” দাবিটি সত্য না মিথ্যা? প্রমাণ দিন। — ৫ নম্বর (সহজ)
  1. L-এ ঠিক ১০০১টি string, তাই L সসীম। — গোনা
  2. প্রতিটি সসীম language regular: প্রতিটি string একটি regex, আর সসীম সংখ্যক regex-এর ∪ আবার regex. — সংজ্ঞা আর closure
  3. তাই দাবিটি মিথ্যা; L regular. Pumping lemma-ও বিরোধ দেয় না: প্রতিপক্ষ p = 2001 নিলে L-এ |s| ≥ p এমন কোনো s নেই। ∎

নম্বর-ভাগ: “মিথ্যা” (১), সসীমতা (১), সসীম ⇒ regular কারণসহ (২), pumping কেন অচল (১)। শিক্ষা: non-regularity আসে অসীম গণনা থেকে।

from itertools import product
def splits(s, p):                          # every x, y, z with |xy| <= p and |y| >= 1
    for j in range(1, p + 1):
        for i in range(j):
            yield s[:i], s[i:j], s[j:]
in_L = lambda w: w == "a" * w.count("a") + "b" * w.count("b") and w.count("a") > w.count("b")
for p in range(1, 8):                      # 3.1: s = a^(p+1) b^p
    S = list(splits("a" * (p + 1) + "b" * p, p))
    up = sum(in_L(x + y * 2 + z) for x, y, z in S)    # splits where i = 2 stays in L
    down = sum(in_L(x + z) for x, y, z in S)          # splits where i = 0 stays in L
    print(f"3.1 p={p} splits={len(S):2}  i=2 stays in L: {up:2}  i=0 stays in L: {down}")
# 3.2: complement of {0^n 1^m : n != m}, intersected with 0*1*, is exactly {0^n 1^n}
W = ["".join(t) for k in range(11) for t in product("01", repeat=k)]
in_01 = lambda w: w == "0" * w.count("0") + "1" * w.count("1")
L2 = lambda w: in_01(w) and w.count("0") != w.count("1")
print("3.2:", sorted((w for w in W if not L2(w) and in_01(w)), key=len))
# 3.3: palindromes, x = a^i b, z = a^i: xz is a palindrome, a^j b a^i is not
pal = lambda w: w == w[::-1]
print("3.3 fooling pairs ok (i, j < 8):", all(pal("a"*i+"b"+"a"*i) and not pal("a"*j+"b"+"a"*i)
      for i in range(8) for j in range(8) if i != j))
for k in range(1, 5):                      # 3.4: k-th symbol from the end is 1
    X = ["".join(t) for t in product("01", repeat=k)]
    ok = all((x + "0" * i)[-k] != (y + "0" * i)[-k]
             for x in X for y in X if x != y
             for i in [next(t for t in range(k) if x[t] != y[t])])
    print(f"3.4 k={k}: {len(X)} strings pairwise distinguishable: {ok}")

আসল আউটপুট (ব্রাউজারের Python):

3.1 p=1 splits= 1  i=2 stays in L:  1  i=0 stays in L: 0
3.1 p=2 splits= 3  i=2 stays in L:  3  i=0 stays in L: 0
3.1 p=3 splits= 6  i=2 stays in L:  6  i=0 stays in L: 0
3.1 p=4 splits=10  i=2 stays in L: 10  i=0 stays in L: 0
3.1 p=5 splits=15  i=2 stays in L: 15  i=0 stays in L: 0
3.1 p=6 splits=21  i=2 stays in L: 21  i=0 stays in L: 0
3.1 p=7 splits=28  i=2 stays in L: 28  i=0 stays in L: 0
3.2: ['', '01', '0011', '000111', '00001111', '0000011111']
3.3 fooling pairs ok (i, j < 8): True
3.4 k=1: 2 strings pairwise distinguishable: True
3.4 k=2: 4 strings pairwise distinguishable: True
3.4 k=3: 8 strings pairwise distinguishable: True
3.4 k=4: 16 strings pairwise distinguishable: True

প্রথম সাতটি লাইন ৩.১-এর প্রতিপক্ষ: p = 1 থেকে 7-এ সব বৈধ বিভাজনে (p = 7-এ ২৮টি) i = 2 string-কে L-এই রাখে, আর i = 0 একবারও রাখে না। তাই pump up দিয়ে লেখা প্রমাণ শূন্য, pump down দিয়ে পূর্ণ। 3.2 দেখায়, দৈর্ঘ্য ১০ পর্যন্ত L̄ ∩ 0∗1∗ ঠিক ε, 01, 0011, …; 3.3 i, j < 8-এর সব জোড়ায় fooling যুক্তি মেলায়; 3.4 k = 1 থেকে 4-এ 2kটি string-এর প্রতিটি জোড়া ঠিক z = 0i−1 দিয়ে আলাদা হয়।

৪ · অংশ গ — Context-free নয়: CFL pumping আর closure

ঝালিয়ে নিন: পর্ব ৩৬ · CFL-এর pumping lemma, পর্ব ৩৭ · CFL-এর closure আর decision. CFL pumping lemma: s = uvxyz, |vy| ≥ 1, |vxy| ≤ p, সব i ≥ 0-এ uvixyiz ∈ L. মনে রাখুন, |vxy| ≤ p শুধু দৈর্ঘ্যের সীমা; vxy s-এর যেকোনো জায়গায় বসতে পারে।

৪.১প্রমাণ করুন: L = {anbncn : n ≥ 0} context-free নয়। — ১০ নম্বর (মাঝারি)
  1. বিরোধের জন্য ধরি L context-free; lemma একটি p দেয়। s = apbpcp ∈ L, |s| = 3p ≥ p. — অনুমান, s বাছাই
  2. যেকোনো বিভাজন s = uvxyz, |vy| ≥ 1, |vxy| ≤ p. শেষ a আর প্রথম c-এর মাঝে p টি b, তাই vxy-তে a আর c একসঙ্গে নেই। — |vxy| ≤ p
  3. ক্ষেত্র ১: v বা y-তে দুই রকম চিহ্ন (যেমন v = ab). i = 2-এ “ab ab” দেখা দেয়, a∗b∗c∗ ক্রম ভাঙে: ∉ L. — ক্রম
  4. ক্ষেত্র ২: v আর y প্রতিটি এক রকম চিহ্নের (বা ফাঁকা)। i = 2-এ vy-এর চিহ্নগুলোর সংখ্যা বাড়ে (|vy| ≥ 1), কিন্তু ধাপ ২ অনুযায়ী অন্তত একটি চিহ্ন অছোঁয়া, তার সংখ্যা p-ই থাকে: তিন সংখ্যা সমান নয়, ∉ L. — গণনা
  5. দুই ক্ষেত্র সব সম্ভাবনা ঢাকে; প্রতিটিতে বিরোধ, তাই L context-free নয়। ∎

নম্বর-ভাগ: অনুমান আর s (২), “a আর c একসঙ্গে নয়” কারণসহ (২), ক্ষেত্র ১ (২), ক্ষেত্র ২ (৩), ক্ষেত্রের পূর্ণতা (১)। যেখানে নম্বর কাটে: “vxy প্রথম p চিহ্নে” লেখা (এটি regular lemma-র |xy| ≤ p); ক্ষেত্র ১ ভুলে যাওয়া; “v = a, y = b ধরি” লিখে একটি বিভাজন বাছা।

৪.২প্রমাণ করুন: L = {ambncmdn : m, n ≥ 0} context-free নয়। — ১০ নম্বর (কঠিন)
  1. বিরোধের জন্য ধরি L CFL, p তার pumping length; s = apbpcpdp ∈ L. — প্রতিটি খণ্ড অন্তত p লম্বা
  2. যেকোনো বৈধ বিভাজনে |vxy| ≤ p, তাই vxy বড়জোর দুটি পাশাপাশি খণ্ড ছোঁয়: (a, b), (b, c) বা (c, d), অথবা একটি খণ্ড। — দৈর্ঘ্যের সীমা
  3. ক্ষেত্র ১: v বা y-তে দুই রকম চিহ্ন। i = 2-এ a∗b∗c∗d∗ ক্রম ভাঙে: ∉ L. — ক্রম
  4. ক্ষেত্র ২: v, y প্রতিটি এক রকম। শর্তের জোড়া (a, c) আর (b, d); কোনো জোড়ার দুই সদস্য পাশাপাশি নয়। vy অন্তত একটি খণ্ড বদলায়, আর তার জোড়ার সঙ্গী খণ্ড vxy-এর বাইরে, তাই i = 2-এ একটির সংখ্যা p-এর বেশি, সঙ্গীটি p: ∉ L. — জোড়ার সঙ্গী অছোঁয়া
  5. সব বিভাজনে বিরোধ; L context-free নয়। ∎

নম্বর-ভাগ: s (১), “পাশাপাশি দুই খণ্ড” (৩), ক্ষেত্র ১ (২), ক্ষেত্র ২-এর জোড়া-সঙ্গী যুক্তি (৩), উপসংহার (১)। যেখানে নম্বর কাটে: |vxy| ≤ p ব্যবহার না করা: তখন v = a, y = c একসঙ্গে বাড়লে string L-এই থাকে, আর প্রমাণ আটকে যায়।

৪.৩প্রমাণ করুন: EQ3 = {w ∈ {a, b, c}∗ : w-এ a, b আর c সমান সংখ্যক} context-free নয়। — ৫ নম্বর (মাঝারি)
  1. বিরোধের জন্য ধরি EQ3 CFL. CFL আর regular language-এর ছেদ CFL (PDA × DFA নির্মাণ, পর্ব ৩৭)। — closure
  2. a∗b∗c∗ regular, আর EQ3 ∩ a∗b∗c∗ = {anbncn}. — set-এর হিসাব
  3. ৪.১ অনুযায়ী এটি CFL নয়: বিরোধ। ∎

নম্বর-ভাগ: সঠিক closure (দুটি CFL-এর ছেদ নয়, regular-এর সঙ্গে ছেদ) (২), ছেদের হিসাব (২), উপসংহার (১)। যেখানে নম্বর কাটে: “CFL ছেদে বদ্ধ” লেখা — মিথ্যা (৪.৪)।

৪.৪প্রমাণ করুন: context-free language ছেদ আর complement-এ বদ্ধ নয়। — ১০ নম্বর (মাঝারি)
  1. L1 = {anbncm}: S → TC, T → aTb ∣ ε, C → cC ∣ ε. L2 = {ambncn}: S → AU, A → aA ∣ ε, U → bUc ∣ ε. দুটিই CFL. — grammar দিয়ে সাক্ষী
  2. L1 ∩ L2 = {anbncn}: প্রথমটি a = b চায়, দ্বিতীয়টি b = c. এটি CFL নয় (৪.১)। তাই ছেদে বদ্ধতা মিথ্যা। — counterexample
  3. ধরি CFL complement-এ বদ্ধ। CFL ∪-এ বদ্ধ (S → S1 ∣ S2), তাই L1 ∩ L2 = L̄1 ∪ L̄2 CFL হতো (De Morgan). ধাপ ২-এর বিরোধ। ∎ — De Morgan

নম্বর-ভাগ: দুটি grammar (৩), ছেদের হিসাব আর ৪.১-এর উল্লেখ (৩), De Morgan যুক্তি (৩), উপসংহার (১)। সতর্কতা: deterministic CFL complement-এ বদ্ধ (পর্ব ৩৫), তাই “সব CFL” কথাটি স্পষ্ট লিখুন।

import re
from itertools import product
def splits(s, p):                     # every u, v, x, y, z with |vxy| <= p and |vy| >= 1
    n = len(s)
    for a in range(n):
        for b in range(a, n + 1):
            for c in range(b, n + 1):
                for d in range(c, min(a + p, n) + 1):
                    if (b - a) + (d - c) >= 1:
                        yield s[:a], s[a:b], s[b:c], s[c:d], s[d:]
def pump(t, i): u, v, x, y, z = t; return u + v * i + x + y * i + z
def L42(w):                           # 4.2: a^m b^n c^m d^n
    m = re.fullmatch(r"(a*)(b*)(c*)(d*)", w)
    return bool(m) and len(m[1]) == len(m[3]) and len(m[2]) == len(m[4])
for p in range(1, 5):
    S = list(splits("a" * p + "b" * p + "c" * p + "d" * p, p))
    wins = [t for t in S if L42(pump(t, 0)) and L42(pump(t, 2))]
    up = sum(L42(pump(t, 2)) for t in S); down = sum(L42(pump(t, 0)) for t in S)
    print(f"4.2 p={p} splits={len(S):4}  adversary wins: {len(wins)}  stay with i=2: {up}  stay with i=0: {down}")
# 4.3: (#a = #b = #c) intersected with a*b*c* gives exactly a^n b^n c^n
W = ["".join(t) for k in range(10) for t in product("abc", repeat=k)]
eq = [w for w in W if w.count("a") == w.count("b") == w.count("c") and re.fullmatch("a*b*c*", w)]
print("4.3:", ["ε" if not w else w for w in eq])
# 4.4: L1 = a^n b^n c^m and L2 = a^m b^n c^n meet in a^n b^n c^n
L1 = lambda w: (m := re.fullmatch(r"(a*)(b*)(c*)", w)) and len(m[1]) == len(m[2])
L2 = lambda w: (m := re.fullmatch(r"(a*)(b*)(c*)", w)) and len(m[2]) == len(m[3])
print("4.4: L1 ∩ L2 == a^n b^n c^n up to length 9:", [w for w in W if L1(w) and L2(w)] == eq)

আসল আউটপুট (ব্রাউজারের Python):

4.2 p=1 splits=   8  adversary wins: 0  stay with i=2: 0  stay with i=0: 0
4.2 p=2 splits=  51  adversary wins: 0  stay with i=2: 0  stay with i=0: 0
4.2 p=3 splits= 169  adversary wins: 0  stay with i=2: 0  stay with i=0: 0
4.2 p=4 splits= 415  adversary wins: 0  stay with i=2: 0  stay with i=0: 0
4.3: ['ε', 'abc', 'aabbcc', 'aaabbbccc']
4.4: L1 ∩ L2 == a^n b^n c^n up to length 9: True

৪.২-এর প্রতিপক্ষকে সব চাল দেওয়া হলো: p = 4-এ ৪১৫টি বৈধ বিভাজন, আর একটিতেও i = 0 বা i = 2-এ string L-এ থাকে না (adversary wins: 0). তাই ক্ষেত্র ২-এ i = 2-এর বদলে i = 0 লিখলেও প্রমাণ ঠিক। ৪.৩-এর ছেদ দৈর্ঘ্য ৯ পর্যন্ত ঠিক ε, abc, aabbcc, aaabbbccc; ৪.৪-এর দুই CFL-এর ছেদও তাই।

৫ · অংশ ঘ — Turing machine-এর simulation আর decidability

ঝালিয়ে নিন: পর্ব ৪৫ · TM-এর রূপভেদ, পর্ব ৪৬ · Nondeterministic TM, পর্ব ৫০ · Decidable আর recognizable. Decidability-র প্রমাণে দুটি আলাদা দাবি: যন্ত্রটি প্রতিটি input-এ থামে (decider), আর ঠিক উত্তর দেয়। শুধু দ্বিতীয়টি দেখালে আপনি একটি recognizer দিয়েছেন।

৫.১প্রমাণের রূপরেখা দিন: প্রতিটি multi-tape TM-এর একটি সমতুল্য single-tape TM আছে; M t(n) ≥ n সময় নিলে simulation O(t(n)2) সময় নেয়। — ১০ নম্বর (মাঝারি)
  1. k-tape M দেওয়া। Single-tape S সব tape পাশাপাশি রাখে: #w1#w2#⋯#wk#, আর প্রতিটি head-এর ঘরের চিহ্নের ওপর একটি ফোঁটা (ফোঁটাওয়ালা চিহ্ন Γ-তে নতুন চিহ্ন)। — এনকোডিং
  2. M-এর এক ধাপের জন্য S বাঁ থেকে ডানে একবার হেঁটে k টি ফোঁটাওয়ালা চিহ্ন পড়ে, finite control-এ রাখে (k স্থির, তাই সসীম তথ্য)। — পড়া
  3. দ্বিতীয় হাঁটায় M-এর δ অনুযায়ী চিহ্ন লেখে আর ফোঁটা সরায়। কোনো ফোঁটা ডানের #-এ পড়লে বাকি tape এক ঘর ডানে সরিয়ে সেখানে ␣ বসায়। — লেখা
  4. Invariant: প্রতিটি simulated ধাপের পর S-এর tape M-এর configuration-এর হুবহু এনকোডিং; তাই M accept/reject করলে S-ও তাই করে, আর L(S) = L(M). — simulation argument
  5. সময়: t(n) ধাপে প্রতিটি tape-এর ব্যবহৃত অংশ O(t(n)), তাই একটি হাঁটা আর বড়জোর k টি সরানো O(t(n)); t(n) ধাপে মোট O(t(n)2). ∎

নম্বর-ভাগ: এনকোডিং (২), এক ধাপের simulation (৩), tape বাড়ানো (১), invariant (২), সময়ের হিসাব (২)। যেখানে নম্বর কাটে: “ফোঁটা” কীভাবে রাখা হয় না বলা; tape বেড়ে যাওয়ার ক্ষেত্র বাদ।

৫.২প্রমাণের রূপরেখা দিন: প্রতিটি nondeterministic TM-এর একটি সমতুল্য deterministic TM আছে। DFS কেন চলবে না, বলুন। — ১০ নম্বর (কঠিন)
  1. N-এর প্রতিটি configuration-এ বড়জোর b টি পছন্দ। Computation tree-এর প্রতিটি node-কে একটি address দিয়ে চেনা যায়: {1, …, b}-এর ওপর একটি string. — গাছের ঠিকানা
  2. D-এর তিনটি tape: input (কখনো বদলায় না), simulation, address. Address shortlex ক্রমে নেওয়া হয় (ε, 1, 2, …, 11, 12, …), যা গাছের BFS. — নির্মাণ
  3. প্রতিটি address-এর জন্য: input simulation tape-এ কপি, তারপর address-এর পছন্দ ধরে N চালানো। Accepting configuration এলে accept; পছন্দ অবৈধ হলে বা address শেষ হলে পরের address. — এক শাখা চালানো
  4. N w গ্রহণ করলে কোনো সসীম গভীরতা d-তে একটি accepting node আছে; তার আগে সসীম সংখ্যক address, তাই D accept করে। N গ্রহণ না করলে D কখনো accept করে না। তাই L(D) = L(N). ∎ — BFS-এর পূর্ণতা

DFS কেন নয়: একটি শাখা অসীম হলে DFS সেখানেই আটকে থাকে, পাশের শাখার accepting node-এ কখনো পৌঁছায় না। বাড়তি: N decider হলে প্রতিটি শাখা সসীম, আর König-এর lemma-য় পুরো গাছ সসীম; তাই D কোনো গভীরতায় সব শাখা থেমেছে দেখে reject করতে পারে। দাম: bO(t(n)) সময়। নম্বর-ভাগ: address (২), তিন tape (২), এক শাখার simulation (২), সঠিকতা (৩), DFS-এর কারণ (১)।

৫.৩প্রমাণ করুন: ADFA = {⟨B, w⟩ : B একটি DFA আর B w গ্রহণ করে} decidable. — ৫ নম্বর (সহজ)
  1. M = “input ⟨B, w⟩: (১) input বৈধ এনকোডিং না হলে reject; (২) B-কে w-এর ওপর simulate করুন, প্রতিটি চিহ্নে transition table থেকে পরের state; (৩) শেষ state F-এ থাকলে accept, নইলে reject.” — নির্মাণ
  2. থামে: ঠিক |w| টি ধাপ, প্রতিটি সসীম table-খোঁজা। — সসীম কাজ
  3. সঠিক: শেষ state = δ̂(q0, w), আর DFA-র গ্রহণের সংজ্ঞা হুবহু এটিই। ∎

নম্বর-ভাগ: decider (২), থামার কারণ (২), সঠিকতা (১)। যেখানে নম্বর কাটে: বৈধ এনকোডিং পরীক্ষা না করা; “থামে” কথাটি না লেখা।

৫.৪প্রমাণ করুন: ECFG = {⟨G⟩ : G একটি CFG আর L(G) = ∅} decidable. — ১০ নম্বর (মাঝারি)
  1. R = “input ⟨G⟩: সব terminal চিহ্নিত করুন; প্রতি round-এ এমন নিয়ম A → U1⋯Uk খুঁজুন যার সব Ui চিহ্নিত, তাহলে A চিহ্নিত; নতুন কিছু না এলে থামুন; S চিহ্নিত না হলে accept, নইলে reject.” — নির্মাণ
  2. থামে: প্রতি round-এ অন্তত একটি নতুন variable চিহ্নিত হয়, নইলে থামা; তাই বড়জোর |V| + 1 round. — সসীম V
  3. (চিহ্নিত ⇒ generating) round-এর ওপর induction: A → U1⋯Uk-এর প্রতিটি Ui থেকে terminal string wi আসে, তাই A ⇒∗ w1⋯wk. — induction
  4. (generating ⇒ চিহ্নিত) A ⇒∗ w-এর parse tree-র উচ্চতার ওপর induction: root-এর নিয়মের প্রতিটি সন্তান ছোট গাছের root, তাই আগেই চিহ্নিত; ফলে A-ও চিহ্নিত হয়। — উল্টো দিক
  5. L(G) = ∅ ⇔ S generating নয় ⇔ S অচিহ্নিত ⇔ R accept. ∎

নম্বর-ভাগ: algorithm (৩), থামা (২), দুই দিকের সঠিকতা (৪), উপসংহার (১)। যেখানে নম্বর কাটে: “সব derivation চেষ্টা করি, কোনো string না এলে accept” — এটি কখনো থামে না, তাই decider নয়।

G1 = {"S": ["AB", "C"], "A": ["aA", "a"], "B": ["bB"], "C": ["cC", "AC"]}
G2 = dict(G1, B=["bB", "b"])                 # one extra rule: B -> b
def decide_E(G):                             # 5.4: mark generating variables, round by round
    marked, rnd = {}, 0                      # variable -> a terminal string it derives
    while True:
        rnd += 1
        new = {}
        for A, rhss in G.items():
            for r in rhss:
                if A not in marked and A not in new and all(c in marked or c not in G for c in r):
                    new[A] = "".join(marked.get(c, c) for c in r)
        print(f"   round {rnd}: newly marked {sorted(new) or '-'}")
        if not new: break
        marked.update(new)
    return "S" not in marked, marked.get("S")
def brute(G, n):                             # terminal strings reachable within n expansions
    forms, words = {"S"}, set()
    for _ in range(n):
        nxt = set()
        for f in forms:
            i = next((k for k, c in enumerate(f) if c in G), None)
            if i is None: words.add(f)
            else: nxt |= {f[:i] + r + f[i + 1:] for r in G[f[i]] if len(f) < 8}
        forms = nxt
    return sorted(words, key=lambda w: (len(w), w))[:3]
for name, G in (("G1", G1), ("G2", G2)):
    print(name)
    empty, witness = decide_E(G)
    print(f"   L({name}) empty: {empty}  witness: {witness}  brute force finds: {brute(G, 8)}")

আসল আউটপুট (ব্রাউজারের Python):

G1
   round 1: newly marked ['A']
   round 2: newly marked -
   L(G1) empty: True  witness: None  brute force finds: []
G2
   round 1: newly marked ['A', 'B']
   round 2: newly marked ['S']
   round 3: newly marked -
   L(G2) empty: False  witness: ab  brute force finds: ['ab', 'aab', 'abb']

G1-এ শুধু A চিহ্নিত হয়: B → bB আর C → cC ∣ AC কখনো শেষ হয় না, তাই S অচিহ্নিত, L(G1) = ∅; সীমিত brute force-ও কিছু পায় না (যদিও তা একা প্রমাণ নয়)। G2-তে একটি নিয়ম B → b যোগ করতেই round ২-এ S চিহ্নিত হয়, আর চিহ্নের সঙ্গে রাখা সাক্ষী string ab brute force-এর সবচেয়ে ছোট string-এর সঙ্গে মেলে। লক্ষ করুন, R তিন round-এর বেশি চলেনি: |V| + 1-এর সীমা।

৫.৫প্রমাণ করুন: L decidable ⇔ L আর L̄ দুটিই Turing-recognizable. — ১০ নম্বর (মাঝারি)
  1. (⇒) L-এর decider নিজেই একটি recognizer. Accept আর reject অদলবদল করলে L̄-এর decider, তাই L̄-ও recognizable. — সংজ্ঞা
  2. (⇐) M1 L চেনে, M2 L̄ চেনে। M = “input w: M1 আর M2-কে পালা করে এক ধাপ এক ধাপ চালান (দুটি tape-এ); M1 accept করলে accept, M2 accept করলে reject.” — সমান্তরাল চালানো
  3. প্রতিটি w হয় L-এ, নয় L̄-এ; তাই M1 বা M2-এর একটি সসীম ধাপে accept করে, আর M থামে: M decider. — থামা
  4. M accept করে ⇔ M1 accept করে ⇔ w ∈ L. ∎

নম্বর-ভাগ: ⇒ (২), পালা করে চালানোর নির্মাণ (৩), থামার যুক্তি (৩), সঠিকতা (২)। যেখানে নম্বর কাটে: “আগে M1 চালাই, না হলে M2” — w ∈ L̄ হলে M1 চিরকাল চলতে পারে, M2-এর পালা কখনো আসে না। এ থেকেই ফল: L̄ recognizable হলে L আর co-recognizable একই কথা।

৬ · অংশ ঙ — Diagonalization, mapping reduction আর Rice

ঝালিয়ে নিন: পর্ব ৫১ · Diagonalization আর halting problem, পর্ব ৫২ · Mapping reduction, পর্ব ৫৩ · Rice-এর theorem. A ≤m B-এর তিন শর্ত: f computable (সব input-এ থামে), সব w-এ w ∈ A ⇔ f(w) ∈ B, আর দিক: B decidable ⇒ A decidable; তাই A undecidable ⇒ B undecidable. জানা-কঠিন সমস্যা সবসময় বাঁয়ে।

৬.১Diagonalization দিয়ে প্রমাণ করুন: ATM = {⟨M, w⟩ : M একটি TM আর M w গ্রহণ করে} decidable নয়। — ১০ নম্বর (কঠিন)
  1. বিরোধের জন্য ধরি H একটি decider যা ATM decide করে: H(⟨M, w⟩) সবসময় থামে, M w গ্রহণ করলে accept, নইলে (reject বা loop) reject. — অনুমান
  2. D = “input ⟨M⟩: H-কে ⟨M, ⟨M⟩⟩-এর ওপর চালান; H accept করলে reject, H reject করলে accept.” H থামে, তাই D-ও সবসময় থামে। — নির্মাণ
  3. যেকোনো TM M-এর জন্য: D ⟨M⟩ গ্রহণ করে ⇔ M ⟨M⟩ গ্রহণ করে না। — H-এর সঠিকতা
  4. D নিজেও একটি TM; M = D বসালে: D ⟨D⟩ গ্রহণ করে ⇔ D ⟨D⟩ গ্রহণ করে না। স্ববিরোধ। — diagonal
  5. H-এর অস্তিত্বের অনুমান ছাড়া সব ধাপ বৈধ, তাই H নেই: ATM undecidable. ∎

নম্বর-ভাগ: H-এর পূর্ণ সংজ্ঞা, “সবসময় থামে” সহ (২), D (৩), সাধারণ M-এর ⇔ (২), D-তে বসানো আর স্ববিরোধ (২), উপসংহার (১)। যেখানে নম্বর কাটে: H-কে recognizer ধরা (তখন D loop করতে পারে, আর স্ববিরোধ আসে না); D-কে ⟨M, w⟩ input দেওয়া (diagonal-এর জন্য M-কে নিজের বর্ণনাই দিতে হয়)।

সারি Mᵢ, কলাম ⟨Mⱼ⟩: Mᵢ কি ⟨Mⱼ⟩ গ্রহণ করে (নিচের ব্লকের মান)
ধাপ
M1 সারি
M2 সারি
M3 সারি
M4 সারি
D সারি
  1. টেবিল। H থাকলে এই অসীম টেবিলের প্রতিটি ঘর হিসাব করা যেত: সারি Mi, কলাম ⟨Mj⟩, ঘরে Mi ⟨Mj⟩ গ্রহণ করে কি না। মানগুলো নিচের ব্লকের পাঁচটি খেলনা program-এর প্রথম চারটি থেকে।
  2. কর্ণ। D শুধু কর্ণের ঘর দেখে: Mi-কে তার নিজের বর্ণনা ⟨Mi⟩ দিলে কী হয়। এখানে acc, rej, rej, acc.
  3. উল্টানো। D প্রতিটি কর্ণের ঘরের উল্টো উত্তর দেয়: rej, acc, acc, rej. এই সারিটিই D-এর আচরণ।
  4. তুলনা। D-এর সারি Mi-এর সারি থেকে অন্তত কলাম i-তে আলাদা, তাই D তালিকার কোনো Mi নয়। কিন্তু তালিকায় সব TM আছে, আর D একটি TM.
  5. D-এর নিজের ঘর। D যদি কোনো সারি Mk হয়, তবে ঘর (k, k)-তে D-এর উত্তর হতে হয় নিজের উল্টো: অসম্ভব। ব্লকে এই ঘরটি হিসাব করতে গেলে Python নিজেকে অবিরাম ডাকতে থাকে।
  6. উপসংহার। স্ববিরোধের একমাত্র উৎস H-এর অস্তিত্ব, তাই ATM-এর কোনো decider নেই। একই কর্ণ-কৌশল Cantor-এর প্রমাণে (পর্ব ০২)।
import sys
sys.setrecursionlimit(300)
M = ["lambda x: True",                      # M1 accepts everything
     "lambda x: len(x) % 2 == 0",           # M2 even length
     "lambda x: x.count('x') > 3",          # M3 more than three letters x
     "lambda x: '%' in x",                  # M4 contains a percent sign
     "lambda x: False"]                     # M5 accepts nothing
run = lambda src, inp: eval(src)(inp)       # "M on input w"
cell = lambda b, diag: (f"[{'acc' if b else 'rej'}]" if diag else ("acc" if b else "rej")).ljust(6)
print(" " * 5 + "".join(f"<M{j + 1}>".ljust(6) for j in range(len(M))))
for i, src in enumerate(M):
    print(f"M{i + 1}:  " + "".join(cell(run(src, M[j]), i == j) for j in range(len(M))))
D = lambda src: not run(src, src)           # flip the diagonal
print("D:   " + "".join(cell(D(s), False) for s in M))
print("D differs from every M_i at column i:", all(D(M[i]) != run(M[i], M[i]) for i in range(len(M))))
D_src = "lambda x: not eval(x)(x)"          # D written as a program of the same kind
try:
    print("D on <D>:", run(D_src, D_src))
except RecursionError:
    print("D on <D>: no answer - infinite self-call, stopped by RecursionError")

আসল আউটপুট (ব্রাউজারের Python):

     <M1>  <M2>  <M3>  <M4>  <M5>  
M1:  [acc] acc   acc   acc   acc   
M2:  acc   [rej] acc   acc   rej   
M3:  rej   rej   [rej] rej   rej   
M4:  rej   acc   rej   [acc] rej   
M5:  rej   rej   rej   rej   [rej] 
D:   rej   acc   acc   rej   acc   
D differs from every M_i at column i: True
D on <D>: no answer - infinite self-call, stopped by RecursionError

পাঁচটি program (Python lambda, যাদের source-ই তাদের ⟨M⟩) পরস্পরের source-এ চালিয়ে টেবিল বানানো হলো; কর্ণ বন্ধনীতে। D কর্ণ উল্টে প্রতিটি সারি থেকে অন্তত এক কলামে আলাদা: True. শেষ লাইনে D-কে একই ধরনের program হিসেবে লিখে তার নিজের source দেওয়া হলো; উত্তর আসে না, Python অবিরাম নিজেকে ডেকে থামে RecursionError-এ। এটি প্রমাণ নয়, প্রমাণের ছায়া মাত্র।

৬.২প্রমাণ করুন: A̅TM (ATM-এর complement) Turing-recognizable নয়। — ৫ নম্বর (মাঝারি)
  1. ATM recognizable: universal TM U = “⟨M, w⟩: M-কে w-এর ওপর চালান, M accept করলে accept”. — পর্ব ৪৮
  2. A̅TM-ও recognizable হলে ৫.৫ অনুযায়ী ATM decidable হতো। — ৫.৫
  3. ৬.১-এর বিরোধী; তাই A̅TM recognizable নয়। ∎

নম্বর-ভাগ: U (২), ৫.৫-এর প্রয়োগ (২), উপসংহার (১)। যেখানে নম্বর কাটে: “ATM undecidable, তাই complement recognizable নয়” — মাঝের ধাপ (ATM recognizable) ছাড়া যুক্তি অসম্পূর্ণ।

৬.৩ATM থেকে mapping reduction দিয়ে প্রমাণ করুন: HALTTM = {⟨M, w⟩ : M w-এর ওপর থামে} undecidable. — ১০ নম্বর (মাঝারি)
  1. f(⟨M, w⟩) = ⟨M′, w⟩, যেখানে M′ = “input x: M-কে x-এর ওপর চালান; M accept করলে accept; M reject করলে চিরকাল loop করুন।” অবৈধ input-এর ছবি একটি স্থির ⟨Mloop, ε⟩, যে কখনো থামে না। — নির্মাণ
  2. f computable: M-এর নিয়মের সারণি নকল করে reject state-কে একটি loop-এ বদলানো; M চালানো হয় না, তাই f সব input-এ থামে। — computability
  3. (⇒) M w গ্রহণ করলে M′ w-এ accept করে থামে: ⟨M′, w⟩ ∈ HALTTM. — প্রথম দিক
  4. (⇐) M w গ্রহণ না করলে হয় reject (M′ loop করে), নয় loop (M′-ও loop করে): ⟨M′, w⟩ ∉ HALTTM. — দ্বিতীয় দিক, দুই উপক্ষেত্র
  5. ATM ≤m HALTTM, আর ATM undecidable (৬.১), তাই HALTTM undecidable. ∎ — দিকের নিয়ম

নম্বর-ভাগ: f আর M′ (৩), computability (২), ⇒ (২), ⇐ দুই উপক্ষেত্রসহ (২), দিকসহ উপসংহার (১)। যেখানে নম্বর কাটে: f-এর ভেতরে M চালিয়ে দেখা (৮.৪); ⇐-এ “M loop করে” ক্ষেত্রটি বাদ।

৬.৪ETM = {⟨M⟩ : L(M) = ∅}. প্রমাণ করুন: ETM undecidable, আর Turing-recognizable-ও নয়। — ১০ নম্বর (কঠিন)
  1. f(⟨M, w⟩) = ⟨M1⟩, M1 = “input x: x ≠ w হলে reject; x = w হলে M-কে w-এর ওপর চালান, M accept করলে accept.” w M1-এর সারণিতে বসানো (hard-wired); f কিছু চালায় না, তাই computable. — নির্মাণ
  2. M w গ্রহণ করলে L(M1) = {w} ≠ ∅; না করলে L(M1) = ∅. তাই ⟨M, w⟩ ∈ ATM ⇔ ⟨M1⟩ ∈ E̅TM: ATM ≤m E̅TM. — ⇔ দুই দিক
  3. তাই E̅TM undecidable; decidable language complement-এ বদ্ধ, তাই ETM-ও undecidable. — দিকের নিয়ম, complement
  4. E̅TM recognizable: সব string-এ M-কে dovetailing-এ চালান, একটি accept হলেই accept. ETM recognizable-ও হলে ৫.৫-এ decidable হতো, ধাপ ৩-এর বিরোধী। ∎ — ৫.৫

নম্বর-ভাগ: M1 আর computability (৩), ⇔ (৩), complement-এর যুক্তি (২), non-recognizability (২)। যেখানে নম্বর কাটে: সরাসরি “ATM ≤m ETM” দাবি — এমন f থাকতেই পারে না, কারণ থাকলে A̅TM ≤m E̅TM হতো, আর E̅TM recognizable বলে A̅TM-ও recognizable হতো (৬.২-এর বিরোধী)।

৬.৫REGULARTM = {⟨M⟩ : L(M) regular}. প্রমাণ করুন: এটি undecidable. — ১০ নম্বর (কঠিন)
  1. f(⟨M, w⟩) = ⟨M2⟩, M2 = “input x: x যদি 0n1n আকারের হয়, accept; নইলে M-কে w-এর ওপর চালান, M accept করলে accept.” — নির্মাণ, computable
  2. M w গ্রহণ করলে প্রতিটি x গৃহীত: L(M2) = Σ∗, regular. — ⇒
  3. না করলে শুধু প্রথম শাখা: L(M2) = {0n1n}, regular নয় (পর্ব ১৭)। — ⇐
  4. ATM ≤m REGULARTM, তাই REGULARTM undecidable. ∎

নম্বর-ভাগ: M2 (৩), দুই দিক (৩ + ৩), উপসংহার (১)। কৌশলের সারকথা: L(M′)-কে “M w গ্রহণ করে কি না” অনুযায়ী দুটি ভিন্ন জাতের language-এর একটি বানানো। ৬.৬-এর Rice এই কৌশলের সাধারণ রূপ।

CAP, XS = 1000, ["", "a", "b", "ab", "ba", "aa", "11", "10"]   # step cap: simulator only
def run(prog, x):                           # a program is a generator: each yield = one step
    g = prog(x)
    for _ in range(CAP):
        try: next(g)
        except StopIteration as e: return "acc" if e.value else "rej"
    return "cap"                            # still running after CAP steps
def PAR(x):                                 # accepts strings with an even number of 1s
    for _ in x: yield
    return x.count("1") % 2 == 0
def SPIN(x):                                # accepts "ab", rejects "", loops on the rest
    yield
    if x == "ab": return True
    if x == "": return False
    while True: yield
def f_halt(M, w):                           # 6.3: A_TM -> HALT_TM, builds M' without running M
    def M2(x):
        r = yield from M(w)
        if r: return True
        while True: yield                   # M rejected: loop forever
    return M2, w
def f_empty(M, w):                          # 6.4: A_TM -> complement of E_TM
    def M1(x):
        if x != w: return False
        return (yield from M(w))
    return M1
for M, name, w in [(PAR, "PAR", "11"), (PAR, "PAR", "10"), (SPIN, "SPIN", "ab"), (SPIN, "SPIN", "ba"), (SPIN, "SPIN", "")]:
    M2, w2 = f_halt(M, w)
    acc = sorted(x for x in XS if run(f_empty(M, w), x) == "acc")
    print(f"{name:4} w={w or 'ε':2}  M on w: {run(M, w)}  M' on w: {run(M2, w2)}  accepted by M1: {acc}")

আসল আউটপুট (ব্রাউজারের Python):

PAR  w=11  M on w: acc  M' on w: acc  accepted by M1: ['11']
PAR  w=10  M on w: rej  M' on w: cap  accepted by M1: []
SPIN w=ab  M on w: acc  M' on w: acc  accepted by M1: ['ab']
SPIN w=ba  M on w: cap  M' on w: cap  accepted by M1: []
SPIN w=ε   M on w: rej  M' on w: cap  accepted by M1: []

প্রতিটি program একটি Python generator, প্রতিটি yield এক ধাপ; simulator ১০০০ ধাপে থামে আর cap লেখে (step cap মানে “এখনো থামেনি”, “কখনো থামবে না” নয়)। f_halt আর f_empty কোনো program চালায় না, শুধু নতুন program বানায়: এটিই f-এর computability. M' on w কলামে ৬.৩-এর দাবি মেলে: M w গ্রহণ করলে M′ থামে (acc), M w বর্জন বা loop করলে M′ থামে না (cap). শেষ কলামে ৬.৪-এর M1: পরীক্ষিত string-গুলোর মধ্যে সে হয় শুধু w নেয়, নয় কিছুই নেয় না।

৬.৬নিচের কোনটি decidable, কোনটি নয়? প্রতিটির কারণ লিখুন; Rice-এর theorem কোথায় খাটে, কোথায় খাটে না, তা স্পষ্ট করুন। (ক) INF = {⟨M⟩ : L(M) অসীম}; (খ) {⟨M⟩ : M-এর state ৫টির কম}; (গ) {⟨M⟩ : M ε-এর ওপর অন্তত ১০০ ধাপ চলে}; (ঘ) {⟨M⟩ : L(M) = Σ∗}. — ১০ নম্বর (মাঝারি)

Rice: TM-এর প্রতিটি non-trivial semantic ধর্ম undecidable. Semantic মানে L(M1) = L(M2) হলে দুটির একই উত্তর; non-trivial মানে অন্তত একটি TM-এ “হ্যাঁ”, একটিতে “না”।

  1. (ক) শুধু L(M)-এর ওপর নির্ভর করে; Σ∗ চেনা যন্ত্রে হ্যাঁ, সব বর্জন করা যন্ত্রে না। Rice: undecidable. — দুই শর্ত যাচাই
  2. (খ) Syntactic: ⟨M⟩ পড়ে state গুনলেই হয়, সবসময় থামে। Decidable; Rice খাটে না। — বর্ণনার ধর্ম
  3. (গ) Language-এর ধর্ম নয়: একই language-এর দুটি যন্ত্র ε-এ ভিন্ন ধাপ নিতে পারে। ১০০ ধাপ simulate করে দেখা যায়, তাই decidable. — সীমিত simulation
  4. (ঘ) Semantic, non-trivial (সব গ্রহণ করা যন্ত্রে হ্যাঁ, সব বর্জন করায় না): undecidable. ∎

নম্বর-ভাগ: প্রতিটি অংশ ২.৫, যার ১ সিদ্ধান্ত আর ১.৫ কারণ। যেখানে নম্বর কাটে: (খ) বা (গ)-তে Rice লাগানো; “non-trivial” শর্ত যাচাই না করে Rice লেখা।

৭ · অংশ চ — NP-completeness আর Savitch

ঝালিয়ে নিন: পর্ব ৫৮ · NP আর verifier, পর্ব ৫৯ · Polynomial-time reduction, পর্ব ৬১ · NP-complete পরিবার, পর্ব ৬৪ · Savitch. “X NP-complete” মানে দুটি আলাদা প্রমাণ: X ∈ NP (একটি polynomial verifier), আর একটি জানা NP-complete সমস্যা থেকে ≤p X (NP-hard). P বনাম NP খোলা প্রশ্ন; NP-completeness দ্রুত algorithm-এর অসম্ভবতা প্রমাণ করে না।

৭.১প্রমাণ করুন: CLIQUE = {⟨G, k⟩ : G-তে k আকারের একটি clique আছে} NP-তে আছে। — ৫ নম্বর (সহজ)
  1. Certificate c: G-এর k টি vertex-এর একটি তালিকা। — সাক্ষী
  2. V = “⟨⟨G, k⟩, c⟩: c-তে ঠিক k টি আলাদা vertex আর সবগুলো G-তে আছে কি না দেখুন; c-এর প্রতিটি জোড়া G-এর edge কি না দেখুন; সব হ্যাঁ হলে accept.” — verifier
  3. সময়: k(k − 1)/2 টি জোড়া, প্রতিটির খোঁজ adjacency matrix-এ স্থির সময়ে; k ≤ n, তাই O(n2), input-এর দৈর্ঘ্যে polynomial. — সময়
  4. ⟨G, k⟩ ∈ CLIQUE ⇔ এমন c আছে যা V accept করে। ∎ — NP-এর সংজ্ঞা

নম্বর-ভাগ: certificate (১), verifier (২), সময় (১), ⇔ (১)। যেখানে নম্বর কাটে: “সব k-subset পরীক্ষা করি” — এটি verifier নয়, সূচকীয় সময়ের সমাধান।

৭.২প্রমাণ করুন: 3SAT ≤p CLIQUE; এ থেকে CLIQUE NP-complete. — ১০ নম্বর (কঠিন)

নির্মাণ: k টি clause-এর 3CNF φ থেকে f(⟨φ⟩) = ⟨G, k⟩. প্রতিটি clause-এর প্রতিটি literal-এর জন্য একটি node (একটি clause-এর তিন node একটি ত্রয়ী, এক ধরনের gadget); দুটি node-এর মধ্যে edge, যদি না (ক) তারা একই ত্রয়ীর, বা (খ) তাদের literal পরস্পরবিরোধী (x আর ¬x).

  1. (⇒) φ satisfiable হলে একটি satisfying মানে প্রতিটি clause-এ অন্তত একটি সত্য literal; প্রতিটি ত্রয়ী থেকে এমন একটি node নিন: k টি node. — বাছাই
  2. যেকোনো দুটি বাছা node ভিন্ন ত্রয়ীর (নিয়ম ক পার), আর দুটিই একই মানে সত্য, তাই পরস্পরবিরোধী নয় (নিয়ম খ পার): edge আছে। তাই k-clique. — দুই নিয়ম
  3. (⇐) G-তে k-clique থাকলে ত্রয়ীর ভেতরে edge নেই বলে প্রতিটি ত্রয়ী থেকে ঠিক একটি node. — pigeonhole
  4. Clique-এর literal-গুলো সত্য ধরুন (অন্য চলক যেকোনো মান)। দুটি পরস্পরবিরোধী literal clique-এ থাকতে পারে না (নিয়ম খ), তাই মানটি সংগত, আর প্রতিটি clause-এ একটি সত্য literal: φ satisfiable. — সংগত assignment
  5. f polynomial: 3k node, প্রতিটি জোড়ার সিদ্ধান্ত স্থির সময়ে, O(k2). তাই 3SAT ≤p CLIQUE; 3SAT NP-complete আর CLIQUE ∈ NP (৭.১), অতএব CLIQUE NP-complete. ∎

নম্বর-ভাগ: নির্মাণ (২), ⇒ (২), ⇐ দুই ধাপে (৩), polynomial সময় (১), NP-তে থাকা আর দিকসহ উপসংহার (২)। যেখানে নম্বর কাটে: শুধু ⇒ প্রমাণ (৮.৫); assignment-এর সংগতি না দেখানো; “CLIQUE ∈ NP” ভুলে যাওয়া — তখন শুধু NP-hard প্রমাণ হয়।

এই ধাপের পর
ধাপ
যা হলো
গণনা
  1. Input. f φ-এর লেখা পড়ে, কোনো মান বসিয়ে পরীক্ষা করে না। Clause তিনটি, তাই লক্ষ্য k = 3.
  2. Node. প্রতিটি literal-এর জন্য আলাদা node, একই চলক দুই clause-এ থাকলেও। মোট 3k = ৯টি node, ৯ × ৮ / ২ = ৩৬টি জোড়া।
  3. নিয়ম ক। প্রতিটি ত্রয়ীর ভেতরে ৩টি জোড়া, মোট ৯টি বাদ। বাকি ২৭টি জোড়া ভিন্ন ত্রয়ীর।
  4. নিয়ম খ। পরস্পরবিরোধী ৬টি জোড়া: C1:x–C2:¬x, C1:x–C3:¬x, C1:¬y–C2:y, C2:y–C3:¬y, C1:z–C3:¬z, C2:z–C3:¬z. বাকি ২১টি edge.
  5. ⇒ দিক। x = 0, y = 0, z = 1 φ-কে সত্য করে। প্রতিটি clause থেকে একটি সত্য literal: C1-এর ¬y, C2-এর ¬x, C3-এর ¬x. তিনটি ভিন্ন ত্রয়ীর, কেউ কারও বিরোধী নয় (দুটি ¬x একই literal): 3-clique.
  6. ⇐ দিক। উল্টো দিকে G-এর আরেকটি clique {C1:x, C2:y, C3:¬z} নিন; x = 1, y = 1, z = 0 বসালে তিন clause-ই সত্য। নিচের চেকার সব ১২টি 3-clique-এর এই হিসাব scratch-এ মিলিয়েছে, আর ৪০০টি এলোমেলো সূত্রে দুই দিক মেলায়।
import random
from itertools import combinations, product
random.seed(84)
def to_graph(phi):                          # 7.2: one node per literal occurrence (clause, place, literal)
    V = [(j, p, lit) for j, cl in enumerate(phi) for p, lit in enumerate(cl)]
    E = {frozenset((u, v)) for u, v in combinations(V, 2)
         if u[0] != v[0] and u[2] != -v[2]}  # rule a: other clause, rule b: no x with not-x
    return V, E, len(phi)
def has_clique(V, E, k, S=(), start=0):     # generic search, knows nothing about clauses
    if len(S) == k: return True
    return any(has_clique(V, E, k, S + (V[i],), i + 1) for i in range(start, len(V))
               if all(frozenset((u, V[i])) in E for u in S))
def n_sat(phi, n):                          # number of satisfying assignments
    return sum(all(any((l > 0) == a[abs(l) - 1] for l in c) for c in phi)
               for a in product([False, True], repeat=n))
phi = [(1, -2, 3), (-1, 2, 3), (-1, -2, -3)]        # x = 1, y = 2, z = 3 ; -1 means not-x
V, E, k = to_graph(phi)
print("example: nodes", len(V), "edges", len(E), "k", k, "| 3-clique:", has_clique(V, E, k),
      "| satisfying assignments:", n_sat(phi, 3))
agree, count = 0, {True: 0, False: 0}
for _ in range(400):                        # random 3CNF formulas over x, y with 2..8 clauses
    f = [tuple(random.choices((1, -1, 2, -2), k=3)) for _ in range(random.randint(2, 8))]
    s = n_sat(f, 2) > 0
    count[s] += 1
    agree += s == has_clique(*to_graph(f))
print("random formulas:", sum(count.values()), "| satisfiable:", count[True],
      "| unsatisfiable:", count[False], "| sat <=> k-clique held in", agree)

আসল আউটপুট (ব্রাউজারের Python):

example: nodes 9 edges 21 k 3 | 3-clique: True | satisfying assignments: 5
random formulas: 400 | satisfiable: 376 | unsatisfiable: 24 | sat <=> k-clique held in 400

প্রথম লাইন stepper-এর সংখ্যা মেলায়: ৯টি node, ২১টি edge, 3-clique আছে, আর satisfying মান ৫টি। দ্বিতীয় লাইনে দুই চলকের ৪০০টি এলোমেলো 3CNF সূত্র (একই literal বারবার আসতে পারে, যেমন x ∨ x ∨ ¬y): ২৪টি unsatisfiable, আর প্রতিটি সূত্রে “satisfiable ⇔ k-clique আছে” সত্য। Clique খোঁজার অংশটি clause চেনে না, তাই যাচাইটি নির্মাণের ওপর নির্ভরশীল নয়।

৭.৩প্রমাণ করুন: CLIQUE ≤p INDEPENDENT-SET আর INDEPENDENT-SET ≤p VERTEX-COVER. — ১০ নম্বর (মাঝারি)
  1. f1(⟨G, k⟩) = ⟨Ḡ, k⟩, যেখানে Ḡ complement graph. S G-তে clique ⇔ S-এর প্রতিটি জোড়া G-এর edge ⇔ কোনো জোড়া Ḡ-এর edge নয় ⇔ S Ḡ-তে independent. — সংজ্ঞা উল্টানো
  2. f2(⟨G, k⟩) = ⟨G, n − k⟩. দাবি: S independent ⇔ V ∖ S একটি vertex cover. — নির্মাণ
  3. (⇒) কোনো edge uv-এর দুই প্রান্তই S-এ থাকতে পারে না, তাই অন্তত একটি V ∖ S-এ: cover. (⇐) V ∖ S cover হলে কোনো edge-এর দুই প্রান্তই S-এ নয়: S independent. — দুই দিক
  4. তাই k আকারের independent set ⇔ n − k আকারের cover. দুটি f-ই polynomial (Ḡ বানাতে O(n2)). VERTEX-COVER ∈ NP হওয়ায় সেটিও NP-complete. ∎

নম্বর-ভাগ: f1 আর ⇔ (৩), f2 (২), দুই দিক (৩), সময় আর উপসংহার (২)। যেখানে নম্বর কাটে: f2-এ k না বদলানো; “≥ k” আর “≤ n − k”-এর দিক গুলিয়ে ফেলা।

৭.৪3SAT ≤p SUBSET-SUM-এর নির্মাণ আর প্রমাণের রূপরেখা দিন। Subset sum-এর জন্য pseudo-polynomial DP থাকলেও এটি P = NP প্রমাণ করে না কেন? — ১০ নম্বর (কঠিন)

নির্মাণ (Sipser): l টি চলক, m টি clause; প্রতিটি সংখ্যা l + m অঙ্কের দশমিক। চলক xi-এর জন্য yi আর zi: দুটিরই কলাম xi-এ 1; yi-এর cj-এ 1 যদি xi cj-এ থাকে, zi-এর cj-এ 1 যদি ¬xi থাকে। প্রতিটি clause-এর জন্য দুটি ফাঁক-ভরানো সংখ্যা gj, hj (শুধু cj-এ 1). লক্ষ্য t = 1…1 3…3.

  1. কোনো কলামে বড়জোর ৫টি 1, তাই যোগে carry হয় না; প্রতিটি কলাম আলাদা পড়া যায়। — ৫ < ১০
  2. (⇒) satisfying মানে xi সত্য হলে yi, নইলে zi; cj কলামে সত্য literal-এর সংখ্যা ১–৩, বাকিটা gj, hj দিয়ে ৩ পূরণ। — যোগফল t
  3. (⇐) চলক-কলামে 1 মানে yi, zi-এর ঠিক একটি নেওয়া: এটিই মান। cj-এ ৩ লাগে, g, h বড়জোর ২ দেয়, তাই একটি নেওয়া literal-সংখ্যা cj-কে সত্য করে। — সব clause সত্য
  4. 2l + 2m টি সংখ্যা, প্রতিটি l + m অঙ্কের: সারণির দৈর্ঘ্য φ-এর দৈর্ঘ্যে polynomial. ∎

DP কেন যথেষ্ট নয়: DP-র সময় t-এর মানের অনুপাতে, আর t-এর মান প্রায় 10l+m: input-এর দৈর্ঘ্যে সূচকীয়। তাই এটি pseudo-polynomial, polynomial নয়। নম্বর-ভাগ: সারণি (৩), carry নেই (১), ⇒ (২), ⇐ (৩), আকার (১)।

import random
from itertools import combinations, product
random.seed(84)
n, P = 5, list(combinations(range(5), 2))   # 7.3: every graph on 5 labelled vertices
def alpha(E):                               # largest independent set
    return max(len(S) for r in range(n + 1) for S in combinations(range(n), r)
               if not any(frozenset(p) in E for p in combinations(S, 2)))
ok = 0
for mask in range(1 << len(P)):
    E = {frozenset(P[i]) for i in range(len(P)) if mask >> i & 1}
    Ec = {frozenset(p) for p in P} - E      # complement graph
    omega = max(r for r in range(n + 1) for S in combinations(range(n), r)
                if all(frozenset(p) in E for p in combinations(S, 2)))
    tau = min(r for r in range(n + 1) for C in combinations(range(n), r)
              if all(set(e) & set(C) for e in Ec))
    ok += omega == alpha(Ec) and tau == n - alpha(Ec)
print("7.3 graphs:", 1 << len(P), "| clique(G) = indep(co-G) and cover(co-G) = n - indep:", ok)
def subset_sum_instance(phi, l):            # 7.4: Sipser's table, decimal digits
    m = len(phi); D = lambda cols: sum(10 ** (l + m - 1 - c) for c in cols)
    nums = [D([i] + [l + j for j, c in enumerate(phi) if s * (i + 1) in c]) for i in range(l) for s in (1, -1)]
    nums += [D([l + j]) for j in range(m) for _ in range(2)]
    return nums, D(range(l)) + 3 * D(range(l, l + m))
agree = unsat = 0
for _ in range(200):
    f = [tuple(random.choices((1, -1, 2, -2), k=3)) for _ in range(random.randint(2, 8))]
    s = any(all(any((x > 0) == a[abs(x) - 1] for x in c) for c in f) for a in product([0, 1], repeat=2))
    nums, t = subset_sum_instance(f, 2); sums = {0}
    for a in nums: sums |= {x + a for x in sums}
    agree += s == (t in sums); unsat += not s
print("7.4 formulas: 200 | unsatisfiable:", unsat, "| sat <=> subset sums to t:", agree)

আসল আউটপুট (ব্রাউজারের Python):

7.3 graphs: 1024 | clique(G) = indep(co-G) and cover(co-G) = n - indep: 1024
7.4 formulas: 200 | unsatisfiable: 15 | sat <=> subset sums to t: 200

পাঁচ vertex-এর সব ১০২৪টি labelled graph-এ ৭.৩-এর দুই সমতা একসঙ্গে খাটে: G-এর সবচেয়ে বড় clique = Ḡ-এর সবচেয়ে বড় independent set, আর Ḡ-এর সবচেয়ে ছোট cover = 5 − সেই সংখ্যা। ৭.৪-এর সারণি ২০০টি এলোমেলো সূত্রে (যার কয়েকটি unsatisfiable) বানিয়ে সব subset-এর যোগফল হিসাব করা হলো; প্রতিটিতে “satisfiable ⇔ কোনো subset-এর যোগফল t”.

৭.৫f(n) ≥ log n. Savitch-এর theorem NSPACE(f(n)) ⊆ SPACE(f(n)2)-এর প্রমাণের রূপরেখা দিন। শর্ত f(n) ≥ log n কোথায় লাগে? — ১০ নম্বর (কঠিন)
  1. N একটি f(n)-space NTM. f(n) জায়গার configuration বড়জোর 2d·f(n) টি (কোনো ধ্রুবক d). ধরা যায় N accept করার আগে tape মুছে একটি নির্দিষ্ট caccept-এ যায়। — configuration গোনা
  2. CANYIELD(c1, c2, t): t = 1 হলে c1 = c2 বা এক ধাপে যাওয়া যায় কি না সরাসরি দেখুন; নইলে প্রতিটি cm-এর জন্য CANYIELD(c1, cm, t/2) আর CANYIELD(cm, c2, t/2); দুটিই হ্যাঁ হলে হ্যাঁ। — মাঝখানে ভাঙা
  3. Deterministic M: CANYIELD(cstart, caccept, 2d·f(n)) চালায়। সঠিকতা t-এর ওপর induction: পথ থাকলে তার মাঝের configuration একটি cm. — সঠিকতা
  4. জায়গা: recursion-এর গভীরতা log2 2d·f(n) = O(f(n)); প্রতিটি স্তরে c1, c2, cm, t রাখতে O(f(n)); মোট O(f(n)2). পরের cm চেষ্টার আগে জায়গা আবার ব্যবহার হয়। ∎ — জায়গা ফেরত আসে

শর্ত কোথায়: একটি configuration-এ input-এ head-এর অবস্থানও থাকে, যা লিখতে log n বিট লাগে; f(n) ≥ log n হলে configuration লিখতে O(f(n)) জায়গাই যথেষ্ট। প্রমাণে সুবিধার জন্য ধরা হয় f(n) নিজে O(f(n)) জায়গায় হিসাব করা যায়; সেই অনুমান সরানোর কৌশল Sipser-এর বইয়ে আছে। নম্বর-ভাগ: configuration গোনা (২), CANYIELD (৩), সঠিকতা (২), জায়গার হিসাব (৩)। যেখানে নম্বর কাটে: সময় আর জায়গা গুলিয়ে ফেলা — এই simulation-এর সময় সূচকীয়; আর ফলটিকে “P = NP” ধরনের সময়ের দাবি ভাবা। ফল: PSPACE = NPSPACE.

৮ · ভুল প্রমাণ ধরুন — ছয়টি ফাঁদ আর সংশোধন

প্রতিটি “প্রমাণ” পড়ে আগে নিজে ভুলের লাইনটি খুঁজুন, তারপর খুলুন। ভালো উত্তরে তিনটি জিনিস: কোন লাইন ভুল, কেন ভুল (সম্ভব হলে একটি counterexample), আর সংশোধিত প্রমাণ। একটি সহজ পরীক্ষা প্রায়ই কাজ করে: একই যুক্তি যদি একটি মিথ্যা সিদ্ধান্তও “প্রমাণ” করে, যুক্তিটি ভুল।

৮.১“দাবি: L = {a2n : n ≥ 0} = (aa)∗ regular নয়। প্রমাণ: s = a2p নিই, x = ε, y = a ধরি। i = 2-এ a2p+1, দৈর্ঘ্য বিজোড়, ∉ L. বিরোধ। ∎” ভুল কোথায়? — ৫ নম্বর (সহজ)

ভুল: বিভাজন বেছে নিয়েছেন প্রমাণকারী নিজে। Lemma শুধু বলে কোনো একটি বিভাজন আছে; প্রতিপক্ষ x = ε, y = aa দিলে প্রতিটি i-তে দৈর্ঘ্য জোড় থাকে, আর string L-এই থাকে (চেকারে p = 2 থেকে 8, i = 0 থেকে 5). সিদ্ধান্তটিও মিথ্যা: দুই state-এর DFA (জোড়/বিজোড় দৈর্ঘ্য) L চেনে। সংশোধন: L regular; প্রমাণ সেই DFA আর তার invariant. “Regular নয়” প্রমাণে সবসময় “যেকোনো বিভাজন s = xyz” দিয়ে শুরু করুন।

৮.২বাজারঘরের SHORT = {⟨M⟩ : M দৈর্ঘ্য ৩ বা তার কম কোনো অর্ডার-কোড গ্রহণ করে}. “প্রমাণ: SHORT ≤m ATM (সব ছোট string-এ পালা করে চালানো যন্ত্র দিয়ে)। ATM undecidable, তাই SHORT undecidable. ∎” ভুল কোথায়? — ১০ নম্বর (মাঝারি)

ভুল: দিক উল্টো। SHORT ≤m ATM থেকে শুধু জানা যায় “ATM decidable হলে SHORT decidable” (যা কাজে আসে না), আর ATM recognizable বলে SHORT recognizable. একই যুক্তি যেকোনো decidable সমস্যাকেও “undecidable” বলত, কারণ প্রতিটি decidable L-এর জন্য L ≤m ATM. সংশোধন: ATM ≤m SHORT: f(⟨M, w⟩) = ⟨M′⟩, M′ = “input x: M-কে w-এর ওপর চালান; accept করলে x-কেও accept”. M w গ্রহণ করলে L(M′) = Σ∗, যাতে ছোট string আছে; না করলে L(M′) = ∅. অথবা সরাসরি Rice: ধর্মটি semantic আর non-trivial. NP-hardness-এও একই ফাঁদ: “নতুন সমস্যা ≤p SAT” দেখায় সমস্যাটি NP-তে, NP-hard নয়।

৮.৩“দাবি: L = {anbncmdm} context-free নয়। s = apbpcpdp. ক্ষেত্র: vxy শুধু a-তে, শুধু b-তে, শুধু c-তে বা শুধু d-তে; প্রতিটিতে i = 2 একটি সমতা ভাঙে। বিরোধ। ∎” ভুল কোথায়? — ১০ নম্বর (মাঝারি)

ভুল: ক্ষেত্রগুলো পূর্ণ নয়। vxy দুটি পাশাপাশি খণ্ড ছুঁতে পারে; প্রতিপক্ষ v = শেষ a, y = প্রথম b দিলে a আর b একসঙ্গে বাড়ে-কমে, সমতা অটুট (চেকার p = 2, 3, 4-এ এমন বিভাজন পায়)। সিদ্ধান্তও মিথ্যা: L = {anbn} · {cmdm}, দুটি CFL-এর concatenation, তাই CFL (S → AB, A → aAb ∣ ε, B → cBd ∣ ε)। ৪.২-এর ভাষার সঙ্গে পার্থক্য: সেখানে জোড়ার সঙ্গী খণ্ড কখনো পাশাপাশি নয়, এখানে পাশাপাশি। শিক্ষা: প্রতিটি সীমানার ওপর বসা vxy আলাদা ক্ষেত্র।

৮.৪“HALTTM ≤m E̅TM: f(⟨M, w⟩) = M w-এ থামলে ⟨Mall⟩ (সব গ্রহণ করে), না থামলে ⟨Mnone⟩ (কিছুই নয়)। ⇔ স্পষ্ট। ∎” ভুল কোথায়? — ১০ নম্বর (মাঝারি)

ভুল: f computable নয়। কোন output দিতে হবে, তা ঠিক করতে f-কে জানতে হয় M w-এ থামে কি না — এটিই HALTTM; M না থামলে f-ও চিরকাল চলে। “⇔” সত্য, কিন্তু reduction-এর প্রথম শর্তই ভাঙা। সংশোধন: সিদ্ধান্তটি output-এর ভেতরে সরান: f(⟨M, w⟩) = ⟨M′⟩, M′ = “input x: x উপেক্ষা করে M-কে w-এর ওপর চালান; থামলে accept”. f শুধু কোড লেখে। M থামলে L(M′) = Σ∗ ≠ ∅, না থামলে ∅. নিয়ম: f-এর ভেতরে কখনো প্রশ্নের যন্ত্রটি চালাবেন না।

৮.৫“3SAT ≤p CLIQUE: প্রতিটি literal একটি node, ভিন্ন clause-এর যেকোনো দুটি node-এর মধ্যে edge, k = clause সংখ্যা। φ satisfiable হলে প্রতিটি clause থেকে একটি সত্য literal নিলে k-clique. ∎” ভুল কোথায়? — ১০ নম্বর (কঠিন)

দুটি ভুল একসঙ্গে: (১) নির্মাণে নিয়ম খ নেই: x আর ¬x-এর মধ্যেও edge. (২) শুধু ⇒ দিক প্রমাণ। ⇐ দিকেই নিয়ম খ লাগে, আর এখানে তা ভাঙে: φ = (x ∨ x ∨ x) ∧ (¬x ∨ ¬x ∨ ¬x) unsatisfiable, অথচ ভুল graph-এ ভিন্ন clause-এর ৯টি জোড়ার সবই edge, তাই 2-clique আছে। f তাই “না” instance-কে “হ্যাঁ”-তে পাঠায়। সংশোধন: ৭.২-এর নির্মাণ আর দুই দিকের প্রমাণ। একটি reduction-এর “⇔”-এর প্রতিটি দিক আলাদা শিরোনামে লিখুন।

৮.৬“L = {aibjck : i = 0 অথবা j = k}. p = 1 নিলে L-এর প্রতিটি s প্রথম চিহ্ন y হিসেবে pump করে। তাই L pumping lemma-র শর্ত পূরণ করে, অতএব L regular. ∎” ভুল কোথায়? — ৫ নম্বর (মাঝারি)

ভুল: Pumping lemma regular-এর প্রয়োজনীয় শর্ত, যথেষ্ট শর্ত নয়: “regular ⇒ pump করে” থেকে “pump করে ⇒ regular” আসে না (converse). L সত্যিই pump করে (চেকারে দৈর্ঘ্য ৭ পর্যন্ত ৫১টি সদস্যের প্রতিটি), তবু regular নয়: L ∩ ab∗c∗ = {abjcj}, আর এটি regular নয় (৩.১-এর মতো pumping); regular হলে ছেদও regular হতো। সংশোধন: “Regular” প্রমাণ করতে যন্ত্র বা regex দিন; “regular নয়” প্রমাণে closure বা Myhill–Nerode দিয়ে চেষ্টা করুন।

import re
from itertools import combinations, product
# 8.1: "(aa)* is not regular, take y = a" -- but the adversary may answer y = aa
even = lambda w: len(w) % 2 == 0
print("8.1 split x=ε, y=aa keeps a^(2p) in L, p = 2..8, i = 0..5:",
      all(even("aa" * i + "a" * (2 * p - 2)) for p in range(2, 9) for i in range(6)))
# 8.3: L = a^n b^n c^m d^m is context-free; find a split that survives every pump
def L83(w):
    m = re.fullmatch(r"(a*)(b*)(c*)(d*)", w)
    return bool(m) and len(m[1]) == len(m[2]) and len(m[3]) == len(m[4])
for p in (2, 3, 4):
    s = "a" * p + "b" * p + "c" * p + "d" * p
    hit = next((s[:a] + "|" + s[a:b] + "|" + s[b:c] + "|" + s[c:d] + "|" + s[d:]
                for a in range(len(s)) for b in range(a, len(s)) for c in range(b, len(s))
                for d in range(c, min(a + p, len(s)) + 1) if b - a + d - c >= 1
                and all(L83(s[:a] + s[a:b] * i + s[b:c] + s[c:d] * i + s[d:]) for i in range(5))), None)
    print(f"8.3 p={p}: surviving split u|v|x|y|z = {hit}")
# 8.5: rule b forgotten. phi = (x or x or x) and (not x or not x or not x) is unsatisfiable
phi = [(1, 1, 1), (-1, -1, -1)]
V = [(j, q, l) for j, c in enumerate(phi) for q, l in enumerate(c)]
bad_E = [(u, v) for u, v in combinations(V, 2) if u[0] != v[0]]    # only rule a
print("8.5 edges without rule b:", len(bad_E), "| so a 2-clique exists although phi is unsatisfiable")
# 8.6: L = {a^i b^j c^k : i = 0 or j = k} passes the pumping test with p = 1
def L86(w):
    m = re.fullmatch(r"(a*)(b*)(c*)", w)
    return bool(m) and (len(m[1]) == 0 or len(m[2]) == len(m[3]))
S = [w for k in range(1, 8) for w in map("".join, product("abc", repeat=k)) if L86(w)]
print("8.6 strings in L of length 1..7:", len(S), "| each pumps with y = first symbol:",
      all(L86(w[0] * i + w[1:]) for w in S for i in range(6)))

আসল আউটপুট (ব্রাউজারের Python):

8.1 split x=ε, y=aa keeps a^(2p) in L, p = 2..8, i = 0..5: True
8.3 p=2: surviving split u|v|x|y|z = a|a||b|bccdd
8.3 p=3: surviving split u|v|x|y|z = a|a|a|b|bbcccddd
8.3 p=4: surviving split u|v|x|y|z = a|a|aa|b|bbbccccdddd
8.5 edges without rule b: 9 | so a 2-clique exists although phi is unsatisfiable
8.6 strings in L of length 1..7: 51 | each pumps with y = first symbol: True

৮.১: প্রতিপক্ষের y = aa চালের বিরুদ্ধে কোনো i কাজ করে না। ৮.৩: প্রতিটি p-তে একটি টিকে থাকা বিভাজন, যেমন p = 3-এ v = a আর y = b, সীমানার দুই পাশে। ৮.৫: নিয়ম খ ছাড়া দুই clause-এর মধ্যে ৯টি edge, তাই unsatisfiable সূত্রেও 2-clique. ৮.৬: L-এর দৈর্ঘ্য ১ থেকে ৭-এর ৫১টি string-এর প্রতিটি প্রথম চিহ্ন pump করে L-এই থাকে, তবু L regular নয়।

৯ · সাধারণ ভুলের ছক আর পরীক্ষার হলের কৌশল

ভুলকেমন দেখায়ঠিক কাজপ্রশ্ন
বিভাজন বা p নিজে বাছা“y = a ধরি”, “p = 3 ধরি”“যেকোনো বিভাজন”, যুক্তি p দিয়ে৩.১, ৮.১
ভুল i{aibj : i > j}-এ pump upকোন দিকে সংখ্যা বদলালে শর্ত ভাঙে, তা দেখে i৩.১
CFL-এ ক্ষেত্র বাদসীমানায় বসা vxy ভুলে যাওয়াপ্রতিটি পাশাপাশি খণ্ড-জোড়া আলাদা ক্ষেত্র৪.২, ৮.৩
Lemma-কে যথেষ্ট শর্ত ভাবা“pump করে, তাই regular”regular দেখাতে যন্ত্র দিন৮.৬
এক দিকের প্রমাণশুধু ⊇ বা শুধু ⇒দুই দিক আলাদা শিরোনামে২.৪, ৭.২
Decider-এর থামা না দেখানো“সব derivation চেষ্টা করি”প্রতিটি loop-এর সসীম সীমা লিখুন৫.৩, ৫.৪
উল্টো দিকের reductionনতুন ≤ ATMATM ≤m নতুন; NP-তে 3SAT ≤p নতুন৮.২
হিসাব-অযোগ্য ff-এর ভেতরে M চালানোসিদ্ধান্ত output-যন্ত্রের ভেতরে৮.৪
Rice-এর অপপ্রয়োগstate সংখ্যা বা ধাপ গোনায় Ricesemantic আর non-trivial দুটিই যাচাই৬.৬
NP-completeness অর্ধেকশুধু reduction, NP-তে থাকা বাদverifier আর reduction দুটিই৭.১, ৭.২

হলে সময়: মোট মিনিট ÷ মোট নম্বর দিয়ে প্রতিটি প্রশ্নের সময় ঠিক করুন। আটকে গেলে অনুমান, s-এর বাছাই বা f-এর নির্মাণ লিখে এগিয়ে যান; নম্বর-ভাগে এগুলোরই আলাদা নম্বর। যে ধাপ পারেননি, সেখানে “এখানে দেখাতে হবে যে …” লিখুন; সৎভাবে ফাঁক দেখানো ভুল দাবির চেয়ে ভালো।

আরও গভীরে: এই পাতার বেশিরভাগ প্রমাণ “এক ধাপে উল্টে দেওয়া” কৌশলের রূপ: Cantor-এর diagonal, ATM-এর D, আর hierarchy theorem (পর্ব ৬৭)। কিন্তু Baker–Gill–Solovay-এর ১৯৭৫ সালের ফল (relativization, পর্ব ৬৮) দেখায়, শুধু এই ধরনের simulation আর diagonal যুক্তি P বনাম NP মেটাতে পারে না; প্রশ্নটি আজও খোলা। Lean বা Coq-এর মতো proof assistant-এ automata theory-র অনেক ফল যন্ত্রে যাচাই করা হয়েছে; খাতার “প্রতিটি ধাপে কারণ” অভ্যাস সেদিকেই প্রথম পা।

পরীক্ষা ও ইন্টারভিউতে: “Pumping lemma-য় কে কী বাছেন?” — p আর বিভাজন প্রতিপক্ষ, s আর i আপনি। “Undecidable দেখাতে reduction কোন দিকে?” — জানা-undecidable থেকে নতুনে, ATM ≤m X. “ETM recognizable?” — না; এর complement recognizable, তাই ETM co-recognizable কিন্তু recognizable নয়। “NP-complete প্রমাণে কয়টি অংশ?” — দুটি: X ∈ NP আর জানা NP-complete ≤p X. “Savitch-এর শর্ত?” — f(n) ≥ log n.

১০ · AI-এর যুগে — AI-এর লেখা প্রমাণ যাচাই

AI সহকারী গণনার তত্ত্বের প্রমাণ সুন্দর ভাষায় লেখে, আর প্রায়ই এই পাতার ছয়টি ফাঁদেই পড়ে: pumping-এ বিভাজন নিজে বাছে বা শুধু i = 2 দিয়ে pump করে, CFL প্রমাণে সীমানার ক্ষেত্র বাদ দেয়, decidable আর recognizable গুলিয়ে ফেলে, reduction উল্টো দিকে করে (A ≤ B প্রমাণ করে B-এর কঠিনতা, A-এর নয়), f-এর ভেতরে যন্ত্র চালায়, theorem-এর শর্ত বাদ দেয় (Savitch-এ f(n) ≥ log n, Rice-এ non-trivial), খোলা প্রশ্নকে মীমাংসিত বলে, আর না-থাকা বইয়ের পাতা উল্লেখ করে। তাই AI-কে লেখক নয়, কড়া পরীক্ষক বানান; প্রতিটি দাবি নিজে মেলান।

নিজের লেখা প্রমাণ AI-কে দিয়ে পরীক্ষা করানোর একটি কাঠামো:

তুমি গণনার তত্ত্বের একজন কড়া পরীক্ষক। নিচে একটি প্রমাণের প্রশ্ন আর আমার লেখা উত্তর দিলাম। [প্রশ্ন] [আমার প্রমাণ — প্রতিটি ধাপ নম্বর দিয়ে] ১. আগে বলো দাবিটি কোন ধরনের (regular / regular নয় / CFL নয় / decidable / undecidable / NP-complete) আর আমি কোন হাতিয়ার নিয়েছি; হাতিয়ারটি দাবির সঙ্গে মেলে কি না। ২. Pumping হলে: p আর বিভাজন কি প্রতিপক্ষের হাতে আছে? সব বিভাজন কি ক্ষেত্র ভাগ করে ধরা হয়েছে? কোন ক্ষেত্র বাদ, লাইন নম্বর ধরে বলো। ৩. Reduction হলে: দিক কোনটি, f কি সব input-এ থামে, আর "⇔"-এর দুই দিক কি আলাদা প্রমাণিত? ৪. যে theorem ব্যবহার করেছি, তার সব শর্ত লেখো আর বলো আমার ক্ষেত্রে পূরণ হয়েছে কি না। ৫. আমার যুক্তি কোনো মিথ্যা দাবিও "প্রমাণ" করে কি না, একটি ছোট উদাহরণে দেখাও। ৬. মার্ক-স্কিম বানিয়ে নম্বর দাও; পুরো সঠিক প্রমাণ নিজে লিখে দিও না। ৭. নিশ্চিত না হলে "নিশ্চিত নই" লেখো; কোনো বই, পাতা বা theorem-এর নাম বানাবে না, আর খোলা প্রশ্নকে মীমাংসিত বলবে না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন। সব তথ্য প্রশ্নের ভেতরেই আছে।

ক্রমMapping reduction দিয়ে “X undecidable” প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. একটি জানা-undecidable উৎস বাছা, যেমন ATM
  2. f নির্মাণ: ⟨M, w⟩ থেকে একটি নতুন যন্ত্রের বর্ণনা
  3. f computable দেখানো: শুধু বর্ণনা লেখে, কিছু চালায় না
  4. “⇔”-এর দুই দিক প্রমাণ: M w গ্রহণ করে আর করে না
  5. দিকের নিয়মে উপসংহার: ATM ≤m X, তাই X undecidable

(সহজ) Regular language-এর pumping lemma দিয়ে “L regular নয়” প্রমাণে কোন জোড়া প্রতিপক্ষের হাতে থাকে?

  • s আর i
  • s আর বিভাজন
  • p আর বিভাজন s = xyz
  • p আর i

(মাঝারি) L = {aibj : i > j ≥ 0}, s = ap+1bp. কোন i প্রতিটি বৈধ বিভাজনে xyiz-কে L-এর বাইরে পাঠায়?

  • i = 0
  • i = 1
  • i = 2
  • i = p + 1

(মাঝারি) L3 = {w ∈ {0, 1}∗ : শেষ থেকে তৃতীয় চিহ্ন 1}. Fooling set যুক্তিতে L3-এর যেকোনো DFA-তে অন্তত কয়টি state?

  • 3
  • 4
  • 6
  • 8

(মাঝারি) CFL pumping lemma-র শর্ত |vxy| ≤ p-এর সঠিক অর্থ কোনটি?

  • vxy s-এর প্রথম p চিহ্নের মধ্যে থাকে
  • vxy একটানা, দৈর্ঘ্য বড়জোর p, কিন্তু s-এর যেকোনো জায়গায়
  • v আর y প্রতিটির দৈর্ঘ্য বড়জোর p/2
  • v আর y দুটিই ফাঁকা নয়

(মাঝারি) বাজারঘরের একটি নতুন প্রশ্ন X undecidable প্রমাণ করতে চান। কোন reduction যথেষ্ট?

  • ATM ≤m X
  • X ≤m ATM
  • X ≤m EDFA
  • EDFA ≤m X

(মাঝারি) ETM = {⟨M⟩ : L(M) = ∅}-এর সঠিক অবস্থা কোনটি?

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

(কঠিন) নিচের কোন সেটের undecidability সরাসরি Rice-এর theorem থেকে আসে?

  • {⟨M⟩ : M-এর state ঠিক ৭টি}
  • {⟨M⟩ : M ε-এর ওপর ৫০ ধাপের মধ্যে থামে}
  • {⟨M⟩ : ⟨M⟩-এর দৈর্ঘ্য জোড়}
  • {⟨M⟩ : L(M)-এ ঠিক ৩টি string}

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

  • চলক সংখ্যার দ্বিগুণ node, k = 3
  • 15টি node, k = 5
  • 15টি node, k = 3
  • 5টি node, k = 5

শব্দকোষ

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

মনে রাখুন

  1. আগে পড়া, তারপর হাতিয়ার: দাবিটি অস্তিত্বের (একটি যন্ত্র দিন) নাকি অসম্ভবতার (সব যন্ত্র বা সব বিভাজনের বিরুদ্ধে খেলুন)? প্রথম লাইনেই পদ্ধতি আর দিক লিখুন।
  2. নির্মাণ আর সঠিকতা আলাদা: product, reversal, CFG থেকে PDA; তারপর invariant আর দুই দিকের inclusion.
  3. Pumping একটি খেলা: p আর বিভাজন প্রতিপক্ষের; সব বিভাজন ক্ষেত্র ভাগ করে ধরুন, দরকারে i = 0. Lemma শুধু প্রয়োজনীয় শর্ত।
  4. Reduction-এর তিন শর্ত: f computable, “⇔”-এর দুই দিক, আর দিক: জানা-কঠিন বাঁয়ে। NP-complete মানে NP-তে থাকা আর NP-hard দুটিই।
  5. যাচাই আর সততা: ছোট ক্ষেত্রে brute force দিয়ে ভুল ধরুন, কিন্তু তাকে প্রমাণ বলবেন না; খোলা প্রশ্নকে খোলা বলুন।

পরের পর্বে: পর্ব ৮৫ “ইন্টারভিউ আর প্রতিযোগিতায় গণনার তত্ত্ব — regex, parsing আর complexity”: এখানকার reduction আর automaton-এর যুক্তি কাজে লাগবে regex, tokenizer, parser আর “এটি কি NP-hard?” ধরনের ইন্টারভিউ প্রশ্নে।

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

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