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

প্রয়োজনীয় গণিত — set, relation, function, graph আর countability

Mathematical Preliminaries — Sets, Relations, Functions, Graphs and Countability for Theory of Computation

Taught in Bangla, this lesson is a focused refresher on the mathematics automata definitions use: power sets and Cartesian products, equivalence classes, reflexive-transitive closure, total and partial functions, and state diagrams as graphs where acceptance is reachability. In-page Python (Pyodide) checks equivalence classes, runs a reachability search, enumerates Σ* in shortlex order and plays out Cantor's diagonal argument, showing why most languages have no machine. It closes with Big-O growth rates.

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

  • Set-builder notation, power set আর Cartesian product দিয়ে machine-এর উপাদান লেখা, আর ∅, {ε}, {∅}-এর পার্থক্য
  • Equivalence relation চেনা, equivalence class গঠন, আর ⊢∗ বা ⇒∗-এর মতো “শূন্য বা বেশি ধাপ” relation পড়া
  • Total আর partial function, injection, surjection, bijection: কোন machine কোন ধরনের function দেয়
  • State diagram-কে directed graph হিসেবে দেখা, BFS দিয়ে reachability, আর DFA-র ভাষা ফাঁকা কি না তা বের করা
  • Σ∗-এর countability-র স্পষ্ট প্রমাণ, Cantor-এর উপপাদ্যের প্রমাণ, আর তা থেকে “সব language চেনা যায় না” সিদ্ধান্ত

১ · কেন এই গণিত, আর কতটুকু

নতুন শহরে রিকশায় ঘুরতে গেলে প্রথমে কয়েকটি শব্দ শিখে নিতে হয়: “ডানে”, “বামে”, “সোজা”, “থামেন”। এই কয়েকটি শব্দ ছাড়া পুরো যাত্রাটাই অচল। গণনার তত্ত্বেও তাই। প্রতিটি machine, grammar আর প্রমাণ লেখা হয় কয়েকটি গাণিতিক শব্দে: set, relation, function, graph, আর “গোনা যায় কি না”। এই পর্ব সেই শব্দভান্ডার এক জায়গায় গুছিয়ে দেয়।

এটি নতুন করে শেখানোর পর্ব নয়। প্রতিটি বিষয়ের বিস্তারিত ব্যাখ্যা, উদাহরণ আর অনুশীলন ডিসক্রিট ম্যাথমেটিক্স কোর্সে আছে; প্রতিটি অংশে সেই পর্বের লিংক দেওয়া হলো। এখানে আমরা দেখব গণনার তত্ত্ব ঠিক কোন জায়গায় এগুলো ব্যবহার করে, আর দুটি কেন্দ্রীয় প্রমাণ নিজে করব: Σ∗ গোনা যায়, আর P(Σ∗) গোনা যায় না। আগের পর্ব ০১ “গণনার তত্ত্বের মানচিত্র” যে তিন প্রশ্ন তুলেছে (কী গণনা করা যায়, কোন যন্ত্রে, কত দ্রুত), তার প্রতিটির উত্তর লিখতে এই গণিত লাগবে।

গাণিতিক ধারণাগণনার তত্ত্বে ব্যবহারযে পর্বে বেশি লাগবে
Set, power set, Cartesian productMachine-এর tuple, Q × Σ, NFA-র δ-এর মান P(Q)-তে, subset constructionপর্ব ০৭, ০৯, ১০
Equivalence relation, classMyhill–Nerode theorem, DFA minimizationপর্ব ১৮, ১৯
Reflexive-transitive closureDerivation ⇒∗, configuration ⊢∗পর্ব ২৬, ৪৩
Partial functionTuring machine যে function গণনা করে (না থামলে অসংজ্ঞায়িত)পর্ব ৪৩, ৫০
Directed graph, reachabilityState diagram, emptiness test, PATH সমস্যাপর্ব ২০, ৬৪, ৬৬
Countable, uncountable, diagonalসব language চেনা যায় না, halting problemপর্ব ৫০, ৫১
Big-OTime আর space complexity, class Pপর্ব ৫৭, ৬৪
এই কোর্সের notation-এর চুক্তি

ℕ = {0, 1, 2, …}, অর্থাৎ এই কোর্সে 0 স্বাভাবিক সংখ্যা (কিছু বই 0 বাদ দেয়)। A ⊆ B মানে A, B-এর subset (সমানও হতে পারে); A ⊂ B মানে proper subset. |A| হলো A-এর আকার। ফাঁকা string-কে লেখা হবে ε (কিছু বই λ লেখে, অর্থ একই)। Σ সবসময় একটি সসীম, অশূন্য alphabet, আর Σ∗ তার ওপর সব সসীম string-এর set; এর বিস্তারিত পর্ব ০৩ “Alphabet, string আর language”-এ।

২ · Set: set-builder, power set আর Cartesian product

একটি set হলো আলাদা আলাদা বস্তুর সংগ্রহ, যেখানে ক্রম বা পুনরাবৃত্তির কোনো মূল্য নেই: {a, b} = {b, a, a}। পূর্ণ আলোচনা ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৪ আর পর্ব ১৫-এ। গণনার তত্ত্বে set লেখার প্রধান উপায় set-builder notation: {x ∈ U : P(x)}, অর্থাৎ U-এর সেই সব x, যাদের জন্য শর্ত P(x) সত্য। একটি language এভাবেই লেখা হয়:

L = { w ∈ {0, 1}∗ : w-তে 1-এর সংখ্যা জোড় }

বাজারঘরের সেন্সর লাইনের parity check ঠিক এই language: যে বার্তায় 1-এর সংখ্যা জোড়, সেটিই বৈধ। আরেকটি উদাহরণ {0n1n : n ∈ ℕ}, অর্থাৎ ε, 01, 0011, …; এখানে “U-এর মধ্যে” অংশটি উহ্য, কারণ প্রসঙ্গ থেকে বোঝা যায়। একটি অভ্যাস রাখুন: সবসময় একটি মূল set (এখানে Σ∗) থেকে বাছাই করুন। এর কারণ ভাবনার প্রশ্ন ৩-এ দেখবেন।

Power set আর Cartesian product

A-এর power set P(A) হলো A-এর সব subset-এর set, ∅ আর A-সহ; |A| = n হলে |P(A)| = 2n, কারণ প্রতিটি উপাদানের জন্য “নেব, নেব না” দুটি পছন্দ। Cartesian product A × B হলো সব ক্রমযুক্ত জোড়া (a, b), যেখানে a ∈ A, b ∈ B; সসীম হলে |A × B| = |A| · |B|। এই দুটি ধারণা দিয়েই finite automaton-এর সংজ্ঞা লেখা হয় (বিস্তারিত পর্ব ০৭ আর ০৯-এ):

অংশগাণিতিক রূপঅর্থ
DFA M = (Q, Σ, δ, q0, F)F ⊆ Q, δ : Q × Σ → Qপ্রতিটি (state, চিহ্ন) জোড়ায় ঠিক একটি পরের state
NFAδ : Q × Σε → P(Q)পরের state-এর একটি set, ফাঁকাও হতে পারে; Σε = Σ ∪ {ε}
Subset constructionনতুন state-এর set = P(Q)|Q| = n হলে সর্বোচ্চ 2nটি state (পর্ব ১০)
Product constructionQ1 × Q2দুটি DFA একসঙ্গে চালানো, |Q1| · |Q2|টি state (পর্ব ০৮)

তিনটি জিনিস আলাদা: ∅ হলো ফাঁকা set (কোনো string নেই), {ε} হলো একটি উপাদানের set (একমাত্র উপাদান ফাঁকা string), আর {∅} হলো সেই set, যার একমাত্র উপাদান ফাঁকা set. |∅| = 0, কিন্তু |{ε}| = |{∅}| = 1. আর P(∅) = {∅}, তাই |P(∅)| = 20 = 1. Language-এর প্রশ্নে “কোনো string গ্রহণ করে না” (∅) আর “শুধু ফাঁকা string গ্রহণ করে” ({ε}) দুটি ভিন্ন machine-এর ভাষা।

৩ · Relation: equivalence class আর “শূন্য বা বেশি ধাপ”

A-এর ওপর একটি binary relation R হলো A × A-এর যেকোনো subset; (x, y) ∈ R হলে লেখা হয় x R y. বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫২ আর পর্ব ৫৫-এ। গণনার তত্ত্বে দুই ধরনের relation বারবার আসে।

সংজ্ঞা ৩.১ (Equivalence relation আর class)

A-এর ওপর R একটি equivalence relation যদি এটি (১) reflexive: সব x-এর জন্য x R x; (২) symmetric: x R y হলে y R x; আর (৩) transitive: x R y আর y R z হলে x R z. x-এর equivalence class [x] = {y ∈ A : x R y}। যেকোনো দুটি class হয় হুবহু সমান, নয়তো সম্পূর্ণ বিচ্ছিন্ন, তাই class-গুলো A-এর একটি partition তৈরি করে।

উদাহরণ: {0, 1}∗-এর ওপর x ~ y যদি x আর y-তে 1-এর সংখ্যার parity (জোড় না বিজোড়) একই হয়। তিনটি শর্তই সহজে মেলে, কারণ “একই parity” মানে “একটি function-এর মান সমান”, আর “f(x) = f(y)” ধরনের সব relation-ই equivalence relation. নিচের stepper দৈর্ঘ্য ২ পর্যন্ত সাতটি string-কে একে একে class-এ বসায়।

