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

Regular language-এর closure property

Closure Properties of Regular Languages — Boolean Operations, Reversal, Homomorphisms, Quotients and Non-Regularity Proofs

Taught in Bangla, this lesson proves that regular languages are closed under union, intersection, complement, difference, concatenation, star, reversal, homomorphism, inverse homomorphism, quotient, prefix and suffix, each by an explicit construction. It uses closure to prove languages non-regular, for example intersecting with 0*1* to reach 0^n1^n, and measures the reversal blow-up. In-page Python (Pyodide) runs the constructions, and a real automata-lib run checks the same claims.

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

  • Closure property-র সংজ্ঞা, আর কোন operation-এ regular language বদ্ধ তার পূর্ণ তালিকা
  • Reversal, homomorphism, inverse homomorphism আর quotient-এর নির্মাণ ও প্রমাণ
  • Closure ব্যবহার করে কোনো language non-regular প্রমাণ করা, আর এর সাধারণ ভুল
  • কোথায় closure নেই (অসীম union, subset), আর প্রতিটি নির্মাণে state কত বাড়ে
  • প্রতিটি নির্মাণ Python-এ চালিয়ে brute force দিয়ে আর automata-lib দিয়ে যাচাই করা

১ · Closure property — validator জোড়া দেওয়ার গণিত

বাজারঘরের দলের হাতে কয়েকটি তৈরি validator আছে। একটি দেখে অর্ডার কোড BG-dddd ঠিক আছে কি না; আরেকটি দেখে কুপনে “SALE” আছে কি না; আরেকটি সেন্সরের লাইনে 1-এর সংখ্যা জোড় কি না। এখন নতুন নিয়ম আসে: “কুপনে SALE থাকবে, কিন্তু শেষে 0 থাকবে না”, বা “লগ-ফাইল উল্টো দিক থেকে পড়ে একই কোড চেনা”। প্রতিবার নতুন যন্ত্র শূন্য থেকে বানাতে হবে? না। যদি জানা থাকে যে পুরোনো যন্ত্রগুলো জোড়া দিয়ে বানানো নতুন নিয়মও একটি finite automaton দিয়ে চেনা যায়, তাহলে নির্মাণটি যান্ত্রিক।

লেগো-র ইটের কথা ভাবুন। দুটি ইট জোড়া দিলে যা পাবেন, তা-ও লেগো দিয়ে বানানো জিনিস, অন্য কোনো উপাদান লাগে না। Regular language-এর শ্রেণিও এমন: union, intersection, reversal-এর মতো “জোড়া দেওয়ার নিয়ম” দিয়ে যা বানাবেন, তা আবার regular, অর্থাৎ আবার একটি সসীম মেমরির যন্ত্রই সেটি চেনে। গণিতে এই ধর্মের নাম closure: শ্রেণিটি operation-এর অধীনে “বদ্ধ”।

সংজ্ঞা ১.১ (closure)

একটি language-শ্রেণি 𝒞 একটি k-স্থানিক operation op-এর অধীনে বদ্ধ (closed), যদি L1, …, Lk ∈ 𝒞 হলে সবসময় op(L1, …, Lk) ∈ 𝒞. এই পর্বে 𝒞 = REG, Σ-এর ওপর সব regular language-এর শ্রেণি।

Closure property দুটি কাজে লাগে। প্রথমত, নির্মাণ: জটিল নিয়মের যন্ত্র ছোট যন্ত্র জুড়ে বানানো। দ্বিতীয়ত, অসম্ভবতা প্রমাণ: কোনো language L regular ধরে নিয়ে closure দিয়ে একটি জানা non-regular language পাওয়া গেলে L-ও regular হতে পারে না। দ্বিতীয় কাজটি পর্ব ১৭-এর pumping lemma আর পর্ব ১৮-এর Myhill–Nerode-এর পাশে তৃতীয় একটি হাতিয়ার, আর প্রায়ই সবচেয়ে ছোট প্রমাণ দেয়।

প্রমাণের সময় মনে রাখার মতো একটি সুবিধা: পর্ব ১৫-এর Kleene-এর উপপাদ্য অনুযায়ী DFA, NFA, ε-NFA আর regex একই শ্রেণি বর্ণনা করে। তাই প্রতিটি closure-এর জন্য যে মডেলে নির্মাণ সবচেয়ে সহজ, সেটিই নেওয়া যায়: complement-এ DFA, concatenation-এ ε-NFA, homomorphism-এ regex.

এই পর্বের notation: DFA M = (Q, Σ, δ, q0, F), δ total; δ̂ পুরো string-এর transition (কিছু বইয়ে δ∗)। NFA-তে δ : Q × Σε → P(Q). Regex-এ union ∪ (বইয়ে “+”, কোডে “|”), অগ্রাধিকার star > concatenation > union. wR হলো w-এর উল্টো, আর ε ফাঁকা string. কোডে আর stepper-এ star লাইনের ওপরেই * বা ∗ হিসেবে লেখা।

২ · Boolean operation — union, intersection, complement আর difference

এই চারটি পর্ব ০৮-এ পুরো প্রমাণসহ এসেছে, তাই এখানে শুধু সারকথা। দুটি DFA M1 (m state) আর M2 (n state) পাশাপাশি চালানোর product construction-এ state হলো জোড়া (p, q), আর δ((p, q), a) = (δ1(p, a), δ2(q, a)). শুধু accepting সেট বদলে চারটি ফল:

LanguageAccepting জোড়া (p, q)State
L1 ∩ L2p ∈ F1 এবং q ∈ F2m · n
L1 ∪ L2p ∈ F1 অথবা q ∈ F2m · n
L1 ∖ L2p ∈ F1 এবং q ∉ F2m · n
L1 ⊕ L2 (symmetric difference)ঠিক একটি সত্যm · n
L̄1 = Σ∗ ∖ L1(product লাগে না) F বদলে Q ∖ Fm

Complement-এর নির্মাণের একটি শর্ত আছে: DFA-কে সম্পূর্ণ হতে হবে। Partial DFA-তে accepting state অদলবদল করলে যে string মাঝপথে আটকে যায়, সেটি দুই যন্ত্রেই বাতিল হয়; তাই আগে dead state যোগ করতে হয় (পর্ব ০৮-এর অংশ ৫)। আর NFA-তে accepting state অদলবদল করলে complement আসে না, কারণ NFA-র গ্রহণ “অন্তত একটি পথ” শর্তে, আর একই string-এর একটি পথ accepting-এ আর আরেকটি non-accepting-এ শেষ হতে পারে। NFA-র complement নিতে আগে subset construction, তাতে state 2n পর্যন্ত বাড়তে পারে। Difference আসলে L1 ∩ L̄2, আর De Morgan-এর সূত্রে L1 ∪ L2 = Σ∗ ∖ (L̄1 ∩ L̄2), তাই ∩ আর complement থাকলেই চারটি পাওয়া যায়।

৩ · Concatenation আর star — NFA আর regex-এর পথ

DFA দিয়ে concatenation L1L2 চেনা কঠিন: কোথায় L1-এর অংশ শেষ আর L2-এর শুরু, DFA আগে থেকে জানে না। NFA সেই সীমানাটি অনুমান করে নেয়। পর্ব ০৯-এ ε ছাড়াই union, concatenation আর star-এর NFA দেখেছেন, আর পর্ব ১৪-এর Thompson construction একই কাজ ε-তীর দিয়ে নিয়মমাফিক করে। সংক্ষেপে, N1, N2 দুটি ε-NFA হলে:

  • Concatenation: N1-এর প্রতিটি accepting state থেকে N2-এর শুরুতে ε-তীর; accepting শুধু N2-এর accepting state. State m + n.
  • Star: নতুন শুরু s, যা নিজে accepting, s থেকে N1-এর শুরুতে ε, আর প্রতিটি accepting state থেকে N1-এর শুরুতে ফেরার ε. State n + 1. নতুন s না দিয়ে পুরোনো শুরুকে accepting করলে ভুল হয়, কারণ শুরুতে ফেরার পথে আসা string-ও তখন গৃহীত হয়ে যেতে পারে।
  • Union: নতুন শুরু s থেকে দুই শুরুতে ε. State m + n + 1.

Regex দিয়ে প্রমাণটি আরও ছোট: L1 = L(R1) আর L2 = L(R2) হলে L1 ∪ L2 = L(R1 ∪ R2), L1L2 = L(R1R2), L1∗ = L(R1∗). পর্ব ১৩-এর সংজ্ঞাতেই এই তিনটি operation আছে, তাই কিছুই প্রমাণ করার নেই। এই কারণে এই তিনটিকে “regular operation” বলা হয়।

একটি ছোট চমক দিয়ে ধারণাটি যাচাই করা যাক। পর্ব ০৮-এর DIV3 (binary মান ৩ দিয়ে বিভাজ্য, ε ধরে) নিন। DIV3 · DIV3 কী? x আর y দুটিই ৩-এর গুণিতক হলে val(xy) = val(x) · 2|y| + val(y), যা আবার ৩-এর গুণিতক; আর ε ∈ DIV3 বলে প্রতিটি w = w · ε. তাই DIV3 · DIV3 = DIV3, আর একই যুক্তিতে DIV3∗ = DIV3. অংশ ৮-এর সত্যিকারের run-এ automata-lib দুটি সমতাই নিশ্চিত করেছে। Concatenation আর star সবসময় নতুন language বানায় না, কিন্তু যা বানায় তা সবসময় regular.

৪ · Reversal — তীর উল্টে দেওয়া

Reversal: LR = {wR : w ∈ L}. বাজারঘরের সার্ভার লগ-ফাইল কখনো শেষ থেকে পড়ে, কারণ নতুন লাইন শেষে থাকে। তখন প্রশ্ন: যে নিয়ম সামনে থেকে পড়ে চেনা যায়, সেটি পেছন থেকে পড়েও কি একটি সসীম যন্ত্রে চেনা যায়? উত্তর হ্যাঁ, আর নির্মাণটি সুন্দর: DFA-র প্রতিটি তীরের দিক উল্টে দিন, আর শুরু ও accepting-এর ভূমিকা অদলবদল করুন।

উপপাদ্য ৪.১ (reversal)

M = (Q, Σ, δ, q0, F) একটি DFA হলে নিচের ε-NFA N ঠিক L(M)R চেনে:
N = (Q ∪ {s}, Σ, δR, s, {q0}), যেখানে নতুন শুরু s থেকে F-এর প্রতিটি state-এ ε-তীর, আর প্রতিটি p ∈ Q, a ∈ Σ-এর জন্য δR(p, a) = {q ∈ Q : δ(q, a) = p}.

লক্ষ করুন, N একটি NFA, DFA নয়: একটি state-এ একই চিহ্নের অনেক তীর ঢুকতে পারে, উল্টালে সেগুলো বের হওয়া তীর হয়ে যায়; আবার কোনো state-এ কোনো চিহ্নের তীর না-ও ঢুকতে পারে, তখন উল্টো যন্ত্রে সেই চিহ্নে কোথাও যাওয়ার নেই। s থেকে ε-তীরগুলোর কাজ শুধু “F-এর যেকোনো একটি থেকে শুরু করা”; কোডে তাই শুরুতেই সেট F নেওয়া যায়।

