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

Decidable আর Turing-recognizable language

Decidable and Turing-Recognizable Languages — Deciders, Recognizers, Co-Recognizers, Decidable Questions about Automata and Grammars, Dovetailing and Closure Properties

Taught in Bangla, this lesson separates deciders, which always halt, from recognizers, which may loop, and defines co-recognizable languages. It builds deciders for A_DFA, E_DFA, EQ_DFA, A_CFG and E_CFG, showing every context-free language is decidable, and shows A_TM is recognizable through the universal machine. It proves L is decidable exactly when L and its complement are both recognizable using dovetailing, and maps closure properties of both classes, with in-page Python (Pyodide) deciders.

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

  • Decidable, Turing-recognizable আর co-recognizable language-এর নিখুঁত সংজ্ঞা আর তাদের অন্য নাম
  • DFA আর CFG নিয়ে পাঁচটি প্রশ্নের decider লেখা ও প্রমাণ, আর কেন প্রতিটি CFL decidable
  • ATM কেন recognizable, আর অসীম সংখ্যক কাজ পালা করে চালানোর কৌশল dovetailing
  • L decidable ⇔ L আর L̄ দুটিই recognizable, এই উপপাদ্যের পূর্ণ প্রমাণ ও Python-এ যাচাই
  • Closure property আর language-শ্রেণির মানচিত্র: কোন language কোথায় বসে

১ · তিন রকম উত্তরদাতা — decider, recognizer আর co-recognizer

পর্ব ৪৩-এ দেখেছেন, একটি Turing machine একটি input-এ তিনটি কাজের একটি করে: গ্রহণ করে থামে, বর্জন করে থামে, অথবা চিরকাল চলে (loop). পর্ব ০৫-এ এর ভিত্তিতে decider আর recognizer-এর প্রাথমিক সংজ্ঞা এসেছিল। এই মডিউলের বিষয় computability: কোন সমস্যা কোনো algorithm দিয়ে আদৌ সমাধান করা যায়। তার প্রথম ধাপ হিসেবে সংজ্ঞাগুলো এখানে নিখুঁত করা হলো, আর প্রথম বড় উপপাদ্যগুলো প্রমাণ করা হলো।

বাজারঘরের হেল্পডেস্কে একজন গ্রাহক জানতে চাইলেন, তাঁর হারানো পার্সেলটি কোনো গুদামে আছে কি না। প্রথম কর্মী গুদামের পর গুদাম খোঁজেন। পার্সেল পেলেই “হ্যাঁ” বলেন। কিন্তু গুদামের তালিকা যদি শেষ না হয়, “নেই” বলার মুহূর্ত তাঁর কখনো আসে না: পরের গুদামেই হয়তো আছে। ইনি একজন recognizer. দ্বিতীয় কর্মী খোঁজেন বাতিলের রসিদ; রসিদ পেলেই নিশ্চিত “না”। ইনি পার্সেলের প্রশ্নের জন্য একজন co-recognizer. দুজনকে পালা করে এক মিনিট করে খুঁজতে দিলে, দুজনের একজন একসময় সফল হবেনই। তখন হেল্পডেস্ক প্রতিটি প্রশ্নের নিশ্চিত উত্তর দেয়: সেটি একটি decider. এই পর্বের মূল উপপাদ্য ঠিক এই ছবি।

নিচের সংজ্ঞায় M একটি সাধারণ (deterministic) Turing machine, Σ তার input alphabet, আর L ⊆ Σ∗. পর্ব ৪৬-এ দেখেছেন, nondeterministic যন্ত্র নিলেও শ্রেণিগুলো বদলায় না।

সংজ্ঞা ১.১ (Decider আর decidable language)

M একটি decider, যদি প্রতিটি input-এ M থামে। M language L-কে decide করে, যদি M decider আর L(M) = L, অর্থাৎ w ∈ L হলে M গ্রহণ করে আর w ∉ L হলে বর্জন করে। কোনো decider L-কে decide করলে L একটি decidable language.

সংজ্ঞা ১.২ (Recognizer আর Turing-recognizable language)

M language L-কে recognize করে, যদি L(M) = L: w ∈ L হলে M একসময় গ্রহণ করে থামে; w ∉ L হলে M বর্জন করে বা চিরকাল চলে, কিন্তু কখনো গ্রহণ করে না। কোনো TM L-কে recognize করলে L একটি Turing-recognizable language.

সংজ্ঞা ১.৩ (Co-recognizable)

L co-Turing-recognizable (সংক্ষেপে co-recognizable), যদি তার complement L̄ = Σ∗ \ L Turing-recognizable হয়। অর্থাৎ এমন একটি যন্ত্র আছে, যা L-এর বাইরের প্রতিটি string-এ একসময় “না, এটি L-এ নেই” নিশ্চিত করে।

সংজ্ঞা থেকেই একটি দিক স্পষ্ট: প্রতিটি decider একটি recognizer-ও, তাই প্রতিটি decidable language recognizable. উল্টোটি সত্য নয়, আর সেটিই পরের পর্বের বিষয়। বইভেদে নামগুলো আলাদা, তাই পরীক্ষায় বা গবেষণাপত্রে যেকোনোটি দেখতে পারেন:

এই কোর্সেঅন্য নামযন্ত্রের আচরণ
Decidablerecursive, computable, solvableসব input-এ থামে
Turing-recognizablerecursively enumerable (r.e.), semi-decidable, computably enumerable (c.e.)সদস্যে থামে আর গ্রহণ করে
Co-recognizableco-r.e., co-c.e.অ-সদস্যে “না” নিশ্চিত করা যায়

বর্ণনার স্তর। পর্ব ৪৩-এর তিন স্তরের বর্ণনার মধ্যে এখন থেকে প্রায় সব যন্ত্র high-level ভাষায় লেখা হবে, যেমন “input ⟨B, w⟩ পেলে: B-কে w-এর ওপর চালান …”। এখানে ⟨B, w⟩ মানে B আর w-এর encoding, একটি string. দুটি রীতি মনে রাখুন। এক, প্রতিটি যন্ত্র প্রথমে দেখে নেয় input সত্যিই একটি বৈধ encoding কি না; না হলে বর্জন করে। এটি একটি সরল পরীক্ষা, তাই সাধারণত লেখা হয় না। দুই, এমন বর্ণনা যে একটি সত্যিকারের TM-এ রূপান্তর করা যায়, তার ভরসা Church–Turing thesis (পর্ব ৪৭) আর আগের মডিউলের নকশার অভিজ্ঞতা।

২ · Regular language-এর প্রশ্ন — ADFA, EDFA আর EQDFA

প্রথম decidable language-গুলো আপনার পরিচিত প্রশ্ন, এবার Turing machine-এর ভাষায়। পর্ব ২০-এ এই প্রশ্নগুলোর algorithm আর খরচ বিস্তারিত দেখেছেন; এখানে লক্ষ্য একটাই: প্রতিটি একটি decider দিয়ে সমাধান হয়, আর কেন সেই যন্ত্র সবসময় থামে।

ADFA = {⟨B, w⟩ : B একটি DFA আর B w-কে গ্রহণ করে}

উপপাদ্য ২.১ (ADFA decidable)

M = “input ⟨B, w⟩ পেলে: ১. B-কে w-এর ওপর চালান। ২. শেষে B একটি accept state-এ থাকলে গ্রহণ করুন, নইলে বর্জন করুন।”

প্রমাণ:

  1. Tape-এ M B-এর বর্তমান state আর w-এর বর্তমান অবস্থান চিহ্ন দিয়ে রাখে; প্রতিটি ধাপে δ-এর সারণি থেকে পরের state খুঁজে নেয়। — simulation
  2. B প্রতিটি চিহ্নে ঠিক একটি ধাপ নেয়, তাই simulation ঠিক |w| ধাপ পরে শেষ হয়; M প্রতিটি input-এ থামে। — DFA-র সংজ্ঞা
  3. M গ্রহণ করে ঠিক তখন, যখন B-এর শেষ state accept state, অর্থাৎ w ∈ L(B). তাই M ADFA-কে decide করে। ∎

একই কৌশলে ANFA আর AREX-ও decidable: আগে NFA-কে পর্ব ১০-এর subset construction দিয়ে, বা regex-কে পর্ব ১৪-এর Thompson construction দিয়ে DFA-তে নিন, তারপর M চালান। একটি decider আরেকটিকে subroutine হিসেবে ব্যবহার করছে: এটি reduction-এর প্রথম রূপ, যা পর্ব ৫২-এ নিখুঁত হবে।

উপপাদ্য ২.২ (EDFA = {⟨A⟩ : A একটি DFA আর L(A) = ∅} decidable)

T = “input ⟨A⟩ পেলে: ১. A-এর start state চিহ্নিত করুন। ২. নতুন কোনো state চিহ্নিত না হওয়া পর্যন্ত: একটি চিহ্নিত state থেকে তীর আসে এমন প্রতিটি state চিহ্নিত করুন। ৩. কোনো accept state চিহ্নিত না হলে গ্রহণ করুন, নইলে বর্জন করুন।”

প্রমাণ: প্রতিটি পুনরাবৃত্তি অন্তত একটি নতুন state চিহ্নিত করে, নইলে থামে; state সসীম (|Q|-টি), তাই ধাপ ২ বড়জোর |Q| বার চলে, আর T থামে। চিহ্নিত state ঠিক সেগুলো, যেগুলোতে start থেকে পৌঁছানো যায় (reachability, যা গ্রাফের BFS-এর মতো)। L(A) ≠ ∅ ⇔ কোনো string A-কে একটি accept state-এ নেয় ⇔ কোনো accept state reachable. তাই T ঠিক তখনই গ্রহণ করে, যখন L(A) = ∅. ∎

উপপাদ্য ২.৩ (EQDFA = {⟨A, B⟩ : A, B DFA আর L(A) = L(B)} decidable)

F = “input ⟨A, B⟩ পেলে: ১. symmetric difference L(C) = (L(A) ∩ L̄(B)) ∪ (L̄(A) ∩ L(B))-এর DFA C বানান। ২. T-কে ⟨C⟩-এর ওপর চালান। ৩. T গ্রহণ করলে গ্রহণ, নইলে বর্জন।”

প্রমাণ: Regular language complement, intersection আর union-এ বদ্ধ, আর পর্ব ০৮-এর product construction C-কে সসীম সময়ে বানায়; তাই ধাপ ১ থামে, আর T decider বলে ধাপ ২-ও থামে। L(C) = ∅ ঠিক তখন, যখন এমন কোনো string নেই যা দুটির একটিতে আছে আর অন্যটিতে নেই, অর্থাৎ L(A) = L(B). ∎

