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

Theory of Computation-এর প্রমাণ — string-এর ওপর induction, construction আর diagonalization

Proof Techniques for Theory of Computation — Induction on Strings, Constructions, Simulation, Pigeonhole, Diagonalization and Reductions

Taught in Bangla, this lesson collects the proof patterns the course relies on. It proves a DFA correct in both directions with a state invariant and induction on |w|, uses structural induction, argues by construction and simulation, applies pigeonhole to finite memory, and previews diagonalization and the direction of reductions. In-page Python (Pyodide) checks invariants, balanced strings both ways, a prefix construction and repeated states on short strings, and a flawed proof is dissected.

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

  • Theory of Computation-এ কোন ধরনের দাবি আসে, আর প্রতিটির জন্য কোন প্রমাণ-কৌশল মানানসই
  • একটি DFA-র সঠিকতা দুই দিকে প্রমাণ করা, আর invariant-কে কেন “শক্ত” করতে হয়
  • String-এর দৈর্ঘ্য আর গঠনের ওপর induction, structural induction দিয়ে বন্ধনীর language-এর দুই দিকের প্রমাণ
  • Construction আর simulation প্রমাণ: একটি automaton থেকে আরেকটি বানিয়ে সঠিকতা দেখানো
  • Pigeonhole, diagonalization আর reduction দিয়ে “পারা যায় না” প্রমাণ, আর প্রতিটি দাবি Python-এ পূর্ণ গণনায় যাচাই

১ · কেন এই কোর্সের প্রমাণ একটু আলাদা

রেলস্টেশনের টিকিট কাউন্টারে একটি নতুন যন্ত্র বসানো হলো, যা টিকিটের কোড দেখে বলে “বৈধ” বা “অবৈধ”। দুটি আলাদা অভিযোগ আসতে পারে: যন্ত্র কোনো জাল টিকিট “বৈধ” বলেছে, অথবা কোনো আসল টিকিট ফিরিয়ে দিয়েছে। যন্ত্রটি ঠিক, এটা বলতে হলে দুই অভিযোগই অসম্ভব দেখাতে হয়। আর যদি কেউ বলেন “এমন যন্ত্র বানানোই অসম্ভব”, তবে কয়েকটি টিকিটে চেষ্টা করে দেখানো যথেষ্ট নয়; সব সম্ভাব্য যন্ত্র ব্যর্থ, এটা দেখাতে হয়।

প্রমাণের সাধারণ পদ্ধতিগুলো আপনি ডিসক্রিট ম্যাথমেটিক্স কোর্সে পাবেন: direct proof, contrapositive আর contradiction (পর্ব ০৮), case আর counterexample (পর্ব ০৯), mathematical induction (পর্ব ১০) আর recursive সংজ্ঞায় structural induction (পর্ব ১২)। এখানে সেগুলো আবার শেখানো হবে না। এই পর্বের কাজ হলো দেখানো, গণনার তত্ত্বে এই পদ্ধতিগুলো কোন চেহারায় আসে। String, language, Σ∗ আর ε-এর notation পর্ব ০৩-এ ঠিক করা হয়েছে; এখানে সেগুলোই ব্যবহার হবে।

কারণটা সহজ: এই কোর্সের প্রায় প্রতিটি দাবি “সব string”, “সব যন্ত্র” বা “সব ইনপুট” নিয়ে, আর এরা অসীম। Σ = {0, 1} হলে দৈর্ঘ্য 20 পর্যন্তই প্রায় ২১ লক্ষ string. কোনো পরীক্ষা সব দেখতে পারে না; প্রমাণ পারে। নিচের টেবিলটি পুরো কোর্সের একটি মানচিত্র: কোন দাবির জন্য কোন কৌশল, আর কোথায় তা পূর্ণরূপে আসবে।

দাবির ধরনসাধারণ কৌশলকোর্সে কোথায়
যন্ত্র M ঠিক L চেনে: L(M) = Lপ্রতিটি state-এর invariant, |w|-এর ওপর induction, দুই দিকপর্ব ০৭, ০৮
L regular বা context-free (অস্তিত্ব)Construction আর তার সঠিকতাপর্ব ১০, ১৪, ৩৪
একটি শ্রেণি কোনো operation-এ বদ্ধConstruction বা simulationপর্ব ১৬, ৩৭
Grammar G ঠিক L তৈরি করেDerivation-এর দৈর্ঘ্য বা গঠনের ওপর inductionপর্ব ২৫, ২৬
L regular নয়Pigeonhole, pumping lemma, Myhill–Nerode, closure দিয়ে contradictionপর্ব ১৭, ১৮
L undecidableDiagonalization, reductionপর্ব ৫১, ৫২
সমস্যা NP-completePolynomial-time reductionপর্ব ৫৯, ৬০

তিনটি পরিচিত পদ্ধতির ToC-চেহারা একবার দেখে নিই। Direct: M একটি সম্পূর্ণ DFA (প্রতিটি state আর চিহ্নে একটি transition) হলে, accepting আর non-accepting state অদলবদল করা M′ ঠিক Σ∗ ∖ L(M) চেনে। কারণ δ অপরিবর্তিত, তাই w পড়ে দুই যন্ত্র একই state-এ থামে; সেই state F′-এ আছে ⇔ F-এ নেই। Contrapositive: “L regular ⇒ LR regular” (পর্ব ১৬) প্রমাণ হলে তার contrapositive “LR regular নয় ⇒ L regular নয়” বিনা খরচে পাওয়া যায়; কঠিন language-কে উল্টে সহজ চেহারায় আনার এই চাল প্রায়ই কাজে লাগে। Contradiction: “ধরি k state-এর একটি DFA আছে” দিয়ে শুরু করে বিরোধে পৌঁছানো, যা §৫-এ দেখবেন।

“যদি এবং কেবল যদি” পড়ার নিয়ম

“M একটি string w গ্রহণ করে ⇔ w-এর ধর্ম P আছে”, এটি একটি biconditional, তাই দুটি আলাদা প্রমাণ: (⇒) গৃহীত হলে P আছে, অর্থাৎ যন্ত্র কোনো ভুল string নেয় না; (⇐) P থাকলে গৃহীত, অর্থাৎ যন্ত্র কোনো ঠিক string ফেরায় না। সেটের ভাষায় এ দুটিই L(M) ⊆ L আর L ⊆ L(M). একটি দিক বাদ দেওয়া এই বিষয়ের সবচেয়ে সাধারণ ভুল।

২ · একটি DFA-র সঠিকতা — invariant আর |w|-এর ওপর induction

বাজারঘরের গুদামে একটি সেন্সর লাইন বিট পাঠায়: 1 মানে “সতর্কতা”, 0 মানে “স্বাভাবিক”। (কাল্পনিক) নিয়ম: পরপর দুটি সতর্কতা, অর্থাৎ “11”, কখনো আসা চলবে না। Language NO11 = {w ∈ {0, 1}∗ : w-এ 11 নেই}. নিচের DFA M = (Q, Σ, δ, q0, F)-এ Q = {A, B, D}, q0 = A, F = {A, B}. State D একটি dead state: একবার ঢুকলে আর বের হওয়া যায় না।

“11 নেই”-এর DFA

দুই দাগের বৃত্ত accepting. বাঁয়ের খোলা তীর শুরুর state. D-তে 0 আর 1 দুটিতেই নিজের কাছে ফেরা।

DFA for binary strings with no two consecutive 1s ABD 101 00,1 1-এ শেষ নয়1-এ শেষ11 পাওয়া
ছবি ৪.১ — প্রতিটি state-এর নিচে লেখা আছে সে কী “মনে রাখে”; এই তিনটি বাক্যই প্রমাণের invariant.

সরাসরি “M গ্রহণ করে ⇔ w-এ 11 নেই” induction দিয়ে প্রমাণ করতে গেলে আটকে যাবেন। ধরুন v-এ 11 নেই আর যন্ত্র v গ্রহণ করেছে; এখন v1-এর কী হবে? উত্তর নির্ভর করে v-এর শেষ চিহ্ন 1 কি না তার ওপর, আর দুর্বল hypothesis সেটা বলে না। সমাধান হলো দাবিটি শক্ত করা: প্রতিটি state-এর জন্য আলাদা বাক্য। এখানে δ̂ হলো পুরো string-এর transition (কিছু বইয়ে δ∗ লেখা হয়): δ̂(q, ε) = q, আর δ̂(q, va) = δ(δ̂(q, v), a).

উপপাদ্য ২.১ (invariant J)

সব w ∈ {0, 1}∗-এর জন্য: δ̂(A, w) = D ⇔ w-এ 11 আছে; δ̂(A, w) = B ⇔ w-এ 11 নেই আর w 1-এ শেষ; δ̂(A, w) = A ⇔ w-এ 11 নেই আর w 1-এ শেষ নয়। ফলে L(M) = NO11.

তিনটি শর্ত পরস্পর বর্জনশীল আর মিলে সব string ঢেকে দেয়, তাই “δ̂(A, w) = J(w)” দেখালেই তিনটি ⇔ একসঙ্গে প্রমাণিত। |w|-এর ওপর induction, শেষ চিহ্ন আলাদা করে (w = va), কারণ δ̂-এর সংজ্ঞাও ঠিক এভাবে লেখা:

  1. Base: w = ε. δ̂(A, ε) = A; ε-এ 11 নেই আর ε 1-এ শেষ নয়, তাই J(ε) = A. — δ̂-এর সংজ্ঞা
  2. Hypothesis: দৈর্ঘ্য n-এর কোনো v-এর জন্য δ̂(A, v) = J(v). w = va, a ∈ {0, 1}. — induction
  3. J(v) = D: v-এ 11 আছে, তাই va-তেও; আর δ(D, a) = D. — D থেকে বের হওয়া যায় না
  4. J(v) = A: a = 0 হলে δ(A, 0) = A, আর v0-তে 11 নেই, 0-তে শেষ। a = 1 হলে δ(A, 1) = B; v 1-এ শেষ নয় বলে v1-এ নতুন 11 তৈরি হয়নি, আর v1 1-এ শেষ। — দুই case
  5. J(v) = B: a = 0 হলে δ(B, 0) = A, আর v0 1-এ শেষ নয়। a = 1 হলে δ(B, 1) = D, আর v 1-এ শেষ বলে v1 “11”-এ শেষ। — দুই case
  6. সব case-এ δ̂(A, va) = δ(J(v), a) = J(va). — hypothesis আর δ̂-এর সংজ্ঞা
  7. (⊆) w ∈ L(M) হলে δ̂(A, w) ∈ {A, B}, তাই J অনুযায়ী w-এ 11 নেই। (⊇) w-এ 11 না থাকলে J(w) ∈ {A, B} = F, তাই গৃহীত। ∎