প্রমাণ (string-এর দৈর্ঘ্যের ওপর induction, পর্ব ০৪-এর মতো)। δ̂R(S, w) দিয়ে বোঝাই, state-সেট S থেকে শুরু করে w পড়ে N যে state-গুলোতে থাকতে পারে (s বাদে)। দাবি: সব p, q ∈ Q আর w-এর জন্য

δ̂(q, w) = p  ⇔  q ∈ δ̂R({p}, wR)
  1. ভিত্তি, w = ε: δ̂(q, ε) = q, আর δ̂R({p}, ε) = {p}. তাই দুই দিকই বলে q = p. — δ̂-এর সংজ্ঞা
  2. ধাপ, w = va: δ̂(q, va) = p ⇔ এমন r আছে যাতে δ̂(q, v) = r আর δ(r, a) = p. — δ̂(q, va) = δ(δ̂(q, v), a)
  3. δ(r, a) = p ⇔ r ∈ δR({p}, a); আর induction hypothesis অনুযায়ী δ̂(q, v) = r ⇔ q ∈ δ̂R({r}, vR). — δR-এর সংজ্ঞা আর |v| < |w|
  4. দুটি মিলিয়ে: q ∈ δ̂R({p}, a vR), আর a vR = (va)R. — (uv)R = vRuR, পর্ব ০৩
  5. এখন w ∈ L(M) ⇔ কোনো f ∈ F-এ δ̂(q0, w) = f ⇔ q0 ∈ δ̂R(F, wR) ⇔ N, wR গ্রহণ করে। তাই L(N) = L(M)R. ∎ — s থেকে ε-তীর F-এ, আর N-এর accepting শুধু q0

Regex দিয়েও একটি দ্বিতীয় প্রমাণ আছে, regex-এর গঠনের ওপর structural induction: ∅R = ∅, εR = ε, aR = a; (R1 ∪ R2)R = R1R ∪ R2R; (R1R2)R = R2RR1R (ক্রম উল্টায়); (R∗)R = (RR)∗. প্রতিটি নিয়মে ফল আবার একটি regex, আর মাপও একই থাকে। যেমন (a ∪ b)∗ab-এর উল্টো ba(a ∪ b)∗.

“ab দিয়ে শেষ” থেকে “ba দিয়ে শুরু”

উপরে মূল DFA E (শুরু q0, accepting q2). নিচে প্রতিটি তীর উল্টানো NFA: শুরু q2 (পুরোনো accepting), accepting q0 (পুরোনো শুরু)।

Reversal of the DFA for strings ending with ab q0q1q2 q0q1q2 abab ba abab ba মূল DFAউল্টো NFA
ছবি ১৬.১ — নিচের যন্ত্রে q1 থেকে a-তে তিনটি তীর (q0, q1, q2), আর q0 ও q2 থেকে a-তে কোনো তীর নেই: উল্টানোর পর যন্ত্রটি আর deterministic নয়। একটিই accepting state ছিল বলে নতুন s না দিয়ে সরাসরি q2-কে শুরু ধরা হয়েছে।
1মূল DFA E2প্রতিটি তীর উল্টানো3শুরু আর accepting অদলবদল4baa পড়া: প্রথম b5তারপর a, a6abb পড়া
এই ধাপের অবস্থা
তীর
বর্তমান সেট
ফল
  1. মূল DFA. E চেনে “ab দিয়ে শেষ”: q1 মানে শেষ চিহ্ন a, q2 মানে শেষ দুটি ab. শুরু q0, accepting শুধু q2. ছয়টি তীর, প্রতিটি state আর চিহ্নে একটি।
  2. তীর উল্টানো। প্রতিটি q →a p তীর হয়ে যায় p →a q. q1-এ a-তীর ঢুকত তিনটি state থেকে (q0, q1, q2), তাই উল্টো যন্ত্রে q1 থেকে a পড়ে তিন দিকে যাওয়া যায়। q0-তে b-তীর ঢুকত q0 আর q2 থেকে, তাই q0 থেকে b-তে q0 আর q2.
  3. শুরু আর accepting. পুরোনো accepting q2 এখন শুরু (একটিই ছিল, তাই নতুন s লাগেনি), আর পুরোনো শুরু q0 এখন একমাত্র accepting. লক্ষ্য: L(E)R = “ba দিয়ে শুরু”।
  4. baa: প্রথম b. শুরু-সেট {q2}. q2 থেকে b-তে একমাত্র তীর q1-এ, তাই সেট {q1}. এখনো q0 সেটে নেই, অর্থাৎ “b” গৃহীত নয়; ঠিকই, কারণ b-এর উল্টো b, যা ab দিয়ে শেষ নয়।
  5. তারপর a, a. q1 থেকে a-তে {q0, q1, q2}. পরের a-তে শুধু q1-এর a-তীর আছে, তাই আবার {q0, q1, q2}. শেষে q0 সেটে আছে: baa গৃহীত। এর উল্টো aab সত্যিই ab দিয়ে শেষ।
  6. abb পড়া। {q2} থেকে a-তে কোনো তীর নেই, সেট ∅, আর ∅ থেকে কোথাও যাওয়া যায় না: বাতিল। abb-এর উল্টো bba ab দিয়ে শেষ নয়, তাই ঠিক। এই NFA-র subset construction-এ ৪টি reachable সেট আসে ({q2}, {q1}, {q0, q1, q2}, ∅): “ba দিয়ে শুরু”-র minimal DFA-ও ৪ state-এর।

নিচের Python ব্লক উপপাদ্যটি সরাসরি কোডে লেখে। NFA এখানে একটি dictionary, যেখানে starts একটি সেট: “নতুন s থেকে F-এ ε-তীর” লেখার বদলে শুরুতেই F নেওয়া, যা একই কথা। এরপর দৈর্ঘ্য 10 পর্যন্ত সব string-এ উল্টো যন্ত্রকে সংজ্ঞার সঙ্গে মেলানো হয়। এই ব্লকের function-গুলো অংশ ৬-এর ব্লকও ব্যবহার করবে (data-shared), তাই আগে এটি চালান।

from itertools import product

def words(sigma, n):                         # all strings of length 0..n
    return ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]

def dfa_accepts(d, w):
    q = d["start"]
    for c in w: q = d["delta"][q, c]
    return q in d["final"]

def nfa_accepts(n, w):                       # follow the set of current states
    S = set(n["starts"])
    for c in w: S = {p for q in S for p in n["delta"].get((q, c), ())}
    return bool(S & n["final"])

def reverse(d):                              # flip arrows, swap start and accept
    delta = {}
    for (q, c), p in d["delta"].items():
        delta.setdefault((p, c), set()).add(q)
    return {"starts": set(d["final"]), "final": {d["start"]}, "delta": delta}

# E = "ends with ab" over {a, b}
E = {"start": "q0", "final": {"q2"}, "delta": {
     ("q0", "a"): "q1", ("q0", "b"): "q0", ("q1", "a"): "q1",
     ("q1", "b"): "q2", ("q2", "a"): "q1", ("q2", "b"): "q0"}}
R = reverse(E)
for (p, c), qs in sorted(R["delta"].items()):
    print(f"  {p} --{c}--> {sorted(qs)}")
ws = words("ab", 10)
bad = sum(nfa_accepts(R, w) != dfa_accepts(E, w[::-1]) for w in ws)
print("reversed NFA vs definition:", bad, "errors on", len(ws), "strings")
print("same as 'starts with ba':", all(nfa_accepts(R, w) == w.startswith("ba") for w in ws))
for w in ["bab", "abb", "ba"]:
    print(f"  {w}: {nfa_accepts(R, w)}")

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

  q0 --b--> ['q0', 'q2']
  q1 --a--> ['q0', 'q1', 'q2']
  q2 --b--> ['q1']
reversed NFA vs definition: 0 errors on 2047 strings
same as 'starts with ba': True
  bab: True
  abb: False
  ba: True

প্রথম তিন লাইন ছবির নিচের অংশের তীর: ছয়টি উল্টানো তীর তিনটি (state, চিহ্ন) জোড়ায় জমা হয়েছে, আর বাকি তিনটি জোড়ায় (যেমন q0 থেকে a) কোনো তীর নেই, তাই dict.get ফাঁকা tuple দেয়। দৈর্ঘ্য 0 থেকে 10-এর সব 2047টি string-এ “N, w গ্রহণ করে” আর “E, wR গ্রহণ করে” একমত; আর উল্টো language-টি ঠিক “ba দিয়ে শুরু”। w[::-1] হলো Python-এ string উল্টানো। Brute force প্রমাণের বিকল্প নয়, কিন্তু নির্মাণ বা কোডে ভুল থাকলে সাধারণত এখানেই ধরা পড়ে।

৫ · Homomorphism আর inverse homomorphism

পর্ব ০৩-এ homomorphism দেখেছেন: h : Σ → Γ∗ প্রতিটি চিহ্নের জায়গায় একটি নির্দিষ্ট string বসায়, আর h(uv) = h(u)h(v) নিয়মে পুরো string-এ ছড়ায়। Language-এ h(L) = {h(w) : w ∈ L}. উল্টো দিকে inverse homomorphism: L ⊆ Γ∗ হলে h−1(L) = {w ∈ Σ∗ : h(w) ∈ L}, অর্থাৎ যেসব string-এর ছবি L-এ পড়ে।

বাজারঘরের উদাহরণেই দুটি ধারণা লুকিয়ে আছে। এই কোর্সে অর্ডার কোড BG-dddd-এর DFA বানানো হয়েছে ছোট alphabet {B, G, -, d}-এর ওপর, যেখানে d মানে “যেকোনো অঙ্ক”। এই বিমূর্ততা নিজেই একটি homomorphism: h(0) = h(1) = ⋯ = h(9) = d, আর h(B) = B, h(G) = G, h(-) = -. সত্যিকারের কোডের language তাহলে h−1(L(BG-dddd)): যেসব string-এর প্রতিটি অঙ্ক d-তে বদলালে BG-dddd ধাঁচ মেলে। পরের উপপাদ্য বলে, ১৩ চিহ্নের আসল alphabet-এর ওপরেও ঠিক একই সংখ্যক state-এর একটি DFA আছে।

উপপাদ্য ৫.১ (homomorphism)

L ⊆ Σ∗ regular আর h : Σ → Γ∗ একটি homomorphism হলে h(L) regular. নির্মাণ: L = L(R) হলে R-এর প্রতিটি চিহ্ন a-এর জায়গায় h(a) বসান (h(a) = ε হলে ε)। নতুন regex h(R)-এর জন্য L(h(R)) = h(L(R)).

প্রমাণ (R-এর গঠনের ওপর structural induction). ভিত্তি: h(∅) = ∅, h(ε) = ε, আর একক চিহ্ন a-তে L(h(a)) = {h(a)}. ধাপে তিনটি সূত্র লাগে, প্রতিটি h(uv) = h(u)h(v) থেকে আসে: h(L1 ∪ L2) = h(L1) ∪ h(L2); h(L1L2) = h(L1)h(L2), কারণ h(uv)-এর প্রতিটি রূপ h(u)h(v); আর h(L∗) = h(L)∗, কারণ h(w1⋯wk) = h(w1)⋯h(wk). তিন ক্ষেত্রেই induction hypothesis উপ-regex-এ বসিয়ে দাবি মেলে। ∎ উদাহরণ: h(a) = 01, h(b) = 1 হলে h((ab)∗) = (011)∗.