নিচের Python ব্লকে তিনটি decider একটি ছোট string encoding-এর ওপর চলে। DFA লেখা হয়েছে "Q|Σ|q0|F|δ" রূপে: যেমন "ab|01|a|a|a0a a1b b0b b1a" মানে state a ও b, alphabet {0, 1}, start a, accept {a}, আর δ(a, 0) = a, δ(a, 1) = b, …। এটি বাজারঘরের সেন্সর-লাইনের “জোড় সংখ্যক 1” parity check. dfa() function আগে encoding যাচাই করে: অসম্পূর্ণ δ বা ভুল আকার পেলে None, আর তখন প্রতিটি decider বর্জন করে। EQDFA এখানে নতুন C না বানিয়ে product-এর reachable জোড়াগুলোতেই দেখে, কোনো জোড়ায় একটি accept আর অন্যটি নয় কি না; এটি একই প্রমাণ। শেষে দৈর্ঘ্য ১০ পর্যন্ত সব string-এ brute force দিয়ে ফল মেলানো হয়েছে।

def dfa(code):                  # "Q|Σ|q0|F|δ-triples" -> tuple, or None if malformed
    p = code.split("|")
    if len(p) != 5: return None
    Q, S, q0, F, D = p; T = D.split(); d = {(t[0], t[1]): t[2] for t in T if len(t) == 3}
    ok = len(T) == len(d) and set(d) == {(q, a) for q in Q for a in S}
    return (Q, S, q0, F, d) if ok and set(q0 + F + "".join(d.values())) <= set(Q) else None
def A_DFA(code, w):             # decider: run M on w for |w| steps
    M = dfa(code)
    if M is None or not set(w) <= set(M[1]): return False
    q = M[2]
    for a in w: q = M[4][q, a]
    return q in M[3]
def reach(d, S, start):         # marking: all states reachable from start
    marked = new = {start}
    while new:
        new = {d[q, a] for q in new for a in S} - marked; marked = marked | new
    return marked
def E_DFA(code):                # decider: no accept state got marked
    M = dfa(code)
    return M is not None and not reach(M[4], M[1], M[2]) & set(M[3])
def EQ_DFA(c1, c2):             # product: is the symmetric difference empty?
    A, B = dfa(c1), dfa(c2)
    if A is None or B is None or A[1] != B[1]: return False
    d = {((p, q), a): (A[4][p, a], B[4][q, a]) for p in A[0] for q in B[0] for a in A[1]}
    return all((p in A[3]) == (q in B[3]) for p, q in reach(d, A[1], (A[2], B[2])))
D1 = "ab|01|a|a|a0a a1b b0b b1a"                       # even number of 1s
D2 = "acbd|01|a|ac|a0c a1b c0a c1d b0d b1a d0b d1c"     # 4 states, same idea
D3 = "ab|01|a|a|a0b a1a b0a b1b"                       # even number of 0s
D4 = "abc|01|a|c|a0a a1b b0b b1a c0c c1c"              # c is unreachable
print("A_DFA:", A_DFA(D1, "0110"), A_DFA(D1, "0111"), A_DFA("ab|01|a|a|a0a", "0"))
print("E_DFA:", E_DFA(D1), E_DFA(D4), E_DFA("ab|01|a|a|a0a a1b b0b"))
W = [format(i, "b")[1:] for i in range(1, 2048)]     # all 2047 strings, length 0..10
for x, y in [(D1, D2), (D1, D3), (D1, D4)]:
    print("EQ_DFA:", EQ_DFA(x, y), "| brute force, first difference:", [w for w in W if A_DFA(x, w) != A_DFA(y, w)][:1])

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

A_DFA: True False False
E_DFA: False True False
EQ_DFA: True | brute force, first difference: []
EQ_DFA: False | brute force, first difference: ['0']
EQ_DFA: False | brute force, first difference: ['']

0110-এ দুটি 1, তাই গৃহীত; 0111-এ তিনটি, বর্জিত। অসম্পূর্ণ encoding "ab|01|a|a|a0a" কোনো DFA নয়, তাই ⟨B, w⟩ ∉ ADFA, বর্জন। EDFA: D1 ε গ্রহণ করে, তাই খালি নয়; D4-এর একমাত্র accept state c-তে কোনো তীর পৌঁছায় না, তাই L(D4) = ∅. শেষ তিন লাইনে decider-এর রায় আর brute force একমত: D2-এর চারটি state থাকলেও language একই; D3 (জোড় সংখ্যক 0) প্রথম আলাদা হয় string 0-তে, আর D4 আলাদা হয় ফাঁকা string ε-তে (ছাপায় ''). একটি সূক্ষ্মতা খেয়াল করুন: brute force শুধু দৈর্ঘ্য ১০ পর্যন্ত দেখেছে, তাই প্রথম লাইনের “[]” নিজে সমতার প্রমাণ নয়; প্রমাণ হলো EQDFA-এর True, যা সব দৈর্ঘ্যের জন্য খাটে।

৩ · Grammar-এর প্রশ্ন — ACFG, ECFG আর প্রতিটি CFL decidable

এবার context-free grammar G = (V, Σ, R, S). প্রথম প্রশ্ন membership: ACFG = {⟨G, w⟩ : G একটি CFG আর w ∈ L(G)}. সরল একটি ধারণা হলো “G-এর সব derivation একটি একটি করে চেষ্টা করুন, w এলে গ্রহণ”। কিন্তু derivation অসীম সংখ্যক, আর w ∉ L(G) হলে এই খোঁজ কখনো থামে না: এটি বড়জোর একটি recognizer. Decider বানাতে খোঁজকে সসীম করতে হয়।

উপপাদ্য ৩.১ (ACFG decidable)

SCFG = “input ⟨G, w⟩ পেলে: ১. G-কে পর্ব ২৯-এর Chomsky normal form-এ রূপান্তর করুন। ২. n = |w|; n = 0 হলে দেখুন S0 → ε নিয়মটি আছে কি না। ৩. n ≥ 1 হলে ঠিক 2n − 1 ধাপের সব derivation তালিকা করুন। ৪. কোনোটি w দিলে গ্রহণ, নইলে বর্জন।”

প্রমাণ:

  1. CNF-এ প্রতিটি নিয়ম A → BC বা A → a. দৈর্ঘ্য n ≥ 1-এর একটি string-এর যেকোনো derivation-এ A → BC ধরনের নিয়ম ঠিক n − 1 বার আর A → a ধরনের ঠিক n বার খাটে, মোট 2n − 1 ধাপ। — প্রতিটি A → BC variable-এর সংখ্যা এক বাড়ায়, প্রতিটি A → a একটি variable-কে terminal করে
  2. প্রতিটি ধাপে সসীম সংখ্যক নিয়ম আর সসীম সংখ্যক জায়গা, তাই 2n − 1 ধাপের derivation সসীম সংখ্যক; ধাপ ৩ থামে। — R সসীম
  3. w ∈ L(G) ⇔ CNF grammar-এ w-এর একটি derivation আছে ⇔ ধাপ ৩-এর তালিকায় তা আছে। তাই যন্ত্রটি decider আর ACFG-কে decide করে। ∎

এই decider সময়ের হিসাবে খুব খারাপ (তালিকা সূচকীয় হারে বড়)। পর্ব ৩১-এর CYK algorithm একই প্রশ্নের উত্তর দেয় n3-এর অনুপাতে সময়ে, যা দেখায় ACFG শ্রেণি P-তে আছে (পর্ব ৫৭)। Computability-র প্রশ্নে অবশ্য দুটির একটিই যথেষ্ট।

উপপাদ্য ৩.২ (ECFG = {⟨G⟩ : G একটি CFG আর L(G) = ∅} decidable)

R = “input ⟨G⟩ পেলে: ১. G-এর সব terminal চিহ্নিত করুন। ২. প্রতিটি round-এ: এমন নিয়ম A → U1U2⋯Uk খুঁজুন, যার প্রতিটি Ui আগেই চিহ্নিত; তাহলে A চিহ্নিত করুন। কোনো round-এ নতুন কিছু চিহ্নিত না হলে থামুন। ৩. Start variable S চিহ্নিত না হলে গ্রহণ করুন, নইলে বর্জন করুন।”

চিহ্নিত variable-গুলো ঠিক generating variable, অর্থাৎ যেগুলো থেকে কোনো terminal string derive করা যায়। পর্ব ২৮-এ useless symbol বাদ দিতে এই চিহ্ন দেওয়ার কৌশলই ব্যবহার হয়েছিল, আর পর্ব ৩৭-এ CFL-এর emptiness প্রশ্নে। নিচের stepper grammar G1-এ R চালায়:

S → AB | CD    A → a    B → bB    C → Da | B    D → AA

1সব terminal চিহ্নিত2A → U1⋯Uk, সব Ui চিহ্নিত ⇒ A চিহ্নিত3নতুন কিছু নেই ⇒ থামা4S চিহ্নিত? বর্জন : গ্রহণ
চিহ্নের অবস্থা
round
নতুন চিহ্ন
সব চিহ্নিত
সাক্ষী string
  1. Round ০. শুধু terminal a আর b চিহ্নিত। কোনো variable এখনো নয়।
  2. Round ১. A → a-এর ডান দিকের সব চিহ্ন চিহ্নিত, তাই A চিহ্নিত। B → bB-তে B নিজে চিহ্নহীন, তাই B নয়। D → AA-র জন্য A-কে আগের round-এ চিহ্নিত থাকতে হতো।
  3. Round ২. এবার A চিহ্নিত, তাই D → AA থেকে D চিহ্নিত। সাক্ষী: D ⇒ AA ⇒∗ aa.
  4. Round ৩. C → Da: D আর a দুটিই চিহ্নিত, তাই C চিহ্নিত। C → B দিয়ে কখনো হতো না, কারণ B চিহ্নহীন।
  5. Round ৪. S → CD: দুটিই চিহ্নিত, S চিহ্নিত। S → AB কাজে আসেনি। সাক্ষী S ⇒ CD ⇒∗ (aaa)(aa) = aaaaa.
  6. Round ৫. নতুন কিছু চিহ্নিত হলো না, R থামে। S চিহ্নিত, তাই L(G1) ≠ ∅ আর R বর্জন করে: ⟨G1⟩ ∉ ECFG. B কখনো চিহ্নিত হয়নি: B → bB থেকে কোনো terminal string আসে না।