1x ~ y  iff  #1(x) ≡ #1(y) mod 22ε    #1 = 0  → new class A30    #1 = 0  → A41    #1 = 1  → new class B500   #1 = 0  → A601   #1 = 1  → B710   #1 = 1  → B811   #1 = 2  → A9partition: {A, B}
Class-এর অবস্থা
A (জোড়)
B (বিজোড়)
class সংখ্যা
  1. Relation ঠিক করা। #1(x) মানে x-এ 1-এর সংখ্যা। দুটি string সম্পর্কিত, যদি এই সংখ্যার parity মেলে। এটি reflexive, symmetric আর transitive, কারণ এটি “একই মান” ধরনের relation.
  2. ε প্রথম। ফাঁকা string-এ কোনো 1 নেই, #1 = 0. এখনো কোনো class নেই, তাই নতুন class A খোলা হলো, প্রতিনিধি ε।
  3. 0. #1 = 0, ε-এর সঙ্গে parity মেলে, তাই 0 ∈ [ε] = A.
  4. 1. #1 = 1, A-এর কারও সঙ্গে মেলে না। নতুন class B, প্রতিনিধি 1.
  5. 00. কোনো 1 নেই, জোড়: A-তে গেল।
  6. 01. একটি 1, বিজোড়: B-তে।
  7. 10. একটি 1: B-তে। লক্ষ করুন, 01 আর 10 ভিন্ন string, কিন্তু এই relation-এর চোখে “একই রকম”।
  8. 11. দুটি 1, জোড়: A-তে। দৈর্ঘ্য ভিন্ন হলেও ε আর 11 একই class-এ।
  9. ফল: দুটি class. সাতটি string দুই ভাগে পড়ল, আর দৈর্ঘ্য যত বাড়ুক, নতুন class আর আসবে না। এই দুটি class-ই parity-র DFA-র দুটি state. এই সংযোগটি পর্ব ১৮-এ Myhill–Nerode theorem হিসেবে পূর্ণ রূপ পাবে।

সব relation equivalence নয়, আর ভুল প্রায়ই transitivity-তে। নিচের ব্লক দৈর্ঘ্য ৩ পর্যন্ত ১৫টি string-এ চারটি relation-এর তিনটি ধর্ম brute force-এ যাচাই করে; কোনো ধর্ম না মিললে একটি counterexample দেখায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
def strings(sigma, maxlen):              # all strings up to maxlen, shortlex order
    return ["".join(t) for n in range(maxlen + 1) for t in product(sigma, repeat=n)]
S = strings("01", 3)                      # 15 strings
def check(name, R):
    refl = all(R(x, x) for x in S)
    sym = all(R(y, x) for x in S for y in S if R(x, y))
    bad = next(((x, y, z) for x in S for y in S for z in S
                if R(x, y) and R(y, z) and not R(x, z)), None)
    print(f"{name:15} refl={refl} sym={sym} trans={bad is None}"
          + ("" if bad is None else f" counterexample {bad}"))
check("same parity", lambda x, y: x.count("1") % 2 == y.count("1") % 2)
check("same length", lambda x, y: len(x) == len(y))
check("is prefix of", lambda x, y: y.startswith(x))
check("share a symbol", lambda x, y: bool(set(x) & set(y)))
classes = {}
for w in S:                               # group strings by parity of 1s
    classes.setdefault(w.count("1") % 2, []).append(w or "ε")
for k, ws in classes.items():
    print("even" if k == 0 else "odd ", ws)

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

same parity     refl=True sym=True trans=True
same length     refl=True sym=True trans=True
is prefix of    refl=True sym=False trans=True
share a symbol  refl=False sym=True trans=False counterexample ('0', '01', '1')
even ['ε', '0', '00', '11', '000', '011', '101', '110']
odd  ['1', '01', '10', '001', '010', '100', '111']

প্রথম দুটি relation তিন ধর্মই পূরণ করে, কারণ দুটিই “একটি মান সমান” ধরনের। Prefix relation symmetric নয়: ε সব string-এর prefix, কিন্তু উল্টোটা নয়। “একটি চিহ্ন ভাগ করে” relation দুই জায়গায় ব্যর্থ: ε নিজের সঙ্গেও কোনো চিহ্ন ভাগ করে না (reflexive নয়), আর counterexample (0, 01, 1) দেখায় 0 ~ 01 আর 01 ~ 1 হলেও 0 আর 1 সম্পর্কিত নয় (transitive নয়)। শেষ দুই লাইনে দৈর্ঘ্য ৩ পর্যন্ত ১৫টি string দুটি class-এ ভাগ হয়েছে, ৮টি জোড় আর ৭টি বিজোড়; stepper-এর সাতটি string-এর ভাগ এর প্রথম অংশ। এমন brute force প্রমাণ নয়, কিন্তু ভুল দাবির counterexample খুঁজে দেয়।

“শূন্য বা বেশি ধাপে”: reflexive-transitive closure

দ্বিতীয় ধরনের relation হলো “এক ধাপে যাওয়া”। Turing machine-এর একটি configuration থেকে এক ধাপে আরেকটিতে যাওয়াকে লেখা হয় C ⊢ C′ (পর্ব ৪৩), আর grammar-এ এক নিয়ম প্রয়োগে u ⇒ v (পর্ব ২৬)। তারপর আসে ⊢∗ আর ⇒∗: “শূন্য বা তার বেশি ধাপে”। গাণিতিকভাবে এটি R-এর reflexive-transitive closure R∗: যে ক্ষুদ্রতম relation R-কে ধারণ করে এবং reflexive ও transitive. সমানভাবে, x R∗ y ঠিক তখন, যখন কোনো k ≥ 0 আর x = x0 R x1 R … R xk = y শিকল আছে। k = 0 অনুমোদিত, তাই সবসময় x R∗ x. বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫৪-এ। Graph-এর ভাষায় R∗ হলো reachability, যা পরের দুই অংশ জুড়ে কাজে লাগবে।

৪ · Function: total, partial আর bijection

A থেকে B-তে একটি function f : A → B হলো A × B-এর এমন একটি subset, যেখানে A-এর প্রতিটি উপাদান ঠিক একটি জোড়ার প্রথম উপাদান। বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৬-এ। গণনার তত্ত্বে “প্রতিটি উপাদান” শর্তটি নিয়েই সবচেয়ে বড় পার্থক্য তৈরি হয়।

Total function

Domain-এর প্রতিটি উপাদানে মান সংজ্ঞায়িত। DFA-র δ total: প্রতিটি (state, চিহ্ন) জোড়ায় পরের state আছে, প্রয়োজনে একটি dead state দিয়ে।

DFA-র δ, যেকোনো decider

Partial function

কিছু ইনপুটে মান অসংজ্ঞায়িত। Turing machine কোনো ইনপুটে চিরকাল চলতে পারে; তখন তার “output”-ই নেই। তাই TM যে function গণনা করে, তা সাধারণভাবে partial.

TM-এর গণনা করা function

একটি total function-এর মান সবখানে আছে; একটি partial function A-এর কোনো subset D-তে সংজ্ঞায়িত, বাকিটায় নয়। মোবাইল ব্যাংকিংয়ের PIN মেনুর কথা ভাবুন: সঠিক ইনপুটে একটি উত্তর আসে, কিন্তু নেটওয়ার্ক আটকে গেলে স্ক্রিন অনির্দিষ্টকাল ঘুরতেই থাকে; সেই ইনপুটের জন্য “উত্তর” বলে কিছু নেই। পর্ব ৫০-এ দেখবেন, decider মানে সব ইনপুটে থামে এমন machine, যা একটি total function দেয়, আর recognizer-এর বেলায় এই নিশ্চয়তা নেই।

সংজ্ঞা ৪.১ (তিন ধরনের function)

f : A → B হলো injection (one-to-one), যদি f(a) = f(a′) হলে a = a′; surjection (onto), যদি প্রতিটি b ∈ B-এর জন্য কোনো a-তে f(a) = b; আর bijection, যদি দুটিই হয়। A থেকে B-তে bijection থাকলে বলা হয় A আর B-এর cardinality সমান, |A| = |B|; injection থাকলে |A| ≤ |B|।

f : {0, 1}∗ → ℕInjection?Surjection?কারণ
f(w) = |w|নাহ্যাঁ01 আর 10 দুটিরই দৈর্ঘ্য 2; প্রতিটি n-এর জন্য 0n আছে
f(w) = w-কে binary সংখ্যা হিসেবে পড়া (ε-তে 0)নাহ্যাঁ1 আর 01 দুটিরই মান 1
f(w) = 1w-এর binary মানহ্যাঁনাশুরুর 1 আলাদা করে; কিন্তু 0 কখনো আসে না
f(w) = 1w-এর binary মান − 1হ্যাঁহ্যাঁএটিই shortlex অবস্থান, অংশ ৬-এ প্রমাণ

শেষ সারিটি আকস্মিক নয়: এক ধাপ সংশোধনে একটি injection bijection হয়ে গেল। গণনার তত্ত্বে encoding (পর্ব ০৫) মানে ঠিক এমন injection: প্রতিটি graph, DFA বা Turing machine-কে একটি আলাদা string ⟨M⟩ দেওয়া। Injection হওয়াই যথেষ্ট, কারণ দুটি ভিন্ন machine-কে একই string দিলে বিভ্রান্তি হয়, কিন্তু কিছু string কোনো machine-এর বৈধ বর্ণনা না হলে সমস্যা নেই।

উদাহরণ ৪.২ (কতগুলো DFA আছে?)