উপপাদ্য ৫.২ (inverse homomorphism)

M = (Q, Γ, δ, q0, F) একটি DFA আর h : Σ → Γ∗ হলে M′ = (Q, Σ, δ′, q0, F), যেখানে δ′(q, a) = δ̂(q, h(a)), ঠিক h−1(L(M)) চেনে। State একই, শুধু alphabet আর তীর বদলায়।

প্রমাণ (|w|-এর ওপর induction): দাবি δ̂′(q, w) = δ̂(q, h(w)). w = ε-তে দুই পাশই q, কারণ h(ε) = ε. w = va-তে δ̂′(q, va) = δ′(δ̂′(q, v), a) = δ̂(δ̂(q, h(v)), h(a)) = δ̂(q, h(v)h(a)) = δ̂(q, h(va)); মাঝের সমতায় induction hypothesis আর δ′-এর সংজ্ঞা, শেষে h(va) = h(v)h(a). তাই w ∈ L(M′) ⇔ δ̂(q0, h(w)) ∈ F ⇔ h(w) ∈ L(M). ∎ নির্মাণটি যন্ত্রকে একটুও বড় করে না: M′-এর প্রতিটি তীর আসলে M-এর ওপর h(a) নামের একটি ছোট “শর্টকাট”।

নিচের stepper-এ DIV3-এর ওপর এই নির্মাণ, h(a) = 01 আর h(b) = 1 নিয়ে। DIV3-এর state qr মানে এ পর্যন্ত পড়া মানের ৩ দিয়ে ভাগশেষ r; একটি bit b পড়লে r থেকে (2r + b) mod 3.

1h আর DIV3 প্রস্তুত2δ′(q0, a) = δ̂(q0, 01)3δ′(q1, a) = δ̂(q1, 01)4δ′(q2, a) = δ̂(q2, 01)5b-এর সারি: δ̂(q, 1)6ab আর ba পরীক্ষা7brute force যাচাই
এই ধাপের হিসাব
হিসাব
δ′ টেবিল
  1. প্রস্তুতি। h : {a, b} → {0, 1}∗, h(a) = 01, h(b) = 1. নতুন যন্ত্রে state একই তিনটি, শুরু আর accepting q0-ই; শুধু ছয়টি তীর (৩ state × ২ চিহ্ন) বের করতে হবে। টেবিলের কলাম q0, q1, q2.
  2. (q0, a). DIV3-কে q0 থেকে 01 পড়ান: 0 পড়ে q0-তেই (0 · 2 + 0 = 0), তারপর 1 পড়ে q1 (0 · 2 + 1 = 1). তাই δ′(q0, a) = q1.
  3. (q1, a). q1 থেকে 0 পড়ে q2 (2 · 1 = 2), তারপর 1 পড়ে (2 · 2 + 1 = 5, ভাগশেষ 2) আবার q2. তাই δ′(q1, a) = q2.
  4. (q2, a). q2 থেকে 0 পড়ে q1 (4, ভাগশেষ 1), তারপর 1 পড়ে q0 (3, ভাগশেষ 0). তাই δ′(q2, a) = q0. পুরো a-সারিটি বলে, a পড়া মানে ভাগশেষে 1 যোগ, কারণ r থেকে 4r + 1 ≡ r + 1 (mod 3).
  5. b-এর সারি। h(b) = 1 একক চিহ্ন, তাই এক ধাপ: q0 থেকে q1, q1 থেকে q0 (3), q2 থেকে q2 (5, ভাগশেষ 2). টেবিল পূর্ণ।
  6. পরীক্ষা। ab: q0 থেকে a-তে q1, b-তে q0, গৃহীত; সত্যিই h(ab) = 011, মান 3. ba: q0 থেকে b-তে q1, a-তে q2, বাতিল; h(ba) = 101, মান 5, ভাগশেষ 2, আর যন্ত্রও ঠিক q2-তে থেমেছে।
  7. যাচাই। দৈর্ঘ্য 0 থেকে 10-এর সব 2047টি {a, b}-string-এ নতুন DFA-র উত্তর আর “h(w)-এর মান ৩ দিয়ে বিভাজ্য” মিলিয়ে একটিও অমিল নেই (অংশ ৬-এর Python ব্লকের প্রথম অংশ)।

একটি সতর্কতা: h(L) regular হলে L regular, এমন কোনো কথা নেই। h(0) = h(1) = ε নিলে যেকোনো L ≠ ∅-এর ছবি {ε}, যা regular, অথচ L নিজে যা খুশি হতে পারে। Closure শুধু এক দিকে কাজ করে: regular থেকে regular-এ। তবে contrapositive-টি কাজের: h(L) non-regular হলে L-ও non-regular, আর h−1(L) non-regular হলে L-ও non-regular. অংশ ৭-এ এই দিকটি ব্যবহার হবে।

৬ · Quotient, prefix আর suffix

অনেক সময় একটি string-এর শেষ অংশ কেটে ফেলতে হয়। বাজারঘরের লগে প্রতিটি অর্ডার কোডের শেষে একটি চেক-অঙ্ক বসে; চেক-অঙ্ক বাদ দিলে কোন কোডগুলো বাকি থাকে? এই প্রশ্নের গণিত হলো right quotient:

L/M = { x ∈ Σ∗ : এমন y ∈ M আছে যাতে xy ∈ L }

কথায়: x এমন একটি string, যার পরে M থেকে কোনো একটি y জুড়লে L-এর সদস্য হয়। যেমন L = {abc, abd, xyz} আর M = {c, z} হলে L/M = {ab, xy}. দুটি বিশেষ রূপ: L/Σ∗ = Pref(L), L-এর string-গুলোর সব prefix; আর L/{ε} = L.

উপপাদ্য ৬.১ (right quotient)

L regular আর M যেকোনো language (regular না হলেও) হলে L/M regular. নির্মাণ: L-এর DFA ML = (Q, Σ, δ, q0, F) নিন, শুধু accepting সেট বদলান:
F′ = { q ∈ Q : এমন y ∈ M আছে যাতে δ̂(q, y) ∈ F }.

প্রমাণ: x ∈ L(M′) ⇔ δ̂(q0, x) ∈ F′ ⇔ এমন y ∈ M আছে যাতে δ̂(δ̂(q0, x), y) ∈ F ⇔ এমন y ∈ M আছে যাতে δ̂(q0, xy) ∈ F ⇔ x ∈ L/M. মাঝের ধাপে δ̂(q, xy) = δ̂(δ̂(q, x), y). ∎

প্রমাণটি ছোট, কিন্তু এর একটি গভীর দিক আছে। এটি বলে F′ আছে, কিন্তু কীভাবে বের করতে হবে, তা বলে না। Q সসীম, তাই F′ হলো Q-এর 2|Q|টি subset-এর একটি, আর তাই L/M regular. কিন্তু M যদি একটি Turing machine-এর language হিসেবে দেওয়া থাকে, তাহলে “এমন y আছে কি না” প্রশ্নটি সাধারণভাবে কোনো algorithm দিয়ে উত্তর দেওয়া যায় না (Turing machine-এর language ফাঁকা কি না, সেই প্রশ্নই undecidable; পর্ব ৫০–৫২)। এ ধরনের প্রমাণকে বলে অ-গঠনমূলক (non-constructive): অস্তিত্ব প্রমাণিত, নির্মাণের পদ্ধতি নয়।

M regular হলে F′ বের করা যায়, আর তার একটি সহজ সীমাও আছে। ধরুন M-এর DFA-তে k-টি state. q থেকে y পড়ার সময় দুই যন্ত্র পাশাপাশি চালালে জোড়া-state থাকে বড়জোর |Q| · k রকম। |y| ≥ |Q| · k হলে pigeonhole নীতিতে কোনো জোড়া দুবার আসে, আর মাঝের চক্রটি কেটে ফেললে একটি ছোট y পাওয়া যায়, যা-ও কাজ করে। তাই দৈর্ঘ্য < |Q| · k-এর y পরীক্ষা করাই যথেষ্ট। পর্ব ২০-এ একই কাজ product আর BFS দিয়ে আরও দ্রুত করা হবে।

Prefix আর suffix: Pref(L) = L/Σ∗, তাই F′ = “যেসব state থেকে F-এ পৌঁছানো যায়”, একটি উল্টো BFS. Suf(L) = {y : কোনো x-এর জন্য xy ∈ L} বানাতে NFA নিন: নতুন শুরু s থেকে q0 থেকে reachable প্রতিটি state-এ ε-তীর, কারণ x পড়ে যেকোনো reachable state-এ পৌঁছানো যায়। অথবা reversal দিয়ে: Suf(L) = (Pref(LR))R. বামের quotient M\L = {y : কোনো x ∈ M-এর জন্য xy ∈ L}-ও একইভাবে regular: M\L = (LR/MR)R. আর substring-এর সেট = Suf(Pref(L)). বাজারঘরের অর্ডার কোডের ভাষা {BG-dddd}-এর suffix ৮টি: ε, d, dd, ddd, dddd, -dddd, G-dddd আর BG-dddd নিজে।

নিচের ব্লক দুটি নির্মাণ চালায়, আর অংশ ৪-এর ব্লকের words আর dfa_accepts ব্যবহার করে। প্রথমে stepper-এর inverse homomorphism; তারপর DIV3-এর তিনটি quotient, M-এর জন্য যথাক্রমে {1}, 1∗ আর Σ∗ (শেষটি মানে Pref). re এখানে শুধু “y ∈ M কি না” যাচাইয়ে, আর y-এর দৈর্ঘ্যের সীমা উপরের pigeonhole যুক্তির n · k.

import re
# DIV3: binary value divisible by 3; state = remainder so far
D = {"start": 0, "final": {0},
     "delta": {(r, b): (2 * r + int(b)) % 3 for r in range(3) for b in "01"}}
def run(d, q, w):                            # δ̂(q, w)
    for c in w: q = d["delta"][q, c]
    return q

# inverse homomorphism: same states, one arrow per (q, x) = run of h(x)
h = {"a": "01", "b": "1"}
inv = {"start": 0, "final": {0},
       "delta": {(q, x): run(D, q, h[x]) for q in range(3) for x in "ab"}}
print("h^-1 DFA:", "  ".join(f"q{q}-{x}->q{p}" for (q, x), p in inv["delta"].items()))
H = lambda w: "".join(h[c] for c in w)
ws = words("ab", 10)
print("errors vs definition:", sum(dfa_accepts(inv, w) != dfa_accepts(D, H(w)) for w in ws),
      "of", len(ws))

# right quotient L/M: same DFA, new accepting set F' = {q : some y in M leads q into F}
def quotient_finals(d, n, M, k):             # n = |Q|, k = states of a DFA for M
    ys = [y for y in words("01", n * k) if re.fullmatch(M, y)]   # |y| < n*k suffices
    return {q for q in range(n) if any(run(d, q, y) in d["final"] for y in ys)}, ys