প্রমাণ (R decider আর সঠিক):

  1. প্রতিটি round-এ অন্তত একটি নতুন variable চিহ্নিত হয়, নইলে R থামে; variable |V|-টি, তাই বড়জোর |V| + 1 round. — সসীমতা
  2. যদি A চিহ্নিত হয়, তবে A ⇒∗ w কোনো terminal string w-এর জন্য। Round-এর ওপর induction: A → U1⋯Uk-এর প্রতিটি Ui আগের round-এ চিহ্নিত, তাই প্রতিটি থেকে একটি terminal string wi আসে, আর A ⇒∗ w1⋯wk. — induction
  3. উল্টো দিকে, A ⇒∗ w হলে A চিহ্নিত হয়। Derivation-এর parse tree-র উচ্চতার ওপর induction: উচ্চতা h-এর গাছের মূলের নিয়ম A → U1⋯Uk, প্রতিটি Ui-এর উপগাছের উচ্চতা < h, তাই প্রতিটি Ui চিহ্নিত, আর পরের round-এ A. — parse tree-তে induction
  4. অতএব S চিহ্নিত ⇔ L(G) ≠ ∅, আর R ঠিক তখন গ্রহণ করে যখন L(G) = ∅. ∎

Python-এ একই algorithm, প্রতিটি variable-এর একটি সাক্ষী string-সহ। G2-এ শুধু একটি নিয়ম বদলানো: C → Da-র বদলে C → cC. শেষ লাইনে একটি স্বাধীন brute force: grammar থেকে দৈর্ঘ্য ৬ পর্যন্ত সব terminal string সরাসরি derive করে দেখা।

def cfg(code):                  # "S>AB,CD;A>a;..."  upper = variable, start first
    rules = [(lhs, rhs) for part in code.split(";")
             for lhs, alts in [part.split(">")] for rhs in alts.split(",")]
    return rules[0][0], rules
def E_CFG(code, show=True):     # decider: mark generating variables round by round
    start, rules = cfg(code)
    wit = {}                    # variable -> a terminal string it derives
    for rnd in range(1, 100):
        new = {}
        for A, rhs in rules:
            if A not in wit and A not in new and all(c.islower() or c in wit for c in rhs):
                new[A] = "".join(wit.get(c, c) for c in rhs)
        if not new: break
        wit.update(new)
        if show: print(f"  round {rnd}: marked {sorted(new)}  witness {new}")
    unmarked = sorted({A for A, _ in rules} - set(wit))
    if show: print(f"  no change; never marked: {unmarked}")
    return start not in wit, wit.get(start)
G1 = "S>AB,CD;A>a;B>bB;C>Da,B;D>AA"
G2 = "S>AB,CD;A>a;B>bB;C>cC,B;D>AA"
print("G1 empty?", E_CFG(G1))
print("G2 empty?", E_CFG(G2))
def gen(code, n):               # brute force: all terminal strings, length <= n
    start, rules = cfg(code); seen, todo, out = set(), [start], set()
    while todo:
        s = todo.pop(); i = next((k for k, c in enumerate(s) if c.isupper()), -1)
        if i < 0: out.add(s); continue
        for A, rhs in rules:
            t = s[:i] + rhs + s[i + 1:]
            if A == s[i] and sum(c.islower() for c in t) <= n and len(t) <= 2 * n and t not in seen:
                seen.add(t); todo.append(t)
    return sorted(out, key=lambda w: (len(w), w))
print("G1 strings up to length 6:", gen(G1, 6), " G2:", gen(G2, 6))

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

  round 1: marked ['A']  witness {'A': 'a'}
  round 2: marked ['D']  witness {'D': 'aa'}
  round 3: marked ['C']  witness {'C': 'aaa'}
  round 4: marked ['S']  witness {'S': 'aaaaa'}
  no change; never marked: ['B']
G1 empty? (False, 'aaaaa')
  round 1: marked ['A']  witness {'A': 'a'}
  round 2: marked ['D']  witness {'D': 'aa'}
  no change; never marked: ['B', 'C', 'S']
G2 empty? (True, None)
G1 strings up to length 6: ['aaaaa']  G2: []

G1-এর চারটি round stepper-এর round ১–৪-এর সঙ্গে হুবহু মেলে (code terminal-গুলো আলাদা করে চিহ্নিত করে না, ছোট হাতের অক্ষরকে সবসময় চিহ্নিত ধরে)। G2-এ C → cC নিজের ওপর নির্ভরশীল, তাই C কখনো চিহ্নিত হয় না, S-ও না: L(G2) = ∅, ⟨G2⟩ ∈ ECFG. Brute force একই কথা বলে: G1-এর language আসলে একটিমাত্র string, aaaaa, আর G2-এর কিছুই নয়। লক্ষ করুন, brute force দৈর্ঘ্য ৬-এ থেমেছে বলে নিজে “খালি” প্রমাণ করে না; R-এর রায় করে।

উপপাদ্য ৩.৩ (প্রতিটি context-free language decidable)

ধরুন L = L(G), G একটি নির্দিষ্ট CFG. MG = “input w পেলে: উপপাদ্য ৩.১-এর SCFG-কে ⟨G, w⟩-এর ওপর চালান; সে গ্রহণ করলে গ্রহণ, নইলে বর্জন।” SCFG decider, তাই MG-ও। ∎

দুটি সূক্ষ্মতা। এক, G এখানে MG-এর ভেতরে লেখা, input নয়; প্রতিটি CFL-এর জন্য আলাদা একটি decider. দুই, L-এর একটি PDA সরাসরি TM-এ অনুকরণ করে কাজ হয় না: PDA-র কিছু শাখা ε-move নিয়ে stack বাড়াতে বাড়াতে চিরকাল চলতে পারে, তাই সেই simulation decider না-ও হতে পারে। Grammar আর CNF-এর পথ এই ফাঁদ এড়ায়।

সব প্রশ্ন decidable নয়। EQDFA-এর কৌশল CFG-তে খাটে না, কারণ CFL complement আর intersection-এ বদ্ধ নয় (পর্ব ৩৭), তাই symmetric difference-এর grammar বানানো যায় না। আর এটি শুধু কৌশলের অভাব নয়: EQCFG সত্যিই undecidable, যা পর্ব ৫৪-এ প্রমাণ হবে।

প্রশ্নDFACFGTM
Membership, AXdecidable (২.১)decidable (৩.১)recognizable, decidable নয় (৪.১, পর্ব ৫১)
Emptiness, EXdecidable (২.২)decidable (৩.২)co-recognizable, decidable নয় (৪.২, পর্ব ৫২)
Equivalence, EQXdecidable (২.৩)undecidable (পর্ব ৫৪)recognizable বা co-recognizable কোনোটিই নয় (পর্ব ৫২)

৪ · Recognizable language — ATM আর dovetailing

এবার input-এ একটি পুরো Turing machine:

ATM = {⟨M, w⟩ : M একটি TM আর M w-কে গ্রহণ করে}

উপপাদ্য ৪.১ (ATM Turing-recognizable)

U = “input ⟨M, w⟩ পেলে: ১. M-কে w-এর ওপর অনুকরণ করুন। ২. M কখনো accept state-এ পৌঁছালে গ্রহণ করুন; reject state-এ পৌঁছালে বর্জন করুন।”

U হলো universal Turing machine: একটি যন্ত্র, যে অন্য যেকোনো যন্ত্রের বর্ণনা পড়ে তাকে চালাতে পারে, ঠিক যেমন একটি interpreter যেকোনো program চালায়। এর গঠন (একটি tape-এ ⟨M⟩, একটিতে M-এর tape, একটিতে M-এর state) পর্ব ৪৮-এর বিষয়। এখানে দরকার শুধু ফলটি: w ∈ L(M) হলে M কিছু সসীম ধাপে গ্রহণ করে, আর U সেই ধাপগুলো অনুকরণ করে গ্রহণ করে; w ∉ L(M) হলে U কখনো গ্রহণ করে না। তাই L(U) = ATM. ∎

কিন্তু M যদি w-এ loop করে, U-ও loop করে। U তাই একটি recognizer, decider নয়। কেউ বলতে পারেন, “loop ধরে ফেলুন”। কিছু loop ধরা যায়: একই configuration দুবার এলে যন্ত্র নিশ্চিত চিরকাল ঘুরবে। কিন্তু অনেক loop কখনো কোনো configuration-এর পুনরাবৃত্তি করে না, যেমন একটি যন্ত্র যে শুধু ডানে হাঁটে আর tape-এ নতুন চিহ্ন লেখে। কোনো চতুর U কি সব ক্ষেত্রে থামতে পারে? না: পর্ব ৫১-এ diagonalization দিয়ে প্রমাণ হবে যে ATM decidable নয়। বাজারঘরের “এই program কি থামবে?” প্রশ্নের নেতিবাচক উত্তর সেখান থেকেই আসে।

অসীম কাজ পালা করে। এবার একটি কঠিনতর recognizer. NETM = {⟨M⟩ : L(M) ≠ ∅}, অর্থাৎ M অন্তত একটি string গ্রহণ করে। স্বাভাবিক চেষ্টা: Σ∗-এর string-গুলো shortlex ক্রমে নিন (ε, 0, 1, 00, …), প্রতিটিতে M চালান, কোনোটি গৃহীত হলে গ্রহণ। ফাঁদটি স্পষ্ট: M যদি ε-তে loop করে, যন্ত্র সেখানেই আটকে থাকে, যদিও M হয়তো 1 গ্রহণ করে। সমাধান হলো সময় আর string দুটিকেই একসঙ্গে ধাপে ধাপে বাড়ানো:

উপপাদ্য ৪.২ (NETM Turing-recognizable)

N = “input ⟨M⟩ পেলে: i = 1, 2, 3, … প্রতিটির জন্য: shortlex ক্রমের প্রথম i-টি string s1, …, si-এর প্রতিটিতে M-কে বড়জোর i ধাপ চালান। কোনোটি গৃহীত হলে গ্রহণ করুন।”

প্রমাণ: ধরুন M sj-কে t ধাপে গ্রহণ করে। round i = max(j, t)-এ sj তালিকায় আছে আর i ≥ t ধাপ পায়, তাই N সেখানে (বা আগেই) গ্রহণ করে। প্রতিটি round-এ সসীম কাজ (i × i ধাপ), তাই N-কে সেখানে পৌঁছাতে সসীম সময় লাগে। L(M) = ∅ হলে কোনো round-এ কিছু গৃহীত হয় না, N কখনো গ্রহণ করে না। তাই L(N) = NETM. ∎ ফলে ETM co-recognizable, কারণ তার complement হলো NETM আর অবৈধ encoding-গুলোর union, যার দুটি অংশই recognizable (অংশ ৬-এর union).