A থেকে B-তে function-এর সংখ্যা |B||A|, কারণ A-এর প্রতিটি উপাদানের জন্য B-এর |B|টি পছন্দ, আর পছন্দগুলো গুণ হয়। এটি দিয়ে একটি পরীক্ষার ধাঁচের প্রশ্নের উত্তর দেওয়া যায়: Q = {q0, q1} (n = 2) আর Σ = {0, 1} (k = 2) স্থির রাখলে কতগুলো আলাদা DFA লেখা যায়? δ : Q × Σ → Q একটি function, তাই δ বাছাইয়ের উপায় nnk = 24 = 16; শুরুর state n = 2 ভাবে; F ⊆ Q, তাই 2n = 4 ভাবে। মোট 16 · 2 · 4 = 128টি DFA. NFA-র বেলায় δ : Q × Σε → P(Q), তাই δ-এর উপায় (2n)n(k+1) = 212 = 4096, আর মোট 4096 · 2 · 4 = 32768. লক্ষ করুন, এগুলো বর্ণনার সংখ্যা; অনেক আলাদা DFA একই language চেনে, যেমন যেকোনো DFA-তে F = ∅ নিলে language ∅।

Pigeonhole-এর ছায়া: A আর B সসীম হলে এবং |A| > |B| হলে A থেকে B-তে কোনো injection নেই; অন্তত দুটি উপাদান একই জায়গায় পড়বে। k-টি state-এর DFA k + 1টি অবস্থান পার হলে কোনো state দুবার আসবেই, আর এখান থেকেই জন্ম নেয় pumping lemma (পর্ব ১৭)। পূর্ণ প্রমাণ পর্ব ০৪-এ, আর নীতিটির বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৩২-এ।

৫ · Graph: state diagram আর reachability

একটি directed graph G = (V, E)-তে V হলো vertex-এর set, আর E ⊆ V × V হলো তীরের set: (u, v) ∈ E মানে u থেকে v-তে একটি তীর। অর্থাৎ directed graph আর একটি set-এর ওপর relation একই জিনিস, শুধু ছবিতে আঁকা। বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫৭ আর পর্ব ৫৯-এ। প্রতিটি finite automaton-এর state diagram একটি directed graph, যার তীরের গায়ে চিহ্ন লেখা থাকে। অনেক প্রশ্নে সেই চিহ্নগুলো বাদ দিলেও উত্তর বদলায় না।

পাঁচ state-এর একটি machine-এর graph

তীরের চিহ্ন বাদ দেওয়া হয়েছে, কারণ reachability শুধু তীরের দিক দেখে। বাঁ দিকের খোলা তীর শুরুর state q0 দেখায়। দুই দাগের বৃত্ত q4 accept state.

Directed graph of a 5-state machine; accept state q4 is unreachable from q0 q0q1q2q3q4 পৌঁছানো যায় নাশুরু
ছবি ২.১ — q4-এ ঢোকার কোনো তীর নেই; q4 থেকে বরং q2-তে যাওয়া যায়। তাই q0 থেকে q4 অগম্য, আর এই machine কোনো string-ই গ্রহণ করে না।

একটি DFA কোনো string গ্রহণ করে ঠিক তখন, যখন শুরুর state থেকে কোনো accept state-এ একটি পথ আছে: পথের তীরগুলোর চিহ্ন পরপর পড়লেই সেই string. তাই “L(M) = ∅ কি না” (emptiness problem, পর্ব ২০) আসলে graph-এর reachability প্রশ্ন, আর BFS (breadth-first search) তা |V| + |E|-এর অনুপাতে সময়ে উত্তর দেয়। BFS-এর বিস্তারিত DSA কোর্সের পর্ব ৪০-এ। নিচের stepper ছবির graph-এ q0 থেকে BFS চালায়।

1queue = [q0], seen = {q0}2pop q0: q1 new3pop q1: q2, q3 new4pop q2: q0 already seen5pop q3: q3 already seen6queue empty: q4 ∉ seen
BFS-এর অবস্থা
queue
seen
বের হলো
  1. শুরু। শুরুর state q0 queue-তে রাখা হলো এবং “দেখা হয়েছে” চিহ্ন দেওয়া হলো। শূন্য ধাপেই q0 নিজের কাছে পৌঁছায় (R∗-এর k = 0).
  2. q0 বের হলো। q0 থেকে একমাত্র তীর q1-এ। q1 নতুন, তাই queue-তে আর seen-এ গেল।
  3. q1 বের হলো। q1 থেকে দুটি তীর: q2 আর q3. দুটিই নতুন, দুটিই queue-তে।
  4. q2 বের হলো। q2 থেকে তীর q0-তে, কিন্তু q0 আগেই দেখা। কিছু যোগ হলো না; এই চিহ্নটির জন্যই BFS কখনো চক্রে আটকে যায় না।
  5. q3 বের হলো। q3-এর একমাত্র তীর নিজের দিকে (self-loop). নতুন কিছু নেই, queue ফাঁকা হলো।
  6. শেষ। q0 থেকে পৌঁছানো যায় {q0, q1, q2, q3}। একমাত্র accept state q4 এই set-এ নেই, তাই L(M) = ∅। খেয়াল করুন, q4 → q2 তীর আছে, কিন্তু উল্টো দিকে নেই: directed graph-এ reachability symmetric নয়।
from collections import deque
# graph of the 5-state machine in Figure 2.1 (symbols on edges dropped)
G = {"q0": ["q1"], "q1": ["q2", "q3"], "q2": ["q0"], "q3": ["q3"], "q4": ["q2"]}
def reach(G, s):
    seen, order, queue = {s}, [], deque([s])
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in G[u]:
            if v not in seen:
                seen.add(v)
                queue.append(v)
    return order, seen
order, seen = reach(G, "q0")
print("BFS order from q0:", order)
for F in ({"q4"}, {"q3", "q4"}):
    print("accept", sorted(F), "-> L(M) empty?", not (seen & F))
# R* (reflexive-transitive closure of the edge relation) = reachability
star = {u: sorted(reach(G, u)[1]) for u in G}
for u, vs in star.items():
    print(u, "->*", vs)
print("q4 ->* q0 ?", "q0" in star["q4"], "| q0 ->* q4 ?", "q4" in star["q0"])

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

BFS order from q0: ['q0', 'q1', 'q2', 'q3']
accept ['q4'] -> L(M) empty? True
accept ['q3', 'q4'] -> L(M) empty? False
q0 ->* ['q0', 'q1', 'q2', 'q3']
q1 ->* ['q0', 'q1', 'q2', 'q3']
q2 ->* ['q0', 'q1', 'q2', 'q3']
q3 ->* ['q3']
q4 ->* ['q0', 'q1', 'q2', 'q3', 'q4']
q4 ->* q0 ? True | q0 ->* q4 ? False

BFS-এর ক্রম stepper-এর সঙ্গে হুবহু মেলে, আর F = {q4} হলে ভাষা ফাঁকা। Accept set-এ q3 যোগ করলেই ভাষা আর ফাঁকা থাকে না, কারণ q3-এ পৌঁছানো যায়। পরের পাঁচ লাইন হলো edge relation-এর reflexive-transitive closure: প্রতিটি সারিতে vertex নিজে আছে (শূন্য ধাপ)। q3 থেকে শুধু q3, কারণ তার একমাত্র তীর self-loop. শেষ লাইন দেখায় q4 থেকে q0-তে যাওয়া যায় (q4 → q2 → q0), কিন্তু q0 থেকে q4-এ নয়: R∗ সাধারণত symmetric নয়।

একই graph-চিন্তা আরেকটি প্রশ্নেরও উত্তর দেয়: L(M) কি অসীম? উত্তর হ্যাঁ ঠিক তখন, যখন এমন একটি চক্র (cycle) আছে, যা শুরু থেকে পৌঁছানো যায় এবং যেখান থেকে কোনো accept state-এ পৌঁছানো যায়: চক্রটি যতবার খুশি ঘুরে অসীম সংখ্যক ভিন্ন দৈর্ঘ্যের string পাওয়া যায়। চক্র না থাকলে প্রতিটি গৃহীত পথ কোনো state দুবার ছোঁয় না, তাই তার দৈর্ঘ্য |Q| − 1-এর বেশি নয়, আর গৃহীত string সসীম সংখ্যক। ছবি ২.১-এ q0 → q1 → q2 → q0 চক্রটি পৌঁছানো যায়, কিন্তু সেখান থেকে q4-এ যাওয়া যায় না, তাই চক্রটি কাজে আসে না। দুটি BFS (একটি শুরু থেকে সামনে, একটি accept state থেকে তীর উল্টে পেছনে) আর একটি চক্র-পরীক্ষাই যথেষ্ট; পর্ব ২০-এ এটি পূর্ণ algorithm হিসেবে আসবে।

৬ · Countable: Σ∗ গোনা যায়

অসীম set-এর “আকার” তুলনা করা হয় bijection দিয়ে। একটি set countable, যদি সেটি সসীম হয়, অথবা ℕ-এর সঙ্গে তার bijection থাকে; দ্বিতীয় ক্ষেত্রে বলা হয় countably infinite. সহজ ভাষায়: উপাদানগুলোকে ০ম, ১ম, ২য়, … এক সারিতে এমনভাবে দাঁড় করানো যায় যে প্রত্যেকে একটি সসীম নম্বর পায়। যে set countable নয়, সেটি uncountable. বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৮-এ, যেখানে ℤ আর ℚ countable এবং বাস্তব সংখ্যা uncountable প্রমাণ করা আছে।