লক্ষ করুন, প্রমাণে সবচেয়ে জরুরি অংশ invariant খুঁজে বের করা, induction-টি প্রায় যান্ত্রিক। নিচের stepper 10110 পড়ে প্রতিটি prefix-এ invariant মেলায়।

1q = A (start)2read 1: A → B3read 0: B → A4read 1: A → B5read 1: B → D6read 0: D → D7D ∉ F → reject
Prefix আর invariant
পড়া অংশ
11 আছে?
1-এ শেষ?
J বলে
যন্ত্রের state
  1. Base case. কিছু পড়া হয়নি, w = ε. 11 নেই, 1-এ শেষ নয়, তাই J(ε) = A, আর যন্ত্রও A-তে।
  2. 1 পড়া। State A-তে 1: case “J(v) = A, a = 1”, ফল B. “1”-এ 11 নেই, 1-এ শেষ: J বলে B. মিলেছে।
  3. 0 পড়া। B-তে 0 গেলে A. “10” 0-তে শেষ, তাই আবার নিরাপদ: J = A.
  4. 1 পড়া। A-তে 1, ফল B. “101”-এ দুটি 1 আছে, কিন্তু পাশাপাশি নয়। J = B.
  5. আবার 1. এবার B-তে 1: শেষ চিহ্ন আগেই 1 ছিল, তাই “1011”-এ 11 তৈরি হলো। Case “J(v) = B, a = 1”, ফল D. এই তথ্যটিই দুর্বল hypothesis দিতে পারত না।
  6. 0 পড়া। D থেকে বের হওয়া যায় না। “10110”-এ 11 আছেই, J = D.
  7. সিদ্ধান্ত। শেষ state D ∉ F = {A, B}, তাই বাতিল। সেন্সর লাইনে সত্যিই পরপর দুটি সতর্কতা এসেছিল।

প্রমাণ হাতে থাকলেও পূর্ণ গণনা হিসাবের ভুল ধরার সবচেয়ে সস্তা উপায়। নিচের ব্লক দৈর্ঘ্য 0 থেকে 12-এর সব string-এ invariant J মেলায়, তারপর দুটি “বাগওয়ালা” যন্ত্রের সবচেয়ে ছোট পাল্টা-উদাহরণ shortlex ক্রমে (আগে দৈর্ঘ্য, তারপর অভিধানের ক্রম) খোঁজে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
def shortlex(sigma, n):                  # all strings, length 0..n
    for k in range(n + 1):
        for t in product(sigma, repeat=k):
            yield "".join(t)
def final(delta, start, w):
    q = start
    for ch in w:
        q = delta[q, ch]
    return q
M = {("A","0"):"A", ("A","1"):"B", ("B","0"):"A",
     ("B","1"):"D", ("D","0"):"D", ("D","1"):"D"}
def claimed(w):                          # the invariant J(w)
    if "11" in w:
        return "D"
    return "B" if w.endswith("1") else "A"
n, bad = 12, 0
for w in shortlex("01", n):
    bad += final(M, "A", w) != claimed(w)
print("invariant: strings", 2**(n+1) - 1, "violations", bad)
def first_counterexample(delta, start, acc):
    for w in shortlex("01", n):
        if (final(delta, start, w) in acc) != ("11" not in w):
            return repr(w)
    return None
BUG1 = dict(M); BUG1["B", "1"] = "A"     # forgot the dead state
print("correct M :", first_counterexample(M, "A", {"A", "B"}))
print("bug 1     :", first_counterexample(BUG1, "A", {"A", "B"}))
print("bug 2     :", first_counterexample(M, "A", {"B"}))  # start not accepting

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

invariant: strings 8191 violations 0
correct M : None
bug 1     : '11'
bug 2     : ''

২১৩ − ১ = ৮১৯১টি string-এ invariant একবারও ভাঙেনি। প্রথম বাগওয়ালা যন্ত্রে dead state ভুলে B-তে 1 পড়লে আবার A-তে ফেরা হয়েছে; সবচেয়ে ছোট পাল্টা-উদাহরণ “11”. দ্বিতীয়টিতে শুরুর state accepting নয়, তাই সে ফাঁকা string ε ফিরিয়ে দেয়, অথচ ε-এ কোনো 11 নেই। দুটিই AI-এর আঁকা automaton-এ খুব পরিচিত ভুল। মনে রাখুন: এই গণনা দৈর্ঘ্য 12 পর্যন্ত নিশ্চয়তা দেয়, সব দৈর্ঘ্যের নিশ্চয়তা দেয় উপপাদ্য ২.১-এর প্রমাণ।

৩ · String-এর গঠনের ওপর induction — structural induction

|w|-এর ওপর induction-এর দুটি রূপ আছে: শেষ চিহ্ন আলাদা করা (w = va), যা DFA-র সঙ্গে মেলে, আর প্রথম চিহ্ন আলাদা করা (w = av), যা অনেক grammar-এর প্রমাণে সুবিধার। কখনো দৈর্ঘ্য n-এর আগের সব দৈর্ঘ্যের ওপর hypothesis লাগে, তখন strong induction (ডিসক্রিট ম্যাথমেটিক্সের পর্ব ১১)। কিন্তু অনেক language দৈর্ঘ্য দিয়ে নয়, নিয়ম দিয়ে সংজ্ঞায়িত। তখন প্রমাণও নিয়ম ধরে চলে।

বাজারঘরের ছোট order-query ভাষায় শর্তগুলো বন্ধনী দিয়ে জোড়া হয়, যেমন (দাম ও (জেলা বা জেলা))। শুধু বন্ধনীগুলো রাখলে পাই ( ( ) ). সুষম বন্ধনীর language BAL একটি recursively defined set:

  1. নিয়ম ১: ε ∈ BAL.
  2. নিয়ম ২: x ∈ BAL হলে (x) ∈ BAL.
  3. নিয়ম ৩: x, y ∈ BAL হলে xy ∈ BAL.
  4. এই নিয়মগুলো সসীমবার প্রয়োগে যা পাওয়া যায়, শুধু সেগুলোই BAL-এ।

এখন একটি “গুনে দেখার” ধর্ম: P(w) মানে w-এ “(” আর “)”-এর সংখ্যা সমান, আর w-এর প্রতিটি prefix-এ “(”-এর সংখ্যা “)”-এর চেয়ে কম নয়। প্রশ্ন: BAL = {w : P(w)}? আবার দুই দিক।

উপপাদ্য ৩.১

সব w ∈ {(, )}∗-এর জন্য w ∈ BAL ⇔ P(w).