এই কৌশলের নাম dovetailing (কাঠের দুটি টুকরো খাঁজে খাঁজে জোড়া দেওয়ার “dovetail” জোড় থেকে)। গণিতের দিক থেকে এটি পর্ব ০২-এর ℕ × ℕ-কে তির্যকভাবে গোনা: (string-এর ক্রম, ধাপের সংখ্যা)-এর প্রতিটি জোড়া কোনো এক সসীম মুহূর্তে আসে। নিচের stepper বাজারঘরের একটি বাগ-ভরা coupon-checker P-তে N চালায়। P ε আর 0-তে চিরকাল চলে (বাগ), 1-কে চতুর্থ ধাপে গ্রহণ করে, আর বাকি সব প্রথম ধাপেই বর্জন করে।

1ভুল পথ: ε-তে P চালাতেই থাকা2round i: প্রথম i string নেওয়া3প্রতিটিতে P-কে i ধাপ চালানো4কোনোটি গৃহীত হলে ACCEPT
এই round-এর ফল
round
চেষ্টার string
প্রতিটিতে ধাপ
ফল
  1. ভুল পথ। ε দিয়ে শুরু করে P-কে থামা পর্যন্ত চালানো হলো। ১০০০ ধাপ পরেও P চলছে, আর চিরকাল চলবে। এই পদ্ধতি কখনো 1-এ পৌঁছায় না।
  2. Round ১. প্রথম একটি string ε, এক ধাপ। P চলছে; কিছু গৃহীত নয়। পরের round.
  3. Round ২. প্রথম দুটি string ε আর 0, প্রতিটি নতুন করে শুরু থেকে দুই ধাপ। দুটিই চলছে।
  4. Round ৩. এবার 1-ও তালিকায়, কিন্তু তিন ধাপে P এখনো 1-এ সিদ্ধান্ত নেয়নি (চতুর্থ ধাপে নেয়)।
  5. Round ৪. চারটি string, প্রতিটিতে চার ধাপ। 1 গৃহীত, 00 বর্জিত, ε আর 0 এখনো চলছে। একটি গৃহীত হওয়াই যথেষ্ট: N গ্রহণ করে, ⟨P⟩ ∈ NETM. মোট ১ + ২ × ২ + ৩ × ৩ + ৪ × ৪ = ৩০টি অনুকৃত ধাপ, সব সীমিত।

Python-এ program-গুলো generator: প্রতিটি next() একটি ধাপ, আর return মানে থেমে যাওয়া (True গ্রহণ, False বর্জন)। Q নামের দ্বিতীয় program কিছুই গ্রহণ করে না: 0 দিয়ে শুরু string-এ loop, বাকিগুলো বর্জন। N সেখানে থামে না, তাই ব্লকটি ৫০ round-এর একটি সীমা (cap) রাখে; সীমায় পৌঁছালে উত্তর “NO ANSWER”, যার মানে “এখনো জানি না”, বর্জন নয়।

from itertools import count, product
def P(w):                         # a buggy coupon checker; next() = one step
    if w in ("", "0"):            # bug: loops for ever on "" and on "0"
        while True: yield
    if w == "1":                  # accepts "1" after 4 steps
        for _ in range(3): yield
        return True
    return False                  # rejects everything else at step 1
def Q(w):                         # accepts nothing: loops on 0..., rejects 1...
    while w.startswith("0"): yield
    return False
def run(M, w, t):                 # run M on w for at most t steps
    g = M(w)
    for _ in range(t):
        try: next(g)
        except StopIteration as e: return "accept" if e.value else "reject"
    return "running"
def shortlex():
    for k in count():
        for t in product("01", repeat=k): yield "".join(t)
def nonempty(M, max_rounds, verbose=False):   # recognizer for L(M) != empty
    for i in range(1, max_rounds + 1):        # round i: first i strings, i steps
        S = [s for s, _ in zip(shortlex(), range(i))]
        res = {s: run(M, s, i) for s in S}
        if verbose: print(f"  round {i}:", {s or "ε": r for s, r in res.items()})
        hit = [s for s in S if res[s] == "accept"]
        if hit: return f"ACCEPT: M accepts {hit[0]!r} (round {i})"
    return f"NO ANSWER after {max_rounds} rounds (cap)"
print("naive, P on '' first:", run(P, "", 1000), "after 1000 steps")
print(nonempty(P, 50, verbose=True))
print("Q:", nonempty(Q, 50))

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

naive, P on '' first: running after 1000 steps
  round 1: {'ε': 'running'}
  round 2: {'ε': 'running', '0': 'running'}
  round 3: {'ε': 'running', '0': 'running', '1': 'running'}
  round 4: {'ε': 'running', '0': 'running', '1': 'accept', '00': 'reject'}
ACCEPT: M accepts '1' (round 4)
Q: NO ANSWER after 50 rounds (cap)

প্রথম লাইন সরল পদ্ধতির ব্যর্থতা; পরের চার লাইন stepper-এর চারটি round, হুবহু। round ৪-এ 1 গৃহীত, যদিও ε আর 0 তখনো চলছে: dovetailing কোনো একটি loop-কে বাকিদের আটকাতে দেয় না। Q-এর language ফাঁকা, তাই N-এর কোনো round-এ গ্রহণ নেই; আসল N সেখানে চিরকাল চলত। এটিই recognizer-এর স্বভাব: “হ্যাঁ” নিশ্চিত আসে, “না” কখনো আসে না। ⟨Q⟩ ∈ ETM নিশ্চিত করতে কোনো সাধারণ যন্ত্র নেই, তা পর্ব ৫২-এ প্রমাণ হবে।

একই কৌশলে recognizer থেকে একটি enumerator বানানো যায়, যে L-এর সব সদস্য একে একে ছাপায়: round i-তে প্রথম i string-এ i ধাপ চালিয়ে যা গৃহীত হয়, তা ছাপানো। এ থেকেই “recursively enumerable” নামটি এসেছে: recognizable ⇔ কোনো enumerator তাকে তালিকা করে। Enumerator-এর সংজ্ঞা আর পূর্ণ প্রমাণ পর্ব ৪৫-এর বিষয়।

৫ · মূল উপপাদ্য — L decidable ⇔ L আর L̄ দুটিই recognizable

উপপাদ্য ৫.১

একটি language L decidable, যদি এবং কেবল যদি L Turing-recognizable আর co-Turing-recognizable. অর্থাৎ decidable = recognizable ∩ co-recognizable.

প্রমাণ (⇒):

  1. ধরুন M L-কে decide করে। M একটি recognizer-ও, তাই L recognizable. — সংজ্ঞা ১.১, ১.২
  2. M-এর qaccept আর qreject অদলবদল করে M′ বানান। M সব input-এ থামে, তাই M′-ও থামে, আর M′ গ্রহণ করে ঠিক যখন M বর্জন করে, অর্থাৎ w ∈ L̄. — M deterministic, তাই প্রতিটি input-এ একটিমাত্র ফল
  3. M′ L̄-কে decide করে, তাই L̄ recognizable, আর L co-recognizable. ∎

প্রমাণ (⇐):

  1. ধরুন M1 L-কে আর M2 L̄-কে recognize করে। দুই tape-এর একটি যন্ত্র M বানান (multi-tape যন্ত্র single-tape-এর সমান শক্তিশালী): “input w পেলে: tape ১-এ M1-এর এক ধাপ, tape ২-এ M2-এর এক ধাপ, আবার M1-এর এক ধাপ, …। M1 গ্রহণ করলে M গ্রহণ করে; M2 গ্রহণ করলে M বর্জন করে।” — parallel simulation
  2. যেকোনো w হয় L-এ, নয় L̄-এ, তৃতীয় কিছু নেই। w ∈ L হলে M1 কিছু সসীম t ধাপে গ্রহণ করে; w ∈ L̄ হলে M2. — complement-এর সংজ্ঞা
  3. পালা করে চলায় M বড়জোর 2t ধাপে সেই মুহূর্তে পৌঁছায়, তাই M প্রতিটি input-এ থামে: M একটি decider. — দুই সিমুলেশনের কোনোটি অন্যটিকে আটকায় না
  4. M1 শুধু L-এর string গ্রহণ করে আর M2 শুধু L̄-এর, তাই M-এর গ্রহণ ⇔ w ∈ L. M L-কে decide করে। ∎

প্রমাণের কেন্দ্রে ধাপ ১-এর “পালা করে”। প্রথমে M1-কে পুরো চালিয়ে তারপর M2 চালালে কাজ হতো না: w ∈ L̄ হলে M1 চিরকাল চলতে পারে, আর M2-এর পালা কখনো আসত না। উদাহরণ হিসেবে একটি সরল language নিন: SQ = {n : n একটি পূর্ণবর্গ}, যেমন বাজারঘরের গুদামে n-টি বাক্স একটি বর্গাকার সারিতে ঠিক সাজানো যায় কি না। M1 k = 0, 1, 2, …-এর জন্য দেখে k2 = n কি না; M2 দেখে k2 < n < (k + 1)2 কি না। কোনোটিই কখনো বর্জন করে না, শুধু খুঁজতে থাকে, তাই দুটিই নিছক recognizer. (SQ অবশ্যই decidable, k2 > n হলেই থামা যায়; এখানে উদ্দেশ্য উপপাদ্যের যন্ত্রটি দেখা।)

1M1-এর এক ধাপ: k² = n ?2M2-এর এক ধাপ: k² < n < (k+1)² ?3M1 গ্রহণ ⇒ ACCEPT4M2 গ্রহণ ⇒ REJECT
দুই tape-এর অবস্থা
input n
M1-এর ধাপ
M2-এর ধাপ
M-এর মোট ধাপ
  1. প্রথম পালা। M1-এর ধাপ ১: k = 0, 0 ≠ 10. তারপর M2-এর ধাপ: 10 কি 0 আর 1-এর মাঝে? না। দুজনেই খুঁজে চলে।
  2. দ্বিতীয় পালা। k = 1: 1 ≠ 10; আর 10 কি 1 আর 4-এর মাঝে? না।
  3. তৃতীয় পালা। k = 2: 4 ≠ 10; 10 কি 4 আর 9-এর মাঝে? না। এখন পর্যন্ত ৬টি ধাপ।
  4. চতুর্থ পালা। M1: 9 ≠ 10. M2: 9 < 10 < 16, গ্রহণ! M2 L̄-এর recognizer, তাই M বর্জন করে: 10 ∉ SQ, মোট ৮ ধাপে। একা M1 এখানে চিরকাল চলত।
  5. n = 9 হলে। সপ্তম ধাপে M1-এর k = 3: 9 = 9, গ্রহণ, তাই M গ্রহণ করে। সাধারণভাবে n = k2 হলে ধাপ 2k + 1-এ গ্রহণ, আর k2 < n < (k + 1)2 হলে ধাপ 2k + 2-এ বর্জন।