পরীক্ষার রোল নম্বরের মতো ভাবুন: প্রতিটি পরীক্ষার্থী একটি নম্বর পাবেন, কেউ বাদ পড়বেন না, দুজন একই নম্বর পাবেন না। Σ∗-এর প্রতিটি string-কে কি এভাবে নম্বর দেওয়া যায়? অভিধানের ক্রম (lexicographic order) চলবে না: {0, 1}∗-এ অভিধান ক্রমে ε, 0, 00, 000, … অসীম সারি আগে আসে, ফলে “1” কখনো সসীম নম্বর পায় না। সমাধান হলো shortlex order: আগে দৈর্ঘ্য অনুযায়ী, একই দৈর্ঘ্যের মধ্যে অভিধান ক্রমে। এই কোর্সে string-এর তালিকা সবসময় এই ক্রমে দেওয়া হবে।

1n=0: ε                 → 02n=1: 0 1               → 1 23n=2: 00 01 10 11       → 3..64n=3: 000 001 … 111     → 7..145rank(w) = val(1w) − 16unrank(10): 11 = 1011 → 011
গণনার অবস্থা
নতুন block-এর মাপ
এ পর্যন্ত মোট
উদাহরণ
  1. দৈর্ঘ্য 0. শুধু ε, সে পায় অবস্থান 0. প্রতিটি দৈর্ঘ্যের block সসীম, এটাই পুরো কৌশলের চাবি।
  2. দৈর্ঘ্য 1. 0 আর 1, অবস্থান 1 আর 2. অভিধান ক্রমের মতো 00 আগে চলে আসে না, কারণ ছোট দৈর্ঘ্য আগে।
  3. দৈর্ঘ্য 2. চারটি string, অবস্থান 3 থেকে 6. এ পর্যন্ত মোট 1 + 2 + 4 = 7টি।
  4. দৈর্ঘ্য 3. আটটি string, অবস্থান 7 থেকে 14. যেকোনো দৈর্ঘ্য n-এর string-এর আগে আছে 2n − 1টি ছোট string, একটি সসীম সংখ্যা।
  5. সূত্র। w-এর সামনে একটি 1 বসিয়ে binary সংখ্যা হিসেবে পড়ুন, তারপর 1 বাদ দিন: rank(1011) = val(11011) − 1 = 27 − 1 = 26. সামনের 1 দৈর্ঘ্য মনে রাখে, তাই 1 আর 01 আলাদা মান পায়।
  6. উল্টো দিক। অবস্থান 10-এর string চাই: 10 + 1 = 11 = binary 1011, সামনের 1 বাদ দিলে 011. দুই দিকেই একটি সসীম হিসাব, তাই এটি সত্যিকারের bijection.
উপপাদ্য ৬.১ (Σ∗ countably infinite)

Σ = {a1, …, ak} একটি সসীম alphabet, k ≥ 1, আর চিহ্নগুলোর একটি নির্দিষ্ট ক্রম ধরা হলো। rank(w) = w-এর shortlex তালিকায় অবস্থান। তাহলে rank : Σ∗ → ℕ একটি bijection. স্পষ্ট সূত্র: w = c1c2…cn এবং d(aj) = j হলে

rank(w) = d(c1)·kn−1 + d(c2)·kn−2 + … + d(cn)·k0

এখানে অঙ্কগুলো 0 থেকে নয়, 1 থেকে k পর্যন্ত (একে bijective base-k বলে)। k = 2-এ d(0) = 1, d(1) = 2, আর তখন সূত্রটি ঠিক val(1w) − 1-এর সমান।

  1. প্রতিটি n-এর জন্য Σn (দৈর্ঘ্য n-এর সব string) সসীম, |Σn| = kn. — গুণের নিয়ম: প্রতিটি অবস্থানে k-টি পছন্দ
  2. Σ∗ = Σ0 ∪ Σ1 ∪ Σ2 ∪ …, আর এই block-গুলো পরস্পর বিচ্ছিন্ন। — প্রতিটি string-এর একটিই দৈর্ঘ্য
  3. Shortlex তালিকা block-গুলো দৈর্ঘ্যের ক্রমে, প্রতিটি block-এর ভেতরে অভিধান ক্রমে সাজায়। দৈর্ঘ্য n-এর w-এর অবস্থান = k0 + … + kn−1 + (Σn-এর ভেতরে w-এর অভিধান-অবস্থান), একটি সসীম সংখ্যা। তাই rank সব w-এ সংজ্ঞায়িত। — ধাপ ১: আগের block-গুলো সসীম
  4. তালিকায় কোনো string দুবার নেই, তাই ভিন্ন string ভিন্ন অবস্থান পায়: rank injection. — block বিচ্ছিন্ন, block-এর ভেতরে অভিধান ক্রম একটি total order
  5. যেকোনো m ∈ ℕ নিন। block-গুলোর মাপের যোগফল 1 + k + k2 + … সীমাহীনভাবে বাড়ে (k ≥ 1), তাই কোনো n-এ m অবস্থানটি block Σn-এর ভেতরে পড়ে, আর সেই অবস্থানে একটি string আছে: rank surjection. — সসীম block-এর অসীম শিকল ℕ ঢেকে ফেলে
  6. Injection আর surjection মিলে bijection, তাই |Σ∗| = |ℕ|। ∎

এই উপপাদ্যের একটি গুরুত্বপূর্ণ ফল: প্রতিটি DFA, CFG বা Turing machine-কে একটি সসীম string হিসেবে লেখা যায় (পর্ব ০৫-এর encoding ⟨M⟩)। ভিন্ন machine-এর বর্ণনা ভিন্ন string, তাই সব Turing machine-এর set থেকে Σ∗-এ একটি injection আছে, অর্থাৎ Turing machine-এর set countable. নিচের ব্লক shortlex তালিকা, rank আর unrank লিখে প্রথম ৫০০০টি অবস্থানে bijection যাচাই করে, আর অভিধান ক্রমের সমস্যাটি সংখ্যায় দেখায়।

from itertools import count, islice, product
def shortlex(sigma):                     # length first, then dictionary order
    for n in count():
        for t in product(sigma, repeat=n):
            yield "".join(t)
def rank(w, sigma):                      # bijective base-k, digits 1..k
    r = 0
    for ch in w:
        r = r * len(sigma) + sigma.index(ch) + 1
    return r
def unrank(r, sigma):
    k, w = len(sigma), []
    while r > 0:
        r, d = divmod(r - 1, k)
        w.append(sigma[d])
    return "".join(reversed(w))
print([w or "ε" for w in islice(shortlex("01"), 15)])
print("rank 1011:", rank("1011", "01"), "| val(11011) - 1:", int("11011", 2) - 1)
print("unrank 10:", unrank(10, "01"), "| rank ba over abc:", rank("ba", "abc"))
for sigma in ("01", "abc"):
    first = list(islice(shortlex(sigma), 5000))
    ok = all(rank(w, sigma) == i and unrank(i, sigma) == w for i, w in enumerate(first))
    print(sigma, "first 5000 positions, rank/unrank agree:", ok)
# plain dictionary order: how many strings of length <= n come before "1"?
for n in range(1, 6):
    words = sorted("".join(t) for m in range(n + 1) for t in product("01", repeat=m))
    print("length <= %d: before '1' ->" % n, words.index("1"))

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

['ε', '0', '1', '00', '01', '10', '11', '000', '001', '010', '011', '100', '101', '110', '111']
rank 1011: 26 | val(11011) - 1: 26
unrank 10: 011 | rank ba over abc: 7
01 first 5000 positions, rank/unrank agree: True
abc first 5000 positions, rank/unrank agree: True
length <= 1: before '1' -> 2
length <= 2: before '1' -> 4
length <= 3: before '1' -> 8
length <= 4: before '1' -> 16
length <= 5: before '1' -> 32

প্রথম লাইন stepper-এর তালিকা। দ্বিতীয় আর তৃতীয় লাইনে সূত্র আর হাতে করা হিসাব মিলেছে: 1011-এর অবস্থান 26, অবস্থান 10-এ 011, আর {a, b, c}-তে ba-এর অবস্থান 7. দুটি alphabet-এই প্রথম ৫০০০টি অবস্থানে rank আর unrank একে অপরের উল্টো, যা উপপাদ্য ৬.১-এর একটি সসীম পরীক্ষা (প্রমাণটি সব অবস্থানের জন্য)। শেষ পাঁচ লাইন অভিধান ক্রমের সমস্যা দেখায়: দৈর্ঘ্য ≤ n-এর string নিলে “1”-এর আগে 2nটি string, আর n বাড়ার সঙ্গে সংখ্যাটি সীমাহীনভাবে বাড়ে। পুরো Σ∗-এ তাই “1”-এর কোনো সসীম অবস্থান নেই।

জোড়াও গোনা যায়: ℕ × ℕ-ও countable; Cantor-এর pairing function ⟨i, j⟩ = (i + j)(i + j + 1)/2 + j তির্যক রেখা ধরে জোড়াগুলোকে গোনে। পরের পর্বগুলোতে “সব machine-কে সব ইনপুটে একটু একটু করে চালানো” (dovetailing) কৌশলের পেছনে এই গণনাই কাজ করে, যেমন পর্ব ৫০-এ recognizer আর enumerator-এর সমতায়।

৭ · Cantor-এর উপপাদ্য: বেশিরভাগ language চেনা যায় না

Σ∗ গোনা গেল। কিন্তু Σ∗-এর ওপর language কয়টি? প্রতিটি language Σ∗-এর একটি subset, তাই সব language-এর set হলো P(Σ∗)। Cantor-এর উপপাদ্য বলে, কোনো set-এর power set সেই set-এর চেয়ে কঠোরভাবে বড়।

উপপাদ্য ৭.১ (Cantor-এর উপপাদ্য)