for M, k in [("1", 3), ("1*", 2), ("(0|1)*", 1)]:
    F2, ys = quotient_finals(D, 3, M, k)
    Q = dict(D, final=F2)
    ok = all(dfa_accepts(Q, x) == any(dfa_accepts(D, x + y) for y in ys)
             for x in words("01", 7))
    print(f"DIV3 / L({M}): F' = {sorted(F2)}, brute force agrees: {ok}")

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

h^-1 DFA: q0-a->q1  q0-b->q1  q1-a->q2  q1-b->q0  q2-a->q0  q2-b->q2
errors vs definition: 0 of 2047
DIV3 / L(1): F' = [1], brute force agrees: True
DIV3 / L(1*): F' = [0, 1], brute force agrees: True
DIV3 / L((0|1)*): F' = [0, 1, 2], brute force agrees: True

প্রথম লাইন stepper-এর টেবিল, হুবহু। তারপর তিনটি quotient. DIV3/{1}-এ F′ = {q1}: শেষে একটি 1 জুড়লে মান ৩-এর গুণিতক হয় ঠিক তখন, যখন আগের মানের ভাগশেষ 1 (2 · 1 + 1 = 3). অর্থাৎ DIV3/{1} = “ভাগশেষ 1”-এর language, নতুন একটি state-ও লাগেনি। 1∗-এ F′ = {q0, q1}: q2 থেকে 1 পড়লে 2 · 2 + 1 = 5, ভাগশেষ আবার 2, তাই q2 থেকে কোনো সংখ্যক 1 দিয়েই q0-তে ফেরা যায় না। আর Pref(DIV3) = Σ∗: যেকোনো binary string-এর পরে কিছু bit জুড়ে ৩-এর গুণিতক বানানো যায়। Q এখানে dict(D, final=F2): একই dictionary, শুধু final বদলানো, ঠিক উপপাদ্যের মতো।

৭ · Closure দিয়ে non-regular প্রমাণ

এবার closure-এর দ্বিতীয় কাজ। কৌশলটি contradiction: L regular ধরে নিন; regular language-এর সঙ্গে closure-এর operation চালিয়ে একটি language পান, যা আগে থেকেই non-regular বলে জানা। তাহলে অনুমানটি মিথ্যা। এই কৌশলের জন্য অন্তত একটি “ভিত্তি” non-regular language দরকার। পর্ব ১৭ আর ১৮ এর জন্য পূর্ণ যন্ত্রপাতি দেবে; এখানে মূল উদাহরণটির একটি ছোট, সম্পূর্ণ প্রমাণ।

Lemma ৭.১

Σ = {0, 1}-এর ওপর B = {0n1n : n ≥ 0} regular নয়।

  1. ধরুন B regular, আর k-state একটি DFA M এটি চেনে। — contradiction-এর জন্য অনুমান
  2. k + 1টি string ε, 0, 00, …, 0k পড়লে M কোনো state-এ থামে; state মাত্র k-টি, তাই এমন i < j আছে যাতে 0i আর 0j একই state-এ থামে। — pigeonhole নীতি
  3. একই state থেকে একই 1i পড়লে একই state-এ পৌঁছায়, তাই M হয় 0i1i আর 0j1i দুটিই গ্রহণ করে, নয়তো দুটিই বাতিল। — DFA deterministic
  4. কিন্তু 0i1i ∈ B আর 0j1i ∉ B (i ≠ j). বিরোধ; তাই B regular নয়। ∎ — B-এর সংজ্ঞা

এই যুক্তিই পর্ব ১০-এর fooling set: ε, 0, 00, … string-গুলোর প্রতিটি জোড়াকে কোনো একটি suffix আলাদা করে, আর অসীম সংখ্যক এমন string থাকলে কোনো সসীম DFA যথেষ্ট নয়। এবার এই ভিত্তির ওপর closure দিয়ে আরও কয়েকটি language.

1অনুমান: EQ regular20*1* regular3∩-এ closure4ছেদটি হিসাব5Lemma ৭.১6বিরোধ7একই কৌশল, complement
এই ধাপের যুক্তি
দাবি
কারণ
  1. অনুমান। EQ = {w ∈ {0, 1}∗ : w-এ 0 আর 1 সমান সংখ্যক}. ধরুন EQ regular. লক্ষ্য একটি বিরোধ। EQ-এর string-এ 0 আর 1 যেকোনো ক্রমে আসতে পারে (যেমন 1010), তাই সরাসরি Lemma ৭.১ খাটে না।
  2. ছাঁকনি। 0∗1∗ নিজেই একটি regex, তাই এর language regular. এটিই “ছাঁকনি”: যেসব string-এ সব 0 আগে আর সব 1 পরে, শুধু সেগুলো রাখে।
  3. Closure. দুটি regular language-এর intersection regular (product construction, পর্ব ০৮)। তাই অনুমান সত্য হলে EQ ∩ 0∗1∗-ও regular হতে হবে।
  4. ছেদ হিসাব। 0∗1∗-এর string 0i1j; এটি EQ-তে থাকে ঠিক তখন, যখন i = j. তাই ছেদ = B = {0n1n}. দৈর্ঘ্য ≤ 10 পর্যন্ত brute force-এ ছেদে ঠিক ε, 01, 0011, 000111, 00001111, 0000011111 আসে।
  5. ভিত্তি। Lemma ৭.১ অনুযায়ী B regular নয়।
  6. বিরোধ। ধাপ ৩ বলছে B regular, ধাপ ৫ বলছে নয়। ধাপ ৩ পর্যন্ত একমাত্র অপ্রমাণিত কথা ছিল ধাপ ১-এর অনুমান, তাই সেটিই মিথ্যা: EQ regular নয়। ∎
  7. Complement-এর পালা। NEQ = {0i1j : i ≠ j}. NEQ regular হলে তার complement regular, আর complement ∩ 0∗1∗ = B (0∗1∗-এর যে string NEQ-তে নেই, তাতে i = j). আবার বিরোধ, তাই NEQ-ও regular নয়।

Homomorphism-এর contrapositive দিয়ে আরেকটি উদাহরণ। বাজারঘরের অর্ডার-query ভাষায় সুষম বন্ধনী BAL লাগে। ধরুন BAL regular. তাহলে BAL ∩ [∗]∗ = {[n]n}-ও regular (এখানে বন্ধনী দুটি [ আর ]). এখন h([) = 0, h(]) = 1 নিলে h({[n]n}) = B, যা regular হতো উপপাদ্য ৫.১ অনুযায়ী। বিরোধ, তাই BAL regular নয়। আর context-free language-এ (পর্ব ২৫) BAL সহজেই ধরা যায়।

নিচের ব্লক দুটি জিনিস দেখায়। প্রথমত, EQ ∩ 0∗1∗-এর brute-force হিসাব। দ্বিতীয়ত, Lemma ৭.১-এর প্রমাণকে একটি algorithm হিসেবে: যেকোনো DFA দিলে সেটি 00, 01, … পড়িয়ে প্রথম পুনরাবৃত্ত state খোঁজে, আর সেখান থেকে একটি নির্দিষ্ট string বের করে, যেখানে যন্ত্রটি ভুল করে। পরীক্ষার জন্য একটি “AI-এর DFA”, যা cap পর্যন্ত 0 গুনতে পারে।

from itertools import product
words = lambda n: ["".join(t) for k in range(n + 1) for t in product("01", repeat=k)]
EQ = lambda w: w.count("0") == w.count("1")          # equal numbers of 0 and 1
in_0s1s = lambda w: "10" not in w                    # w in L(0*1*)
both = [w or "ε" for w in words(10) if EQ(w) and in_0s1s(w)]
print("EQ ∩ 0*1* (length <= 10):", both)

def ai_dfa(cap):          # a "DFA for 0^n 1^n" that can only count up to cap
    d = {}
    for i in range(cap + 1):
        d["Z", i] = {"0": ("Z", min(i + 1, cap)), "1": ("O", i, 1) if i else "dead"}
        for j in range(1, i + 1):
            d["O", i, j] = {"0": "dead", "1": ("O", i, j + 1) if j < i else "dead"}
    d["dead"] = {"0": "dead", "1": "dead"}
    final = {("Z", 0)} | {("O", i, i) for i in range(1, cap + 1)}
    return d, ("Z", 0), final

def run(d, q, w):
    for c in w: q = d[q][c]
    return q

def find_mistake(d, start, final):  # pigeonhole on 0^0, 0^1, ..., 0^k
    seen, q, i = {}, start, 0
    while q not in seen:
        seen[q] = i; q = d[q]["0"]; i += 1
    j = seen[q]                      # 0^j and 0^i end in the same state, j < i
    if run(d, start, "0" * j + "1" * j) not in final:
        return "0" * j + "1" * j, "rejected but in L"
    return "0" * i + "1" * j, "accepted but not in L"

for cap in [3, 10]:
    d, s, F = ai_dfa(cap)
    w, why = find_mistake(d, s, F)
    print(f"cap={cap}: {len(d)} states, mistake on 0^{w.count('0')} 1^{w.count('1')}: {why}")

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

EQ ∩ 0*1* (length <= 10): ['ε', '01', '0011', '000111', '00001111', '0000011111']
cap=3: 11 states, mistake on 0^4 1^3: accepted but not in L
cap=10: 67 states, mistake on 0^11 1^10: accepted but not in L

প্রথম লাইন stepper-এর ধাপ ৪. তারপর find_mistake: cap = 3-এর ১১-state DFA-তে 03 আর 04 একই state (“Z”, 3)-এ থামে, কারণ যন্ত্রটি ৩-এর বেশি গুনতে পারে না। তাই 0313 গ্রহণ করলে 0413-ও গ্রহণ করে, যা B-তে নেই। cap = 10-এ ৬৭টি state, তবু ভুল আসে 011110-এ। State যত বাড়ান, ভুল শুধু আরও লম্বা string-এ সরে যায়, কখনো মোছে না: ঠিক Lemma ৭.১-এর কথা। কোডটি কোনো নির্দিষ্ট DFA-র ওপর নির্ভর করে না; যেকোনো DFA দিলে একটি counterexample দেবে।

চারটি সাধারণ ভুল। (১) Non-regular language-এর সঙ্গে ছেদ: EQ ∩ B = B দেখিয়ে কিছু প্রমাণ হয় না, কারণ closure শুধু দুটি regular language-এর ক্ষেত্রে খাটে; ছাঁকনিটি সবসময় regular হতে হবে। (২) Subset-এর ভুল: “B ⊆ 0∗1∗ আর 0∗1∗ regular, তাই B regular” মিথ্যা; Σ∗ regular, আর প্রতিটি language তার subset. (৩) উল্টো দিক: L1 ∪ L2 regular হলে L1, L2 regular, এমন নয়: EQ ∪ (EQ-এর complement) = Σ∗. (৪) ভিত্তি ছাড়া যুক্তি: শেষে যে language পাওয়া গেল, তার non-regularity আগে প্রমাণিত (Lemma ৭.১, পর্ব ১৭–১৮) হতে হবে; “দেখতে কঠিন” যথেষ্ট নয়।

৮ · কোথায় closure ভাঙে, আর প্রতিটি নির্মাণের খরচ