from math import isqrt
# Recognizers as generators: next() = ONE step; return = accept; they never reject.
def M1(n):                       # recognizes SQ = {n : n is a perfect square}
    k = 0
    while True:
        if k * k == n: return f"M1 k={k}: {k*k} == {n}  ACCEPT"
        yield f"M1 k={k}: {k*k} != {n}"
        k += 1
def M2(n):                       # recognizes the complement of SQ
    k = 0
    while True:
        if k * k < n < (k + 1) ** 2: return f"M2 k={k}: {k*k} < {n} < {(k+1)**2}  ACCEPT"
        yield f"M2 k={k}: {n} not between {k*k} and {(k+1)**2}"
        k += 1
def alone(M, n, cap):            # one recognizer with a step cap
    g = M(n)
    for step in range(1, cap + 1):
        try: next(g)
        except StopIteration: return f"accept at step {step}"
    return f"NO ANSWER after {cap} steps (cap)"
def decide(n, verbose=False):    # dovetail: a step of M1, a step of M2, ...
    g = {"M1": M1(n), "M2": M2(n)}; steps = 0
    while True:
        for name in ("M1", "M2"):
            steps += 1
            try: line = next(g[name])
            except StopIteration as e:
                if verbose: print("   ", steps, e.value)
                return ("accept" if name == "M1" else "reject"), steps
            if verbose: print("   ", steps, line)
print("M1 alone on 10:", alone(M1, 10, 1000), "| M2 alone on 9:", alone(M2, 9, 1000))
print("decide(10):", decide(10, verbose=True))
print("decide(9):", decide(9), " decide(1000000):", decide(1000000))
ok = all((decide(n)[0] == "accept") == (isqrt(n) ** 2 == n) for n in range(2001))
print("n = 0..2000 all agree with isqrt:", ok)

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

M1 alone on 10: NO ANSWER after 1000 steps (cap) | M2 alone on 9: NO ANSWER after 1000 steps (cap)
    1 M1 k=0: 0 != 10
    2 M2 k=0: 10 not between 0 and 1
    3 M1 k=1: 1 != 10
    4 M2 k=1: 10 not between 1 and 4
    5 M1 k=2: 4 != 10
    6 M2 k=2: 10 not between 4 and 9
    7 M1 k=3: 9 != 10
    8 M2 k=3: 9 < 10 < 16  ACCEPT
decide(10): ('reject', 8)
decide(9): ('accept', 7)  decide(1000000): ('accept', 2001)
n = 0..2000 all agree with isqrt: True

একা চালালে দুটি recognizer-ই আটকে যায়: 10-এ M1, 9-এ M2, প্রতিটি ১০০০ ধাপের সীমা পেরিয়েও। পালা করে চালালে প্রতিটি input-এ উত্তর আসে: 10 বর্জিত ৮ ধাপে, 9 গৃহীত ৭ ধাপে, ঠিক stepper-এর মতো। 1000000 = 10002, তাই k = 1000-এ ধাপ 2 × 1000 + 1 = 2001. শেষ লাইনে 0 থেকে 2000 পর্যন্ত ২০০১টি সংখ্যার প্রতিটিতে সিদ্ধান্ত math.isqrt-এর সঙ্গে মিলেছে। দাম লক্ষ করুন: M মোট ধাপ গোনে দুই যন্ত্রের যোগফলে, সবচেয়ে বেশি দ্রুততর সফল যন্ত্রের সময়ের প্রায় দ্বিগুণ।

অনুসিদ্ধান্ত ৫.২

L recognizable কিন্তু decidable নয় হলে L̄ recognizable নয়। পর্ব ৫১-এ প্রমাণ হবে ATM decidable নয়; উপপাদ্য ৪.১-এ এটি recognizable; তাই ĀTM, অর্থাৎ ATM-এর complement, Turing-recognizable নয়।

অনুসিদ্ধান্তটি উপপাদ্য ৫.১-এর contrapositive: L̄-ও recognizable হলে L decidable হতো। এটি আমাদের প্রথম “recognizable নয়” language-এর পথ দেখায়। কথাটি সহজ ভাষায়: “M w গ্রহণ করে” প্রমাণের একটি সসীম সাক্ষী আছে (গ্রহণ পর্যন্ত configuration-এর তালিকা), কিন্তু “M w গ্রহণ করে না” প্রমাণের কোনো সাধারণ সসীম সাক্ষী নেই।

৬ · Closure property — কোন operation-এ কোন শ্রেণি বদ্ধ

Regular আর context-free শ্রেণির closure property আগের মডিউলগুলোতে দেখেছেন (পর্ব ১৬, পর্ব ৩৭)। এবার দুটি নতুন শ্রেণি। প্রমাণগুলো ছোট, কিন্তু প্রতিটিতে একটি প্রশ্ন বারবার আসে: কোনো উপ-যন্ত্র যদি loop করে, তাহলে কী হবে?

OperationDecidableRecognizableমূল কৌশল
Union L1 ∪ L2বদ্ধবদ্ধrecognizable-এ পালা করে চালানো জরুরি
Intersection L1 ∩ L2বদ্ধবদ্ধএকটির পর আরেকটি চালালেই হয়
Complement L̄বদ্ধবদ্ধ নয়decider-এ accept/reject অদলবদল; ATM উল্টো উদাহরণ
Concatenation L1L2বদ্ধবদ্ধw = xy-এর সব |w| + 1 ভাগ; recognizable-এ ভাগগুলো পালা করে
Kleene star L∗বদ্ধবদ্ধw-এর সব সসীম ভাগ; recognizable-এ পালা করে
Difference L1 \ L2বদ্ধবদ্ধ নয়Σ∗ \ ATM = ĀTM

Recognizable শ্রেণির union (প্রমাণ): M1, M2 যথাক্রমে L1, L2-কে recognize করে। M = “input w পেলে: M1 আর M2-কে w-এর ওপর পালা করে এক ধাপ করে চালান; কোনো একটি গ্রহণ করলে গ্রহণ করুন।” w ∈ L1 ∪ L2 হলে অন্তত একটি সসীম ধাপে গ্রহণ করে, আর পালা করে চলায় অন্যটির loop তাকে আটকায় না; w ∉ L1 ∪ L2 হলে কেউ গ্রহণ করে না। ∎ একটির পর আরেকটি চালালে প্রমাণ ভাঙে: w ∈ L2 \ L1-এ M1 loop করলে M2-এর পালা আসে না।

Recognizable শ্রেণির intersection (প্রমাণ): M = “M1 চালান; গ্রহণ করলে M2 চালান; সে-ও গ্রহণ করলে গ্রহণ।” এখানে পরপর চালানোই যথেষ্ট। M1 loop করলে w ∉ L1, তাই w ∉ L1 ∩ L2, আর M-এর গ্রহণ না করাই ঠিক। ∎ পার্থক্যটি মনে রাখার মতো: “দুটিই লাগবে” হলে একটির loop কোনো ক্ষতি করে না; “যেকোনো একটি যথেষ্ট” হলে করে।

Decidable শ্রেণির complement উপপাদ্য ৫.১-এর (⇒) অংশের ধাপ ২: deterministic decider-এ accept আর reject অদলবদল। পর্ব ৪৬-এর সতর্কতা এখানে প্রাসঙ্গিক: NTM decider-এ এই অদলবদল কাজ করে না, তাই প্রমাণটি deterministic decider দিয়েই। আর recognizable শ্রেণি complement-এ বদ্ধ নয়, কারণ ATM recognizable অথচ ĀTM নয় (অনুসিদ্ধান্ত ৫.২)। Recognizer-এ অদলবদল কেন ব্যর্থ, তা অনুশীলন ২-এ।

৭ · শ্রেণির মানচিত্র — কোন language কোথায় বসে

এ পর্যন্ত যা প্রমাণ হলো আর পরের পর্বগুলোতে যা হবে, সব একটি ছবিতে। পর্ব ০৬-এর Chomsky hierarchy-র বাইরে এখন দুটি শ্রেণি, recognizable আর co-recognizable, যাদের ছেদ ঠিক decidable শ্রেণি (উপপাদ্য ৫.১)।

Language-শ্রেণির মানচিত্র

নীল: recognizable; হলুদ: co-recognizable; সবুজ ছেদ: decidable. ভেতরে Chomsky hierarchy-র তিনটি স্তর।

Classes of languages: recognizable, co-recognizable, decidable and the Chomsky levels সব language Recognizable Co-recognizable Decidable CSL · aⁿbⁿcⁿ CFL · aⁿbⁿ Regular R ∩ co-R জোড় সংখ্যক 1 BG-dddd ATM HALTTM ĀTM ETM EQTM আর অগণিত বাকি language
ছবি ৫০.১ — শুধু নীল অংশ: recognizable কিন্তু decidable নয় (ATM, পর্ব ৫১)। শুধু হলুদ অংশ: তাদের complement. দুটির বাইরে EQTM (পর্ব ৫২), আর countability-র যুক্তিতে বেশিরভাগ language. প্রতিটি সীমানা কঠোর (⊊)।

নিচের stepper ছয়টি language এক এক করে মানচিত্রে বসায়। প্রতিটির জন্য দুটি প্রশ্ন: কোনো recognizer আছে? Complement-এর recognizer আছে?

1Regular (DFA)2CFL, regular নয়3Decidable, CFL নয়4Recognizable, decidable নয়5Co-recognizable, decidable নয়6কোনোটিই নয়
এই language
language
recognizer?
complement-এর?
প্রমাণ কোথায়
  1. জোড় সংখ্যক 1. দুই state-এর একটি DFA (পর্ব ০৭)। প্রতিটি DFA একটি decider, তাই language আর তার complement দুটিই decidable. মানচিত্রের সবচেয়ে ভেতরে।
  2. aⁿbⁿ. Pumping lemma দেখায় এটি regular নয় (পর্ব ১৭); একটি CFG S → aSb | ε এটি তৈরি করে (পর্ব ২৫)। উপপাদ্য ৩.৩-এ প্রতিটি CFL decidable.
  3. aⁿbⁿcⁿ. CFL নয় (পর্ব ৩৬), কিন্তু crossing off করে একটি TM decider আছে (পর্ব ৪৩)। এটি context-sensitive (CSL), আর decidable শ্রেণিতে।
  4. ATM. U একটি recognizer (উপপাদ্য ৪.১), কিন্তু কোনো decider নেই (পর্ব ৫১)। তাই উপপাদ্য ৫.১ অনুযায়ী complement-এর recognizer থাকতে পারে না। শুধু নীল অংশে; HALTTM-ও এখানে।
  5. ĀTM. এর complement ATM, যাকে U চেনে: co-recognizable. নিজে recognizable নয় (অনুসিদ্ধান্ত ৫.২)। শুধু হলুদ অংশে; ETM-ও এখানে (উপপাদ্য ৪.২)।
  6. EQTM. দুটি TM একই language চেনে কি না। পর্ব ৫২-এ দেখবেন, এটি বা এর complement কোনোটিই recognizable নয়: দুই বাক্সের বাইরে।