যেকোনো set A-এর জন্য (সসীম বা অসীম) A থেকে P(A)-তে কোনো surjection নেই। ফলে |A| < |P(A)|।

  1. ধরি, বিপরীতে, f : A → P(A) একটি surjection. — contradiction-এর প্রমাণ শুরু
  2. D = {a ∈ A : a ∉ f(a)} সংজ্ঞায়িত করি: যে উপাদান নিজের ছবির ভেতরে নেই। D ⊆ A, তাই D ∈ P(A). — set-builder, A থেকে বাছাই
  3. f surjection, তাই কোনো d ∈ A-তে f(d) = D. — surjection-এর সংজ্ঞা
  4. যদি d ∈ D হয়, তবে D-এর শর্ত অনুযায়ী d ∉ f(d) = D, স্ববিরোধ। যদি d ∉ D হয়, তবে d ∉ f(d), অর্থাৎ d শর্ত মানে, তাই d ∈ D, আবার স্ববিরোধ। — দুটি case, দুটিতেই বিরোধ
  5. অতএব কোনো surjection নেই, আর তাই কোনো bijection-ও নেই। অন্যদিকে a ↦ {a} একটি injection, তাই |A| ≤ |P(A)|। দুটি মিলে |A| < |P(A)|। ∎

A = ℕ হলে D-কে diagonal argument-এর রূপে দেখা যায়: language-গুলো সারি, shortlex-এ string-গুলো কলাম, ঘরে 1 মানে “string-টি language-এ আছে”। D কর্ণ বরাবর প্রতিটি ঘর উল্টে দেয়। নিচের stepper চারটি language আর প্রথম চারটি string-এ এটি দেখায়।

1         ε  0  1  002L0 even1: 1  1  0  13L1 Σ+   : 0  1  1  14L2 1…   : 0  0  1  05L3 ∅    : 0  0  0  06D       : 0  0  0  1
Diagonal-এর অবস্থা
কর্ণের ঘর
D-এর সিদ্ধান্ত
  1. টেবিল। চারটি language: L0 = জোড় সংখ্যক 1, L1 = Σ+ (অশূন্য string), L2 = 1 দিয়ে শুরু, L3 = ∅। কলামে shortlex-এর প্রথম চার string: ε, 0, 1, 00. প্রতিটি ঘর হিসাব করা: যেমন L0-তে 1 নেই, কারণ তাতে একটি 1.
  2. সারি ০, কলাম ০. ε-তে শূন্যটি 1, জোড়, তাই ε ∈ L0, ঘরে 1. D উল্টো করে: ε ∉ D. তাই D আর L0 ε-তে আলাদা।
  3. সারি ১, কলাম ১. 0 অশূন্য, তাই 0 ∈ L1. D-তে 0 থাকবে না, ফলে D ≠ L1.
  4. সারি ২, কলাম ২. 1 দিয়ে শুরু, তাই 1 ∈ L2. উল্টে 1 ∉ D, ফলে D ≠ L2.
  5. সারি ৩, কলাম ৩. ∅-তে কিছুই নেই, ঘরে 0. উল্টে 00 ∈ D, ফলে D ≠ L3.
  6. D-এর সারি। প্রথম চার কলামে D = 0 0 0 1. i-তম সারির সঙ্গে D অন্তত i-তম কলামে আলাদা, তাই D টেবিলের কোনো সারির সমান নয়।
  7. সাধারণ সিদ্ধান্ত। যেকোনো অসীম তালিকা L0, L1, L2, … নিলেও D = {si : si ∉ Li} তালিকার বাইরে থাকে (si = shortlex-এর i-তম string). তাই কোনো তালিকা সব language ধরতে পারে না: P(Σ∗) uncountable.
ফলাফল ৭.২ (সব language চেনা যায় না)

যেকোনো alphabet Σ-এর জন্য এমন language L ⊆ Σ∗ আছে, যা কোনো Turing machine চেনে না (অর্থাৎ L Turing-recognizable নয়)।

প্রমাণের রূপরেখা: প্রতিটি Turing machine একটিমাত্র language চেনে, L(M). Machine-এর set countable (অংশ ৬), তাই recognizable language-এর set-ও countable: machine-গুলোর তালিকা থেকেই এদের একটি তালিকা পাওয়া যায়। কিন্তু উপপাদ্য ৬.১ আর ৭.১ মিলে P(Σ∗) uncountable. একটি countable set একটি uncountable set-কে ঢাকতে পারে না, তাই কিছু language (আসলে “বেশিরভাগ”, uncountably many) বাইরে থেকে যায়। ∎ এটি অস্তিত্বের প্রমাণ: কোন নির্দিষ্ট language চেনা যায় না, তা বলে না। একটি স্পষ্ট উদাহরণ পেতে D-এর কৌশলটি machine-এর নিজের বর্ণনার ওপর চালাতে হয়, আর সেটিই পর্ব ৫১-এর halting problem-এর প্রমাণ।

সসীম ক্ষেত্রে উপপাদ্যটি পুরোপুরি পরীক্ষা করা যায়। নিচের ব্লক A = {0, 1, 2} নিয়ে A থেকে P(A)-তে সব 83 = 512টি function তৈরি করে, দেখে কোনোটি surjection কি না, আর প্রতিটির জন্য D যে ছবির বাইরে, তা যাচাই করে। তারপর stepper-এর টেবিলটি হিসাব করে।

from itertools import chain, combinations, product
A = [0, 1, 2]
P = [frozenset(c) for c in chain.from_iterable(combinations(A, r) for r in range(4))]
print("|A| =", len(A), " |P(A)| =", len(P))
funcs = surj = 0
for images in product(P, repeat=len(A)):     # every f: A -> P(A), f(a) = images[a]
    funcs += 1
    surj += set(images) == set(P)
    D = frozenset(a for a in A if a not in images[a])
    assert D not in images                   # Cantor's set is never an image
print("functions:", funcs, " surjective:", surj)
s = ["", "0", "1", "00"]                     # first 4 strings in shortlex order
L = [lambda w: w.count("1") % 2 == 0,      # L0: even number of 1s
     lambda w: len(w) >= 1,                 # L1: non-empty strings
     lambda w: w.startswith("1"),           # L2: starts with 1
     lambda w: False]                       # L3: the empty language
table = [[int(f(x)) for x in s] for f in L]
for i, row in enumerate(table):
    print(f"L{i}", row)
D = [1 - table[i][i] for i in range(4)]
print("diagonal flipped:", D, "-> D contains", [s[j] or "ε" for j in range(4) if D[j]])
print("D differs from every Li at s_i:", all(D[i] != table[i][i] for i in range(4)))

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

|A| = 3  |P(A)| = 8
functions: 512  surjective: 0
L0 [1, 1, 0, 1]
L1 [0, 1, 1, 1]
L2 [0, 0, 1, 0]
L3 [0, 0, 0, 0]
diagonal flipped: [0, 0, 0, 1] -> D contains ['00']
D differs from every Li at s_i: True

|A| = 3 থেকে |P(A)| = 23 = 8, আর A থেকে P(A)-তে মোট 83 = 512টি function. একটিও surjection নয়, আর প্রতিটির জন্য assert নিশ্চিত করেছে যে Cantor-এর D সেই function-এর কোনো ছবি নয়, প্রমাণের ধাপ ৪ যা বলে। এখানে surjection না থাকা সসীম গণনাতেই স্পষ্ট (৩টি ছবি দিয়ে ৮টি subset ঢাকা যায় না); উপপাদ্যের আসল শক্তি অসীম set-এ, যেখানে গোনা চলে না, শুধু D-এর যুক্তি চলে। শেষ অংশ stepper-এর টেবিল: কর্ণ 1, 1, 1, 0, উল্টে 0, 0, 0, 1, তাই প্রথম চার string-এর মধ্যে D-তে শুধু 00, আর প্রতিটি Li থেকে D অন্তত si-তে আলাদা।

৮ · Big-O: বৃদ্ধির হার এক নজরে

মডিউল ১০ থেকে প্রশ্ন বদলে যাবে “করা যায় কি না” থেকে “কত ধাপে করা যায়”-তে। সেখানে ভাষা হবে Big-O: f(n) = O(g(n)) মানে এমন ধ্রুবক c > 0 আর n0 আছে, যাতে সব n ≥ n0-এ f(n) ≤ c · g(n). পূর্ণ আলোচনা DSA কোর্সের পর্ব ০৪-এ। উদাহরণ: 3n2 + 5n = O(n2), কারণ c = 4, n0 = 5 নিলে 3n2 + 5n ≤ 4n2 ⇔ 5n ≤ n2 ⇔ n ≥ 5. কিন্তু 3n2 + 5n ≠ O(n), কারণ যেকোনো c-এর জন্য n > c হলে 3n2 > cn.

nn22nদৈর্ঘ্য ≤ n-এর binary string, 2n+1 − 1
1010010242047
2040010485762097151
401600প্রায় 1.1 × 1012প্রায় 2.2 × 1012

শেষ কলামটি এই কোর্সে বারবার ফিরবে। Brute force দিয়ে “দুটি automaton কি একই language চেনে?” যাচাই করতে আমরা দৈর্ঘ্য ≤ n-এর সব string চালাই; n = 10-এ ২০৪৭টি, মুহূর্তের কাজ, কিন্তু n = 40-এ এক লাখ কোটির বেশি। তাই brute force ভুল ধরার সস্তা উপায়, প্রমাণের বিকল্প নয়। পর্ব ১০-এর 2n state, পর্ব ৫৭-এর polynomial time আর পর্ব ৬৩-এর P বনাম NP প্রশ্ন, সবই এই টেবিলের বাঁ আর ডান কলামের পার্থক্য নিয়ে।