অসীম union-এ closure নেই। প্রতিটি n-এর জন্য {0n1n} একটি এক-string-এর language, তাই regular. কিন্তু সব n-এর union B, যা regular নয়। দুটি, তিনটি বা যেকোনো সসীম সংখ্যক regular language-এর union regular (দুটির ফল থেকে induction-এ), কিন্তু অসীম সংখ্যকের নয়। একই কারণে অসীম intersection-এও নেই: De Morgan-এ ⋂n (Σ∗ ∖ {0n1n}) = Σ∗ ∖ B, যা regular হলে complement নিয়ে B regular হতো। আর অংশ ৭-এর ভুল (২) অনুযায়ী subset নেওয়ায়ও closure নেই। এর মানে হলো, প্রতিটি সসীম language regular হলেও “অনেক ছোট নিয়ম মিলে একটি বড় নিয়ম” সবসময় regular নয়।

যে operation-এ closure আছে, সেখানেও যন্ত্রের আকার কত বাড়ে, সেটি বাস্তবে গুরুত্বপূর্ণ। একটি language-এর minimal DFA-র state-সংখ্যাকে বলে তার state complexity. সারণিতে এই পর্বের নির্মাণগুলোর খরচ (m আর n হলো ইনপুট যন্ত্রের state):

Operationসহজ নির্মাণফলের আকার
∪, ∩, ∖, ⊕DFA-র productm · n
Complementসম্পূর্ণ DFA, F অদলবদলn (DFA); NFA থেকে 2n পর্যন্ত
Concatenationε-NFA জোড়াNFA m + n; DFA-তে প্রায় m · 2n পর্যন্ত
Starε-NFA, নতুন শুরুNFA n + 1; DFA-তে প্রায় ¾ · 2n পর্যন্ত
Reversalতীর উল্টানো NFANFA n + 1; DFA-তে 2n পর্যন্ত
Homomorphismregex-এ h(a) বসানোregex-এর দৈর্ঘ্য বড়জোর |R| · max|h(a)|
Inverse homomorphismδ′(q, a) = δ̂(q, h(a))n, একই state
Quotient L/M (M regular)শুধু F বদলানোn; F′ বের করতে প্রতি state-এ একটি খোঁজ

Reversal-এর লাফটি নিজে দেখা যাক। “শুরু থেকে n-তম চিহ্ন 1” language-এর DFA-তে মাত্র n + 2টি state (n − 1টি গোনার state, তারপর পরীক্ষার state, আর দুটি ফাঁদ)। এর reversal “শেষ থেকে n-তম চিহ্ন 1”, যার যেকোনো DFA-তে অন্তত 2nটি state লাগে বলে পর্ব ১০-এ প্রমাণ হয়েছে। নিচের JavaScript ব্লক তীর উল্টে subset construction চালায়, শুধু reachable সেট গুনে।

// Reversal blow-up: DFA for "n-th symbol from the start is 1" (n + 2 states),
// reversed into an NFA, then subset construction (reachable subsets only).
function forward(n) {             // states 0..n-1 count, "Y" = yes trap, "N" = no trap
  const d = {};
  for (let i = 0; i < n - 1; i++) d[i] = { 0: i + 1, 1: i + 1 };
  d[n - 1] = { 0: "N", 1: "Y" };
  d.Y = { 0: "Y", 1: "Y" }; d.N = { 0: "N", 1: "N" };
  return d;                        // start 0, accepting {"Y"}
}
function reversedSubsets(d) {
  const back = {};                 // back[p][c] = all q with d[q][c] = p
  for (const q in d) for (const c of "01") ((back[d[q][c]] ??= { 0: [], 1: [] })[c]).push(q);
  const key = S => [...S].sort().join(",");
  const startSet = new Set(["Y"]); // old accepting states; accept if "0" is inside
  const seen = new Map([[key(startSet), startSet]]), todo = [startSet];
  while (todo.length) {
    const S = todo.pop();
    for (const c of "01") {
      const T = new Set([...S].flatMap(p => back[p]?.[c] ?? []));
      if (!seen.has(key(T))) { seen.set(key(T), T); todo.push(T); }
    }
  }
  return seen;
}
const t0 = performance.now();
for (let n = 1; n <= 12; n++) {
  const d = forward(n), subs = reversedSubsets(d);
  const accepting = [...subs.values()].filter(S => S.has("0")).length;
  const empty = subs.has("") ? "yes" : "no";
  console.log(`n=${String(n).padStart(2)}: ${String(n + 2).padStart(2)} -> ${String(subs.size).padStart(4)} states, accepting ${accepting}, empty set: ${empty}`);
}
console.log("under 1 s:", performance.now() - t0 < 1000);

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

n= 1:  3 ->    2 states, accepting 1, empty set: no
n= 2:  4 ->    4 states, accepting 2, empty set: no
n= 3:  5 ->    8 states, accepting 4, empty set: no
n= 4:  6 ->   16 states, accepting 8, empty set: no
n= 5:  7 ->   32 states, accepting 16, empty set: no
n= 6:  8 ->   64 states, accepting 32, empty set: no
n= 7:  9 ->  128 states, accepting 64, empty set: no
n= 8: 10 ->  256 states, accepting 128, empty set: no
n= 9: 11 ->  512 states, accepting 256, empty set: no
n=10: 12 -> 1024 states, accepting 512, empty set: no
n=11: 13 -> 2048 states, accepting 1024, empty set: no
n=12: 14 -> 4096 states, accepting 2048, empty set: no
under 1 s: true

n = 12-এ ১৪-state DFA-র reversal-এ ৪০৯৬টি reachable state; প্রতিটি সারিতে ঠিক 2n. পর্ব ১০-এর নিম্নসীমা অনুযায়ী এর চেয়ে কম সম্ভব নয়, তাই এখানে subset construction-এর ফলই minimal DFA. অর্ধেক state accepting (যে সেটে পুরোনো শুরু 0 আছে), আর ফাঁকা সেট কখনো আসে না, কারণ ফাঁদ Y সবসময় নিজের কাছে ফেরে। ব্লকটি Y থেকে শুরু করে, অর্থাৎ পুরোনো accepting সেট থেকে, যা উপপাদ্য ৪.১-এর ε-তীরের সমান। Language regular থাকে, কিন্তু DFA ঘাতের হারে বড় হতে পারে, আর সেটি এড়ানো যায় না। শেষ লাইন দেখায়, পুরো হিসাব এক সেকেন্ডের কম সময়ে শেষ। (কোডের ??= মানে “ফাঁকা হলে তবেই মান বসানো”।)

সত্যিকারের run — automata-lib দিয়ে একই দাবি

নিজের কোডের দাবিগুলো একটি স্বাধীন library-তে মেলানো দরকার। automata-lib (MIT licence) Python-এর একটি automata library, যার DFA-তে |, &, -, ~ operator আর NFA-তে concatenate, kleene_star, reverse, right_quotient method আছে। Library-র কোডে network বা usage-reporting-এর কোনো অংশ নেই (scratch-এ খুঁজে দেখা হয়েছে)। Script-টি ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে চালানো হয়েছে: automata-lib 9.2.0, Python 3.12.

from importlib.metadata import version
from automata.fa.dfa import DFA
from automata.fa.nfa import NFA

print("automata-lib", version("automata-lib"))
B = {"0", "1"}
def mod3(final):                      # binary value mod 3, accept remainders in final
    return DFA(states={0, 1, 2}, input_symbols=B, initial_state=0, final_states=final,
               transitions={r: {b: (2 * r + int(b)) % 3 for b in "01"} for r in range(3)})
div3, rem1 = mod3({0}), mod3({1})
even1 = DFA(states={"e", "o"}, input_symbols=B, initial_state="e", final_states={"e"},
            transitions={"e": {"0": "e", "1": "o"}, "o": {"0": "o", "1": "e"}})

for name, d in [("union", div3 | even1), ("intersection", div3 & even1),
                ("difference", div3 - even1), ("complement", ~div3)]:
    print(f"{name:12} product/raw states {len(d.states)}, minimal {len(d.minify().states)}")

n3 = NFA.from_dfa(div3)
print("DIV3 . DIV3 == DIV3:", DFA.from_nfa(n3.concatenate(n3)) == div3)
print("DIV3*      == DIV3:", DFA.from_nfa(n3.kleene_star()) == div3)
one = NFA.from_regex("1", input_symbols=B)
print("DIV3 / {1} == remainder 1:", DFA.from_nfa(n3.right_quotient(one)) == rem1)

print("reversal of 'n-th symbol from start is 1':")
for n in range(1, 9):
    fwd = DFA.nth_from_start(B, "1", n)
    rev = NFA.from_dfa(fwd).reverse()
    raw, small = DFA.from_nfa(rev, minify=False), DFA.from_nfa(rev)
    ok = small == DFA.nth_from_end(B, "1", n)
    print(f"  n={n}: {len(fwd.states):2} -> subsets {len(raw.states):3}, minimal {len(small.states):3}, correct: {ok}")

সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12):

~/bazarghar-toc$ uv run python closure_run.py
automata-lib 9.2.0
union        product/raw states 6, minimal 6
intersection product/raw states 6, minimal 6
difference   product/raw states 6, minimal 6
complement   product/raw states 3, minimal 3
DIV3 . DIV3 == DIV3: True
DIV3*      == DIV3: True
DIV3 / {1} == remainder 1: True
reversal of 'n-th symbol from start is 1':
  n=1:  3 -> subsets   3, minimal   2, correct: True
  n=2:  4 -> subsets   5, minimal   4, correct: True
  n=3:  5 -> subsets   9, minimal   8, correct: True
  n=4:  6 -> subsets  17, minimal  16, correct: True
  n=5:  7 -> subsets  33, minimal  32, correct: True
  n=6:  8 -> subsets  65, minimal  64, correct: True
  n=7:  9 -> subsets 129, minimal 128, correct: True
  n=8: 10 -> subsets 257, minimal 256, correct: True

DIV3 (৩ state) আর “1-এর সংখ্যা জোড়” (২ state)-এর product-এ ৩ × ২ = ৬টি state, আর minimise করলেও ৬: এখানে product-এর কোনো state বাড়তি নয়। অংশ ৩-এর দুটি চমক (DIV3 · DIV3 = DIV3, DIV3∗ = DIV3) আর অংশ ৬-এর DIV3/{1} = “ভাগশেষ 1” library-র নিজস্ব সমতা-পরীক্ষায় True, অর্থাৎ সব দৈর্ঘ্যে সত্য, শুধু brute-force সীমা পর্যন্ত নয়। Reversal-এ library-র subset সংখ্যা 2n + 1, আমাদের JavaScript-এর চেয়ে একটি বেশি, কারণ library উপপাদ্য ৪.১-এর মতো একটি নতুন শুরু state যোগ করে, আর {নতুন শুরু, Y} সেটটি নাম হিসেবে {Y} থেকে আলাদা, যদিও দুটির আচরণ একই। Minimise করলে ঠিক 2n, আর library নিশ্চিত করেছে যে ফলটি “শেষ থেকে n-তম চিহ্ন 1”-এর DFA-র সমান।