বেশিরভাগ language কোথায়? প্রতিটি TM একটি সসীম বর্ণনা ⟨M⟩, তাই TM-এর set countable; প্রতিটি TM একটি language চেনে, তাই recognizable language-ও countable, আর co-recognizable-ও। কিন্তু Σ∗-এর সব subset-এর set uncountable (পর্ব ০২-এর Cantor-এর উপপাদ্য; গণিতের দিক থেকে বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৮-এ)। তাই প্রায় সব language মানচিত্রের সবচেয়ে বাইরের অংশে। কিন্তু countability শুধু অস্তিত্ব দেখায়; কোনো নির্দিষ্ট, স্বাভাবিক language (যেমন ATM) কোথায়, তা বলতে diagonalization আর reduction লাগে, যা পর্ব ৫১–৫২-এর কাজ।

সীমানাপৃথককারী উদাহরণপ্রমাণ
Regular ⊊ CFLaⁿbⁿপর্ব ১৭
CFL ⊊ CSLaⁿbⁿcⁿপর্ব ৩৬
CSL ⊊ decidableLBA-দের ওপর diagonalization-এ বানানো languageআরও গভীরে (নিচে)
Decidable ⊊ recognizableATMপর্ব ৫১
Recognizable ∪ co-recognizable ⊊ সবEQTM; countabilityপর্ব ৫২; পর্ব ০২

আরও গভীরে: CSL ⊊ decidable-এর প্রমাণ একটি diagonalization: সব context-sensitive grammar G1, G2, …-এর তালিকা করে D = {wi : wi ∉ L(Gi)} বানান; প্রতিটি CSG-এর membership decidable, তাই D decidable, অথচ কোনো CSG-এর language নয়। Logic-এ এই শ্রেণিগুলো arithmetical hierarchy-র নিচের তলা: recognizable = Σ1, co-recognizable = Π1, decidable = Δ1, আর EQTM আরও এক তলা ওপরে (Π2). Emil Post ১৯৪৪ সালে প্রশ্ন তোলেন, ATM-এর চেয়ে “সহজ” কিন্তু undecidable কোনো recognizable language আছে কি না; Friedberg আর Muchnik ১৯৫০-এর দশকে আলাদাভাবে দেখান যে আছে, যা recursion theory-র একটি বড় অধ্যায়ের সূচনা বলে পরিচিত।

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

  • Decidable আর Turing-recognizable language-এর পার্থক্য কী? Decider সব input-এ থামে; recognizer শুধু সদস্যে থামার নিশ্চয়তা দেয়।
  • ECFG decidable, প্রমাণ করুন। Terminal থেকে শুরু করে generating variable চিহ্নিত করা; S চিহ্নিত না হলে গ্রহণ।
  • প্রমাণ করুন L আর L̄ recognizable হলে L decidable. দুই recognizer পালা করে এক ধাপ করে; একটি অবশ্যই গ্রহণ করে।
  • Recognizable শ্রেণি complement-এ বদ্ধ কি? না: ATM recognizable, ĀTM নয়।
  • প্রতিটি CFL decidable কেন? CNF-এ 2n − 1 ধাপের derivation, বা CYK; PDA-র সরাসরি simulation নয়।

৮ · AI-এর যুগে decidable আর recognizable

AI assistant এই বিষয়ে সাবলীল উত্তর দেয়, কিন্তু কয়েকটি ভুল প্রায় নিয়মিত: “ATM decidable, শুধু M চালিয়ে দেখুন”, recognizer-এর accept/reject অদলবদল করে complement, আর “recursively enumerable” শুনে regular expression বা recursion-এর সঙ্গে গুলিয়ে ফেলা। নিচের সারণিতে আরও কয়েকটি আর ধরার উপায়।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“Simulator সবসময় থামে”, বা একটি recognizer-কে decider বলাযন্ত্রটি loop-করা একটি input-এ চালিয়ে দেখুন, ধাপের সীমাসহ; “NO ANSWER” মানে বর্জন নয়
দুই recognizer একটির পর আরেকটি চালিয়ে union বা উপপাদ্য ৫.১-এর প্রমাণপ্রথম যন্ত্র loop করে এমন একটি input খুঁজুন; পালা করে চালানো (dovetailing) লাগে কি না দেখুন
“সব derivation চেষ্টা করুন” দিয়ে ACFG-এর deciderw ∉ L(G) হলে খোঁজ থামে কি? CNF-এর 2n − 1 সীমা বা CYK আছে কি না দেখুন
EQCFG-কে symmetric difference দিয়ে decidable বলাCFL complement আর intersection-এ বদ্ধ নয় (পর্ব ৩৭); EQCFG undecidable (পর্ব ৫৪)
Reduction-এর দিক উল্টো, বা “recognizable হলে complement-ও recognizable”উপপাদ্য ৫.১ আর অনুসিদ্ধান্ত ৫.২ মিলিয়ে নিন; reduction-এর দিক পর্ব ৫২-এর নিয়মে যাচাই
বানানো সাল বা রেফারেন্স (যেমন Post-এর কাজের ভুল বছর)Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখুন

AI-কে কাজে লাগানোর ভালো উপায়: একটি decider-এর high-level বর্ণনা, কেন সেটি সবসময় থামে তার যুক্তি, আর একটি ছোট Python পরীক্ষা চাওয়া, যা আপনি নিজে brute force দিয়ে মেলাবেন।

আমি গণনার তত্ত্ব শিখছি। ALL_DFA = {⟨A⟩ : A একটি DFA আর L(A) = Σ*} আর SUB_DFA = {⟨A, B⟩ : L(A) ⊆ L(B)}, এই দুটি language নিয়ে কাজ করো। ১. Sipser রীতিতে প্রতিটির জন্য একটি decider-এর high-level বর্ণনা দাও, শুধু E_DFA-র decider-কে subroutine হিসেবে ব্যবহার করে। ২. প্রতিটি decider কেন সব input-এ থামে আর কেন সঠিক, ধাপে ধাপে প্রমাণ দাও; complement নেওয়ার আগে DFA-টি complete কি না, সেই শর্তটি স্পষ্ট বলো। ৩. শুধু standard library দিয়ে Python code দাও, যা DFA-কে dict হিসেবে নেয়, দুটি decider চালায়, আর দৈর্ঘ্য 10 পর্যন্ত সব string-এ brute force দিয়ে ফল মেলায়। ৪. ALL_CFG-এর জন্য একই পদ্ধতি কেন কাজ করে না, এক অনুচ্ছেদে বলো। ৫. কোনো দাবি নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১“Recursive” আর “recursively enumerable”, এই অদ্ভুত নামগুলো কোথা থেকে এল, আর অনেকে কেন এখন “computable” আর “computably enumerable” বলতে চান?

নামগুলো ১৯৩০-এর দশকের গণিত থেকে এসেছে, Turing machine-এর আগের এবং সমসাময়িক একটি ধারা থেকে। Gödel ১৯৩১ সালের অসম্পূর্ণতার প্রবন্ধে “recursive” function ব্যবহার করেন, যেগুলো নিজেকে ছোট মানে ডেকে সংজ্ঞায়িত হয়, প্রোগ্রামিংয়ের recursion-এর মতো। পরে Herbrand আর Gödel-এর “general recursive” function আর Kleene-এর μ-recursive function (পর্ব ৪৯) গণনাযোগ্য function-এর একটি সংজ্ঞা হয়ে দাঁড়ায়। Church আর Turing-এর ১৯৩৬ সালের কাজের পর দেখা গেল, এই সংজ্ঞা আর Turing machine একই function শ্রেণি দেয়। ফলে “recursive set” মানে দাঁড়াল এমন set, যার সদস্যপদ একটি recursive function দিয়ে নির্ণয় করা যায়, অর্থাৎ decidable.

“Recursively enumerable” মানে এমন set, যার সদস্যদের একটি recursive function দিয়ে একে একে তালিকা করা যায়, অংশ ৪-এর enumerator-এর মতো। Emil Post ১৯৪৪ সালে r.e. set আর তাদের decision problem নিয়ে একটি প্রভাবশালী প্রবন্ধ লেখেন বলে পরিচিত; “একটি set recursive ঠিক তখন, যখন সেটি আর তার complement দুটিই r.e.”, এই উপপাদ্য সাধারণত সেই সময়ের Kleene আর Post-এর কাজের সঙ্গে যুক্ত করা হয়।

সমস্যা হলো, “recursive” শব্দটি ছাত্রছাত্রীদের বিভ্রান্ত করে: তারা ভাবে এর সঙ্গে নিজেকে ডাকা function-এর সম্পর্ক আছে, বা “recursively enumerable” মানে কোনোভাবে regular expression. Robert Soare ১৯৯৬ সালের একটি প্রবন্ধে প্রস্তাব করেন, ক্ষেত্রটিকে “computability theory” আর এই set-গুলোকে “computable” আর “computably enumerable (c.e.)” বলা হোক, যাতে অর্থ স্পষ্ট থাকে। আজ গবেষণায় c.e. বেশ প্রচলিত, তবে পুরোনো নামও সমান চলে। Sipser-এর পাঠ্যবই “decidable” আর “Turing-recognizable” ব্যবহার করে, এই কোর্সও তাই।

পরীক্ষায় তাই একই ধারণা চার-পাঁচটি নামে আসতে পারে; সংজ্ঞাটি যন্ত্রের আচরণ দিয়ে মনে রাখলে নাম নিয়ে বিভ্রান্তি হয় না।

মূল উপলব্ধি: Recursive = decidable = computable, আর recursively enumerable = recognizable = c.e.; নামগুলো ইতিহাসের ছাপ, কিন্তু অর্থ একটাই: সবসময় থামে, নাকি শুধু সদস্যে থামার নিশ্চয়তা।

প্র ০২বাস্তবে কোনো recognizable-কিন্তু-undecidable সমস্যা নিয়ে কি software বানানো হয়? “শুধু হ্যাঁ নিশ্চিত” পদ্ধতি দিয়ে মানুষ কী কাজ করে?