আরও গভীরে: Directed graph-এ reachability (PATH সমস্যা) NL-complete, অর্থাৎ nondeterministic logarithmic space-এর “সবচেয়ে কঠিন” সমস্যা, আর Savitch-এর theorem এই সমস্যার একটি চতুর recursion থেকেই আসে (পর্ব ৬৪, ৬৬)। Undirected graph-এ reachability যে deterministic logarithmic space-এই সমাধান করা যায়, তা Omer Reingold ২০০৫ সালে প্রমাণ করেন। অসীম set-এর দিকে, ℕ আর ℝ-এর মাঝামাঝি আকারের কোনো set আছে কি না (continuum hypothesis), তা প্রচলিত ZFC স্বতঃসিদ্ধ দিয়ে প্রমাণ বা খণ্ডন করা যায় না (Gödel ১৯৪০, Cohen ১৯৬৩); গণনার তত্ত্বের কোনো ফল অবশ্য এর ওপর নির্ভর করে না।

পরীক্ষা ও ইন্টারভিউতে:

  • |A| = 4 হলে |P(A)| আর |A × A| কত? 16 আর 16; দুটি মিলে যাওয়া কাকতালীয়, |A| = 3-এ 8 আর 9.
  • {0, 1}∗ কি countable? প্রমাণ দিন। হ্যাঁ; shortlex অবস্থান rank(w) = val(1w) − 1 একটি bijection.
  • অসীম binary sequence-এর set কি countable? না; diagonal argument. এগুলো string নয়, কারণ string সসীম।
  • “x, y-এর prefix” কি equivalence relation? না; reflexive আর transitive, কিন্তু symmetric নয় (0, 01-এর prefix, উল্টোটা নয়)।
  • কেন সব language decidable হতে পারে না? Machine countable, language uncountable (Cantor).

৯ · AI-এর যুগে: গণিতের দাবি যাচাই

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

AI-এর দাবিসমস্যাযাচাইয়ের উপায়
“Σ∗ uncountable, diagonal দিয়ে প্রমাণ”Diagonal থেকে পাওয়া বস্তু অসীম sequence, string নয়নতুন বস্তুটি সসীম কি না জিজ্ঞেস করুন
“অভিধান ক্রমে Σ∗ গোনা যায়”“1” কখনো সসীম অবস্থান পায় না“1”-এর আগে কয়টি string, গুনে দেখুন
“এই relation equivalence”Transitivity বা ε-তে reflexivity বাদছোট set-এ তিন ধর্ম brute force-এ পরীক্ষা
“|P(∅)| = 0”P(∅) = {∅}, আকার 120 = 1, সংজ্ঞা থেকে
“O(n2) মানে ঠিক n2 ধাপ”O শুধু ওপরের সীমা, ধ্রুবক আর ছোট n উপেক্ষা করেc আর n0 স্পষ্ট লিখতে বলুন

AI-কে প্রমাণ লিখতে দিলে প্রতিটি ধাপের কারণ আর একটি কম্পিউটার-যাচাই চেয়ে নিন। একটি কাঠামো:

আমি গণনার তত্ত্ব শিখছি। প্রমাণ করো যে {a, b, c}* countable, একটি স্পষ্ট bijection f: {a,b,c}* → ℕ দিয়ে। ১. f-এর সূত্র দাও, আর f(ba) ও f(cab) হাতে হিসাব করে দেখাও। ২. প্রমাণটি নম্বর দেওয়া ধাপে লেখো; প্রতিটি ধাপের পাশে কোন সংজ্ঞা বা নিয়ম ব্যবহার করলে, বলো। ৩. injective আর surjective দুটি অংশ আলাদা করে প্রমাণ করো। ৪. একটি ছোট Python কোড দাও, যা প্রথম ১০০০টি string-এ f আর তার inverse মিলিয়ে দেখে। ৫. কোনো দাবি নিয়ে নিশ্চিত না হলে স্পষ্ট বলো; কোনো বই বা paper-এর নাম বানিয়ে দিও না।

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

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

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

প্র ০১Cantor-এর diagonal কৌশল কীভাবে জন্ম নিল, আর কীভাবে তা Turing-এর হাতে কম্পিউটারের সীমা প্রমাণের অস্ত্র হলো?

Georg Cantor ১৮৭৪ সালে প্রথম দেখান যে বাস্তব সংখ্যার set countable নয়। মজার ব্যাপার, সেই প্রথম প্রমাণে diagonal ছিল না; সেটি ছিল সংকুচিত হতে থাকা ব্যবধির একটি যুক্তি। Diagonal কৌশলটি তিনি প্রকাশ করেন ১৮৯১ সালে, এবং একই ধাঁচের যুক্তিতে দেখান যে কোনো set-এর সব subset-এর set সেই set-এর চেয়ে বড়। ফলে অসীমেরও একটি সিঁড়ি তৈরি হলো: ℕ, P(ℕ), P(P(ℕ)), …, প্রতিটি আগেরটির চেয়ে বড়।

সেই সময়ের অনেক গণিতবিদ এটি সহজে মেনে নেননি; Leopold Kronecker-এর মতো কেউ কেউ “সম্পূর্ণ অসীম” নিয়ে কাজ করাকেই সন্দেহের চোখে দেখতেন। অন্যদিকে David Hilbert ১৯২০-এর দশকে বলেছিলেন, Cantor যে স্বর্গ তৈরি করেছেন, সেখান থেকে কেউ আমাদের বের করে দিতে পারবে না।

১৯৩৬ সালে Alan Turing “On Computable Numbers” প্রবন্ধে এই কৌশলটিকে একেবারে নতুন কাজে লাগান। তিনি দেখান, সব machine-এর বর্ণনা সসীম লেখা, তাই machine গোনা যায়, এবং diagonal ধাঁচের যুক্তিতে প্রমাণ করেন যে কিছু প্রশ্ন কোনো machine-ই সব ইনপুটে সঠিক উত্তর দিয়ে সমাধান করতে পারে না। পার্থক্য এক জায়গায়: Cantor-এর diagonal শুধু “তালিকার বাইরে কিছু আছে” বলে, আর Turing-এর diagonal machine-কে নিজের বর্ণনার ওপর চালিয়ে একটি নির্দিষ্ট অমীমাংসেয় প্রশ্ন দেখায়। এই কোর্সের পর্ব ৫১-এ সেই প্রমাণটি পূর্ণ রূপে আসবে, আর পর্ব ৬৭-এর hierarchy theorem-এও diagonal ফিরবে, এবার সময় আর মেমরির মাপ নিয়ে।

একটি সতর্কতা: diagonal সব কাজ করে না। পর্ব ৬৮-এ দেখবেন, শুধু “machine-কে machine দিয়ে simulate করা” ধরনের যুক্তি দিয়ে P বনাম NP-এর মতো প্রশ্নের নিষ্পত্তি সম্ভব নয় বলে ১৯৭৫ সালে Baker, Gill আর Solovay দেখিয়েছেন (relativization বাধা)।

মূল উপলব্ধি: একটি সরল কৌশল (তালিকার i-তম সদস্যকে i-তম জায়গায় উল্টে দেওয়া) অসীমের আকার মাপা থেকে শুরু করে কম্পিউটারের মৌলিক সীমা পর্যন্ত প্রমাণ করে। কৌশলটি চিনে রাখলে এই কোর্সের অর্ধেক কঠিন প্রমাণ পরিচিত লাগবে।

প্র ০২Turing machine-এর function partial কেন রাখতে হয়? সব machine-কে “total” করে নিলে ক্ষতি কী?

প্রথম চিন্তায় মনে হয়, যে machine কিছু ইনপুটে থামে না, সেটি ত্রুটিপূর্ণ; শুধু সব ইনপুটে থামে এমন machine নিয়ে তত্ত্ব গড়লেই তো পরিষ্কার হয়। সমস্যাটি হলো, “সব ইনপুটে থামে” এমন machine-গুলোকে কোনো যান্ত্রিক উপায়ে চেনা যায় না, আর তাদের একটি সম্পূর্ণ, কার্যকর তালিকাও বানানো যায় না।

যুক্তিটি diagonal-এর। ধরুন f0, f1, f2, … সব total computable function-এর একটি তালিকা, এবং একটি program i দিলে fi(n) হিসাব করা যায়। তাহলে g(n) = fn(n) + 1 একটি total এবং computable function, কিন্তু g তালিকার কোনো fi-এর সমান নয়, কারণ i-তে মান আলাদা। অর্থাৎ total function-এর জগতে থেকে একটি “সম্পূর্ণ” programming মডেল পাওয়া যায় না। Partial function মেনে নিলে এই বাধা ওঠে: তালিকায় সব program থাকে, আর g-এর যুক্তি আটকে যায়, কারণ fn(n) অসংজ্ঞায়িত হতে পারে।

ইতিহাসেও এভাবেই এসেছে। Stephen Kleene ১৯৩০-এর দশকের শেষে partial recursive function-এর ধারণা স্পষ্ট করেন; তার আগে recursive function মূলত total ধরা হতো। পরে এটিই আদর্শ হয়ে দাঁড়ায়: একটি Turing machine একটি partial function গণনা করে, যার domain হলো যেসব ইনপুটে machine থামে।

বাস্তব programming-এও এটি পরিচিত। Python-এ একটি while True loop লেখা যায়, আর ভাষাটি তা আটকায় না। কিছু ভাষা (যেমন proof assistant-এ ব্যবহৃত কিছু “total” ভাষা) ইচ্ছা করে শুধু সব ইনপুটে থামে এমন program লিখতে দেয়; তার দাম হলো, কিছু বৈধ program সেই ভাষায় লেখা যায় না বা ঘুরিয়ে লিখতে হয়। “এই program কি সব ইনপুটে থামবে?” প্রশ্নটি সাধারণভাবে অমীমাংসেয়, যা পর্ব ৫১ থেকে ৫৩-এ দেখবেন।