(⇒) Structural induction দিয়ে। প্রতিটি নিয়মের জন্য দেখাতে হবে: নিয়মের ইনপুটে P সত্য হলে আউটপুটেও সত্য। balance(u) লিখি “(”-এর সংখ্যা বিয়োগ “)”-এর সংখ্যা।

  1. নিয়ম ১: ε-এ দুই সংখ্যাই 0, আর একমাত্র prefix ε-এর balance 0 ≥ 0. — basis
  2. নিয়ম ২: P(x) ধরি। (x)-এর prefix তিন রকম: ε (balance 0); “(” তারপর x-এর কোনো prefix u (balance 1 + balance(u) ≥ 1); অথবা পুরো (x), যার balance 1 + 0 − 1 = 0. সব ≥ 0, আর মোট balance 0. — hypothesis P(x)
  3. নিয়ম ৩: P(x), P(y) ধরি। xy-এর prefix হয় x-এর prefix (balance ≥ 0), নয় x তারপর y-এর prefix u, যার balance 0 + balance(u) ≥ 0. মোট 0 + 0 = 0. — hypothesis P(x), P(y)
  4. নিয়ম ১–৩ ছাড়া BAL-এ কিছু ঢোকে না, তাই প্রতিটি সদস্যে P সত্য। ∎

(⇐) |w|-এর ওপর strong induction (প্রমাণের রূপরেখা)। P(w) আর w ≠ ε ধরি। প্রথম চিহ্ন “(” হতেই হবে (না হলে প্রথম prefix-এর balance ঋণাত্মক হতো)। প্রথম যে অবস্থানে prefix-এর balance আবার 0 হয়, সেখানে ভাগ করুন: w = (u)v. তখন u আর v দুটিই P মানে আর w-এর চেয়ে ছোট, তাই hypothesis অনুযায়ী u, v ∈ BAL. নিয়ম ২-এ (u) ∈ BAL, নিয়ম ৩-এ (u)v ∈ BAL. (u-এর prefix-এর balance কেন ≥ 0, তা “প্রথম শূন্য”-এর সংজ্ঞা থেকে আসে; বিস্তারিত পরিশ্রম অনুশীলনের জন্য রাখা হলো।)

1rule 1: ε2rule 2 on ε: ()3rule 3 on (), (): ()()4rule 2 on ()(): (()())5test: )(
ধর্ম P-এর হিসাব
string
“(” সংখ্যা
“)” সংখ্যা
সবচেয়ে কম prefix balance
P
  1. Basis. নিয়ম ১ দেয় ε. দুই সংখ্যা 0, একমাত্র prefix-এর balance 0: P সত্য।
  2. নিয়ম ২, x = ε. ফল (). Prefix-এর balance 0, 1, 0: কখনো ঋণাত্মক নয়, শেষে 0.
  3. নিয়ম ৩, x = y = (). ফল ()(). প্রমাণের ধাপ ৩: x শেষ হলে balance 0, তারপর y-এর হিসাব নতুন করে শুরু।
  4. নিয়ম ২, x = ()(). ফল (()()). বাইরের “(” প্রতিটি ভেতরের prefix-এর balance 1 বাড়ায়, তাই সবচেয়ে কম মান 0 (শুরুর ε আর শেষে)।
  5. উল্টো দিকের সতর্কতা। )(-এ সংখ্যা সমান, কিন্তু প্রথম prefix “)”-এর balance −1, তাই P মিথ্যা। শুধু “সংখ্যা সমান” শর্তটি BAL বোঝাতে যথেষ্ট নয়; prefix-এর শর্তটি দরকারি।

একই কৌশল regular expression-এর ওপরও চলে, কারণ regex নিজেই নিয়ম দিয়ে সংজ্ঞায়িত (পর্ব ১৩)। একটি ছোট উদাহরণ: “যে regex-এ ∗ নেই, তার language সসীম।” Basis ∅, ε আর একটি চিহ্ন a: language-গুলো ∅, {ε}, {a}, সবই সসীম। Union R1 ∪ R2-এ দুটি সসীম সেটের union সসীম; concatenation R1R2-এ বড়জোর |L1| · |L2|টি string. ∎ Grammar-এর ক্ষেত্রে “derivation-এর ধাপ-সংখ্যার ওপর induction” একই ধাঁচের, যা পর্ব ২৬-এ বারবার আসবে। নিচের ব্লক উপপাদ্য ৩.১-এর দুই দিকই দৈর্ঘ্য 8 পর্যন্ত যাচাই করে: নিয়ম থেকে BAL তৈরি করে, আর আলাদাভাবে P মানা সব string গুনে দুটি সেট মেলায়।

from itertools import product
N = 8                                    # longest string we build
B = {""}                                 # rule 1: epsilon is in B
while True:                              # apply rules 2 and 3 until nothing new
    new = {"(" + x + ")" for x in B if len(x) + 2 <= N}
    new |= {x + y for x in B for y in B if len(x + y) <= N}
    if new <= B:
        break
    B |= new
def P(w):                                # equal counts, no prefix dips below 0
    bal = 0
    for c in w:
        bal += 1 if c == "(" else -1
        if bal < 0:
            return False
    return bal == 0
allP = {"".join(t) for k in range(N + 1)
        for t in product("()", repeat=k) if P("".join(t))}
print("built by rules :", len(B))
print("satisfy P      :", len(allP))
print("every rule-built string has P:", all(P(w) for w in B))
print("every P-string is rule-built :", allP == B)
print("count by length:", [sum(len(w) == k for w in B) for k in range(0, N + 1, 2)])
print("equal counts but not P:", sorted(w for w in map("".join, product("()", repeat=4))
                                      if w.count("(") == 2 and not P(w)))

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

built by rules : 23
satisfy P      : 23
every rule-built string has P: True
every P-string is rule-built : True
count by length: [1, 1, 2, 5, 14]
equal counts but not P: ['())(', ')(()', ')()(', '))((']

নিয়ম থেকে তৈরি ২৩টি string আর P মানা ২৩টি string হুবহু এক সেট: তৃতীয় লাইন (⇒), চতুর্থ লাইন (⇐)। দৈর্ঘ্য 0, 2, 4, 6, 8-এ সংখ্যাগুলো 1, 1, 2, 5, 14, যা Catalan সংখ্যা (ডিসক্রিট ম্যাথমেটিক্সের পর্ব ৫০)। শেষ লাইন দেখায় দৈর্ঘ্য 4-এ চারটি string-এ সংখ্যা সমান অথচ P মিথ্যা, তাই prefix-শর্ত বাদ দিলে দাবিটি ভুল হতো।

৪ · Construction আর simulation — “M দেওয়া আছে, M′ বানাই”

“L regular হলে L-এর অমুক রূপান্তরও regular”, এমন দাবির প্রমাণ প্রায় সবসময় একটি construction proof: L-এর একটি DFA M ধরে নিয়ে তা থেকে নতুন যন্ত্র M′-এর রেসিপি লেখা, তারপর দুই দিকে দেখানো যে L(M′) ঠিক কাঙ্ক্ষিত language. রেসিপিটি নিজেই একটি algorithm, তাই এমন প্রমাণ সঙ্গে সঙ্গে প্রোগ্রামও দেয়।

বাজারঘরের অর্ডার-কোড: “BG-” তারপর ৪টি অঙ্ক, যেমন BG-0042. ক্রেতা কোড টাইপ করার সময় ফর্মটি প্রতিটি অক্ষরে বলতে চায়: “এখনো বৈধ কোড হয়ে উঠতে পারে” নাকি “ভুল পথে গেছেন”। এর গণিত হলো prefix language: Pref(L) = {x : কোনো y-এর জন্য xy ∈ L}.

উপপাদ্য ৪.১ (Pref-এর construction)

M = (Q, Σ, δ, q0, F) একটি সম্পূর্ণ DFA হলে M′ = (Q, Σ, δ, q0, F′), যেখানে F′ = {q ∈ Q : q থেকে transition ধরে F-এর কোনো state-এ পৌঁছানো যায়}, Pref(L(M)) চেনে। ফলে regular language-এর শ্রেণি Pref operation-এ বদ্ধ।

  1. F′ নির্ণয়যোগ্য: state diagram-কে directed graph ভাবলে এটি F থেকে উল্টো দিকে reachability, যা সসীম ধাপে শেষ হয়। — graph-এর reachability (পর্ব ০২)
  2. (⊆) x ∈ Pref(L) ধরি, তাই কোনো y-এ xy ∈ L. q = δ̂(q0, x) হলে δ̂(q, y) = δ̂(q0, xy) ∈ F, অর্থাৎ q থেকে F-এ পথ আছে; q ∈ F′, তাই M′ x গ্রহণ করে। — δ̂(q0, xy) = δ̂(δ̂(q0, x), y)
  3. (⊇) M′ x গ্রহণ করলে q = δ̂(q0, x) ∈ F′, তাই q থেকে F-এ একটি পথ আছে; সেই পথের তীরের চিহ্নগুলো পরপর লিখলে একটি y, যাতে δ̂(q, y) ∈ F. তাহলে xy ∈ L, অর্থাৎ x ∈ Pref(L). ∎
1M: q0 B q1 G q2 - q3, digits q4..q72F' := {q7}3add every q with an edge into F'4stop: F' = {q0..q7}5proof (⊆)6proof (⊇)7test BG-0 and B-
Construction-এর অবস্থা
F′
X (dead)
  1. দেওয়া যন্ত্র। q0 থেকে B, G, - পড়ে q3; তারপর প্রতিটি অঙ্কে এক ধাপ, ৪টি অঙ্ক শেষে q7, যা একমাত্র accepting state. ভুল চিহ্ন বা q7-এর পরে আরও চিহ্ন এলে dead state X.
  2. শুরু। F-এর state-গুলো নিজেরাই F-এ পৌঁছায় (ফাঁকা পথ), তাই F′ শুরু হয় {q7} দিয়ে।
  3. উল্টো দিকে ছড়ানো। প্রতি রাউন্ডে এমন state যোগ হয়, যার কোনো তীর F′-এ ঢোকে। প্রথম রাউন্ডে q6 (অঙ্ক পড়ে q7), তারপর একে একে q5 থেকে q0: মোট ৭ রাউন্ড।
  4. থামা। X থেকে সব তীর X-এই ফেরে, তাই X কখনো যোগ হয় না। F′ = {q0, …, q7}: “এখনো dead state-এ পড়িনি” মানেই “এখনো বৈধ কোড হয়ে উঠতে পারে”।
  5. (⊆) দিক। যেকোনো বৈধ কোডের prefix, যেমন BG-0, পড়ে যন্ত্র একটি জীবিত state-এ থাকে, আর সেখান থেকে বাকি অংশ পড়ে q7-এ যাওয়া যায়।
  6. (⊇) দিক। M′ x গ্রহণ করলে x শেষে state F′-এ, তাই F-এ পৌঁছানোর একটি পথ আছে; সেই পথের লেবেলই প্রয়োজনীয় y.
  7. পরীক্ষা। BG-0 পড়ে q4, যা F′-এ: গৃহীত। B- পড়ে দ্বিতীয় চিহ্নেই X: বাতিল, কারণ “B-” দিয়ে কোনো বৈধ কোড শুরু হয় না।

প্রমাণ সাধারণ; নিচের ব্লক একটি নির্দিষ্ট ক্ষেত্রে মেলায়। হিসাব ছোট রাখতে অঙ্ক শুধু 0 আর 1 নেওয়া হয়েছে (Σ = {B, G, -, 0, 1})। Pref(L) সংজ্ঞা থেকে সরাসরি বানানো হয় (L-এর প্রতিটি সদস্যের প্রতিটি prefix), আর দৈর্ঘ্য 7 পর্যন্ত Σ-এর সব string-এ M′-এর উত্তরের সঙ্গে মেলানো হয়।

from itertools import product
SIG = "BG-01"                            # digits cut to 0 and 1 for the check
PAT = ["B", "G", "-", "01", "01", "01", "01"]  # what position i must hold
def delta(q, c):                         # states 0..7, and "X" = dead
    if q == "X" or q == 7 or c not in PAT[q]:
        return "X"
    return q + 1
Q = list(range(8)) + ["X"]
F = {7}
Fp = set(F)                              # F' = states that can still reach F
while True:
    more = {q for q in Q for c in SIG if delta(q, c) in Fp} - Fp
    if not more:
        break
    Fp |= more
print("F' =", sorted(Fp, key=str))
def accepts(w, acc):
    q = 0
    for c in w:
        q = delta(q, c)
    return q in acc
L = {"BG-" + "".join(t) for t in product("01", repeat=4)}
pref = {x[:k] for x in L for k in range(len(x) + 1)}   # Pref(L) by definition
bad = total = 0
for k in range(8):
    for w in map("".join, product(SIG, repeat=k)):
        total += 1
        bad += accepts(w, Fp) != (w in pref)
print("|L| =", len(L), " |Pref(L)| =", len(pref))
print("strings checked", total, " disagreements", bad)
print({w: accepts(w, Fp) for w in ("BG-0", "BG-01", "B-", "BG-01011")})

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

F' = [0, 1, 2, 3, 4, 5, 6, 7]
|L| = 16  |Pref(L)| = 34
strings checked 97656  disagreements 0
{'BG-0': True, 'BG-01': True, 'B-': False, 'BG-01011': False}

F′-এ X নেই, ঠিক stepper-এর মতো। L-এ ২৪ = ১৬টি কোড; তাদের prefix গুনলে দৈর্ঘ্য 0 থেকে 7-এ 1 + 1 + 1 + 1 + 2 + 4 + 8 + 16 = ৩৪টি। দৈর্ঘ্য 7 পর্যন্ত ৯৭,৬৫৬টি string-এ একটিও অমিল নেই। শেষ লাইনে BG-01011 বাতিল: পাঁচটি অঙ্ক হয়ে গেছে, কোনো y জুড়ে আর বৈধ কোড বানানো যায় না।

Simulation argument

অনেক construction আসলে একটি simulation: নতুন যন্ত্র M′ ধাপে ধাপে পুরনো যন্ত্র M (বা একাধিক যন্ত্র) “অভিনয় করে” চালায়। প্রমাণের কাঠামো সবসময় একই, আর এটি আসলে একটি invariant:

  1. M আর M′-এর configuration-এর মধ্যে একটি সম্পর্ক R সংজ্ঞায়িত করুন (“M′-এর এই অবস্থা M-এর ওই অবস্থাকে প্রকাশ করে”)।
  2. শুরুর configuration দুটি R-এ সম্পর্কিত।
  3. M এক ধাপ চললে M′ এক বা কয়েক ধাপে এমন configuration-এ যায়, যা আবার R-এ সম্পর্কিত।
  4. R-এ সম্পর্কিত configuration-এ দুই যন্ত্রের গ্রহণ-বর্জনের সিদ্ধান্ত এক।

দুটি DFA-কে একসঙ্গে চালানো product construction (পর্ব ০৮)-এ R হলো “M′-এর state (p, q) মানে প্রথম যন্ত্র p-তে, দ্বিতীয়টি q-তে”; subset construction (পর্ব ১০)-এ “M′-এর state S মানে NFA-র সম্ভাব্য state-এর সেট ঠিক S”; আর multi-tape Turing machine-কে এক tape-এ চালানোর প্রমাণে (পর্ব ৪৫) R বলে এক tape-এর লেখা কীভাবে অনেক tape-এর লেখা আর head-এর অবস্থান ধরে রাখে। ধাপ ৩-এ “কয়েক ধাপ” কতগুলো, সেটি গুনলেই পরে complexity-র হিসাব আসে: একটি simulation কতটা ধীর।

৫ · Pigeonhole — সসীম স্মৃতি যখন ফুরিয়ে যায়

Pigeonhole principle (ডিসক্রিট ম্যাথমেটিক্সের পর্ব ৩২) বলে n-টি খোপে n-এর বেশি কবুতর রাখলে কোনো খোপে দুটি থাকবেই। পরীক্ষার হলে ৩০টি বেঞ্চে ৩১ জন বসলে কোনো বেঞ্চে দুজন। DFA-তে খোপ হলো state, আর কবুতর হলো string পড়ার অবস্থান।

উপপাদ্য ৫.১ (পুনরাবৃত্ত state)

M-এর state-সংখ্যা k, আর w = w1w2…wm, m ≥ k. rt = δ̂(q0, w1…wt) লিখি, যেখানে t = 0, 1, …, m. তাহলে 0 ≤ i < j ≤ k এমন i, j আছে, যাতে ri = rj.

  1. r0, r1, …, rk মোট k + 1টি মান, কারণ m ≥ k বলে এরা সবাই সংজ্ঞায়িত। — অবস্থান গোনা
  2. প্রতিটি মান Q-এর একটি state, আর |Q| = k. — DFA-র সংজ্ঞা
  3. k + 1টি কবুতর, k-টি খোপ: কোনো দুটি অবস্থান i < j-এ একই state. — pigeonhole
  4. x = w1…wi, y = wi+1…wj, z = বাকিটা নিলে |xy| = j ≤ k, |y| ≥ 1, আর y পড়ে যন্ত্র একই state-এ ফেরে। তাই সব n ≥ 0-এ δ̂(q0, xynz) = δ̂(q0, w): xynz গৃহীত ⇔ w গৃহীত। ∎

শেষ ধাপটিই regular language-এর pumping lemma-র হৃদয়, যা পর্ব ১৭ “Regular language-এর pumping lemma — non-regular প্রমাণ”-এ পূর্ণ রূপে আসবে। নিচের stepper ৩ দিয়ে বিভাজ্যতার DFA (state = এ পর্যন্ত পড়া binary মান mod 3, δ(q, b) = (2q + b) mod 3; ডিসক্রিট ম্যাথমেটিক্সের পর্ব ৭৪-এ এর সঠিকতা প্রমাণিত) দিয়ে 1001 (= 9) পড়ে।

1t=0: r0 = 02t=1 read 1: r1 = 13t=2 read 0: r2 = 24t=3 read 0: r3 = 1  repeat!5x = 1, y = 00, z = 16pump: 1 (00)^n 1
খোপ আর কবুতর
অবস্থান t
state rt
দেখা state
pump করা string
  1. শুরু। অবস্থান 0-তে state 0. k = 3টি খোপের একটি ভরল।
  2. 1 পড়া। (2 · 0 + 1) mod 3 = 1. দুটি খোপ ভরা।
  3. 0 পড়া। (2 · 1 + 0) mod 3 = 2. তিনটি খোপই ভরা; পরের অবস্থানে নতুন খোপ আর নেই।
  4. 0 পড়া। (2 · 2 + 0) mod 3 = 1, যা অবস্থান 1-এও ছিল। উপপাদ্য অনুযায়ী j ≤ k = 3, আর সত্যিই j = 3.
  5. ভাগ করা। x = 1 (অবস্থান 0 থেকে 1), y = 00 (অবস্থান 1 থেকে 3), z = 1. |xy| = 3 ≤ k, |y| = 2 ≥ 1.
  6. Pump. y-এর লুপ যতবার খুশি ঘোরানো বা বাদ দেওয়া যায়: 11 = 3, 100001 = 33, দুটিই ৩ দিয়ে বিভাজ্য, তাই গৃহীত, ঠিক 1001-এর মতো।

Pigeonhole থেকে আরেকটি পরিষ্কার হাতিয়ার আসে, যা “L regular নয়” প্রমাণে প্রায়ই pumping-এর চেয়ে সহজ। দুটি string x, y একটি language L-এর সাপেক্ষে distinguishable, যদি এমন z থাকে যে xz আর yz-এর ঠিক একটি L-এ আছে।

উপপাদ্য ৫.২ (distinguishable string আর state-সংখ্যা)

L-এর সাপেক্ষে k + 1টি পরস্পর distinguishable string থাকলে L-এর যেকোনো DFA-তে অন্তত k + 1টি state. অসীম সংখ্যক পরস্পর distinguishable string থাকলে L regular নয়।

  1. বিরোধের জন্য ধরি k state-এর DFA M, L(M) = L. — contradiction
  2. k + 1টি string পড়ে k + 1টি শেষ state; দুটি string x ≠ y একই state q-এ থামে। — pigeonhole
  3. যেকোনো z-এ δ̂(q0, xz) = δ̂(q, z) = δ̂(q0, yz), তাই xz আর yz দুটিই গৃহীত বা দুটিই বাতিল। — DFA deterministic
  4. কিন্তু x, y distinguishable, তাই কোনো z-এ ঠিক একটি গৃহীত: বিরোধ। অসীম সংখ্যক থাকলে কোনো সসীম k যথেষ্ট নয়। ∎

উদাহরণ: L = {anbn : n ≥ 0}. i ≠ j হলে ai আর aj distinguishable, z = bi দিয়ে: aibi ∈ L, কিন্তু ajbi ∉ L. a, aa, aaa, … অসীম সংখ্যক পরস্পর distinguishable string, তাই L regular নয়। এই ধারণাই পর্ব ১৮-এর Myhill–Nerode theorem-এ “যদি এবং কেবল যদি” রূপ পায়।

from itertools import combinations
M3 = {(q, b): (2 * q + int(b)) % 3 for q in range(3) for b in "01"}
def first_repeat(delta, start, w):
    q, seen = start, {start: 0}          # state -> first position seen
    for j, ch in enumerate(w, 1):
        q = delta[q, ch]
        if q in seen:
            return seen[q], j, q
        seen[q] = j
    return None
def accepts(w):
    q = 0
    for b in w:
        q = M3[q, b]
    return q == 0
w = "1001"
i, j, q = first_repeat(M3, 0, w)
x, y, z = w[:i], w[i:j], w[j:]
print("repeat: state", q, "at positions", i, "and", j)
print("x, y, z =", repr(x), repr(y), repr(z))
for k in range(4):
    s = x + y * k + z
    print(" k =", k, s, int(s, 2), "accepted" if accepts(s) else "rejected")
# a^i and a^j (i != j) are told apart by z = b^i for L = a^n b^n
inL = lambda s: s == "a" * (len(s) // 2) + "b" * (len(s) // 2)
pairs = list(combinations(range(8), 2))
ok = all(inL("a" * i + "b" * i) != inL("a" * j + "b" * i) for i, j in pairs)
print("pairs a^i, a^j (0..7) distinguished:", len(pairs), ok)

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

repeat: state 1 at positions 1 and 3
x, y, z = '1' '00' '1'
 k = 0 11 3 accepted
 k = 1 1001 9 accepted
 k = 2 100001 33 accepted
 k = 3 10000001 129 accepted
pairs a^i, a^j (0..7) distinguished: 28 True

প্রথম দুই লাইন stepper-এর i = 1, j = 3 আর x, y, z হুবহু। y = 00 শূন্যবার থেকে তিনবার ঘোরালে মান 3, 9, 33, 129, সবই ৩-এর গুণিতক, আর সবই গৃহীত। শেষ লাইন 0 থেকে 7 পর্যন্ত a-এর ঘাতের সব ২৮টি জোড়ায় z = bi দিয়ে পার্থক্য দেখায়। এটি উপপাদ্য ৫.২-এর একটি উদাহরণ মাত্র; “অসীম সংখ্যক” অংশটি প্রমাণ থেকে আসে, এই গণনা থেকে নয়।

৬ · Diagonalization — সব language চেনা যায় না

Cantor-এর diagonal যুক্তি (ডিসক্রিট ম্যাথমেটিক্সের পর্ব ১৮; এই কোর্সে পর্ব ০২) একটি তালিকা দেখে এমন বস্তু বানায়, যা তালিকার প্রতিটি সারি থেকে অন্তত এক জায়গায় আলাদা। গণনার তত্ত্বে তালিকাটি হলো যন্ত্রের তালিকা, আর বস্তুটি একটি language. এই কৌশলের নাম diagonalization.

উপপাদ্য ৬.১

{0, 1}-এর ওপর এমন একটি language আছে, যা কোনো Turing machine চেনে না, অর্থাৎ যা Turing-recognizable নয়।

প্রমাণের রূপরেখা (encoding-এর খুঁটিনাটি পর্ব ০৫ আর পর্ব ৪৮-এ, পূর্ণ প্রমাণ পর্ব ৫১-এ):

  1. প্রতিটি Turing machine M একটি সসীম বর্ণনা, তাই একটি binary string ⟨M⟩ হিসেবে লেখা যায়। String-গুলো গোনা যায় (countable), তাই যন্ত্রগুলোও তালিকা করা যায়: M1, M2, M3, … — encoding
  2. {0, 1}∗-এর string-গুলো shortlex ক্রমে: w1 = ε, w2 = 0, w3 = 1, w4 = 00, … — Σ∗ countable
  3. D = {wi : wi ∉ L(Mi)} সংজ্ঞায়িত করুন: “i-তম যন্ত্র i-তম string-কে যা বলে, তার উল্টো”। — diagonal উল্টানো
  4. ধরি কোনো j-এর জন্য L(Mj) = D. তাহলে wj ∈ D ⇔ wj ∉ L(Mj) ⇔ wj ∉ D. বিরোধ। — D-এর সংজ্ঞা
  5. তাই D তালিকার কোনো যন্ত্রের language নয়, আর তালিকায় সব যন্ত্র আছে। ∎

বাস্তব যন্ত্রের তালিকা অসীম, তাই stepper-এ চারটি ছোট language আর প্রথম চারটি string দিয়ে যুক্তির কাঠামোটি দেখা যাক: L1 = সব string, L2 = জোড় দৈর্ঘ্যের string, L3 = অন্তত একটি 1 আছে, L4 = 0-এ শেষ। ঘরে 1 মানে string-টি সেই language-এ আছে।

1      ε   0   1   002L1:  [1]  1   1   13L2:   1  [0]  0   14L3:   0   0  [1]  05L4:   0   1   0  [1]6D :   0   1   0   0
D তৈরি হচ্ছে
এই ধাপের ঘর
D-এর সিদ্ধান্ত
D কার থেকে আলাদা
  1. টেবিল। সারি i = language Li, কলাম j = string wj (shortlex ক্রমে ε, 0, 1, 00 সাজানো)। বন্ধনীর ঘরগুলো diagonal: সারি i-এর কলাম i.
  2. প্রথম ঘর। L1 সব string নেয়, তাই L1(ε) = 1. D এর উল্টো করে: ε ∉ D. ফলে D ≠ L1, পার্থক্য ε-তে।
  3. দ্বিতীয় ঘর। “0”-এর দৈর্ঘ্য 1, বিজোড়, তাই L2(0) = 0; উল্টে 0 ∈ D. D ≠ L2.
  4. তৃতীয় ঘর। “1”-এ একটি 1 আছে, L3(1) = 1; উল্টে 1 ∉ D. D ≠ L3.
  5. চতুর্থ ঘর। “00” 0-এ শেষ, L4(00) = 1; উল্টে 00 ∉ D. D ≠ L4.
  6. সিদ্ধান্ত। এই চার string-এ D-এ শুধু “0”, আর D প্রতিটি সারি থেকে তার নিজের diagonal ঘরে আলাদা। তালিকা অসীম হলেও একই যুক্তি: D তালিকার বাইরে।

একই যুক্তির একটি গণনার রূপও আছে: যন্ত্র countable, কিন্তু {0, 1}∗-এর সব subset-এর সেট (power set) uncountable, তাই “প্রায় সব” language-ই কোনো যন্ত্র চেনে না। Diagonal প্রমাণের সুবিধা হলো এটি একটি নির্দিষ্ট D দেখায়। পর্ব ৫১-এ এই কৌশল একটি স্বাভাবিক প্রশ্নে খাটানো হবে: বাজারঘরের যাচাইকারী কি যেকোনো প্রোগ্রাম দেখে বলতে পারবে “এটি নিশ্চিত থামবে”? সেটাই halting problem, আর উত্তর “না”।

৭ · Reduction — এক অসম্ভবতা থেকে আরেক অসম্ভবতা

প্রতিটি নতুন সমস্যার জন্য নতুন diagonal বানানো কষ্টের। সহজ পথ: নতুন সমস্যা B-কে একটি পুরনো, জানা-কঠিন সমস্যা A-এর সঙ্গে জুড়ে দেওয়া। এর সবচেয়ে সরল রূপ হলো mapping reduction.

সংজ্ঞা ৭.১ আর তার ফল

A ≤m B (A, B-তে mapping reducible), যদি এমন একটি computable function f থাকে (সব ইনপুটে থামে এমন যন্ত্র যা হিসাব করে) যে সব w-এর জন্য w ∈ A ⇔ f(w) ∈ B. তাহলে: B decidable হলে A-ও decidable হয়। Contrapositive: A undecidable হলে B undecidable.

B-এর decider থাকলে A-এর decider বানানো যেত

ডটেড বাক্সটি পুরোটা মিলে A-এর একটি decider. A-এর decider যেহেতু অসম্ভব, B-এর decider-ও অসম্ভব।

Mapping reduction from A to B f হিসাব করুন B-এর decider ইনপুট w f(w) হ্যাঁ ⇔ w ∈ A A-এর decider
ছবি ৪.২ — Reduction-এর তীর A থেকে B-এর দিকে: “A-কে B-এর ভাষায় অনুবাদ করা যায়”, তাই B অন্তত A-এর মতো কঠিন।

দিকটি মনে রাখার উপায়: ≤ চিহ্নের ডান দিকের সমস্যা অন্তত বাঁ দিকেরটির মতো কঠিন। A ≤m B দেখিয়ে B-এর কঠিনতা প্রমাণ হয়, A-এর নয়। উল্টো দিকে reduction লিখে “B কঠিন” দাবি করা এই বিষয়ের সবচেয়ে পরিচিত ভুল; পর্ব ৫২ “Reduction দিয়ে undecidability — mapping reduction” আর পর্ব ৫৯-এ (polynomial-time রূপ, ≤p) এটি বিস্তারিত আসবে।

Regular language-এর জগতেও reduction-এর একটি ছোট আত্মীয় আছে: closure property দিয়ে contradiction. দাবি: EQ = {w ∈ {a, b}∗ : a আর b-এর সংখ্যা সমান} regular নয়।

  1. বিরোধের জন্য ধরি EQ regular. — contradiction
  2. a∗b∗ regular, কারণ এটি নিজেই একটি regular expression. — সংজ্ঞা
  3. দুটি regular language-এর intersection regular, তাই EQ ∩ a∗b∗ regular. — closure, product construction (পর্ব ০৮)
  4. কিন্তু EQ ∩ a∗b∗ = {anbn : n ≥ 0}, যা §৫-এ regular নয় প্রমাণিত। বিরোধ। ∎

সাবধান: “EQ-এর ভেতরে anbn আছে, তাই EQ regular নয়” যুক্তিটি ভুল। Regular language-এর subset regular না-ও হতে পারে (Σ∗ regular, আর প্রতিটি language তার একটি অংশ)। Intersection-টা দরকার, কারণ closure property শুধু “regular-এ regular মেশালে regular” বলে।

৮ · প্রমাণের সাধারণ ভুল আর একটি ভুল প্রমাণ

ভুলকেন ভুল, কী করবেন
শুধু এক দিক প্রমাণ (“যন্ত্র কোনো ভুল string নেয় না”)সব string বাতিল করা যন্ত্রও এটি মানে; L ⊆ L(M)-ও দেখান
Invariant শুধু accepting state নিয়েInduction-এর ধাপে আটকে যায়; প্রতিটি state-এর বাক্য লিখুন
ε বা ফাঁকা language ভুলে যাওয়াBase case-এ ε আলাদা করে দেখুন; ∅ ≠ {ε}
Pumping-এ নিজে বিভাজন বেছে নেওয়াবিভাজন প্রতিপক্ষের; প্রতিটি বৈধ বিভাজন ব্যর্থ দেখান
Reduction উল্টো দিকেB-এর কঠিনতা দেখাতে জানা-কঠিন A থেকে B-তে, A ≤ B
“n = 1 থেকে 10 পর্যন্ত মিলেছে, তাই সত্য”সসীম গণনা উদাহরণ বা পাল্টা-উদাহরণ দেয়, প্রমাণ নয়
অসীম union-এ closure ধরে নেওয়াClosure শুধু সসীম সংখ্যক operation-এ; অনুশীলন ৪ দেখুন

প্রমাণের ভুল ধরুন: “দুই দিকই এক”

একজন লিখলেন: “দাবি: Σ = {a, b}-এর ওপর DFA N, যার একটিমাত্র state s, যা শুরু আর accepting, আর দুই চিহ্নেই s-এ ফেরে, ঠিক EVEN = {w : |w| জোড়} চেনে। প্রমাণ: w ∈ EVEN হলে w পড়ে N s-এ থাকে, আর s ∈ F, তাই গৃহীত। ∎”

ভুল কোথায়: শুধু (⊇) দেখানো হয়েছে: EVEN ⊆ L(N). (⊆) দিক, অর্থাৎ “গৃহীত হলে জোড় দৈর্ঘ্য”, পরীক্ষাই করা হয়নি, আর সেটিই মিথ্যা: “a” গৃহীত, অথচ দৈর্ঘ্য 1. আসলে L(N) = Σ∗. ঠিক যন্ত্রে দুটি state লাগে (জোড়, বিজোড়), আর invariant “δ̂(জোড়, w) = জোড় ⇔ |w| জোড়”। এই ভুলটি নির্দোষ দেখায়, কারণ যা প্রমাণিত হয়েছে তা সত্যি; শুধু দাবিটির অর্ধেক।

আরও গভীরে: Diagonalization এত শক্তিশালী যে computability-র প্রায় সব প্রথম ফল এ থেকে আসে, কিন্তু এর একটি জানা সীমা আছে। Baker, Gill আর Solovay ১৯৭৫ সালে দেখান, এমন oracle আছে যার সাপেক্ষে P = NP, আর এমনও আছে যার সাপেক্ষে P ≠ NP; তাই শুধু “relativize করে” এমন diagonal যুক্তি P বনাম NP মীমাংসা করতে পারে না (পর্ব ৬৮)। আজ automata তত্ত্বের অনেক প্রমাণ Coq বা Lean-এর মতো proof assistant-এ যন্ত্র দিয়ে যাচাই করা হয়েছে বলে জানা যায়, যেখানে এই পর্বের প্রতিটি “দুই দিক” আলাদা lemma হিসেবে লিখতে হয়।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এমন প্রশ্ন প্রায়ই আসে:

  • DFA M ঠিক L চেনে, প্রমাণে কী কী লাগে? L(M) ⊆ L আর L ⊆ L(M); সাধারণত প্রতিটি state-এর invariant আর |w|-এর ওপর induction.
  • k state-এর DFA দৈর্ঘ্য ≥ k-এর string পড়লে কী নিশ্চিত? প্রথম k + 1টি অবস্থানে কোনো state দুবার; এখান থেকে pumping.
  • Regular language-এর prefix language regular কেন? একই DFA, F′ = যেসব state থেকে F-এ পৌঁছানো যায়।
  • সব language recognizable নয় কেন? যন্ত্র countable, language uncountable; বা diagonal D = {wi : wi ∉ L(Mi)}.
  • A ≤m B আর A undecidable হলে? B undecidable; উল্টোটা কিছু বলে না।

৯ · AI-এর যুগে — প্রমাণ লেখায় AI-কে কীভাবে ব্যবহার করবেন

AI সহকারী গুছিয়ে, আত্মবিশ্বাসী ভঙ্গিতে প্রমাণ লেখে, আর ঠিক সেজন্যই ভুল চোখ এড়িয়ে যায়। গণনার তত্ত্বে কয়েকটি ভুল বারবার দেখা যায়:

AI-এর ভুলকীভাবে ধরবেন
Automaton ভুল language নেয়: গোনায় এক কম-বেশি, ε ভুল, dead state বাদদৈর্ঘ্য 0 থেকে 10-এর সব string-এ যন্ত্র চালিয়ে সংজ্ঞার সঙ্গে মেলান, যেমন §২-এর ব্লক
“L(M) = L”-এর এক দিক প্রমাণ করে থেমে যাওয়া⊆ আর ⊇ আলাদা শিরোনামে খুঁজুন; না পেলে প্রমাণ অসম্পূর্ণ
Pumping-এর প্রমাণে নিজে বিভাজন বাছা, বা একটি case pump করাQuantifier-এর ক্রম ∃p ∀s ∃xyz ∀i লিখে প্রতিটি ধাপ মেলান
Decidable আর recognizable গুলিয়ে ফেলা, reduction উল্টো দিকেপ্রতিটি ≤ চিহ্নে জিজ্ঞেস করুন: কোন সমস্যার কঠিনতা জানা, কোনটির প্রমাণ হচ্ছে?
Theorem-এর শর্ত বাদ, খোলা প্রশ্নকে মীমাংসিত বলা, বানানো referenceSipser বা Hopcroft–Motwani–Ullman-এর মতো বিশ্বস্ত পাঠ্যবইয়ে মেলান

AI-এর কাছে প্রমাণ চাইলে এমন কাঠামো দিন, যাতে প্রতিটি দাবি আলাদা করে যাচাই করা যায়:

নিচের দাবিটির প্রমাণ ধাপে ধাপে লেখো: দাবি: [যেমন "এই DFA ঠিক সেই binary string গ্রহণ করে যাতে 11 নেই"] ১. দাবিটি "যদি এবং কেবল যদি" হলে দুই দিক (⊆ আর ⊇) আলাদা শিরোনামে প্রমাণ করো। ২. Induction ব্যবহার করলে কীসের ওপর (|w|, structure, derivation-এর দৈর্ঘ্য), base case আর hypothesis স্পষ্ট লেখো; DFA হলে প্রতিটি state-এর invariant দাও। ৩. প্রতিটি ধাপের পাশে তার যুক্তি (সংজ্ঞা, theorem-এর নাম আর শর্ত) লেখো। ৪. Reduction থাকলে কোন দিকে, আর তাতে কোন সমস্যার কঠিনতা প্রমাণ হয়, তা এক লাইনে বলো। ৫. শুধু itertools দিয়ে দৈর্ঘ্য 10 পর্যন্ত সব string-এ দাবিটি পরীক্ষার একটি ছোট Python কোড দাও। ৬. কোনো সাল, নাম বা বইয়ের উল্লেখে নিশ্চিত না হলে স্পষ্ট বলো।

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

একটি ভালো অভ্যাস: AI-এর প্রমাণ পড়ার আগে তার দাবিটি নিজে Python-এ পরীক্ষা করুন। পাল্টা-উদাহরণ পেলে প্রমাণ পড়ার দরকারই নেই; না পেলে প্রমাণের প্রতিটি ধাপ পড়ুন, কারণ গণনা শুধু সসীম অংশের নিশ্চয়তা দেয়।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Cantor-এর diagonal কীভাবে সংখ্যার তত্ত্ব থেকে গণনার সীমা প্রমাণের হাতিয়ার হয়ে উঠল?

Georg Cantor ১৮৭৪ সালে প্রথম দেখান যে বাস্তব সংখ্যা গোনা যায় না, তবে সেই প্রমাণ ছিল অন্য ধাঁচের। ১৮৯১ সালের একটি ছোট প্রবন্ধে তিনি যে যুক্তি দেন, সেটিই আজ “diagonal argument” নামে পরিচিত: যেকোনো তালিকার n-তম সারির n-তম ঘর বদলে দিলে এমন একটি বস্তু পাওয়া যায়, যা তালিকায় নেই। একই যুক্তি থেকে আসে যে কোনো সেট তার power set-এর সমান বড় নয়।

কৌশলটির মূল উপাদান “নিজের সম্পর্কে প্রশ্ন”: i-তম সারিকে i-তম কলাম নিয়ে জিজ্ঞেস করা। Bertrand Russell ১৯০১ সালের দিকে “যে সেটগুলো নিজের সদস্য নয়, তাদের সেট” দিয়ে set theory-র একটি paradox খুঁজে পান, যা একই ছাঁচের। Kurt Gödel ১৯৩১ সালে গাণিতিক বাক্যকে সংখ্যা দিয়ে encode করে এমন একটি বাক্য বানান, যা কার্যত বলে “আমাকে এই পদ্ধতিতে প্রমাণ করা যায় না”। আর Alan Turing ১৯৩৬ সালের “On Computable Numbers” প্রবন্ধে যন্ত্রকেই সংখ্যা দিয়ে encode করেন, যাতে যন্ত্রের তালিকা বানানো যায়, তারপর diagonal দিয়ে দেখান যে কিছু প্রশ্ন কোনো যন্ত্র সমাধান করতে পারে না।

এই ধারাবাহিকতায় একটি জিনিস লক্ষ করার মতো: প্রতিবার আসল কাজ ছিল encoding, অর্থাৎ বস্তুগুলোকে (বাক্য, যন্ত্র) একটি তালিকায় সাজানো। তালিকা পেলেই diagonal প্রায় নিজে থেকে চলে। এজন্যই এই কোর্সে পর্ব ০৫-এ encoding ⟨M⟩ আর পর্ব ৪৮-এ universal Turing machine আগে আসে, তারপর পর্ব ৫১-এ halting problem. §৬-এর উপপাদ্যও একই গঠনের: যন্ত্রের তালিকা, string-এর তালিকা, diagonal উল্টানো।

তবে diagonalization সর্বশক্তিমান নয়। “আরও গভীরে” বাক্সে যেমন বলা হয়েছে, ১৯৭৫ সালের Baker–Gill–Solovay ফল দেখায় যে শুধু এমন যুক্তি দিয়ে P বনাম NP মীমাংসা সম্ভব নয়; এই প্রশ্ন আজও খোলা।

মূল উপলব্ধি: Diagonal যুক্তি একটি সাধারণ ছাঁচ: বস্তুগুলোকে তালিকায় সাজাতে পারলে, “নিজের সম্পর্কে উল্টো উত্তর” দিয়ে তালিকার বাইরের বস্তু বানানো যায়; Cantor থেকে Gödel হয়ে Turing পর্যন্ত একই কৌশল বারবার ফিরে এসেছে।

প্র ০২কঠিন দাবি প্রমাণ করা কখনো কখনো সহজ দাবির চেয়ে সহজ কেন?

§২-এ “M গ্রহণ করে ⇔ w-এ 11 নেই” সরাসরি induction-এ প্রমাণ করা যায়নি, কিন্তু তার চেয়ে বেশি বলা দাবি, অর্থাৎ তিনটি state-এর তিনটি বাক্য, সহজেই গেছে। এটা অদ্ভুত শোনায়, কিন্তু induction-এর গঠন থেকেই আসে: hypothesis যত শক্ত, পরের ধাপে হাতে তত বেশি তথ্য। দুর্বল hypothesis শুধু বলে “এ পর্যন্ত ঠিক আছে”, কিন্তু পরের চিহ্নে কী হবে তা বলার মতো তথ্য দেয় না।

গণিতবিদ George Pólya ১৯৪৫ সালের বই “How to Solve It”-এ এই ঘটনার নাম দেন “inventor's paradox”: বেশি উচ্চাকাঙ্ক্ষী পরিকল্পনা কখনো কখনো সফল হওয়ার সম্ভাবনা বেশি। প্রোগ্রামের সঠিকতায় একই কথা আসে loop invariant-এর রূপে। Robert Floyd ১৯৬৭ সালের “Assigning Meanings to Programs” আর C. A. R. Hoare ১৯৬৯ সালের “An Axiomatic Basis for Computer Programming” প্রবন্ধে প্রোগ্রামের প্রতিটি বিন্দুতে একটি শর্ত লিখে সঠিকতা প্রমাণের পদ্ধতি দেন (ডিসক্রিট ম্যাথমেটিক্সের পর্ব ১৩)। একটি DFA আসলে একটি লুপ: প্রতিবার একটি চিহ্ন পড়ে, আর state হলো তার একমাত্র variable. তাই DFA-র invariant ঠিক loop invariant.

বাস্তবে ভালো invariant কোথা থেকে আসে? সবচেয়ে কাজের প্রশ্ন: “এই state-এ পৌঁছানো সব string-এর মধ্যে মিল কী?” §২-এর ছবিতে প্রতিটি state-এর নিচে লেখা বাক্যগুলো ঠিক সেই উত্তর। DFA নকশার সময় এই বাক্য আগে লিখলে নকশা আর প্রমাণ একসঙ্গে তৈরি হয়। পর্ব ১৮-এর Myhill–Nerode theorem এই ধারণাকে চূড়ান্ত রূপ দেয়: সবচেয়ে ছোট DFA-র প্রতিটি state হলো “ভবিষ্যতে একইভাবে আচরণ করে এমন string-এর একটি class”, এই অর্থে।

আধুনিক verification tool-ও এই সমস্যার সঙ্গে লড়ে: স্বয়ংক্রিয়ভাবে যথেষ্ট শক্ত invariant খুঁজে বের করা সাধারণভাবে কঠিন, আর অনেক ক্ষেত্রে undecidable প্রশ্নের সঙ্গে জড়িত, যা পর্ব ৭৮-এ দেখবেন।

মূল উপলব্ধি: Induction-এ hypothesis শক্ত করলে পরের ধাপের জন্য বেশি তথ্য পাওয়া যায়; DFA-র ক্ষেত্রে প্রতিটি state-এর জন্য একটি বাক্য লেখাই সেই শক্ত hypothesis, আর এটি প্রোগ্রামের loop invariant-এর সরাসরি আত্মীয়।

প্র ০৩“এমন যন্ত্র আছে” আর “এই যে যন্ত্র”, দুটি প্রমাণের পার্থক্য গণনার তত্ত্বে কতটা গুরুত্বপূর্ণ?

§৪-এর Pref-এর প্রমাণ একটি নির্দিষ্ট যন্ত্র M′ বানিয়ে দেয়; প্রমাণ পড়লেই প্রোগ্রাম লেখা যায়। Michael Rabin আর Dana Scott ১৯৫৯ সালে NFA থেকে DFA-র যে subset construction দেন, সেটিও এমন: অস্তিত্বের প্রমাণ, আবার algorithm-ও। গণনার তত্ত্বের বেশিরভাগ ইতিবাচক ফল এমন constructive, কারণ এখানে “আছে” বলার মানে প্রায়ই “বানানো যায়”।

কিন্তু একটি বিখ্যাত উদাহরণ দেখায় যে “decidable” সংজ্ঞাটি নিজে constructive নয়। Language G ভাবুন: Goldbach-এর অনুমান (৪-এর বড় প্রতিটি জোড় সংখ্যা দুটি মৌলিক সংখ্যার যোগফল) সত্য হলে G = {1}, মিথ্যা হলে G = ∅. G কি decidable? হ্যাঁ, কারণ দুই ক্ষেত্রেই একটি খুব সরল যন্ত্র আছে: একটি যন্ত্র শুধু “1” গ্রহণ করে, অন্যটি কিছুই না। দুটির একটি ঠিক, তাই decider আছে। অথচ কোনটি ঠিক, তা আমরা জানি না, কারণ Goldbach-এর অনুমান আজও প্রমাণিত বা খণ্ডিত হয়নি। “Decidable” মানে “একটি decider আছে”, “আমরা সেটা চিনি” নয়।

এই পার্থক্য দর্শনেও বড় বিতর্ক তৈরি করেছিল। L. E. J. Brouwer-এর intuitionism ধারা বিংশ শতাব্দীর শুরুতে এমন অস্তিত্বের প্রমাণ মেনে নিতে অস্বীকার করে, যা কোনো উদাহরণ দেয় না। আজ type theory আর proof assistant-এর একটি অংশ এই constructive গণিতের ওপর দাঁড়ানো, যেখানে একটি প্রমাণ থেকে সরাসরি প্রোগ্রাম বের করে আনা যায়।

অনুশীলনের জন্য পরামর্শ: “L regular” দেখাতে বললে একটি নির্দিষ্ট DFA, NFA বা regex দিন আর তার সঠিকতা প্রমাণ করুন; এটিই পরীক্ষায় পূর্ণ নম্বরের উত্তর। আর “L decidable নয়” দাবিগুলো সবসময় অস্তিত্বহীনতার দাবি, সেখানে diagonal বা reduction লাগে।

মূল উপলব্ধি: Construction প্রমাণ একই সঙ্গে algorithm দেয়, আর এই কোর্সের বেশিরভাগ ইতিবাচক ফল তাই; কিন্তু “decidable” সংজ্ঞা শুধু একটি decider-এর অস্তিত্ব চায়, তাই কোনো language decidable হয়েও আমাদের অজানা থাকতে পারে কোন যন্ত্রটি তা decide করে।

প্র ০৪কম্পিউটারে সব ক্ষেত্র পরীক্ষা করা কি প্রমাণ? কখন হ্যাঁ, কখন না?

এই পর্বের প্রতিটি ব্লক “দৈর্ঘ্য n পর্যন্ত সব string” পরীক্ষা করেছে। এটি একটি সসীম দাবির পূর্ণ প্রমাণ: “দৈর্ঘ্য 12 পর্যন্ত সব string-এ invariant সত্য” এখন প্রমাণিত (প্রোগ্রাম আর কম্পিউটার ঠিক থাকলে)। কিন্তু “সব দৈর্ঘ্যে” দাবিটি অসীম, আর সসীম পরীক্ষা তা প্রমাণ করতে পারে না। গণিতের ইতিহাসে এমন অনুমান আছে, যা বিশাল সংখ্যা পর্যন্ত সত্য থেকে পরে ভুল প্রমাণিত হয়েছে, যেমন Pólya-র একটি অনুমান, যার প্রথম পাল্টা-উদাহরণ কয়েক শত কোটির ঘরের একটি সংখ্যা বলে জানা যায়।

তবে কম্পিউটার-পরীক্ষা প্রমাণের অংশ হতে পারে, যদি যুক্তি দিয়ে অসীম প্রশ্নকে সসীম সংখ্যক ক্ষেত্রে নামানো যায়। ১৯৭৬ সালে Kenneth Appel আর Wolfgang Haken চার রঙের উপপাদ্য প্রমাণ করেন এভাবে: হাতে-লেখা যুক্তি দেখায় যে প্রায় দুই হাজার ধরনের বিন্যাস পরীক্ষা করলেই যথেষ্ট, আর কম্পিউটার সেগুলো পরীক্ষা করে। পরে ২০০৫ সালের দিকে Georges Gonthier পুরো প্রমাণ Coq proof assistant-এ যাচাই করেন। Thomas Hales-এর Kepler অনুমানের প্রমাণও (১৯৯৮) কম্পিউটার-নির্ভর ছিল, আর Flyspeck প্রকল্প ২০১৪ সালে তা formal ভাবে যাচাই করে। গণনার তত্ত্বেই সাম্প্রতিক উদাহরণ: ২০২৪ সালে bbchallenge সহযোগিতা প্রমাণ করে যে ৫ state-এর Busy Beaver মান BB(5) = 47,176,870, আর সেই প্রমাণও Coq-এ যাচাই করা (পর্ব ৫৫)।

এই উদাহরণগুলোর মিল: প্রথমে একটি গাণিতিক যুক্তি প্রশ্নকে সসীম করে, তারপর পূর্ণ গণনা। আমাদের ব্লকগুলোতে প্রথম অংশটি নেই, তাই এগুলো যাচাই, প্রমাণ নয়। আবার উল্টো দিকে একটি পাল্টা-উদাহরণ একাই একটি সার্বিক দাবি খণ্ডন করে: §২-এ “11” খুঁজে পাওয়াই বাগওয়ালা যন্ত্রের ভুলের পূর্ণ প্রমাণ।

মূল উপলব্ধি: পূর্ণ গণনা সসীম দাবির প্রমাণ আর সার্বিক দাবির খণ্ডন দিতে পারে; অসীম দাবির প্রমাণে কম্পিউটার তখনই অংশ নেয়, যখন একটি যুক্তি আগে প্রশ্নটিকে সসীম সংখ্যক ক্ষেত্রে নামিয়ে আনে।

প্র ০৫Reduction-এর দিক নিয়ে এত বিভ্রান্তি কেন, আর ইতিহাসে এই ধারণা কীভাবে এল?

দৈনন্দিন ভাষায় “A-কে B-তে নামিয়ে আনা” শুনলে মনে হয় A-ই বড় সমস্যা। গণিতে উল্টো: A ≤ B মানে “B সমাধান করতে পারলে A-ও পারা যায়”, তাই B অন্তত A-এর মতো কঠিন। একটি তুলনা: ঢাকা থেকে রাজশাহী যাওয়ার প্রশ্নকে আপনি “কমলাপুর স্টেশনে পৌঁছানো আর একটি ট্রেন ধরা”-তে নামিয়ে আনলেন। এর মানে ট্রেন ব্যবস্থা অন্তত এই যাত্রার সমস্যার মতো শক্তিশালী; যাত্রাটি ট্রেনের চেয়ে কঠিন, এমন কিছু প্রমাণ হয় না। কঠিনতা প্রমাণে আমরা contrapositive ব্যবহার করি: জানা-অসম্ভব A থেকে B-তে reduction দিলে B-ও অসম্ভব। এই দ্বিস্তরের উল্টে যাওয়াই বিভ্রান্তির উৎস।

ঐতিহাসিকভাবে Turing ১৯৩৬ সালে নিজের halting-ধাঁচের ফল থেকে Hilbert-এর Entscheidungsproblem-এর অসমাধানযোগ্যতা দেখান, যা কার্যত একটি reduction. ১৯৩৯ সালে Turing oracle machine-এর ধারণা দেন, যা থেকে “Turing reducibility” আসে। Emil Post ১৯৪৪ সালের একটি প্রভাবশালী প্রবন্ধে বিভিন্ন ধরনের reducibility, তার মধ্যে many-one, অর্থাৎ আজকের mapping reduction, পদ্ধতিগতভাবে আলোচনা করেন বলে জানা যায়। পরে complexity-তে Stephen Cook ১৯৭১ আর Richard Karp ১৯৭২ সালে polynomial সময়ের reduction দিয়ে NP-completeness-এর তত্ত্ব গড়েন; Karp একসঙ্গে ২১টি সমস্যাকে NP-complete দেখান।

দিক ঠিক রাখার একটি ব্যবহারিক কৌশল: reduction লেখার সময় সবসময় বাক্যটি পুরো লিখুন, “যদি B-এর decider থাকত, তাহলে A-এর decider এভাবে বানাতাম”। §৭-এর ছবির ডটেড বাক্সটি ঠিক এই বাক্য। তারপর জিজ্ঞেস করুন, A-এর decider কি অসম্ভব বলে জানা? হ্যাঁ হলে B-এর কঠিনতা প্রমাণ হলো।

মূল উপলব্ধি: A ≤ B মানে B অন্তত A-এর মতো কঠিন; কঠিনতা প্রমাণে জানা-কঠিন সমস্যা থেকে নতুন সমস্যার দিকে reduction দিতে হয়, আর “B-এর decider থাকলে A-এর decider বানাতাম” বাক্যটি পুরো লিখলে দিক ভুল হয় না।

অনুশীলন

আগে খাতায় করুন, তারপর উত্তর খুলে মেলান।

  1. নকশা ও প্রমাণ: Σ = {a, b}-এর ওপর L = {w : w “ab”-তে শেষ}-এর একটি DFA নকশা করুন। প্রতিটি state-এর invariant লিখুন, আর L(M) = L দুই দিকে প্রমাণ করুন।

    State S0 (শুরু), S1, S2; F = {S2}. δ(S0, a) = S1, δ(S0, b) = S0, δ(S1, a) = S1, δ(S1, b) = S2, δ(S2, a) = S1, δ(S2, b) = S0.

    • Invariant: δ̂(S0, w) = S1 ⇔ w a-তে শেষ; = S2 ⇔ w ab-তে শেষ; = S0 ⇔ বাকি সব (w = ε, অথবা b-তে শেষ কিন্তু ab-তে নয়)।
    • Base: ε-এ S0, আর ε “বাকি সব”-এর মধ্যে।
    • Step (w = va): a = a হলে যেকোনো state থেকে S1, আর va a-তে শেষ। a = b হলে: v a-তে শেষ (S1) ⇔ vb ab-তে শেষ, তাই S2; অন্যথায় (S0 বা S2) vb b-তে শেষ কিন্তু ab-তে নয়, তাই S0.
    • দুই দিক: গৃহীত ⇔ শেষ state S2 ⇔ invariant অনুযায়ী ab-তে শেষ। দৈর্ঘ্য 12 পর্যন্ত সব string-এ scratch-এ পূর্ণ গণনায় মেলানো।
  2. প্রমাণ: L = {ww : w ∈ {0, 1}∗} regular নয়, উপপাদ্য ৫.২ (distinguishable string) দিয়ে প্রমাণ করুন। ইঙ্গিত: 0i1 ধরনের string দেখুন।
    1. i ≠ j ধরি, x = 0i1, y = 0j1, আর z = 0i1. — z বাছাই আমাদের
    2. xz = 0i1 0i1 = uu, যেখানে u = 0i1; তাই xz ∈ L.
    3. yz = 0j1 0i1-এ ঠিক দুটি 1. এটি uu হলে প্রতিটি u-তে ঠিক একটি 1, আর প্রতিটি u 1-এ শেষ (কারণ uu 1-এ শেষ আর প্রথম u-এর পরেই দ্বিতীয় u শুরু), তাই প্রথম u = 0j1 আর দ্বিতীয় u = 0i1, অর্থাৎ i = j. বিরোধ, তাই yz ∉ L.
    4. তাই 1, 01, 001, … অসীম সংখ্যক পরস্পর distinguishable string, আর উপপাদ্য ৫.২ অনুযায়ী L regular নয়। ∎

    “0a10b1 একটি ww ⇔ a = b”, এই দাবি a, b ≤ 7-এ scratch-এ পূর্ণ গণনায় মেলানো।

  3. আউটপুট অনুমান: কোড না চালিয়ে বলুন কী ছাপা হবে। তারপর যেকোনো Python-এ চালিয়ে মেলান।
    M3 = {(q, b): (2*q + int(b)) % 3 for q in range(3) for b in "01"}
    def first_repeat(w):
        q, seen = 0, {0: 0}
        for j, b in enumerate(w, 1):
            q = M3[q, b]
            if q in seen:
                return seen[q], j
            seen[q] = j
    for w in ("110", "1011", "10"):
        print(w, first_repeat(w))
    110 (0, 2)
    1011 (2, 3)
    10 None

    110: state 0 → 1 → 0, তাই অবস্থান 0 আর 2-এ একই state; এখানে x = ε, y = 11 (মান 3, যা ৩ দিয়ে বিভাজ্য বলে state 0-এ ফেরে)। 1011: 0 → 1 → 2 → 2, পুনরাবৃত্তি অবস্থান 2 আর 3-এ। 10: দৈর্ঘ্য 2 < k = 3, মাত্র তিনটি অবস্থান 0, 1, 2 আর state-ও তিনটি ভিন্ন, তাই কোনো পুনরাবৃত্তি নেই: pigeonhole-এর শর্ত m ≥ k এখানে খাটে না, আর ফাংশন কিছু ফেরত না দিলে Python None ছাপে। (CPython 3.14-এ চালিয়ে মেলানো।)

  4. প্রমাণের ভুল ধরুন: “দাবি: L = {anbn : n ≥ 0} regular. প্রমাণ: প্রতিটি নির্দিষ্ট n-এর জন্য {anbn} একটি এক-string-এর সসীম language, তাই regular. L = {ε} ∪ {ab} ∪ {aabb} ∪ …, আর regular language-এর union regular. ∎” ভুল কোথায়?
    • ভুল ধাপ: Closure property “দুটি (তাই সসীম সংখ্যক) regular language-এর union regular” বলে। এর প্রমাণ একটি construction, যা দুটি যন্ত্র জুড়ে একটি সসীম যন্ত্র দেয়; অসীম সংখ্যক যন্ত্র জুড়লে state-এর সংখ্যা আর সসীম থাকে না।
    • কেন এটি নিশ্চিত ভুল: যেকোনো language তার এক-string-এর subset-গুলোর union. অসীম union-এ closure সত্য হলে সব language regular হতো, অথচ §৫-এ anbn regular নয় প্রমাণিত।
    • শিক্ষা: Induction “প্রতিটি সসীম n-এ” সত্য দেয়, “অসীম সংগ্রহে” নয়। প্রতিটি closure-এর ব্যবহারে জিজ্ঞেস করুন: কয়টি operand?

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

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

ক্রম“এমন language আছে যা কোনো Turing machine চেনে না”, এই প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. প্রতিটি Turing machine-কে string হিসেবে encode করে তালিকা M1, M2, … বানানো
  2. সব string-কে shortlex ক্রমে w1, w2, … সাজানো
  3. D = {wi : wi ∉ L(Mi)} সংজ্ঞায়িত করা
  4. ধরে নেওয়া যে কোনো j-এর জন্য L(Mj) = D
  5. wj ∈ D ⇔ wj ∉ D বিরোধ থেকে সিদ্ধান্ত: D কোনো যন্ত্রের language নয়

একটি DFA M আর একটি language L-এর জন্য L(M) = L প্রমাণ করতে কী দেখাতে হয়?

  • শুধু L(M) ⊆ L
  • শুধু L ⊆ L(M)
  • L(M) ⊆ L আর L ⊆ L(M) দুটিই
  • M অন্তত একটি L-এর string গ্রহণ করে

৫টি state-এর একটি DFA দৈর্ঘ্য 7-এর একটি string পড়ছে। নিচের কোনটি নিশ্চিত?

  • অবস্থান 0 থেকে 5-এর মধ্যে কোনো state দুবার আসে
  • যন্ত্র সব ৫টি state-এ অন্তত একবার যায়
  • String-টি গৃহীত হয়
  • দৈর্ঘ্য অন্তত 10 না হলে কিছু নিশ্চিত নয়

A ≤m B (A থেকে B-তে একটি mapping reduction আছে) আর A undecidable বলে জানা। কী সিদ্ধান্ত নেওয়া যায়?

  • A decidable হয়ে যায়
  • B undecidable
  • B decidable
  • কিছুই বলা যায় না

Language BAL সংজ্ঞায়িত: ε ∈ BAL; x ∈ BAL হলে (x) ∈ BAL; x, y ∈ BAL হলে xy ∈ BAL; আর কিছু নয়। Structural induction দিয়ে “BAL-এর প্রতিটি string-এ ধর্ম P আছে” প্রমাণ করতে কী দেখাতে হয়?

  • দৈর্ঘ্য 8 পর্যন্ত সব BAL string-এ P সত্য
  • শুধু P(ε)
  • P মানা প্রতিটি string নিয়ম দিয়ে তৈরি করা যায়
  • P(ε), আর P(x) থেকে P((x)), আর P(x), P(y) থেকে P(xy)

Σ = {0, 1}-এ language L1 = সব string, L2 = জোড় দৈর্ঘ্যের string, L3 = অন্তত একটি 1 আছে, L4 = 0-এ শেষ; আর w1 = ε, w2 = 0, w3 = 1, w4 = 00. D = {wi : wi ∉ Li, i = 1, …, 4} হলে D কী?

  • {0}
  • {ε, 00}
  • {1}
  • ∅

EQ = {w ∈ {a, b}∗ : a আর b-এর সংখ্যা সমান} regular নয়, এর একটি সঠিক প্রমাণ কোনটি?

  • EQ ∩ a∗b∗ = {anbn}, যা regular নয়; EQ regular হলে intersection regular হতো
  • EQ অসীম, তাই regular নয়
  • ৩ state-এর কোনো DFA EQ চেনে না, তাই regular নয়
  • EQ-এর ভেতরে anbn আছে, যা regular নয়

শব্দকোষ

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

মনে রাখুন

  1. দুই দিক: L(M) = L মানে L(M) ⊆ L আর L ⊆ L(M); প্রতিটি state-এর invariant লিখে |w|-এর ওপর induction দিলে দুটি একসঙ্গে আসে।
  2. Structural induction: নিয়মে সংজ্ঞায়িত language-এ basis আর প্রতিটি নিয়মে ধর্ম রক্ষা দেখান; উল্টো দিক সাধারণত দৈর্ঘ্যের ওপর strong induction.
  3. Construction আর simulation: M থেকে M′-এর রেসিপি, তারপর সঠিকতা; simulation-এ configuration-এর সম্পর্ক R প্রতিটি ধাপে টিকে থাকে।
  4. Pigeonhole: k state, k + 1টি অবস্থান, কোনো state দুবার; এখান থেকে pumping, আর অসীম distinguishable string মানে regular নয়।
  5. Diagonalization আর reduction: D = {wi : wi ∉ L(Mi)} কোনো যন্ত্র চেনে না; A ≤m B আর A undecidable হলে B undecidable.

পরের পর্বে: পর্ব ০৫ “সমস্যাকে language হিসেবে দেখা — encoding আর decision problem”: একটি গ্রাফ, একটি DFA বা একটি প্রোগ্রামকে কীভাবে string বানানো হয়, আর কেন “সমস্যা সমাধান করা” মানে “একটি language decide করা”।

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

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