হ্যাঁ, আর সবচেয়ে বিখ্যাত উদাহরণ first-order logic-এর theorem prover. Gödel ১৯২৯–৩০ সালে completeness theorem প্রমাণ করেন: first-order logic-এ যে বাক্য সব model-এ সত্য, তার একটি সসীম প্রমাণ আছে। প্রমাণগুলো string, তাই সব প্রমাণ shortlex ক্রমে তালিকা করে মিলিয়ে দেখলে প্রতিটি valid বাক্যের প্রমাণ একসময় পাওয়া যায়: validity recognizable. কিন্তু Church আর Turing ১৯৩৬ সালে আলাদাভাবে দেখান যে validity decidable নয়; এটিই Hilbert-এর Entscheidungsproblem-এর নেতিবাচক উত্তর। উপপাদ্য ৫.১ তাই বলে, “এই বাক্য valid নয়” recognizable হতে পারে না।

বাস্তবের automated theorem prover (যেমন resolution-ভিত্তিক prover) ঠিক এই আচরণ দেখায়: বাক্যটি সত্য হলে প্রায়ই প্রমাণ খুঁজে পায়, কিন্তু মিথ্যা হলে অনেক সময় চিরকাল খুঁজতে থাকে। তাই এদের সঙ্গে সবসময় একটি সময়-সীমা থাকে, আর সীমা পেরোলে উত্তর “জানি না”, “মিথ্যা” নয়। AI Foundations কোর্সের পর্ব ৪৬-এ first-order logic-এর ভাষা দেখতে পারেন।

দ্বিতীয় কৌশল উপপাদ্য ৫.১-এর ছবি অনুসরণ করে: দুই দিক থেকে খোঁজা। Model checking আর verification-এ একটি tool প্রমাণ খোঁজে (“program নিরাপদ”), অন্যটি counterexample খোঁজে (“এই input-এ crash”). দুটি পাশাপাশি চালালে যেটি আগে সফল হয়, সেটিই উত্তর। সাধারণ ক্ষেত্রে দুটির কোনোটিই নিশ্চিত সফল হয় না, কারণ সমস্যাটি undecidable; কিন্তু বাস্তবের অনেক নির্দিষ্ট program-এ একটি না একটি দ্রুত সফল হয়। SAT solver-এর জগতেও একই ধরন: সমাধান পেলে তা সাক্ষী, আর “সমাধান নেই” বললে কিছু solver একটি প্রমাণও দেয়, যা আলাদা একটি checker মিলিয়ে দেখে।

মূল উপলব্ধি: Recognizable-কিন্তু-undecidable সমস্যায় প্রকৌশলীরা “হ্যাঁ”-এর সাক্ষী খোঁজেন, সময়-সীমা বসান, আর সম্ভব হলে “না”-এর সাক্ষীও একসঙ্গে খোঁজেন; উপপাদ্য ৫.১ বলে কখন এই দুই খোঁজ মিলে একটি পূর্ণ decider হয়।

প্র ০৩DFA-র জন্য membership, emptiness আর equivalence তিনটিই decidable, CFG-তে প্রথম দুটি decidable অথচ equivalence নয়। কোন বৈশিষ্ট্যটি এই পার্থক্য তৈরি করে, আর deterministic PDA কোথায় বসে?

EQDFA-এর প্রমাণ দুটি জিনিসের ওপর দাঁড়িয়ে: emptiness decidable, আর regular শ্রেণি complement ও intersection-এ বদ্ধ, যাতে symmetric difference-এর একটি DFA বানানো যায়। CFG-তে প্রথমটি আছে (ECFG), দ্বিতীয়টি নেই: দুটি CFL-এর ছেদ বা একটি CFL-এর complement context-free না-ও হতে পারে (পর্ব ৩৭)। তাই প্রমাণের কৌশল ভেঙে যায়। কিন্তু কৌশল ভাঙা আর undecidable হওয়া আলাদা কথা; EQCFG-এর undecidability আলাদা প্রমাণ চায়, যা পর্ব ৫৪-এ Post correspondence problem দিয়ে আসবে। একই পথে ALLCFG = {⟨G⟩ : L(G) = Σ∗}-ও undecidable, যদিও তার DFA-সংস্করণ সহজ।

মজার মাঝামাঝি ক্ষেত্র deterministic PDA (পর্ব ৩৫)। Deterministic CFL complement-এ বদ্ধ, তাই প্রশ্ন ওঠে, দুটি DPDA-র equivalence decidable কি না। এই প্রশ্ন বহু দশক খোলা ছিল। Géraud Sénizergues ১৯৯৭ সালের দিকে প্রমাণ ঘোষণা করেন যে এটি decidable, আর এই কাজের জন্য ২০০২ সালে Gödel Prize পান বলে পরিচিত। প্রমাণটি দীর্ঘ আর কঠিন, আর algorithm-টির খরচ নিয়ে পরে আরও গবেষণা হয়েছে। লক্ষ করুন, DPDA-র ক্ষেত্রেও সরল symmetric-difference কৌশল চলে না, কারণ deterministic CFL intersection-এ বদ্ধ নয়।

শিক্ষাটি সাধারণ: একটি decision problem decidable কি না, তা নির্ভর করে শ্রেণিটির closure property আর emptiness-এর ওপর; কিন্তু শুধু একটি প্রমাণ-কৌশল ব্যর্থ হওয়া undecidability-র প্রমাণ নয়।

মূল উপলব্ধি: EQDFA decidable কারণ regular শ্রেণি boolean operation-এ বদ্ধ আর emptiness decidable; CFG-তে closure ভাঙে আর equivalence সত্যিই undecidable, অথচ DPDA-র equivalence অনেক কষ্টে decidable প্রমাণিত।

প্র ০৪“Decidable” মানে কি “বাস্তবে সমাধানযোগ্য”? এমন decidable সমস্যা আছে কি, যার decider কোনো কম্পিউটারে কার্যত চলবে না?

না, decidable শুধু বলে একটি algorithm আছে যা সবসময় থামে; কত সময়ে, তা বলে না। কয়েকটি বিখ্যাত উদাহরণ দেখায় ফারাকটি কত বড় হতে পারে।

প্রথম, Presburger arithmetic: যোগ আছে কিন্তু গুণ নেই এমন স্বাভাবিক সংখ্যার first-order তত্ত্ব। Mojżesz Presburger ১৯২৯ সালে দেখান এর সত্যতা decidable. কিন্তু Fischer আর Rabin ১৯৭৪ সালে প্রমাণ করেন, যেকোনো decider-এর জন্য কিছু দৈর্ঘ্য n-এর বাক্যে মোটামুটি 22cn ধাপ লাগে, অর্থাৎ দ্বিগুণ সূচকীয়। ছোট বাক্যেই এটি মহাবিশ্বের বয়সের চেয়ে বেশি সময়।

দ্বিতীয়, regular expression-এর equivalence. সাধারণ regex-এ এটি PSPACE-complete (পর্ব ২০, ৬৫)। Meyer আর Stockmeyer ১৯৭০-এর দশকের শুরুতে দেখান, regex-এ complement-এর operation যোগ করলে সমস্যাটি এখনো decidable, কিন্তু খরচ কোনো নির্দিষ্ট উচ্চতার সূচক-স্তম্ভ (22⋯) দিয়েও বাঁধা যায় না, যাকে non-elementary বলে।

তৃতীয়, এই পর্বের ACFG-এর প্রথম decider নিজেই: সব 2n − 1 ধাপের derivation তালিকা করা সূচকীয় সময়, যদিও CYK একই উত্তর n3-এর অনুপাতে দেয়। একই সমস্যার decider ভালো বা খারাপ হতে পারে।

এই কারণেই কোর্সের পরের অংশ (মডিউল ১০–১১) decidable সমস্যাগুলোকে আবার ভাগ করে: P, NP, PSPACE, EXPTIME. Computability প্রশ্ন করে “আদৌ সম্ভব?”; complexity প্রশ্ন করে “কত দামে?”। বাজারঘরের ডেলিভারি রুটের প্রশ্ন decidable (সব রুট সসীম), কিন্তু দক্ষ algorithm জানা নেই (পর্ব ৫৯–৬৩)।

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

প্র ০৫Dovetailing শুধু প্রমাণের কৌশল, নাকি কম্পিউটিংয়ে এর বাস্তব রূপ আছে? “সবকিছু একটু একটু করে চালানো” ধারণাটি কোথায় কোথায় দেখা যায়?

Dovetailing-এর মূল কথা ন্যায্যতা (fairness): অসীম সংখ্যক কাজের প্রতিটি সসীম সময়ের মধ্যে যথেষ্ট সুযোগ পাবে, কোনো একটি কাজ বাকিদের আটকাতে পারবে না। গণিতে এটি ℕ × ℕ-কে তির্যকভাবে গোনা (পর্ব ০২); অংশ ৪-এ এটি (string, ধাপ)-এর জোড়া গোনা।

সবচেয়ে পরিচিত বাস্তব রূপ operating system-এর time-sharing. Round-robin scheduling-এ প্রতিটি process একটি ছোট সময়-খণ্ড পায়, তারপর পরেরটি; একটি process অসীম loop-এ পড়লেও অন্যগুলো চলতে থাকে। এটি উপপাদ্য ৫.১-এর পালা করে চালানোর হুবহু ছবি। একটি single-core কম্পিউটারে আপনার browser আর music player “একসঙ্গে” চলে এভাবেই।

দ্বিতীয় রূপ Leonid Levin-এর “universal search” (১৯৭৩ সালের প্রবন্ধে, যেখানে তিনি NP-completeness-এর ধারণাও দেন বলে পরিচিত)। ধারণাটি: একটি সমাধান খুঁজতে সব program পালা করে চালানো হয়, প্রতিটি program p-কে তার দৈর্ঘ্যের অনুপাতে সূচকীয়ভাবে কম সময় দিয়ে; যে program প্রথম একটি যাচাইযোগ্য সমাধান দেয়, সেটি গ্রহণ। ফলাফল তাত্ত্বিকভাবে চমকপ্রদ: সেরা algorithm-এর চেয়ে বড়জোর একটি ধ্রুবক গুণ ধীর, যদিও সেই ধ্রুবক এত বিশাল যে বাস্তবে অচল।