মূল উপলব্ধি: Partial function কোনো দুর্বলতা নয়, সম্পূর্ণতার মূল্য। যে মডেল সব গণনা ধরতে চায়, তাকে “না থামা”-কেও জায়গা দিতে হয়; decider আর recognizer-এর পার্থক্য এখান থেকেই আসে।

প্র ০৩Set-builder notation-এ সবসময় {w ∈ Σ∗ : …} লেখা হয়, শুধু {w : …} নয়। এই সামান্য অভ্যাসের পেছনে কোন ঐতিহাসিক সংকট আছে?

উনিশ শতকের শেষে Gottlob Frege গণিতকে যুক্তিবিদ্যার ওপর দাঁড় করানোর চেষ্টা করছিলেন। তাঁর ব্যবস্থায় একটি মৌলিক নীতি ছিল: যেকোনো শর্ত P দিলে {x : P(x)} একটি set. ১৯০১ সালে Bertrand Russell লক্ষ করেন, শর্তটি যদি হয় “x নিজের সদস্য নয়”, তবে R = {x : x ∉ x} নিয়ে প্রশ্ন ওঠে: R কি নিজের সদস্য? হলে, সংজ্ঞায় হওয়ার কথা নয়; না হলে, সংজ্ঞায় হওয়ার কথা। ১৯০২ সালে Russell চিঠিতে Frege-কে এটি জানান, আর Frege তাঁর বইয়ের দ্বিতীয় খণ্ডের পরিশিষ্টে স্বীকার করেন যে ভিত্তিটি নড়ে গেছে।

সমাধানের একটি প্রধান পথ হলো Zermelo-র স্বতঃসিদ্ধ (পরে Zermelo–Fraenkel, ZF): শর্ত দিয়ে নতুন set বানানো যাবে শুধু একটি আগে থেকে থাকা set থেকে বাছাই করে, {x ∈ U : P(x)}। এই সীমার মধ্যে Russell-এর যুক্তি আর স্ববিরোধ তৈরি করে না; সেটি শুধু দেখায় যে “সব set-এর set” বলে কিছু নেই।

লক্ষ করুন, Russell-এর R আর Cantor-এর D = {a ∈ A : a ∉ f(a)} হুবহু একই ছাঁচ: “যে নিজের ভেতরে নেই”। Cantor-এর ক্ষেত্রে বাছাই হয় একটি নির্দিষ্ট set A থেকে, তাই স্ববিরোধ হয় না; বরং f-এর অস্তিত্ব নিয়ে আমাদের অনুমানটি ভুল প্রমাণিত হয়। Halting problem-এর প্রমাণেও (পর্ব ৫১) একই আত্ম-উল্লেখের ছাঁচ, সেখানে ভুল প্রমাণিত হয় “একটি halting decider আছে” অনুমানটি।

গণনার তত্ত্বে আমরা প্রায় সবসময় Σ∗, ℕ বা একটি machine-এর Q-এর মতো সুনির্দিষ্ট set থেকে বাছাই করি, তাই এই সংকট সরাসরি আসে না। তবু {w ∈ Σ∗ : …} লেখার অভ্যাস দুটি উপকার দেয়: alphabet কোনটি তা স্পষ্ট থাকে (একই শর্ত {0, 1} আর {0, 1, 2}-এ ভিন্ন language দেয়), আর complement-এর মানে নির্দিষ্ট হয়: L-এর complement মানে Σ∗ − L.

মূল উপলব্ধি: notation-এর ছোট নিয়ম অনেক সময় বড় দুর্ঘটনার স্মৃতি বহন করে। আর আত্ম-উল্লেখ (“যে নিজের সম্পর্কে X নয়”) গণিতে স্ববিরোধও তৈরি করে, শক্তিশালী অসম্ভবতার প্রমাণও।

প্র ০৪Equivalence relation কীভাবে একটি language-এর “ন্যূনতম স্মৃতি” মাপে? Myhill–Nerode-এর ধারণা এখানে কী যোগ করে?

একটি language L ⊆ Σ∗ নিন। দুটি string x আর y-কে “L-এর চোখে সমান” বলুন, যদি সব z ∈ Σ∗-এর জন্য xz ∈ L ⇔ yz ∈ L হয়; অর্থাৎ ভবিষ্যতে যা-ই পড়া হোক, x আর y একই সিদ্ধান্তে পৌঁছায়। এটি একটি equivalence relation (তিনটি ধর্মই “⇔”-এর ধর্ম থেকে আসে)। এর class-গুলো বলে, string পড়ার মাঝপথে একটি machine-কে ন্যূনতম কতগুলো আলাদা অবস্থা মনে রাখতে হবে।

John Myhill (১৯৫৭) আর Anil Nerode (১৯৫৮) স্বাধীনভাবে যে ফল পান, তার সারকথা: L regular ঠিক তখন, যখন এই relation-এর class সসীম সংখ্যক, আর তখন class-এর সংখ্যাই L-এর ক্ষুদ্রতম DFA-র state সংখ্যা। “জোড় সংখ্যক 1” language-এ class দুটি, এই পর্বের stepper-এর A আর B, তাই ২ state-এর DFA-ই সবচেয়ে ছোট। অন্যদিকে {0n1n}-এ 0, 00, 000, … সবাই ভিন্ন class-এ পড়ে (0i-এর পরে 1i জুড়লে গৃহীত, 0j-এর পরে নয়), তাই অসীম class, এবং language-টি regular নয়।

এর ব্যবহারিক রূপ DFA minimization (পর্ব ১৯): state-গুলোকে “একই রকম আচরণ” অনুযায়ী ভাগ করে প্রতিটি ভাগকে একটি state বানানো। Lexer generator বা regex engine বড় automaton তৈরির পর এমন ভাগ করে মেমরি বাঁচায়, আর এর বিখ্যাত দ্রুত algorithm-টি John Hopcroft ১৯৭১ সালে দেন। ভাগগুলো ক্রমশ সূক্ষ্ম করার এই কৌশলের নাম partition refinement, আর এটি graph isomorphism-এর heuristic থেকে model checking পর্যন্ত নানা জায়গায় ব্যবহৃত হয়।

লক্ষ করুন, এখানে partition-এর তিনটি ধর্মই কাজে লাগে: প্রতিটি string একটি class-এ (একটি state), কোনো string দুটি class-এ নয় (DFA deterministic), আর সব class মিলে পুরো Σ∗। এই পর্বের relation-এর সংজ্ঞাটি মুখস্থ বিদ্যা নয়, machine নকশার মূল ভাষা।

মূল উপলব্ধি: “কোন string-গুলো ভবিষ্যতের জন্য একই রকম” প্রশ্নটি একটি equivalence relation, আর তার class-এর সংখ্যাই একটি সমস্যার জন্য দরকারি সসীম স্মৃতির মাপ। সসীম হলে finite automaton যথেষ্ট, অসীম হলে নয়।

প্র ০৫Big-O ধ্রুবক উপেক্ষা করে। তাহলে “polynomial time মানে দক্ষ” কথাটি কোথা থেকে এলো, আর এর সীমা কী?

১৯৬৫ সালে দুটি প্রবন্ধ প্রায় একই সময়ে একটি ধারণা সামনে আনে। Alan Cobham যুক্তি দেন যে “কার্যকরভাবে গণনাযোগ্য” function-এর একটি স্বাভাবিক শ্রেণি হলো যেগুলো ইনপুটের দৈর্ঘ্যের polynomial সময়ে হিসাব করা যায়, আর শ্রেণিটি machine মডেল বদলালেও (একটি tape না অনেক tape) বদলায় না। Jack Edmonds matching নিয়ে তাঁর প্রবন্ধে একই রকম যুক্তি দেন যে polynomial সময়ের algorithm আর সূচকীয় খোঁজের মধ্যে একটি গুণগত পার্থক্য আছে। এই ধারণাকে অনেকে Cobham–Edmonds thesis বলেন, আর এটিই পর্ব ৫৭-এর class P-এর ভিত্তি।

যুক্তিটির শক্তি তিন জায়গায়। প্রথমত, polynomial-গুলোর যোগ, গুণ আর composition আবার polynomial, তাই polynomial সময়ের অংশ জুড়ে বড় algorithm বানালেও শ্রেণির বাইরে যাওয়া হয় না। দ্বিতীয়ত, যুক্তিসংগত machine মডেলগুলো একে অন্যকে polynomial overhead-এ simulate করে, তাই শ্রেণিটি নির্দিষ্ট কম্পিউটারের ওপর নির্ভর করে না। তৃতীয়ত, এই পর্বের টেবিলের মতো, n2 আর 2n-এর পার্থক্য n বাড়লে এত বিশাল যে ধ্রুবক দিয়ে তা পূরণ হয় না।

সীমাও স্পষ্ট। n100 সময়ের algorithm তাত্ত্বিকভাবে polynomial, কিন্তু ব্যবহারে অচল। উল্টো দিকে, simplex পদ্ধতির worst case সূচকীয় হতে পারে (Klee আর Minty ১৯৭২ সালে উদাহরণ দেন), তবু বাস্তবের বেশিরভাগ ইনপুটে এটি খুব দ্রুত। SAT solver-গুলো (পর্ব ৭৩) worst case-এ সূচকীয় হলেও বিশাল বাস্তব সমস্যা সমাধান করে। আর Big-O ধ্রুবক লুকায়, তাই ছোট n-এ “ধীর” algorithm-ও জিততে পারে।

