এই পর্বে যা শিখবেন
- দাবির আকার দেখে হাতিয়ার বাছা: নির্মাণ, 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-এ “সব যন্ত্র” একসঙ্গে হারাতে হয়। তাই “একটি উদাহরণে মিলেছে” কখনো যথেষ্ট নয়। প্রমাণের ধরনগুলো পর্ব ০৪-এ শেখানো হয়েছে; এখানে সেগুলো খাতায় লেখার অনুশীলন।
- পড়া: দাবিটি কোন ধরনের? “L regular” (অস্তিত্ব: একটি যন্ত্র দেখান), “L regular নয়” (সব যন্ত্রের বিরুদ্ধে), “X undecidable” (কোনো decider নেই), “X NP-complete” (দুটি আলাদা দাবি)।
- হাতিয়ার: নিচের ছবির সংকেত দেখে বাছুন, আর প্রথম লাইনেই লিখুন: “বিরোধের জন্য ধরি L regular” বা “ATM ≤m X দেখাব”।
- লেখা: প্রতিটি লাইনের পাশে কারণ: সংজ্ঞা, lemma-র কোন শর্ত, কোন পর্বের উপপাদ্য। নির্মাণ থাকলে আগে নির্মাণ, তারপর আলাদা করে সঠিকতা।
- যাচাই: খসড়ায় ছোট p, ছোট string বা ছোট সূত্রে মেলান। মিলে গেলেও তা প্রমাণ নয়; না মিললে দাবি বা যুক্তি ভুল।
ছবি ৮৪.১ — দাবির আকার থেকে প্রমাণের হাতিয়ার
বাঁয়ে প্রশ্নে যা দেখবেন, ডানে প্রথমে যে হাতিয়ার চেষ্টা করবেন
ছবিটি প্রথম চেষ্টার দিক, নিয়ম নয়। একই দাবির একাধিক প্রমাণ থাকে: {0n1m : n ≠ m} সরাসরি pumping-এ কঠিন, কিন্তু closure দিয়ে তিন লাইনে হয় (৩.২)। নিচের stepper-এ একটি ১০ নম্বরের pumping উত্তর শুরু থেকে ∎ পর্যন্ত গড়া হয়েছে, প্রতিটি ধাপে জমা নম্বরসহ।
| ধাপ | |
| খাতায় যা লিখলেন | |
| উদাহরণের string | |
| জমা নম্বর |
- অনুমান — ১ নম্বর। p-এর মান আপনি জানেন না, আর জানার দরকারও নেই। p = 4 শুধু উদাহরণ দেখানোর জন্য; খাতায় সব যুক্তি p দিয়ে।
- s বাছাই — আরও ২। s-কে L-এর সদস্য হতে হবে: apbp নিলে a আর b সমান, তাই s ∉ L, আর পুরো প্রমাণ অচল। এক বাড়তি a সমস্যাটি মেটায়।
- বিভাজন — নম্বর নেই। প্রতিপক্ষের চাল। উদাহরণের বিভাজনটি তাঁর একটি সম্ভাব্য চাল মাত্র; আপনি এটি বাছেননি, তাই পরের ধাপে সব বিভাজন একসঙ্গে ধরতে হবে।
- সাধারণ রূপ — আরও ৩। |xy| ≤ p থেকে y শুধু a. এই এক লাইনেই প্রতিপক্ষের সব চাল ধরা পড়ে; নম্বরের বড় অংশ এখানেই।
- i বাছাই — আরও ৩। Pump up (i = 2) a বাড়ায়, তাতে i > j আরও শক্ত হয়, string L-এই থাকে। তাই pump down (i = 0): a কমে বড়জোর p, আর b = p, তাই i > j ভাঙে।
- উপসংহার — শেষ ১। “প্রতিটি বৈধ বিভাজনে” কথাটি লিখুন, আর 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 অদলবদল করলে কেন একই যুক্তি চলে না, একটি উদাহরণ দিন। — ৫ নম্বর (সহজ)
- L regular, তাই L চেনে এমন একটি সম্পূর্ণ DFA M = (Q, Σ, δ, q0, F) আছে (NFA থেকে subset construction, দরকারে dead state যোগ করে)। — পর্ব ১০
- M′ = (Q, Σ, δ, q0, Q ∖ F) নিন: শুধু accepting state-এর সেট উল্টানো। — নির্মাণ
- M সম্পূর্ণ আর deterministic, তাই প্রতিটি w-এ δ̂(q0, w) ঠিক একটি state, আর M ও M′-এ সেটি একই। তাই w ∈ L(M′) ⇔ δ̂(q0, w) ∉ F ⇔ w ∉ L. — একই run, ভিন্ন F
- অতএব 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 দিয়ে দেখান। — ১০ নম্বর (মাঝারি)
- M1 = (Q1, Σ, δ1, q1, F1) আর M2 = (Q2, Σ, δ2, q2, F2) সম্পূর্ণ DFA, L(Mi) = Li. — অনুমান
- M = (Q1 × Q2, Σ, δ, (q1, q2), F1 × F2), যেখানে δ((r, s), a) = (δ1(r, a), δ2(s, a)). — product construction
- দাবি: সব w-এ δ̂((q1, q2), w) = (δ̂1(q1, w), δ̂2(q2, w)). ভিত্তি w = ε: দুই দিকই (q1, q2). — |w|-এর ওপর induction
- ধাপ w = ua: δ̂(…, ua) = δ(δ̂(…, u), a) = δ((δ̂1(q1, u), δ̂2(q2, u)), a) = (δ̂1(q1, ua), δ̂2(q2, ua)). — hypothesis, তারপর δ-র সংজ্ঞা
- তাই 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}, অর্থাৎ প্রতিটি তীর উল্টো।
- (⇒) w = a1⋯an ∈ L হলে M-এর run r0 = q0, r1, …, rn ∈ F আছে, যেখানে δ(ri−1, ai) = ri. — DFA-র গ্রহণ
- δR-এর সংজ্ঞায় ri−1 ∈ δR(ri, ai). তাই N-এ পথ s → rn → rn−1 → ⋯ → r0 = q0, যা an⋯a1 = wR পড়ে accepting state-এ থামে। — পথ উল্টো পড়া
- (⇐) 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. — একই সংজ্ঞা, উল্টো দিকে
- 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).
- (⊆) দাবি: S থেকে আসা প্রতিটি sentential form হয় aiSbj, নয় aibj, যেখানে i ≥ j. Derivation-এর ধাপের ওপর induction; ভিত্তি: S = a0Sb0. — invariant
- ধাপ: একটিমাত্র variable S, তার তিন নিয়ম। aiSbj থেকে S → aSb দেয় ai+1Sbj+1, S → aS দেয় ai+1Sbj, S → ε দেয় aibj; তিনটিতেই i ≥ j টিকে থাকে। — নিয়ম গুনে দেখা
- L(G)-এর string-এ variable নেই, তাই তা aibj, i ≥ j: L(G) ⊆ L. — invariant-এর ফল
- (⊇) 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: “ε, $ → ε”.
- G-এর জন্য qloop-এর নিয়ম: ε, S → aSb; ε, S → aS; ε, S → ε; a, a → ε; b, b → ε. — নির্মাণ
- Invariant: input-এর u অংশ পড়া হয়েছে আর stack-এ γ$ (ওপর বাঁয়ে) থাকলে, S ⇒∗ uγ একটি leftmost derivation-এ। — stack = sentential form-এর বাকি অংশ
- Variable ওপরে থাকলে PDA একটি নিয়ম অনুমান করে (leftmost derivation-এর এক ধাপ); terminal ওপরে থাকলে input-এর পরের চিহ্নের সঙ্গে মেলায়। — nondeterminism অনুমানের কাজ করে
- $ ওপরে এলে আর 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 নয়। — ১০ নম্বর (মাঝারি)
- বিরোধের জন্য ধরি L regular; lemma একটি pumping length p দেয়। — contradiction
- s = ap+1bp নিন: p + 1 > p, তাই s ∈ L; |s| = 2p + 1 ≥ p. — s আপনার চাল
- যেকোনো বিভাজন s = xyz, |xy| ≤ p, |y| ≥ 1. s-এর প্রথম p চিহ্ন a, তাই y = ak, 1 ≤ k ≤ p. — সব বিভাজন একসঙ্গে
- i = 0: xz = ap+1−kbp. k ≥ 1, তাই a-র সংখ্যা ≤ p = b-র সংখ্যা: xz ∉ L. — pump down
- প্রতিটি বৈধ বিভাজনে lemma-র শর্ত ৩ ভাঙে, তাই L regular নয়। ∎
নম্বর-ভাগ: অনুমান (১), s আর s ∈ L (২), y-এর সাধারণ রূপ (৩), i = 0 আর কারণ (৩), উপসংহার (১)। যেখানে নম্বর কাটে: i = 2 নেওয়া: a বাড়লে i > j আরও সত্য হয়, তাই কোনো বিরোধ নেই (চেকার সব বিভাজনে তা দেখায়); s = apbp নেওয়া, যা L-এই নেই।
৩.২Closure property দিয়ে প্রমাণ করুন: L = {0n1m : n ≠ m} regular নয়। — ৫ নম্বর (মাঝারি)
- বিরোধের জন্য ধরি L regular. — অনুমান
- Regular language complement (২.১) আর ছেদে (২.২) বদ্ধ, আর 0∗1∗ regular; তাই L̄ ∩ 0∗1∗ regular. — closure
- L̄-এ 0∗1∗ আকারের বাইরের সব string আর 0n1n; ছেদ নিলে বাইরের অংশ বাদ যায়: L̄ ∩ 0∗1∗ = {0n1n : n ≥ 0}. — set-এর হিসাব
- কিন্তু {0n1n} regular নয় (পর্ব ১৭)। বিরোধ; L regular নয়। ∎
নম্বর-ভাগ: কোন closure কেন (২), ছেদের হিসাব (২), উপসংহার (১)। সরাসরি pumping এখানে কঠিন; closure পথটি নিরাপদ।
৩.৩Myhill–Nerode দিয়ে প্রমাণ করুন: PAL = {w ∈ {a, b}∗ : w = wR} regular নয়। S = {ai : i ≥ 0} নিলে z = ai কেন কাজ করে না, আর কোন z করে, তাও বলুন। — ১০ নম্বর (মাঝারি)
- S = {aib : i ≥ 0} নিন; S অসীম। — fooling set
- i ≠ j হলে z = ai নিন। aibai palindrome, তাই ∈ PAL. — সরাসরি
- ajbai-এ ঠিক একটি b; palindrome হলে b-টি মাঝখানে থাকত আর দুই পাশে সমান a থাকত। j ≠ i, তাই ∉ PAL. — একমাত্র b-এর অবস্থান
- 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 লাগে। — ১০ নম্বর (কঠিন)
- S = {0, 1}k, দৈর্ঘ্য k-এর সব string; |S| = 2k. — প্রার্থী সেট
- x ≠ y ∈ S নিন; i = প্রথম অবস্থান যেখানে তারা আলাদা (1 ≤ i ≤ k). সাধারণতা না হারিয়ে xi = 1, yi = 0. — নামকরণ
- z = 0i−1. |xz| = k + i − 1, তাই xz-এর শেষ থেকে k-তম চিহ্ন অবস্থান (k + i − 1) − k + 1 = i-তে: xi = 1, অর্থাৎ xz ∈ Lk; একইভাবে yz-এ সেখানে 0, তাই yz ∉ Lk. — অবস্থান গোনা
- 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 নয়।” দাবিটি সত্য না মিথ্যা? প্রমাণ দিন। — ৫ নম্বর (সহজ)
- L-এ ঠিক ১০০১টি string, তাই L সসীম। — গোনা
- প্রতিটি সসীম language regular: প্রতিটি string একটি regex, আর সসীম সংখ্যক regex-এর ∪ আবার regex. — সংজ্ঞা আর closure
- তাই দাবিটি মিথ্যা; 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 নয়। — ১০ নম্বর (মাঝারি)
- বিরোধের জন্য ধরি L context-free; lemma একটি p দেয়। s = apbpcp ∈ L, |s| = 3p ≥ p. — অনুমান, s বাছাই
- যেকোনো বিভাজন s = uvxyz, |vy| ≥ 1, |vxy| ≤ p. শেষ a আর প্রথম c-এর মাঝে p টি b, তাই vxy-তে a আর c একসঙ্গে নেই। — |vxy| ≤ p
- ক্ষেত্র ১: v বা y-তে দুই রকম চিহ্ন (যেমন v = ab). i = 2-এ “ab ab” দেখা দেয়, a∗b∗c∗ ক্রম ভাঙে: ∉ L. — ক্রম
- ক্ষেত্র ২: v আর y প্রতিটি এক রকম চিহ্নের (বা ফাঁকা)। i = 2-এ vy-এর চিহ্নগুলোর সংখ্যা বাড়ে (|vy| ≥ 1), কিন্তু ধাপ ২ অনুযায়ী অন্তত একটি চিহ্ন অছোঁয়া, তার সংখ্যা p-ই থাকে: তিন সংখ্যা সমান নয়, ∉ L. — গণনা
- দুই ক্ষেত্র সব সম্ভাবনা ঢাকে; প্রতিটিতে বিরোধ, তাই L context-free নয়। ∎
নম্বর-ভাগ: অনুমান আর s (২), “a আর c একসঙ্গে নয়” কারণসহ (২), ক্ষেত্র ১ (২), ক্ষেত্র ২ (৩), ক্ষেত্রের পূর্ণতা (১)। যেখানে নম্বর কাটে: “vxy প্রথম p চিহ্নে” লেখা (এটি regular lemma-র |xy| ≤ p); ক্ষেত্র ১ ভুলে যাওয়া; “v = a, y = b ধরি” লিখে একটি বিভাজন বাছা।
৪.২প্রমাণ করুন: L = {ambncmdn : m, n ≥ 0} context-free নয়। — ১০ নম্বর (কঠিন)
- বিরোধের জন্য ধরি L CFL, p তার pumping length; s = apbpcpdp ∈ L. — প্রতিটি খণ্ড অন্তত p লম্বা
- যেকোনো বৈধ বিভাজনে |vxy| ≤ p, তাই vxy বড়জোর দুটি পাশাপাশি খণ্ড ছোঁয়: (a, b), (b, c) বা (c, d), অথবা একটি খণ্ড। — দৈর্ঘ্যের সীমা
- ক্ষেত্র ১: v বা y-তে দুই রকম চিহ্ন। i = 2-এ a∗b∗c∗d∗ ক্রম ভাঙে: ∉ L. — ক্রম
- ক্ষেত্র ২: v, y প্রতিটি এক রকম। শর্তের জোড়া (a, c) আর (b, d); কোনো জোড়ার দুই সদস্য পাশাপাশি নয়। vy অন্তত একটি খণ্ড বদলায়, আর তার জোড়ার সঙ্গী খণ্ড vxy-এর বাইরে, তাই i = 2-এ একটির সংখ্যা p-এর বেশি, সঙ্গীটি p: ∉ L. — জোড়ার সঙ্গী অছোঁয়া
- সব বিভাজনে বিরোধ; L context-free নয়। ∎
নম্বর-ভাগ: s (১), “পাশাপাশি দুই খণ্ড” (৩), ক্ষেত্র ১ (২), ক্ষেত্র ২-এর জোড়া-সঙ্গী যুক্তি (৩), উপসংহার (১)। যেখানে নম্বর কাটে: |vxy| ≤ p ব্যবহার না করা: তখন v = a, y = c একসঙ্গে বাড়লে string L-এই থাকে, আর প্রমাণ আটকে যায়।
৪.৩প্রমাণ করুন: EQ3 = {w ∈ {a, b, c}∗ : w-এ a, b আর c সমান সংখ্যক} context-free নয়। — ৫ নম্বর (মাঝারি)
- বিরোধের জন্য ধরি EQ3 CFL. CFL আর regular language-এর ছেদ CFL (PDA × DFA নির্মাণ, পর্ব ৩৭)। — closure
- a∗b∗c∗ regular, আর EQ3 ∩ a∗b∗c∗ = {anbncn}. — set-এর হিসাব
- ৪.১ অনুযায়ী এটি CFL নয়: বিরোধ। ∎
নম্বর-ভাগ: সঠিক closure (দুটি CFL-এর ছেদ নয়, regular-এর সঙ্গে ছেদ) (২), ছেদের হিসাব (২), উপসংহার (১)। যেখানে নম্বর কাটে: “CFL ছেদে বদ্ধ” লেখা — মিথ্যা (৪.৪)।
৪.৪প্রমাণ করুন: context-free language ছেদ আর complement-এ বদ্ধ নয়। — ১০ নম্বর (মাঝারি)
- L1 = {anbncm}: S → TC, T → aTb ∣ ε, C → cC ∣ ε. L2 = {ambncn}: S → AU, A → aA ∣ ε, U → bUc ∣ ε. দুটিই CFL. — grammar দিয়ে সাক্ষী
- L1 ∩ L2 = {anbncn}: প্রথমটি a = b চায়, দ্বিতীয়টি b = c. এটি CFL নয় (৪.১)। তাই ছেদে বদ্ধতা মিথ্যা। — counterexample
- ধরি 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) সময় নেয়। — ১০ নম্বর (মাঝারি)
- k-tape M দেওয়া। Single-tape S সব tape পাশাপাশি রাখে: #w1#w2#⋯#wk#, আর প্রতিটি head-এর ঘরের চিহ্নের ওপর একটি ফোঁটা (ফোঁটাওয়ালা চিহ্ন Γ-তে নতুন চিহ্ন)। — এনকোডিং
- M-এর এক ধাপের জন্য S বাঁ থেকে ডানে একবার হেঁটে k টি ফোঁটাওয়ালা চিহ্ন পড়ে, finite control-এ রাখে (k স্থির, তাই সসীম তথ্য)। — পড়া
- দ্বিতীয় হাঁটায় M-এর δ অনুযায়ী চিহ্ন লেখে আর ফোঁটা সরায়। কোনো ফোঁটা ডানের #-এ পড়লে বাকি tape এক ঘর ডানে সরিয়ে সেখানে ␣ বসায়। — লেখা
- Invariant: প্রতিটি simulated ধাপের পর S-এর tape M-এর configuration-এর হুবহু এনকোডিং; তাই M accept/reject করলে S-ও তাই করে, আর L(S) = L(M). — simulation argument
- সময়: 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 কেন চলবে না, বলুন। — ১০ নম্বর (কঠিন)
- N-এর প্রতিটি configuration-এ বড়জোর b টি পছন্দ। Computation tree-এর প্রতিটি node-কে একটি address দিয়ে চেনা যায়: {1, …, b}-এর ওপর একটি string. — গাছের ঠিকানা
- D-এর তিনটি tape: input (কখনো বদলায় না), simulation, address. Address shortlex ক্রমে নেওয়া হয় (ε, 1, 2, …, 11, 12, …), যা গাছের BFS. — নির্মাণ
- প্রতিটি address-এর জন্য: input simulation tape-এ কপি, তারপর address-এর পছন্দ ধরে N চালানো। Accepting configuration এলে accept; পছন্দ অবৈধ হলে বা address শেষ হলে পরের address. — এক শাখা চালানো
- 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. — ৫ নম্বর (সহজ)
- M = “input ⟨B, w⟩: (১) input বৈধ এনকোডিং না হলে reject; (২) B-কে w-এর ওপর simulate করুন, প্রতিটি চিহ্নে transition table থেকে পরের state; (৩) শেষ state F-এ থাকলে accept, নইলে reject.” — নির্মাণ
- থামে: ঠিক |w| টি ধাপ, প্রতিটি সসীম table-খোঁজা। — সসীম কাজ
- সঠিক: শেষ state = δ̂(q0, w), আর DFA-র গ্রহণের সংজ্ঞা হুবহু এটিই। ∎
নম্বর-ভাগ: decider (২), থামার কারণ (২), সঠিকতা (১)। যেখানে নম্বর কাটে: বৈধ এনকোডিং পরীক্ষা না করা; “থামে” কথাটি না লেখা।
৫.৪প্রমাণ করুন: ECFG = {⟨G⟩ : G একটি CFG আর L(G) = ∅} decidable. — ১০ নম্বর (মাঝারি)
- R = “input ⟨G⟩: সব terminal চিহ্নিত করুন; প্রতি round-এ এমন নিয়ম A → U1⋯Uk খুঁজুন যার সব Ui চিহ্নিত, তাহলে A চিহ্নিত; নতুন কিছু না এলে থামুন; S চিহ্নিত না হলে accept, নইলে reject.” — নির্মাণ
- থামে: প্রতি round-এ অন্তত একটি নতুন variable চিহ্নিত হয়, নইলে থামা; তাই বড়জোর |V| + 1 round. — সসীম V
- (চিহ্নিত ⇒ generating) round-এর ওপর induction: A → U1⋯Uk-এর প্রতিটি Ui থেকে terminal string wi আসে, তাই A ⇒∗ w1⋯wk. — induction
- (generating ⇒ চিহ্নিত) A ⇒∗ w-এর parse tree-র উচ্চতার ওপর induction: root-এর নিয়মের প্রতিটি সন্তান ছোট গাছের root, তাই আগেই চিহ্নিত; ফলে A-ও চিহ্নিত হয়। — উল্টো দিক
- 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. — ১০ নম্বর (মাঝারি)
- (⇒) L-এর decider নিজেই একটি recognizer. Accept আর reject অদলবদল করলে L̄-এর decider, তাই L̄-ও recognizable. — সংজ্ঞা
- (⇐) M1 L চেনে, M2 L̄ চেনে। M = “input w: M1 আর M2-কে পালা করে এক ধাপ এক ধাপ চালান (দুটি tape-এ); M1 accept করলে accept, M2 accept করলে reject.” — সমান্তরাল চালানো
- প্রতিটি w হয় L-এ, নয় L̄-এ; তাই M1 বা M2-এর একটি সসীম ধাপে accept করে, আর M থামে: M decider. — থামা
- 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 নয়। — ১০ নম্বর (কঠিন)
- বিরোধের জন্য ধরি H একটি decider যা ATM decide করে: H(⟨M, w⟩) সবসময় থামে, M w গ্রহণ করলে accept, নইলে (reject বা loop) reject. — অনুমান
- D = “input ⟨M⟩: H-কে ⟨M, ⟨M⟩⟩-এর ওপর চালান; H accept করলে reject, H reject করলে accept.” H থামে, তাই D-ও সবসময় থামে। — নির্মাণ
- যেকোনো TM M-এর জন্য: D ⟨M⟩ গ্রহণ করে ⇔ M ⟨M⟩ গ্রহণ করে না। — H-এর সঠিকতা
- D নিজেও একটি TM; M = D বসালে: D ⟨D⟩ গ্রহণ করে ⇔ D ⟨D⟩ গ্রহণ করে না। স্ববিরোধ। — diagonal
- H-এর অস্তিত্বের অনুমান ছাড়া সব ধাপ বৈধ, তাই H নেই: ATM undecidable. ∎
নম্বর-ভাগ: H-এর পূর্ণ সংজ্ঞা, “সবসময় থামে” সহ (২), D (৩), সাধারণ M-এর ⇔ (২), D-তে বসানো আর স্ববিরোধ (২), উপসংহার (১)। যেখানে নম্বর কাটে: H-কে recognizer ধরা (তখন D loop করতে পারে, আর স্ববিরোধ আসে না); D-কে ⟨M, w⟩ input দেওয়া (diagonal-এর জন্য M-কে নিজের বর্ণনাই দিতে হয়)।
| ধাপ | |
| M1 সারি | |
| M2 সারি | |
| M3 সারি | |
| M4 সারি | |
| D সারি |
- টেবিল। H থাকলে এই অসীম টেবিলের প্রতিটি ঘর হিসাব করা যেত: সারি Mi, কলাম ⟨Mj⟩, ঘরে Mi ⟨Mj⟩ গ্রহণ করে কি না। মানগুলো নিচের ব্লকের পাঁচটি খেলনা program-এর প্রথম চারটি থেকে।
- কর্ণ। D শুধু কর্ণের ঘর দেখে: Mi-কে তার নিজের বর্ণনা ⟨Mi⟩ দিলে কী হয়। এখানে acc, rej, rej, acc.
- উল্টানো। D প্রতিটি কর্ণের ঘরের উল্টো উত্তর দেয়: rej, acc, acc, rej. এই সারিটিই D-এর আচরণ।
- তুলনা। D-এর সারি Mi-এর সারি থেকে অন্তত কলাম i-তে আলাদা, তাই D তালিকার কোনো Mi নয়। কিন্তু তালিকায় সব TM আছে, আর D একটি TM.
- D-এর নিজের ঘর। D যদি কোনো সারি Mk হয়, তবে ঘর (k, k)-তে D-এর উত্তর হতে হয় নিজের উল্টো: অসম্ভব। ব্লকে এই ঘরটি হিসাব করতে গেলে Python নিজেকে অবিরাম ডাকতে থাকে।
- উপসংহার। স্ববিরোধের একমাত্র উৎস 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 নয়। — ৫ নম্বর (মাঝারি)
- ATM recognizable: universal TM U = “⟨M, w⟩: M-কে w-এর ওপর চালান, M accept করলে accept”. — পর্ব ৪৮
- A̅TM-ও recognizable হলে ৫.৫ অনুযায়ী ATM decidable হতো। — ৫.৫
- ৬.১-এর বিরোধী; তাই A̅TM recognizable নয়। ∎
নম্বর-ভাগ: U (২), ৫.৫-এর প্রয়োগ (২), উপসংহার (১)। যেখানে নম্বর কাটে: “ATM undecidable, তাই complement recognizable নয়” — মাঝের ধাপ (ATM recognizable) ছাড়া যুক্তি অসম্পূর্ণ।
৬.৩ATM থেকে mapping reduction দিয়ে প্রমাণ করুন: HALTTM = {⟨M, w⟩ : M w-এর ওপর থামে} undecidable. — ১০ নম্বর (মাঝারি)
- f(⟨M, w⟩) = ⟨M′, w⟩, যেখানে M′ = “input x: M-কে x-এর ওপর চালান; M accept করলে accept; M reject করলে চিরকাল loop করুন।” অবৈধ input-এর ছবি একটি স্থির ⟨Mloop, ε⟩, যে কখনো থামে না। — নির্মাণ
- f computable: M-এর নিয়মের সারণি নকল করে reject state-কে একটি loop-এ বদলানো; M চালানো হয় না, তাই f সব input-এ থামে। — computability
- (⇒) M w গ্রহণ করলে M′ w-এ accept করে থামে: ⟨M′, w⟩ ∈ HALTTM. — প্রথম দিক
- (⇐) M w গ্রহণ না করলে হয় reject (M′ loop করে), নয় loop (M′-ও loop করে): ⟨M′, w⟩ ∉ HALTTM. — দ্বিতীয় দিক, দুই উপক্ষেত্র
- ATM ≤m HALTTM, আর ATM undecidable (৬.১), তাই HALTTM undecidable. ∎ — দিকের নিয়ম
নম্বর-ভাগ: f আর M′ (৩), computability (২), ⇒ (২), ⇐ দুই উপক্ষেত্রসহ (২), দিকসহ উপসংহার (১)। যেখানে নম্বর কাটে: f-এর ভেতরে M চালিয়ে দেখা (৮.৪); ⇐-এ “M loop করে” ক্ষেত্রটি বাদ।
৬.৪ETM = {⟨M⟩ : L(M) = ∅}. প্রমাণ করুন: ETM undecidable, আর Turing-recognizable-ও নয়। — ১০ নম্বর (কঠিন)
- f(⟨M, w⟩) = ⟨M1⟩, M1 = “input x: x ≠ w হলে reject; x = w হলে M-কে w-এর ওপর চালান, M accept করলে accept.” w M1-এর সারণিতে বসানো (hard-wired); f কিছু চালায় না, তাই computable. — নির্মাণ
- M w গ্রহণ করলে L(M1) = {w} ≠ ∅; না করলে L(M1) = ∅. তাই ⟨M, w⟩ ∈ ATM ⇔ ⟨M1⟩ ∈ E̅TM: ATM ≤m E̅TM. — ⇔ দুই দিক
- তাই E̅TM undecidable; decidable language complement-এ বদ্ধ, তাই ETM-ও undecidable. — দিকের নিয়ম, complement
- 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. — ১০ নম্বর (কঠিন)
- f(⟨M, w⟩) = ⟨M2⟩, M2 = “input x: x যদি 0n1n আকারের হয়, accept; নইলে M-কে w-এর ওপর চালান, M accept করলে accept.” — নির্মাণ, computable
- M w গ্রহণ করলে প্রতিটি x গৃহীত: L(M2) = Σ∗, regular. — ⇒
- না করলে শুধু প্রথম শাখা: L(M2) = {0n1n}, regular নয় (পর্ব ১৭)। — ⇐
- 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-এ “হ্যাঁ”, একটিতে “না”।
- (ক) শুধু L(M)-এর ওপর নির্ভর করে; Σ∗ চেনা যন্ত্রে হ্যাঁ, সব বর্জন করা যন্ত্রে না। Rice: undecidable. — দুই শর্ত যাচাই
- (খ) Syntactic: ⟨M⟩ পড়ে state গুনলেই হয়, সবসময় থামে। Decidable; Rice খাটে না। — বর্ণনার ধর্ম
- (গ) Language-এর ধর্ম নয়: একই language-এর দুটি যন্ত্র ε-এ ভিন্ন ধাপ নিতে পারে। ১০০ ধাপ simulate করে দেখা যায়, তাই decidable. — সীমিত simulation
- (ঘ) 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-তে আছে। — ৫ নম্বর (সহজ)
- Certificate c: G-এর k টি vertex-এর একটি তালিকা। — সাক্ষী
- V = “⟨⟨G, k⟩, c⟩: c-তে ঠিক k টি আলাদা vertex আর সবগুলো G-তে আছে কি না দেখুন; c-এর প্রতিটি জোড়া G-এর edge কি না দেখুন; সব হ্যাঁ হলে accept.” — verifier
- সময়: k(k − 1)/2 টি জোড়া, প্রতিটির খোঁজ adjacency matrix-এ স্থির সময়ে; k ≤ n, তাই O(n2), input-এর দৈর্ঘ্যে polynomial. — সময়
- ⟨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).
- (⇒) φ satisfiable হলে একটি satisfying মানে প্রতিটি clause-এ অন্তত একটি সত্য literal; প্রতিটি ত্রয়ী থেকে এমন একটি node নিন: k টি node. — বাছাই
- যেকোনো দুটি বাছা node ভিন্ন ত্রয়ীর (নিয়ম ক পার), আর দুটিই একই মানে সত্য, তাই পরস্পরবিরোধী নয় (নিয়ম খ পার): edge আছে। তাই k-clique. — দুই নিয়ম
- (⇐) G-তে k-clique থাকলে ত্রয়ীর ভেতরে edge নেই বলে প্রতিটি ত্রয়ী থেকে ঠিক একটি node. — pigeonhole
- Clique-এর literal-গুলো সত্য ধরুন (অন্য চলক যেকোনো মান)। দুটি পরস্পরবিরোধী literal clique-এ থাকতে পারে না (নিয়ম খ), তাই মানটি সংগত, আর প্রতিটি clause-এ একটি সত্য literal: φ satisfiable. — সংগত assignment
- f polynomial: 3k node, প্রতিটি জোড়ার সিদ্ধান্ত স্থির সময়ে, O(k2). তাই 3SAT ≤p CLIQUE; 3SAT NP-complete আর CLIQUE ∈ NP (৭.১), অতএব CLIQUE NP-complete. ∎
নম্বর-ভাগ: নির্মাণ (২), ⇒ (২), ⇐ দুই ধাপে (৩), polynomial সময় (১), NP-তে থাকা আর দিকসহ উপসংহার (২)। যেখানে নম্বর কাটে: শুধু ⇒ প্রমাণ (৮.৫); assignment-এর সংগতি না দেখানো; “CLIQUE ∈ NP” ভুলে যাওয়া — তখন শুধু NP-hard প্রমাণ হয়।
| ধাপ | |
| যা হলো | |
| গণনা |
- Input. f φ-এর লেখা পড়ে, কোনো মান বসিয়ে পরীক্ষা করে না। Clause তিনটি, তাই লক্ষ্য k = 3.
- Node. প্রতিটি literal-এর জন্য আলাদা node, একই চলক দুই clause-এ থাকলেও। মোট 3k = ৯টি node, ৯ × ৮ / ২ = ৩৬টি জোড়া।
- নিয়ম ক। প্রতিটি ত্রয়ীর ভেতরে ৩টি জোড়া, মোট ৯টি বাদ। বাকি ২৭টি জোড়া ভিন্ন ত্রয়ীর।
- নিয়ম খ। পরস্পরবিরোধী ৬টি জোড়া: 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.
- ⇒ দিক। x = 0, y = 0, z = 1 φ-কে সত্য করে। প্রতিটি clause থেকে একটি সত্য literal: C1-এর ¬y, C2-এর ¬x, C3-এর ¬x. তিনটি ভিন্ন ত্রয়ীর, কেউ কারও বিরোধী নয় (দুটি ¬x একই literal): 3-clique.
- ⇐ দিক। উল্টো দিকে 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. — ১০ নম্বর (মাঝারি)
- f1(⟨G, k⟩) = ⟨Ḡ, k⟩, যেখানে Ḡ complement graph. S G-তে clique ⇔ S-এর প্রতিটি জোড়া G-এর edge ⇔ কোনো জোড়া Ḡ-এর edge নয় ⇔ S Ḡ-তে independent. — সংজ্ঞা উল্টানো
- f2(⟨G, k⟩) = ⟨G, n − k⟩. দাবি: S independent ⇔ V ∖ S একটি vertex cover. — নির্মাণ
- (⇒) কোনো edge uv-এর দুই প্রান্তই S-এ থাকতে পারে না, তাই অন্তত একটি V ∖ S-এ: cover. (⇐) V ∖ S cover হলে কোনো edge-এর দুই প্রান্তই S-এ নয়: S independent. — দুই দিক
- তাই 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, তাই যোগে carry হয় না; প্রতিটি কলাম আলাদা পড়া যায়। — ৫ < ১০
- (⇒) satisfying মানে xi সত্য হলে yi, নইলে zi; cj কলামে সত্য literal-এর সংখ্যা ১–৩, বাকিটা gj, hj দিয়ে ৩ পূরণ। — যোগফল t
- (⇐) চলক-কলামে 1 মানে yi, zi-এর ঠিক একটি নেওয়া: এটিই মান। cj-এ ৩ লাগে, g, h বড়জোর ২ দেয়, তাই একটি নেওয়া literal-সংখ্যা cj-কে সত্য করে। — সব clause সত্য
- 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 কোথায় লাগে? — ১০ নম্বর (কঠিন)
- N একটি f(n)-space NTM. f(n) জায়গার configuration বড়জোর 2d·f(n) টি (কোনো ধ্রুবক d). ধরা যায় N accept করার আগে tape মুছে একটি নির্দিষ্ট caccept-এ যায়। — configuration গোনা
- CANYIELD(c1, c2, t): t = 1 হলে c1 = c2 বা এক ধাপে যাওয়া যায় কি না সরাসরি দেখুন; নইলে প্রতিটি cm-এর জন্য CANYIELD(c1, cm, t/2) আর CANYIELD(cm, c2, t/2); দুটিই হ্যাঁ হলে হ্যাঁ। — মাঝখানে ভাঙা
- Deterministic M: CANYIELD(cstart, caccept, 2d·f(n)) চালায়। সঠিকতা t-এর ওপর induction: পথ থাকলে তার মাঝের configuration একটি cm. — সঠিকতা
- জায়গা: 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 | নতুন ≤ ATM | ATM ≤m নতুন; NP-তে 3SAT ≤p নতুন | ৮.২ |
| হিসাব-অযোগ্য f | f-এর ভেতরে M চালানো | সিদ্ধান্ত output-যন্ত্রের ভেতরে | ৮.৪ |
| Rice-এর অপপ্রয়োগ | state সংখ্যা বা ধাপ গোনায় Rice | semantic আর 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-কে দিয়ে পরীক্ষা করানোর একটি কাঠামো:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন। সব তথ্য প্রশ্নের ভেতরেই আছে।
ক্রমMapping reduction দিয়ে “X undecidable” প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- একটি জানা-undecidable উৎস বাছা, যেমন ATM
- f নির্মাণ: ⟨M, w⟩ থেকে একটি নতুন যন্ত্রের বর্ণনা
- f computable দেখানো: শুধু বর্ণনা লেখে, কিছু চালায় না
- “⇔”-এর দুই দিক প্রমাণ: M w গ্রহণ করে আর করে না
- দিকের নিয়মে উপসংহার: 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
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:
মনে রাখুন
- আগে পড়া, তারপর হাতিয়ার: দাবিটি অস্তিত্বের (একটি যন্ত্র দিন) নাকি অসম্ভবতার (সব যন্ত্র বা সব বিভাজনের বিরুদ্ধে খেলুন)? প্রথম লাইনেই পদ্ধতি আর দিক লিখুন।
- নির্মাণ আর সঠিকতা আলাদা: product, reversal, CFG থেকে PDA; তারপর invariant আর দুই দিকের inclusion.
- Pumping একটি খেলা: p আর বিভাজন প্রতিপক্ষের; সব বিভাজন ক্ষেত্র ভাগ করে ধরুন, দরকারে i = 0. Lemma শুধু প্রয়োজনীয় শর্ত।
- Reduction-এর তিন শর্ত: f computable, “⇔”-এর দুই দিক, আর দিক: জানা-কঠিন বাঁয়ে। NP-complete মানে NP-তে থাকা আর NP-hard দুটিই।
- যাচাই আর সততা: ছোট ক্ষেত্রে brute force দিয়ে ভুল ধরুন, কিন্তু তাকে প্রমাণ বলবেন না; খোলা প্রশ্নকে খোলা বলুন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৮৫ · ইন্টারভিউ আর প্রতিযোগিতায় গণনার তত্ত্ব — regex, parsing আর complexityপরবর্তী পর্বRegex, parser, state machine আর complexity-র ইন্টারভিউ প্রশ্ন।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্বপুরো কোর্সের মানচিত্র আর ১৪টি মডিউল।
- পর্ব ০৪ · Theory of Computation-এর প্রমাণআবার পড়ুনInduction, construction, simulation আর diagonalization-এর মূল আলোচনা।
- পর্ব ৫২ · Reduction দিয়ে undecidabilityআবার পড়ুনMapping reduction-এর দিক, ETM, REGULARTM আর reduction-এর ছাঁচ।
- পর্ব ৬১ · NP-complete সমস্যার পরিবারআবার পড়ুনVERTEX-COVER, SUBSET-SUM, HAMPATH আর 3-COLOR-এর পূর্ণ gadget.
- পর্ব ৮২ · MCQ প্রশ্নব্যাংক — গণনার তত্ত্বঅনুশীলন১৩টি মডিউলের MCQ, প্রতিটি বিকল্পের ব্যাখ্যাসহ।
- পর্ব ৮১ · Automaton আর grammar নকশার অনুশীলনঅনুশীলনDFA, CFG, PDA আর TM নকশার পূর্ণ সমাধান।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৮২ · প্রমাণ লেখার অনুশীলনপাশের ট্র্যাকInduction, contradiction, pigeonhole আর diagonal-এর আদর্শ প্রমাণ।