তৃতীয় রূপ search-এর জগতে: Prolog-এর DFS অসীম শাখায় আটকে যায়, আর fair search বা iterative deepening (পর্ব ৪৬) সেটি এড়ায়; fuzzer আর property-based testing টুলও অনেক input-এর মধ্যে সময় ভাগ করে, যাতে একটি ধীর input পুরো পরীক্ষা আটকে না দেয়। আর প্রতিটি ক্ষেত্রে বিপদ একই: পরপর চালালে একটি অসীম কাজ সবকিছু থামিয়ে দেয়।

মূল উপলব্ধি: Dovetailing হলো ন্যায্য সময়-ভাগের গাণিতিক রূপ; OS-এর round-robin, Levin-এর universal search আর fair search সবই একই নীতি মানে: কোনো একটি অসীম কাজকে বাকিদের আটকাতে দেওয়া চলবে না।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। dfa_deciders.py, ecfg_marking.py আর dovetail_decider.py-তে নিজের input বসিয়ে উত্তর যাচাইও করতে পারেন।

  1. নকশা: ALLDFA = {⟨A⟩ : A একটি DFA আর L(A) = Σ∗} আর SUBDFA = {⟨A, B⟩ : A, B DFA আর L(A) ⊆ L(B)}, দুটির জন্য decider-এর high-level বর্ণনা দিন, EDFA-এর decider T-কে subroutine হিসেবে ব্যবহার করে। কেন দুটি যন্ত্রই সবসময় থামে?

    ALLDFA: “input ⟨A⟩ পেলে: A-এর accept আর non-accept state অদলবদল করে A′ বানান; T-কে ⟨A′⟩-এর ওপর চালান; T গ্রহণ করলে গ্রহণ।” DFA-র δ total (প্রতিটি state আর চিহ্নে একটি তীর), তাই L(A′) = L̄(A), আর L(A) = Σ∗ ⇔ L̄(A) = ∅. (একটি partial DFA দেওয়া থাকলে আগে একটি dead state যোগ করে complete করতে হয়; নইলে অদলবদল ভুল language দেয়।)

    SUBDFA: “input ⟨A, B⟩ পেলে: product construction দিয়ে L(A) ∩ L̄(B)-এর DFA C বানান; T-কে ⟨C⟩-এর ওপর চালান; গ্রহণ করলে গ্রহণ।” L(A) ⊆ L(B) ⇔ A-এর এমন কোনো string নেই যা B-তে নেই ⇔ L(C) = ∅. দুটি যন্ত্রেই নির্মাণ সসীম (state-সংখ্যা |QA| × |QB|), আর T decider, তাই দুটিই সবসময় থামে। EQDFA আসলে দুই দিকের SUBDFA.

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: recognizable language complement-এ বদ্ধ। প্রমাণ: M L-কে recognize করে। M-এর qaccept আর qreject অদলবদল করে M′ বানাই। M যে string গ্রহণ করত, M′ তা বর্জন করে, আর M যা বর্জন করত, M′ তা গ্রহণ করে। তাই L(M′) = L̄. ∎” ভুলটি কোথায়, আর কোন বাড়তি শর্তে প্রমাণটি ঠিক?

    ভুল বাক্যটি শেষ সিদ্ধান্ত “তাই L(M′) = L̄”। M-এর তিনটি সম্ভাব্য ফল: গ্রহণ, বর্জন, loop. অদলবদল প্রথম দুটি উল্টায়, কিন্তু loop loop-ই থাকে। যে string-এ M loop করে, সেটি L̄-এ আছে (M গ্রহণ করে না), কিন্তু M′-ও সেখানে loop করে, তাই গ্রহণ করে না। ফলে L(M′) শুধু M-এর বর্জিত string-গুলো, যা L̄-এর একটি অংশ মাত্র।

    দাবিটি নিজেই মিথ্যা: ATM recognizable কিন্তু ĀTM নয় (অনুসিদ্ধান্ত ৫.২)। প্রমাণটি ঠিক হয় যখন M একটি deterministic decider: তখন loop নেই, আর এটিই উপপাদ্য ৫.১-এর (⇒) অংশের ধাপ ২, যা দেখায় decidable শ্রেণি complement-এ বদ্ধ।

  3. আউটপুট অনুমান: SQ = {n : n পূর্ণবর্গ}-এর জন্য দুটি recognizer: M1 k = 0, 1, 2, …-এ দেখে k2 = n কি না, M2 দেখে k2 < n < (k + 1)2 কি না; সফল হলে গ্রহণ, নইলে k বাড়ায়। M ধাপ ১-এ M1, ধাপ ২-এ M2, এভাবে পালা করে চালায়; M1 গ্রহণ করলে M গ্রহণ, M2 গ্রহণ করলে বর্জন। decide(17) আর decide(16) কী ফেরত দেবে (ফল, মোট ধাপ)?

    17: 16 < 17 < 25, তাই M2 k = 4-এ গ্রহণ করে। M2-এর পঞ্চম চেষ্টা (k = 0 থেকে 4) M-এর ধাপ 2 × 4 + 2 = 10. ফল ('reject', 10).

    16 = 42, তাই M1 k = 4-এ গ্রহণ করে, M-এর ধাপ 2 × 4 + 1 = 9-এ, M2-এর পঞ্চম চেষ্টার আগেই (M2 k = 3-এ দেখেছিল 9 < 16 < 16 মিথ্যা)। ফল ('accept', 9). dovetail_decider.py-তে decide(17, verbose=True) চালালে ঠিক এই দুটি ফল আর প্রতিটি ধাপ দেখা যায়।

  4. হিসাব: G3-এর নিয়ম: S → AB | C, A → aA | a, B → bB | AC, C → cC. ECFG-এর marking algorithm round ধরে চালান। কোন variable-গুলো চিহ্নিত হয়, ⟨G3⟩ ∈ ECFG কি না, আর কেন?

    Round ০: terminal a, b, c. Round ১: A, কারণ A → a. Round ২: আর কিছু নয়। B → bB-তে B নিজে চিহ্নহীন, B → AC-তে C চিহ্নহীন; C → cC-তে C নিজে; S → AB-তে B আর S → C-তে C চিহ্নহীন। Algorithm থামে, চিহ্নিত শুধু A.

    S চিহ্নিত নয়, তাই L(G3) = ∅ আর ⟨G3⟩ ∈ ECFG: decider গ্রহণ করে। কারণটি সহজ: C থেকে প্রতিটি derivation-এ একটি C থেকে যায় (C → cC), আর B থেকে প্রতিটিতে একটি B বা C থেকে যায়; তাই S থেকে কখনো শুধু terminal-এর string আসে না। ecfg_marking.py-তে E_CFG("S>AB,C;A>aA,a;B>bB,AC;C>cC") চালালে একই ফল: round 1-এ শুধু A, তারপর (True, None).

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

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

ক্রমL-এর recognizer M1 আর L̄-এর recognizer M2 থেকে L-এর decider M বানানো ও চালানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. input w দুটি tape-এ কপি করা, একটি M1-এর, একটি M2-এর জন্য
  2. tape ১-এ M1-এর একটি ধাপ চালানো
  3. tape ২-এ M2-এর একটি ধাপ চালানো
  4. কেউ গ্রহণ না করলে আবার M1-এর পরের ধাপে ফেরা
  5. M1 গ্রহণ করলে গ্রহণ, M2 গ্রহণ করলে বর্জন করে থামা

একটি Turing machine M language L-কে recognize করে, কিন্তু decide করে না। নিচের কোনটি অবশ্যই সত্য?

  • M L-এর কিছু সদস্যে চিরকাল চলে
  • L অবশ্যই undecidable
  • L-এর বাইরের অন্তত একটি string-এ M চিরকাল চলে
  • M L-এর বাইরের কিছু string গ্রহণ করে

একটি language L আর তার complement L̄ দুটিই Turing-recognizable. L সম্পর্কে কী বলা যায়?

  • L অবশ্যই regular
  • L decidable
  • L recognizable কিন্তু undecidable
  • L-এর একটি polynomial সময়ের decider আছে

নিচের কোন operation-এ Turing-recognizable language-এর শ্রেণি বদ্ধ নয়?

  • Union
  • Intersection
  • Concatenation
  • Complement

CFG G-এর নিয়ম: S → AB, A → a, B → bB. ECFG-এর decider (terminal থেকে শুরু করে generating variable চিহ্নিত করা) G-এ কী করে?

  • শুধু A চিহ্নিত হয়, S হয় না; তাই L(G) = ∅ আর decider গ্রহণ করে
  • S চিহ্নিত হয়, তাই L(G) ≠ ∅ আর decider বর্জন করে
  • B → bB অসীম derivation দেয়, তাই decider থামে না
  • কোনো variable চিহ্নিত হয় না

ATM = {⟨M, w⟩ : M একটি TM আর M w-কে গ্রহণ করে} সম্পর্কে কোন বক্তব্যটি সঠিক?

  • ATM decidable, কারণ M-কে w-এর ওপর চালিয়ে দেখলেই হয়
  • ATM Turing-recognizable নয়
  • ATM recognizable, কিন্তু তার complement recognizable নয়
  • ATM আর তার complement দুটিই recognizable

EQDFA decidable প্রমাণে symmetric difference-এর automaton বানিয়ে emptiness পরীক্ষা করা হয়। একই পদ্ধতি EQCFG-এ কাজ করে না কেন?

  • CFG-এর emptiness পরীক্ষা undecidable
  • Context-free language complement আর intersection-এ বদ্ধ নয়
  • CFG-এর membership পরীক্ষা undecidable
  • কিছু CFG-কে Chomsky normal form-এ নেওয়া যায় না

শব্দকোষ

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

মনে রাখুন

  1. Decider সব input-এ থামে; recognizer সদস্যে গ্রহণ করে থামে, বাকিগুলোতে loop করতে পারে। L̄ recognizable হলে L co-recognizable.
  2. ADFA, EDFA, EQDFA, ACFG, ECFG decidable; প্রতিটি CFL decidable. EQCFG undecidable (পর্ব ৫৪)।
  3. ATM recognizable (universal TM U); ETM-এর complement recognizable dovetailing দিয়ে: round i-তে প্রথম i string-এ i ধাপ।
  4. L decidable ⇔ L আর L̄ দুটিই recognizable; প্রমাণে দুই recognizer পালা করে, পরপর নয়।
  5. Decidable শ্রেণি boolean operation, concatenation আর star-এ বদ্ধ; recognizable শ্রেণি union, intersection, concatenation, star-এ বদ্ধ, complement-এ নয়।

পরের পর্বে: Diagonalization আর halting problem: TM-এর সংখ্যা countable অথচ language uncountable, যন্ত্র D দিয়ে ATM-এর undecidability-র পূর্ণ প্রমাণ, আর ATM থেকে HALTTM.

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

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