আরও গভীরে: সারণির “প্রায়” সংখ্যাগুলোর নিখুঁত রূপ state complexity-র গবেষণার বিষয়; Yu, Zhuang আর Salomaa-র ১৯৯৪ সালের একটি পরিচিত প্রবন্ধে concatenation-এর জন্য m · 2n − 2n−1 আর star-এর জন্য 2n−1 + 2n−2 সীমা (ছোট কিছু ব্যতিক্রমসহ) দেখানো হয়েছে বলে উল্লেখ পাওয়া যায়। Homomorphism-এর আরও সাধারণ রূপ substitution, যেখানে প্রতিটি চিহ্নের জায়গায় একটি পুরো regular language বসে; regular language এতেও বদ্ধ। Ginsburg আর Greibach ১৯৬০-এর দশকের শেষে language-পরিবারের একটি বিমূর্ত তত্ত্ব (abstract family of languages) গড়েন, যার মূলে কয়েকটি operation-এ closure: homomorphism, inverse homomorphism, regular language-এর সঙ্গে ছেদ, union, concatenation আর star; regular আর context-free দুটিই এমন পরিবার। আর reversal-এর একটি সুন্দর ব্যবহার Brzozowski-র (১৯৬০-এর দশকের শুরু) minimisation: উল্টানো, subset construction, আবার উল্টানো, আবার subset construction করলে minimal DFA আসে (পর্ব ১৯)।

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

  • Regular language কোন কোন operation-এ বদ্ধ? ∪, ∩, complement, difference, concatenation, star, reversal, homomorphism, inverse homomorphism, quotient; অসীম union-এ নয়।
  • L regular হলে LR regular প্রমাণ করুন। DFA-র তীর উল্টে, নতুন শুরু থেকে পুরোনো accepting-এ ε, পুরোনো শুরুকে accepting; অথবা regex-এর গঠনের ওপর induction.
  • Closure দিয়ে দেখান “0 আর 1 সমান সংখ্যক” regular নয়। 0∗1∗-এর সঙ্গে ছেদ নিয়ে {0n1n}, যা non-regular.
  • L/M কখন regular? L regular হলেই, M যেকোনো হোক; নির্মাণে শুধু accepting সেট বদলায়।
  • অসীম union-এ closure নেই কেন? {0n1n}-এর প্রতিটি সদস্য একা regular, কিন্তু সবগুলোর union নয়।

৯ · AI-এর যুগে closure property

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

AI-এর ভুলকীভাবে ধরবেন
NFA-তে accepting state অদলবদল করে “complement” বলাদুটি পথের একটি accepting-এ শেষ হয় এমন একটি string খুঁজে দুই যন্ত্রে চালানো
Partial DFA-তে complement, dead state ছাড়াইমাঝপথে আটকে যাওয়া একটি string দুই যন্ত্রে দেওয়া
Reversal-এ শুধু তীর উল্টানো, শুরু আর accepting অদলবদল না করাছোট string-এ brute force: LR-এর সংজ্ঞার সঙ্গে মেলানো
Non-regular language-এর সঙ্গে ছেদ নিয়ে “প্রমাণ”, বা subset regular ধরে নেওয়াপ্রতিটি ধাপে দেখা: যে language-এর সঙ্গে operation, সেটি কি প্রমাণিতভাবে regular?
“h(L) regular, তাই L regular” ধরনের উল্টো দিকের যুক্তিerasing homomorphism (h(a) = ε) দিয়ে পাল্টা-উদাহরণ ভাবা
“Regular language অসীম union-এ বদ্ধ” বা “regular-এর subset regular”{0n1n} = ⋃n {0n1n} মনে রাখা
বানানো রেফারেন্স বা ভুল সালSipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখা

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

আমি গণনার তত্ত্ব শিখছি। Σ = {a, b}-এর ওপর L = “a-এর সংখ্যা জোড়” language-এর DFA: p0 (শুরু, accepting): a পড়লে p1, b পড়লে p0 p1: a পড়লে p0, b পড়লে p1 ১. h(0) = ab, h(1) = aa নিয়ে h⁻¹(L)-এর DFA বানাও: প্রতিটি δ′(q, x) = δ̂(q, h(x)) আলাদা করে হিসাব করে দেখাও। ২. h⁻¹(L) কোন language, এক বাক্যে বলো। ৩. L-এর reversal-এর NFA বানাও (তীর উল্টে, শুরু আর accepting অদলবদল), আর বলো L-এর reversal L-এর সমান কি না। ৪. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা দৈর্ঘ্য ≤ 10-এর সব string-এ তোমার দুটি যন্ত্রকে সংজ্ঞার সঙ্গে মিলিয়ে দেখে। ৫. প্রতিটি দাবির পাশে লেখো, সেটি প্রমাণিত নাকি শুধু পরীক্ষিত।

(নিজে যাচাই করুন: h(0) = ab-তে একটি a, তাই 0 পড়লে parity বদলায়; h(1) = aa-তে দুটি a, তাই 1 পড়লে বদলায় না। অর্থাৎ h−1(L) = “0-এর সংখ্যা জোড়”, যার DFA-তেও দুটি state. আর w আর wR-এ a-এর সংখ্যা সমান, তাই LR = L.)

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

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

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

প্র ০১গণিতের regex-এ intersection আর complement নেই, অথচ regular language এই দুটিতে বদ্ধ। তাহলে এই দুটি operation সরাসরি regex-এ রাখা হয়নি কেন, আর বাস্তবের টুলে এর প্রভাব কী?

Kleene-এর ১৯৫৬ সালের কাজে regex-এর মূল operation ছিল তিনটি: union, concatenation আর star. এগুলো একটি যন্ত্রের পথের ভাষা: বিকল্প পথ, পরপর পথ, চক্র। Intersection আর complement এই অর্থে “পথের” operation নয়; এদের জন্য দুটি যন্ত্র একসঙ্গে চালাতে হয় (product), বা একটি DFA-র সব পথ একসঙ্গে জানতে হয় (complement). তাই regex-এর ছোট সংজ্ঞায় এরা নেই, কিন্তু Rabin আর Scott-এর ১৯৫৯ সালের প্রবন্ধের মতো প্রথম দিকের কাজে automaton দিয়ে এদের closure প্রমাণিত হয়েছে বলে পরিচিত।

এগুলো regex-এ যোগ করলে প্রকাশের শক্তি বাড়ে না, কারণ ফল এমনিতেই regular. কিন্তু লেখা অনেক ছোট হতে পারে, আর তার দাম দিতে হয় অন্য জায়গায়। পর্ব ১৩-এ দেখেছেন, দুটি regex-এর intersection-এর সাধারণ regex মূল দুটির চেয়ে ঘাতের হারে বড় হতে পারে। আর complement-যুক্ত regex-এর equivalence পরীক্ষা সাধারণ regex-এর তুলনায় অনেক বেশি কঠিন বলে জানা, কারণ প্রতিটি complement-এর জন্য একটি subset construction লাগতে পারে, আর সেগুলো একটির ভেতরে আরেকটি বসে।

বাস্তবের টুলে এই কারণেই একটি মিশ্র ছবি দেখা যায়। Python-এর re বা JavaScript-এর RegExp-এ সরাসরি ∩ বা complement নেই; lookahead দিয়ে কিছুটা অনুকরণ করা যায়, কিন্তু তা backtracking-এর ওপর নির্ভর করে (পর্ব ২১)। grep-এর মতো টুলে “-v” (যে লাইন মেলে না) একটি লাইন-স্তরের complement দেয়, আর দুটি grep পরপর চালালে লাইন-স্তরের intersection. অর্থাৎ বাস্তবে প্রকৌশলীরা closure property ব্যবহার করেন টুল জোড়া দিয়ে, regex-এর ভেতরে নয়।

বাজারঘরের উদাহরণে: “কুপনে SALE আছে, কিন্তু শেষে 0 নেই” নিয়মটি একটি regex-এ লিখতে কষ্ট হয়, কিন্তু দুটি validator পরপর চালানো সহজ, আর closure property নিশ্চিত করে যে ফলটি একটি সসীম যন্ত্রে চেনা যায়। দরকার হলে product construction দিয়ে একটি DFA-তেও জুড়ে দেওয়া যায়, তাতে প্রতিটি অক্ষরে একটিই টেবিল-দেখা।

মূল উপলব্ধি: Closure property প্রকাশের শক্তির কথা বলে, লেখার সুবিধার নয়। Intersection আর complement regular language-এর শ্রেণি থেকে বের হয় না, কিন্তু regex-এ এদের দাম লেখার আকারে, তাই বাস্তবে এরা যন্ত্র বা টুল জোড়ার স্তরে ব্যবহার হয়।

প্র ০২L আর LR দুটিই regular, অথচ একটির DFA-তে n + 2টি state আর অন্যটিতে 2n. পড়ার দিক কেন এত বড় পার্থক্য তৈরি করে?

DFA একটি “স্ট্রিমিং” যন্ত্র: বাঁ থেকে ডানে একবার পড়ে, আর পড়ার সময় শুধু বর্তমান state মনে রাখে। তাই প্রশ্নটি হলো, পড়ার প্রতিটি মুহূর্তে ভবিষ্যতের উত্তর দিতে অতীতের কতটুকু তথ্য রাখতে হয়। “শুরু থেকে n-তম চিহ্ন 1” পরীক্ষায় n-তম চিহ্ন দেখামাত্র উত্তর ঠিক হয়ে যায়, তারপর আর কিছু মনে রাখার নেই। “শেষ থেকে n-তম চিহ্ন 1” পরীক্ষায় কিন্তু string কখন শেষ হবে জানা নেই, তাই প্রতিটি মুহূর্তে শেষ n-টি চিহ্নই মনে রাখতে হয়: 2n রকম সম্ভাবনা, আর পর্ব ১০-এর fooling-set যুক্তি দেখায় এর প্রতিটি আলাদা রাখতেই হয়।

NFA-তে এই অসমতা নেই। উল্টো যন্ত্রটি এখনো n + 1-এর কাছাকাছি state-এর, কারণ NFA “অনুমান” করতে পারে কোথায় শেষ থেকে n-তম চিহ্ন। Reversal তাই NFA-র জগতে সস্তা আর DFA-র জগতে দামি। এই কারণেই অনেক তাত্ত্বিক নির্মাণ NFA-তে করা হয়, আর বাস্তবের অনেক regex engine পুরো DFA না বানিয়ে NFA-র state-সেট ধরে চলে বা প্রয়োজনমতো DFA-র state বানায় (lazy DFA, পর্ব ১০ ও ২১)।

বাস্তবে পড়ার দিক বেছে নেওয়ার সুযোগ থাকলে সেটি কাজে লাগে। লগ-ফাইলের শেষের দিকের ধাঁচ খুঁজতে ফাইলটি শেষ থেকে পড়ে LR-এর ছোট DFA চালানো যায়, যদি সেটি ছোট হয়। কিছু string-matching algorithm-ও এই ধারণা ব্যবহার করে: Boyer–Moore পদ্ধতি pattern ডান থেকে বাঁয়ে মেলায়, আর এর কিছু automaton-ভিত্তিক রূপ pattern-এর উল্টো রূপের automaton দিয়ে লেখার ওপর বড় লাফ দেয় বলে জানা।