আরেকটি সূক্ষ্মতা ইনপুটের দৈর্ঘ্য: একটি সংখ্যা N binary-তে প্রায় log2 N বিট, তাই 1 থেকে N পর্যন্ত লুপ চালানো আসলে দৈর্ঘ্যের সূচকীয় সময়। পর্ব ০৫-এ encoding-এর আলোচনায় এই pseudo-polynomial ফাঁদটি দেখবেন।

মূল উপলব্ধি: “Polynomial = দক্ষ” একটি দরকারি গাণিতিক আদর্শ, প্রাকৃতিক নিয়ম নয়। তত্ত্বে এটি পরিষ্কার শ্রেণি দেয়; বাস্তবে ধ্রুবক, ঘাত আর বাস্তব ইনপুটও দেখতে হয়।

অনুশীলন

খাতা-কলমে সমাধান করুন, তারপর উত্তর মেলান। হিসাবগুলো উপরের Python ব্লক বদলে নিজে যাচাই করতে পারেন।

  1. Equivalence class থেকে machine নকশা: {0, 1}∗-এ x ~ y যদি #1(x) ≡ #1(y) (mod 3). (ক) class কয়টি, প্রতিটির দুটি সদস্য দিন। (খ) class-গুলোকে state ধরে “1-এর সংখ্যা ৩ দিয়ে বিভাজ্য” language-এর একটি DFA-র পূর্ণ ৫-tuple লিখুন।

    (ক) তিনটি class: C0 (1-এর সংখ্যা ≡ 0), যেমন ε, 111; C1 (≡ 1), যেমন 1, 010; C2 (≡ 2), যেমন 11, 0101.

    (খ) M = (Q, Σ, δ, q0, F), যেখানে Q = {C0, C1, C2}, Σ = {0, 1}, δ(Ci, 0) = Ci, δ(Ci, 1) = C(i+1) mod 3, q0 = C0 (কারণ ε ∈ C0), F = {C0}। δ total, প্রতিটি জোড়ায় ঠিক একটি মান। সঠিকতা: “পড়া অংশের class = বর্তমান state”, |w|-এর ওপর induction. যাচাই: দৈর্ঘ্য ০ থেকে ১০-এর সব ২০৪৭টি string-এ এই DFA-র সিদ্ধান্ত আর “1-এর সংখ্যা mod 3 = 0” scratch script-এ হুবহু মিলেছে।

  2. ভুল প্রমাণটি ধরুন: “দাবি: {0, 1}∗ uncountable. প্রমাণ: ধরি w0, w1, w2, … সব string-এর একটি তালিকা। নতুন string x বানাই, যার i-তম চিহ্ন wi-এর i-তম চিহ্নের উল্টো। তাহলে x কোনো wi-এর সমান নয়, তাই তালিকাটি অসম্পূর্ণ। ∎” ভুলটি কোথায়?

    দুটি ভুল। প্রথম ও প্রধান: x-এর প্রতিটি i-এর জন্য একটি চিহ্ন আছে, তাই x একটি অসীম sequence, string নয়; string সবসময় সসীম। তাই x ∉ {0, 1}∗, আর “তালিকায় x নেই” কোনো স্ববিরোধ নয়। দ্বিতীয়: wi-এর দৈর্ঘ্য i-এর চেয়ে কম হতে পারে (যেমন w0 = ε-এর কোনো ০-তম চিহ্নই নেই), তাই নির্মাণটি সংজ্ঞায়িতই নয়। একই যুক্তি অসীম binary sequence-এর set-এর জন্য সঠিক, আর তা দেখায় সেই set uncountable; উপপাদ্য ৬.১ অনুযায়ী {0, 1}∗ countable.

  3. হিসাব করুন: {0, 1}∗-এর shortlex তালিকায় (ক) 1011-এর অবস্থান, (খ) অবস্থান 10-এর string, (গ) {a, b, c}∗-এ (a < b < c) ba আর cab-এর অবস্থান কত? (অবস্থান 0 থেকে শুরু।)

    (ক) val(11011) − 1 = 27 − 1 = 26. পরীক্ষা: দৈর্ঘ্য ৪-এর block শুরু 15-তে, আর 1011 সেই block-এর 11-তম (0 থেকে), 15 + 11 = 26.

    (খ) 10 + 1 = 11 = binary 1011, সামনের 1 বাদ দিলে 011. পরীক্ষা: দৈর্ঘ্য ৩-এর block 7-এ শুরু: 000 = 7, 001 = 8, 010 = 9, 011 = 10.

    (গ) d(a) = 1, d(b) = 2, d(c) = 3, k = 3. rank(ba) = 2 · 3 + 1 = 7; rank(cab) = 3 · 9 + 1 · 3 + 2 = 32. দুটিই shortlex.py ব্লকের মতো একটি গণনায় মিলিয়ে দেখা হয়েছে।

  4. Relation-এর ধর্ম আর closure: A = {p, q, r, s}-এ “এক ধাপে” relation R = {(p, q), (q, r), (s, s)}। (ক) R কি reflexive, symmetric বা transitive? (খ) R∗ (reflexive-transitive closure)-এর সব জোড়া লিখুন। (গ) p R∗ s কি সত্য?

    (ক) Reflexive নয় ((p, p) নেই), symmetric নয় ((p, q) আছে, (q, p) নেই), transitive নয় ((p, q) আর (q, r) আছে, কিন্তু (p, r) নেই)।

    (খ) শূন্য ধাপ: (p, p), (q, q), (r, r), (s, s). এক ধাপ: (p, q), (q, r), (s, s). দুই ধাপ: (p, r). আর কিছু নতুন আসে না। তাই R∗ = {(p, p), (q, q), (r, r), (s, s), (p, q), (q, r), (p, r)}, মোট ৭টি জোড়া।

    (গ) না। p থেকে তীর ধরে শুধু q আর r-এ পৌঁছানো যায়; s-এ ঢোকার একমাত্র তীর s থেকেই। Machine-এর ভাষায়: configuration p থেকে কখনো s-এ পৌঁছানো যাবে না।

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

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

ক্রমCantor-এর উপপাদ্যের (কোনো f : A → P(A) surjection নয়) প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. ধরি f : A → P(A) একটি surjection
  2. D = {a ∈ A : a ∉ f(a)} সংজ্ঞায়িত করি; D ⊆ A
  3. Surjection বলে কোনো d-তে f(d) = D
  4. d ∈ D আর d ∉ D, দুটি case-ই স্ববিরোধে পৌঁছায়
  5. অতএব surjection নেই; a ↦ {a} injection বলে |A| < |P(A)|

একটি NFA-র state-এর set Q-তে ৪টি state. Subset construction-এ তৈরি DFA-র state সর্বোচ্চ কয়টি হতে পারে?

  • 4
  • 16
  • 8
  • 24

Σ = {0, 1} হলে নিচের কোন set uncountable?

  • Σ∗, সব সসীম binary string
  • সব DFA-র set
  • P(Σ∗), Σ-এর ওপর সব language
  • ℕ × ℕ

{0, 1}∗-কে ℕ-এর সঙ্গে মেলাতে শুধু অভিধান ক্রম (lexicographic order) কেন যথেষ্ট নয়?

  • “1”-এর আগে অসীম সংখ্যক string আসে, তাই “1” কোনো সসীম নম্বর পায় না
  • অভিধান ক্রমে একই string দুবার আসে
  • অভিধান ক্রমে দুটি string তুলনা করা যায় না
  • কারণ {0, 1}∗ আসলে uncountable

{0, 1}∗-এর ওপর নিচের কোন relation একটি equivalence relation?

  • x, y-এর prefix
  • |x| = |y|
  • |x| < |y|
  • x আর y অন্তত একটি চিহ্ন ভাগ করে

একটি Turing machine কিছু ইনপুটে থামে না। সে যে function গণনা করে, তার সবচেয়ে সঠিক বর্ণনা কোনটি?

  • একটি total function
  • একটি bijection
  • একটি total function, যা না থামা ইনপুটে 0 দেয়
  • একটি partial function, যার domain হলো যেসব ইনপুটে machine থামে

একটি DFA-র state diagram-এ শুরুর state থেকে কোনো accept state-এ কোনো directed path নেই। এর ভাষা L(M) কী?

  • {ε}
  • Σ∗
  • ∅
  • আরও তথ্য ছাড়া বলা যায় না

শব্দকোষ

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

মনে রাখুন

  1. Machine-এর সংজ্ঞা set আর function দিয়ে: F ⊆ Q, δ : Q × Σ → Q; NFA-তে মান P(Q)-তে, তাই subset construction-এ সর্বোচ্চ 2n state.
  2. ∅ ≠ {ε} ≠ {∅}; |P(∅)| = 1.
  3. Equivalence relation = reflexive + symmetric + transitive; তার class-গুলো একটি partition, আর পরে এগুলোই DFA-র state. R∗ মানে “শূন্য বা বেশি ধাপ”।
  4. TM-এর function partial; DFA-র δ total. Emptiness মানে শুরু থেকে accept state-এ reachability নেই।
  5. Σ∗ countable (shortlex, rank(w) = val(1w) − 1); P(Σ∗) uncountable (Cantor); machine countable, তাই কিছু language কোনো machine চেনে না।

পরের পর্বে: এই পর্বে Σ∗ আর language-কে set হিসেবে ব্যবহার করলাম। পর্ব ০৩-এ string আর language-এর নিজস্ব বীজগণিত: concatenation, reversal, Kleene star, আর কোন identity সত্য, কোনটি মনে হলেও মিথ্যা।

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

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