তাত্ত্বিক দিক থেকেও reversal গভীর। Brzozowski-র minimisation পদ্ধতি দুবার reversal আর দুবার subset construction করে minimal DFA পায়; তার যুক্তির মূলে একটি তথ্য: যে DFA-র সব state reachable, তার reversal-এর subset construction সবসময় minimal DFA দেয়। এই পর্বের JavaScript ব্লকেও ঠিক তাই হয়েছে: 2nটি reachable সেট, আর minimal DFA-র আকারও 2n.

মূল উপলব্ধি: Regularity পড়ার দিকের ওপর নির্ভর করে না, কিন্তু DFA-র আকার করে। কোন দিক থেকে পড়লে কম তথ্য মনে রাখতে হয়, সেটিই ঠিক করে যন্ত্র ছোট হবে না ঘাতের হারে বড়।

প্র ০৩Automaton-এর জন্য inverse homomorphism কেন homomorphism-এর চেয়েও “স্বাভাবিক”? বাস্তবে encoding বদলানোর সঙ্গে এর সম্পর্ক কী?

Homomorphism h(L) বানাতে প্রতিটি চিহ্নকে একটি string দিয়ে বদলাতে হয়। DFA-তে এর মানে একটি তীরকে কয়েকটি তীরের শিকল বানানো, আর h(a) = ε হলে তীরটি ε-তীর হয়ে যায়, ফলে যন্ত্র NFA হয়ে যায়। Inverse homomorphism-এ উল্টো: নতুন যন্ত্রের প্রতিটি তীর পুরোনো যন্ত্রের ওপর h(a)-এর একটি গোটা যাত্রা। কোনো নতুন state নেই, কোনো অনিশ্চয়তা নেই, আর DFA DFA-ই থাকে। যন্ত্রের দৃষ্টিতে h−1 তাই প্রায় বিনামূল্যে আসে।

বাস্তবের সবচেয়ে চেনা উদাহরণ character encoding. UTF-8 প্রতিটি Unicode অক্ষরকে এক থেকে চার byte-এর একটি নির্দিষ্ট ক্রমে বদলায়, অর্থাৎ এটি অক্ষর থেকে byte-string-এ একটি homomorphism. ধরুন একটি validator byte-এর স্তরে লেখা (যেমন নেটওয়ার্ক প্যাকেট পরীক্ষা), আর আপনি জানতে চান কোন অক্ষর-string-এর encoding এটি পাস করে। সেই সেটটি h−1(L), আর উপপাদ্য ৫.২ বলে এটিও একই state-এর একটি DFA দিয়ে চেনা যায়, যার প্রতিটি অক্ষর-তীর byte-স্তরের কয়েকটি তীরের যোগফল। উল্টো দিকে, অক্ষর-স্তরের নিয়ম L থেকে byte-স্তরের h(L) পেতে homomorphism, আর সেটিও regular. বাংলা লেখা নিয়ে কাজ করা প্রোগ্রামে এই দুই স্তরের পার্থক্য প্রায়ই ভুলের উৎস।

বাজারঘরের অর্ডার কোডের ক্ষেত্রেও একই চিত্র: {B, G, -, d}-এর ওপর বানানো ৮-state partial DFA (dead state ছাড়া) থেকে inverse homomorphism দিয়ে ১৩ চিহ্নের আসল alphabet-এর DFA, state একই, শুধু প্রতিটি d-তীর দশটি অঙ্কের তীরে ভাগ হয়। অর্থাৎ এই কোর্সে “d মানে যেকোনো অঙ্ক” ধরে নেওয়ার বিমূর্ততা গাণিতিকভাবে নিরাপদ।

তত্ত্বে inverse homomorphism একটি মৌলিক operation. ১৯৬০-এর দশকের শেষে Ginsburg আর Greibach যে language-পরিবারের কাঠামো নিয়ে কাজ করেন, তার সংজ্ঞায় homomorphism, inverse homomorphism আর regular language-এর সঙ্গে ছেদ, এই তিনটি একসঙ্গে আসে; regular আর context-free দুটিই এই তিনটিতে বদ্ধ। এর একটি ব্যবহার হলো, এক language থেকে আরেক language-এ “অনুবাদ” করে non-regularity বা non-context-freeness প্রমাণ।

মূল উপলব্ধি: Inverse homomorphism মানে “নতুন alphabet-এর প্রতিটি চিহ্ন পুরোনো যন্ত্রের একটি শর্টকাট”: state বাড়ে না, determinism থাকে। Encoding বদলানো বা বিমূর্ত alphabet থেকে আসলে ফেরা এর সবচেয়ে সাধারণ বাস্তব রূপ।

প্র ০৪L/M regular, M যেকোনো language হলেও; অথচ M কঠিন হলে F′ বের করার কোনো algorithm না-ও থাকতে পারে। “আছে জানি, কিন্তু বের করতে পারি না” কথাটি গণিতে কীভাবে সম্ভব?

উপপাদ্য ৬.১-এর প্রমাণে F′-এর একটি সংজ্ঞা দেওয়া হয়েছে: “যেসব state থেকে M-এর কোনো string F-এ নিয়ে যায়”। Q সসীম, তাই F′ অবশ্যই Q-এর কোনো একটি subset, আর যেকোনো subset নিলে একটি বৈধ DFA পাওয়া যায়। তাই L/M-এর জন্য একটি DFA আছে: 2|Q|টি সম্ভাব্য যন্ত্রের একটি। প্রমাণটি কোনটি, তা বলে না; শুধু বলে যে উত্তরটি এই সসীম তালিকার মধ্যেই আছে।

কোনটি, সেটি জানতে প্রতিটি state q-এর জন্য একটি প্রশ্নের উত্তর লাগে: L(Mq) ∩ M ফাঁকা কি না, যেখানে Mq মানে q থেকে শুরু করা DFA. M regular হলে এটি product আর reachability দিয়ে সহজ (পর্ব ২০), আর অংশ ৬-এর pigeonhole সীমা দেখায় যে সসীম সংখ্যক string পরীক্ষা করলেই চলে। কিন্তু M যদি একটি Turing machine T-এর language হিসেবে দেওয়া থাকে, তাহলে L = Σ∗-এর মতো সরল ক্ষেত্রেও প্রশ্নটি হয়ে যায় “T কি কোনো string গ্রহণ করে?”, আর এর কোনো সাধারণ algorithm নেই বলে প্রমাণিত (পর্ব ৫০–৫২)। ফলে প্রতিটি নির্দিষ্ট M-এর জন্য L/M regular, কিন্তু “M দিলে L/M-এর DFA দাও” কাজটির কোনো সাধারণ program থাকতে পারে না।

গণিতে এই পার্থক্যের নাম constructive বনাম non-constructive প্রমাণ। ক্লাসিক্যাল গণিত “সব সম্ভাবনার মধ্যে একটি সত্য” ধরনের যুক্তি মেনে নেয় (law of excluded middle): প্রতিটি q হয় F′-এ আছে, নয়তো নেই, আমরা জানি বা না জানি। গণিতের constructive ধারার গবেষকরা, যাঁদের শিকড় বিংশ শতকের শুরুর দিকে L. E. J. Brouwer-এর intuitionism-এ, এমন প্রমাণকে কম মূল্য দেন, কারণ সেটি কোনো পদ্ধতি দেয় না। গণনার তত্ত্বের দৃষ্টিতে প্রশ্নটি খুব বাস্তব: “অস্তিত্ব” আর “গণনাযোগ্যতা” আলাদা জিনিস।

বাজারঘরের ভাষায়: কেউ বললেন, “আমাদের ছাড়ের নিয়ম M যত জটিলই হোক, ‘যেসব অর্ডার কোডের পরে কোনো ছাড়-কোড জুড়লে বৈধ হয়’ তাদের সেট একটি সসীম যন্ত্রে চেনা যায়।” কথাটি সত্য। কিন্তু M যদি একটি ইচ্ছামতো program দিয়ে সংজ্ঞায়িত হয়, তাহলে সেই যন্ত্রটি আসলে বানিয়ে দেওয়ার কোনো সাধারণ উপায়ের নিশ্চয়তা নেই।

মূল উপলব্ধি: একটি language regular হওয়া আর তার DFA বের করা যাওয়া আলাদা দাবি। Quotient-এর closure প্রথমটি প্রমাণ করে যেকোনো M-এর জন্য, কিন্তু দ্বিতীয়টি শুধু তখন, যখন M-এর ফাঁকা হওয়ার প্রশ্ন decidable, যেমন M regular হলে।

প্র ০৫Non-regular প্রমাণের তিনটি পথ আছে: closure, pumping lemma আর Myhill–Nerode. কখন কোনটি সবচেয়ে ভালো, আর closure-এর পথের সীমা কোথায়?

Closure-এর পথ একটি “অনুবাদ”: নতুন language-কে regular-রক্ষাকারী operation দিয়ে একটি জানা non-regular language-এ নিয়ে যাওয়া। তাই এর জন্য একটি ভিত্তি লাগে, সাধারণত {0n1n}, যার প্রমাণ অন্য পথে (pigeonhole, pumping বা Myhill–Nerode) আসে। সুবিধা হলো, ভিত্তি একবার প্রমাণ হলে নতুন প্রমাণগুলো ছোট আর যান্ত্রিক: EQ, NEQ, সুষম বন্ধনী, {a2nbn} সবই দু-তিন লাইনে। অসুবিধা হলো, সঠিক ছাঁকনি বা homomorphism খুঁজে পেতে কল্পনা লাগে, আর প্রতিটি ছাঁকনি প্রমাণিতভাবে regular হতে হয়।

Pumping lemma (পর্ব ১৭) সরাসরি language-এর ওপর কাজ করে, কিন্তু একটি খেলার মতো: প্রতিপক্ষ p আর ভাগ বেছে নেয়, আপনি string আর i বাছেন। এটি শুধু একটি প্রয়োজনীয় শর্ত, তাই কিছু non-regular language pump করেও যায়, যেমন পর্ব ১৭-এর {aibjck : i = 0 অথবা j = k}. এমন ক্ষেত্রে closure প্রায়ই উদ্ধার করে: ab∗c∗-এর সঙ্গে ছেদ নিলে পাওয়া যায় {abjcj}, যার ওপর আবার একটি homomorphism বা quotient নিয়ে {bjcj}-এর মতো ভিত্তি language-এ পৌঁছানো যায়।

Myhill–Nerode (পর্ব ১৮) সবচেয়ে শক্তিশালী: এটি একটি “যদি ও কেবল যদি”, তাই প্রতিটি non-regular language-এর জন্য একটি প্রমাণ এই পথে আছে, আর regular language-এর minimal DFA-র আকারও এটি দেয়। Lemma ৭.১-এর প্রমাণও আসলে এর একটি ছোট রূপ: ε, 0, 00, … string-গুলো জোড়ায় জোড়ায় আলাদা করা যায়।

Closure-এর একটি বড় সীমা পরের মডিউলগুলোতে দেখা দেয়। Context-free language intersection আর complement-এ বদ্ধ নয় (পর্ব ৩৭), তাই সেখানে এই কৌশল সাবধানে ব্যবহার করতে হয়: CFL-এর সঙ্গে শুধু regular language-এর ছেদ নেওয়া নিরাপদ। পরীক্ষার উত্তরে তাই প্রতিটি closure-ধাপের পাশে লিখে দেওয়া ভালো, কোন শ্রেণির কোন operation ব্যবহার হলো।

মূল উপলব্ধি: Closure দ্রুত, কিন্তু ধার করা ভিত্তির ওপর দাঁড়ায়; pumping lemma সরাসরি, কিন্তু শুধু প্রয়োজনীয় শর্ত; Myhill–Nerode সম্পূর্ণ। ভালো প্রমাণে প্রায়ই তিনটি মিলিয়ে ব্যবহার হয়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। closure_lab.py ব্লকের function দিয়ে নিজের যন্ত্রও যাচাই করতে পারেন।

  1. নকশা: Σ = {a, b}-এর ওপর DROP-ONE(L) = {xy : কোনো c ∈ Σ-এর জন্য xcy ∈ L}, অর্থাৎ L-এর কোনো string থেকে ঠিক একটি চিহ্ন মুছে যা পাওয়া যায়। (ক) L-এর DFA থেকে DROP-ONE(L)-এর একটি NFA নকশা করুন। (খ) L = (ab)∗ নিলে DROP-ONE(L)-এর দৈর্ঘ্য ≤ 3-এর সব string লিখুন, আর একটি regex দিন।

    (ক) L-এর DFA M-এর দুটি কপি নিন: কপি ১ (এখনো কিছু মোছা হয়নি) আর কপি ২ (একটি চিহ্ন মোছা হয়ে গেছে)। দুই কপির ভেতরে তীর M-এর মতোই। কপি ১-এর প্রতিটি state q থেকে, প্রতিটি c ∈ Σ-এর জন্য, কপি ২-এর δ(q, c)-তে একটি ε-তীর: “এখানে c ছিল, যা মুছে গেছে” অনুমান করা। শুরু কপি ১-এর q0, accepting শুধু কপি ২-এর F. State 2|Q|. সঠিকতা: গৃহীত পথ ঠিক একবার কপি বদলায়, আর সেখানে মুছে যাওয়া c-টি বসালে M-এর একটি গৃহীত পথ পাওয়া যায়, উল্টোটিও।

    (খ) দৈর্ঘ্য ≤ 3: a, b, aab, aba, abb, bab (ab থেকে a বা b; abab থেকে চারটি অবস্থান)। Regex: (ab)∗(a ∪ b)(ab)∗, কারণ মোছা চিহ্নটি কোনো একটি ab-জোড়ার, আর জোড়াটির বাকি অংশ a বা b. Scratch-এ দৈর্ঘ্য 10 পর্যন্ত সব 2047টি string-এ NFA, এই regex আর সংজ্ঞা তিনটিই মিলেছে।

  2. প্রমাণের ভুল ধরুন: দাবি: “L = {0i1j : i ≥ j} regular.” প্রমাণ: “L ⊆ 0∗1∗, আর 0∗1∗ regular. Regular language-এর subset regular, তাই L regular. ∎” ভুলটি কোথায়? দাবিটি কি আসলে সত্য?

    ভুল ধাপ: “regular language-এর subset regular”. Regular language subset নেওয়ায় বদ্ধ নয়; {0n1n} ⊆ 0∗1∗, অথচ এটি non-regular (Lemma ৭.১)। আর প্রতিটি language Σ∗-এর subset, তাই এই নিয়ম সত্য হলে সব language regular হতো।

    দাবিটিও মিথ্যা। Lemma ৭.১-এর মতো যুক্তি: k-state DFA ধরলে ε, 0, …, 0k-এর মধ্যে i < j আছে যাতে 0i আর 0j একই state-এ থামে। তাহলে 0i1j আর 0j1j-এর উত্তর একই হতে হবে। কিন্তু 0j1j ∈ L (j ≥ j) আর 0i1j ∉ L (i < j). বিরোধ, তাই L regular নয়। ∎

  3. প্রমাণ: Σ = {a, b}-এর ওপর L = {w : w-এ a-এর সংখ্যা b-এর সংখ্যার ঠিক দ্বিগুণ}. Closure property আর Lemma ৭.১ ব্যবহার করে প্রমাণ করুন যে L regular নয়। (ইঙ্গিত: আগে একটি regular ছাঁকনি, তারপর একটি inverse homomorphism.)
    1. ধরুন L regular. — contradiction-এর জন্য
    2. a∗b∗ regular, তাই L1 = L ∩ a∗b∗ = {a2nbn : n ≥ 0} regular. — ∩-এ closure
    3. h : {0, 1} → {a, b}∗, h(0) = aa, h(1) = b নিন। তাহলে h−1(L1) regular. — উপপাদ্য ৫.২
    4. h(w) ∈ L1 ⇔ h(w) = a2nbn ⇔ w = 0n1n, কারণ h(w)-এ সব a আগে থাকতে হলে w-এ সব 0 আগে, আর 0-এর সংখ্যা n হলে a-এর সংখ্যা 2n. তাই h−1(L1) = {0n1n}. — h-এর সংজ্ঞা
    5. কিন্তু Lemma ৭.১ অনুযায়ী এটি regular নয়। বিরোধ, তাই L regular নয়। ∎

    Scratch-এ যাচাই: দৈর্ঘ্য ≤ 9 পর্যন্ত L ∩ a∗b∗-এ ঠিক ε, aab, aaaabb, aaaaaabbb; আর দৈর্ঘ্য ≤ 6-এর {0, 1}-string-এর মধ্যে h−1-এ ঠিক ε, 01, 0011, 000111.

  4. আউটপুট অনুমান: DIV3-এর DFA (state qr = ভাগশেষ r, bit b পড়লে r থেকে (2r + b) mod 3, accepting q0). inverse_quotient.py ব্লকের quotient_finals দিয়ে M = L(0), L(01) আর L(0*1) নিলে F′ কী ছাপবে? প্রতিটির অর্থ এক লাইনে বলুন।

    M = {0}: δ(qr, 0) = q2r mod 3, আর 2r ≡ 0 ⇔ r = 0. ছাপবে [0]; অর্থাৎ DIV3/{0} = DIV3: শেষে 0 জোড়া মানে দ্বিগুণ করা, যা ৩-এর গুণিতকতা বদলায় না।

    M = {01}: r থেকে 0 পড়ে 2r, তারপর 1 পড়ে 4r + 1 ≡ r + 1. শূন্য হয় r = 2-এ। ছাপবে [2]: “ভাগশেষ 2”-এর string-এর পরে 01 জুড়লে ৩-এর গুণিতক।

    M = 0∗1: k-টি 0-এর পর 1: মান 2k·r + 1-এর ভাগশেষ লাগবে 0. k জোড় হলে 2k ≡ 1, তাই r = 2; k বিজোড় হলে 2k ≡ 2, তাই 2r ≡ 2, r = 1. ছাপবে [1, 2]: ভাগশেষ 0 ছাড়া যেকোনো string. Scratch-এ তিনটি উত্তরই একই কোড চালিয়ে মিলেছে।

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

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

ক্রমClosure property দিয়ে একটি language L non-regular প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Contradiction-এর জন্য ধরে নেওয়া যে L regular
  2. একটি প্রমাণিতভাবে regular ছাঁকনি language বেছে নেওয়া, যেমন 0∗1∗
  3. Closure-রক্ষাকারী operation চালিয়ে বলা যে ফলের language-ও regular হতে হবে
  4. ফলের language-টি হিসাব করে দেখানো যে এটি একটি জানা non-regular language, যেমন {0n1n}
  5. বিরোধ থেকে সিদ্ধান্ত নেওয়া যে L regular নয়

Σ-এর ওপর regular language-এর শ্রেণি নিচের কোন operation-এ বদ্ধ নয়?

  • Reversal
  • Inverse homomorphism
  • অসীম সংখ্যক regular language-এর union
  • Right quotient L/M

একটি n-state DFA M থেকে তীর উল্টে, শুরু আর accepting অদলবদল করে L(M)R-এর যন্ত্র বানানো হলো। নিচের কোনটি সাধারণভাবে সত্য?

  • ফলটি সবসময় একটি n-state DFA
  • ফলটি প্রায় n state-এর একটি NFA, কিন্তু L(M)R-এর DFA-তে 2n-এর কাছাকাছি state লাগতে পারে
  • L(M)R কখনো কখনো regular নয়
  • শুরু আর accepting অদলবদল দরকারই নেই

L1 regular, আর L1 ∪ L2-ও regular. L2 সম্পর্কে কী বলা যায়?

  • L2 অবশ্যই regular
  • L2 অবশ্যই non-regular
  • L1 ∩ L2 অবশ্যই regular
  • L2 regular কি না, তা নিশ্চিত বলা যায় না

Σ = {0, 1}-এর ওপর EQ = {w : 0 আর 1 সমান সংখ্যক}. Closure দিয়ে EQ non-regular প্রমাণ করতে EQ-এর সঙ্গে কোন language-এর ছেদ নেওয়া সঠিক কৌশল?

  • 0∗1∗
  • {0n1n : n ≥ 0}
  • Σ∗
  • (01)∗

DFA M = (Q, Γ, δ, q0, F) আর homomorphism h : Σ → Γ∗ থেকে h−1(L(M))-এর DFA বানাতে নতুন transition কী?

  • δ′(q, a) = δ(q, a)
  • δ′(q, a) = δ(q, h−1(a))
  • δ′(q, a) = δ̂(q, h(a))
  • h(a)-এর প্রতিটি চিহ্নের জন্য নতুন state যোগ করে ε-তীর

L regular, আর M একটি non-regular language. Right quotient L/M = {x : কোনো y ∈ M-এর জন্য xy ∈ L} সম্পর্কে কোনটি সত্য?

  • L/M regular হয় শুধু M regular হলে
  • L/M সবসময় regular
  • L/M কখনো regular নয়
  • L/M regular হয় শুধু M সসীম হলে

শব্দকোষ

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

মনে রাখুন

  1. Regular language ∪, ∩, complement, difference, concatenation, star, reversal, homomorphism, inverse homomorphism, quotient, prefix আর suffix-এ বদ্ধ; প্রতিটির প্রমাণ একটি নির্মাণ।
  2. Reversal: তীর উল্টানো আর শুরু ও accepting অদলবদল, ফল একটি NFA; DFA-তে n + 2 থেকে 2n state পর্যন্ত লাগতে পারে।
  3. Inverse homomorphism: δ′(q, a) = δ̂(q, h(a)), একই state; quotient: একই DFA, শুধু F′ = {q : কোনো y ∈ M, δ̂(q, y) ∈ F}, M যেকোনো হলেও।
  4. Non-regular প্রমাণ: L regular ধরে, regular ছাঁকনি বা homomorphism দিয়ে {0n1n}-এর মতো জানা non-regular language পেলে বিরোধ।
  5. অসীম union আর subset-এ closure নেই; আর closure শুধু এক দিকে: regular থেকে regular, উল্টো দিকে কিছু নয়।

পরের পর্বে: Regular language-এর pumping lemma: সব quantifier-সহ সঠিক বিবৃতি, DFA-র state-এ pigeonhole দিয়ে প্রমাণ, প্রতিপক্ষের খেলা, আর anbn, palindrome আর মৌলিক দৈর্ঘ্যের language-এর non-regular প্রমাণ।

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

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