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

DFA নকশা — product construction, complement আর গণনার কৌশল

DFA Design — Counting mod m, Pattern Detection, the Product Construction, Complement and Testing a Design

Taught in Bangla, this lesson designs DFAs by first writing what each state must remember. It covers counting designs (mod m, at least or exactly k) and pattern designs (prefix, suffix, substring, last k symbols), builds product automata for intersection, union and difference, and shows why swapping accept states complements only a complete DFA. In-page Python (Pyodide) brute-forces designs up to length 12 to find the shortest counterexample, and a real automata-lib run checks product, complement and equivalence.

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

  • একটি language-এর বর্ণনা থেকে ধাপে ধাপে DFA নকশা করা, আর প্রতিটি state-এর অর্থ লিখে রাখা
  • Binary সংখ্যার m দিয়ে বিভাজ্যতা, “ঠিক k” গোনা আর substring খোঁজার DFA, সঙ্গে সঠিকতার প্রমাণ
  • Product construction-এর সংজ্ঞা, intersection, union, difference-এর accepting সেট আর তার প্রমাণ
  • Complement কেন সম্পূর্ণ DFA চায়, আর partial DFA-তে ভুলটা ঠিক কোথায় হয়
  • Brute force আর random পরীক্ষায় নকশার বাগ খোঁজা, আর automata-lib দিয়ে equivalence যাচাই

১ · নকশার মূল প্রশ্ন — “কী মনে রাখতে হবে?”

ক্রিকেটের স্কোরবোর্ডে যিনি বল গোনেন, তাঁর কাছে একটাই প্রশ্ন: ওভার শেষ হলো কি? এর জন্য ম্যাচের সব বলের তালিকা লাগে না, শুধু “এই ওভারে কয়টি বৈধ বল হয়েছে”, 0 থেকে 5. ছয় নম্বর বলে আবার 0. অর্থাৎ অসীম ইতিহাস থেকে তিনি একটি সসীম সারাংশ রাখেন, আর প্রতিটি নতুন বলে সেই সারাংশ হালনাগাদ করেন। DFA নকশার পুরো কৌশল এটুকুই: ঠিক সেই সারাংশ খুঁজে বের করা, যা ভবিষ্যতের সিদ্ধান্তের জন্য যথেষ্ট।

পর্ব ০৭ “DFA — formal definition, transition আর language গ্রহণ”-এ সংজ্ঞাগুলো এসেছে; এখানে শুধু মনে করিয়ে দিই। একটি DFA হলো M = (Q, Σ, δ, q0, F): সসীম state-এর সেট Q, alphabet Σ, transition function δ: Q × Σ → Q, শুরুর state q0 ∈ Q আর accepting state-এর সেট F ⊆ Q. δ total, অর্থাৎ প্রতিটি state আর প্রতিটি চিহ্নে ঠিক একটি পরের state. পুরো string-এর জন্য δ̂ (কিছু বইয়ে δ∗) সংজ্ঞায়িত: δ̂(q, ε) = q আর δ̂(q, va) = δ(δ̂(q, v), a). যন্ত্রের language L(M) = {w ∈ Σ∗ : δ̂(q0, w) ∈ F}. এখানে ε হলো ফাঁকা string (কিছু বই λ লেখে)। ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৪-এ mod 3-এর একটি DFA আর product-এর প্রথম পরিচয় আছে; এই পর্ব সেখান থেকে অনেক গভীরে যায়।

এই পর্বের প্রশ্ন উল্টো দিক থেকে: যন্ত্র নয়, language দেওয়া আছে; যন্ত্রটি বানাতে হবে। পরীক্ষায় যেমন, বাস্তবেও তেমন: বাজারঘরের (আমাদের কাল্পনিক অনলাইন দোকান) কুপন-ফর্ম, অর্ডার-কোডের যাচাই বা গুদামের সেন্সর লাইন, সবখানেই আগে নিয়মটি বাংলায় লেখা থাকে, তারপর তা যন্ত্রে রূপ নেয়। নিচের রেসিপি প্রায় সব নকশায় কাজ করে।

DFA নকশার ছয় ধাপ
  1. বর্ণনা পরিষ্কার করুন। Σ কী? ε কি language-এ আছে? “অন্তত” না “ঠিক”? Leading zero চলবে? ছোট উদাহরণে হ্যাঁ/না লিখে ফেলুন।
  2. কী মনে রাখতে হবে ঠিক করুন। প্রতিটি state একটি বাক্য: “এ পর্যন্ত a-এর সংখ্যা জোড়”, “শেষ দুটি চিহ্ন 01”, “ভাগশেষ 2”. বাক্যগুলো পরস্পর বর্জনশীল আর মিলে সব string ঢাকে।
  3. Transition লিখুন অর্থ থেকে। “এই বাক্য সত্য থাকা অবস্থায় a এলে কোন বাক্য সত্য হবে?” প্রতিটি state আর প্রতিটি চিহ্নের জন্য।
  4. শুরু আর গ্রহণ। ε কোন বাক্যে পড়ে, সেটিই q0. যে বাক্যগুলো “language-এ আছে” বোঝায়, সেগুলো F.
  5. সম্পূর্ণ করুন। যে চিহ্নে আর কোনো আশা নেই, সেখানে একটি dead state; প্রতিটি ঘর পূরণ হয়েছে কি না transition table-এ দেখুন।
  6. যাচাই করুন। ছোট দৈর্ঘ্যের সব string-এ সংজ্ঞার সঙ্গে মেলান, তারপর ধাপ ২-এর বাক্যগুলো invariant হিসেবে |w|-এর ওপর induction দিয়ে প্রমাণ করুন (পর্ব ০৪-এর ধাঁচে)।

ধাপ ২-ই আসল নকশা। একটি গভীর কথা এখানে লুকিয়ে আছে: একটি state আসলে এমন সব string-এর দল, যাদের “ভবিষ্যৎ” এক, অর্থাৎ পরে যে string-ই আসুক, দলের সবার জন্য গ্রহণ-বর্জনের উত্তর এক। দুটি অতীতের ভবিষ্যৎ আলাদা হলে তাদের আলাদা state লাগবেই; এই ধারণাই পর্ব ১৮-এর Myhill–Nerode theorem আর পর্ব ১৯-এর minimization-এর ভিত্তি। এই পর্বে আমরা এটি নকশার অন্তর্দৃষ্টি হিসেবে ব্যবহার করব, §৮-এ একটু বেশি।

২ · গোনার কৌশল — mod m আর “অন্তত, বড়জোর, ঠিক k”

বাজারঘরের গুদামের একটি যন্ত্র binary-তে বাক্সের সংখ্যা পাঠায়, সবচেয়ে বড় ঘরের অঙ্ক আগে (most significant bit first). বাক্স তিনটি করে ক্রেটে যায়, তাই প্রশ্ন: সংখ্যাটি ৩ দিয়ে বিভাজ্য কি? Language DIV3 = {w ∈ {0, 1}∗ : val(w) ≡ 0 (mod 3)}, যেখানে val(w) হলো w-এর binary মান, আর আমরা ধরে নিই val(ε) = 0, তাই ε ∈ DIV3. Leading zero চলবে: “0110” মানে 6.

পুরো সংখ্যা মনে রাখা যায় না, কারণ সংখ্যা অসীম বড় হতে পারে, আর DFA-র স্মৃতি সসীম। কিন্তু ভবিষ্যতের জন্য দরকার শুধু ভাগশেষ। কারণ: একটি নতুন bit b এলে মান হয় val(wb) = 2 · val(w) + b, আর ভাগশেষের হিসাবে val(wb) mod 3 = (2 · (val(w) mod 3) + b) mod 3. অর্থাৎ নতুন ভাগশেষ শুধু পুরনো ভাগশেষ আর b-এর ওপর নির্ভর করে। (ভাগশেষের এই নিয়ম ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ২২-এ আছে।) তাই তিনটি state যথেষ্ট: r0, r1, r2, যেখানে ri মানে “এ পর্যন্ত পড়া সংখ্যার ভাগশেষ i”.

1remember: value v of the prefix2too big: keep r = v mod 33read bit b: v becomes 2v + b4so r becomes (2r + b) mod 35fill the table for r0, r1, r26start r0, F = {r0}7test 110 and 111
Transition table তৈরি হচ্ছে
δ(r0, 0), δ(r0, 1)
δ(r1, 0), δ(r1, 1)
δ(r2, 0), δ(r2, 1)
শুরু, F
  1. সহজ ভাবনা। পড়া অংশের পুরো মান v মনে রাখলে উত্তর দেওয়া সহজ, কিন্তু v অসীম রকম হতে পারে, আর DFA-র state সসীম।
  2. যা যথেষ্ট। “৩ দিয়ে বিভাজ্য?” প্রশ্নের জন্য v নয়, v mod 3 যথেষ্ট, যদি দেখানো যায় যে ভাগশেষ নিজেই হালনাগাদ করা যায়।
  3. এক bit পড়লে। Binary-তে ডানে একটি bit বসানো মানে আগের মান দ্বিগুণ করে b যোগ: “11” (3) থেকে “110” (6) = 2 · 3 + 0.
  4. ভাগশেষের হালনাগাদ। (2v + b) mod 3 = (2 · (v mod 3) + b) mod 3. তাই নতুন state শুধু পুরনো state আর b থেকেই আসে: δ(r, b) = r(2r + b) mod 3.
  5. টেবিল। r0-তে 0 → 0, 1 → 1; r1-এ 0 → 2, 1 → 3 mod 3 = 0; r2-তে 0 → 4 mod 3 = 1, 1 → 5 mod 3 = 2. ছয়টি ঘর, কোনোটি ফাঁকা নেই, তাই dead state লাগেনি।
  6. শুরু আর গ্রহণ। কিছু না পড়লে মান 0, তাই শুরু r0. বিভাজ্য মানে ভাগশেষ 0, তাই F = {r0}.
  7. পরীক্ষা। 110 = 6: r0 → r1 → r0 → r0, গৃহীত। 111 = 7: শেষে r1, কারণ 7 mod 3 = 1, বাতিল।

Binary-তে ৩ দিয়ে বিভাজ্যতার DFA

দুই দাগের বৃত্ত accepting. বাঁয়ের খোলা তীর শুরুর state. প্রতিটি বৃত্তের নিচে তার অর্থ।

DFA for binary numbers divisible by 3 r0r1r2 1100 01 ভাগশেষ 0ভাগশেষ 1ভাগশেষ 2
ছবি ৮.১ — r0 আর r1-এর মধ্যে 1-এর তীর দুই দিকে, r1 আর r2-এর মধ্যে 0-এর তীর দুই দিকে। লক্ষ করুন, প্রতিটি state থেকে ঠিক দুটি তীর বের হয়েছে: যন্ত্রটি সম্পূর্ণ।
উপপাদ্য ২.১ (mod m-এর DFA)

m ≥ 1 হলে Mm = ({r0, …, rm−1}, {0, 1}, δ, r0, {r0}), যেখানে δ(ri, b) = r(2i + b) mod m, ঠিক সেই binary string গ্রহণ করে যাদের মান m দিয়ে বিভাজ্য (val(ε) = 0 ধরে)।

Invariant: সব w-এর জন্য δ̂(r0, w) = rval(w) mod m. |w|-এর ওপর induction, শেষ চিহ্ন আলাদা করে:

  1. Base: w = ε. δ̂(r0, ε) = r0, আর val(ε) mod m = 0. — δ̂-এর সংজ্ঞা
  2. Hypothesis: δ̂(r0, v) = ri, যেখানে i = val(v) mod m. w = vb. — induction
  3. δ̂(r0, vb) = δ(ri, b) = r(2i + b) mod m. — δ̂ আর δ-এর সংজ্ঞা
  4. val(vb) = 2 · val(v) + b, আর val(v) ≡ i (mod m), তাই val(vb) ≡ 2i + b (mod m). — congruence যোগ-গুণে টেকে
  5. ধাপ ৩ আর ৪ মিলে δ̂(r0, vb) = rval(vb) mod m; invariant রক্ষা পেল।
  6. w গৃহীত ⇔ δ̂(r0, w) = r0 ⇔ val(w) mod m = 0. দুই দিক একসঙ্গে এল, কারণ invariant একটি সমতা। ∎

একই কৌশল অন্য ভিত্তিতেও চলে: দশমিকে অঙ্ক d পড়লে r → (10r + d) mod m. আর গণনা যদি সংখ্যার মান নয়, কোনো চিহ্নের সংখ্যা হয় (“a-এর সংখ্যা m দিয়ে বিভাজ্য”), তবে আরও সহজ: a-তে r → (r + 1) mod m, অন্য চিহ্নে state বদলায় না। গুদামের সেন্সর লাইনের “1-এর সংখ্যা জোড়” এরই m = 2 রূপ।

অন্তত, বড়জোর, ঠিক k

বাজারঘরের একটি নিয়ম: একটি অর্ডারে ঠিক দুটি “ফ্ল্যাশ-সেল” পণ্য থাকতে হবে। অর্ডারকে string ভাবুন, a মানে ফ্ল্যাশ-সেল পণ্য, b মানে সাধারণ পণ্য। এখানে গোনা থামানো যায়: দুইয়ের বেশি হলে “কত বেশি” জানা অপ্রয়োজনীয়। এই “থামানো গণক” (saturating counter) দিয়ে তিনটি পরিচিত ধাঁচ:

Language (Σ = {a, b})State-এর অর্থFState সংখ্যা
অন্তত k-টি a0, 1, …, k−1, “k বা বেশি”{k}k + 1
বড়জোর k-টি a0, 1, …, k, “k-এর বেশি” (dead){0, …, k}k + 2
ঠিক k-টি a0, 1, …, k, “k-এর বেশি” (dead){k}k + 2

সবচেয়ে পরিচিত ভুল “ঠিক k”-তে “k-এর বেশি” state বাদ দেওয়া: গণক k-তে থেমে গেলে k + 1টি a-ও k-এর মতো দেখায়। “অন্তত k”-তে ঠিক সেটিই চাই, “ঠিক k”-তে সেটিই বাগ। প্রতিটি সারির state সংখ্যা যে সবচেয়ে কম, তা অনুশীলন ৪-এ প্রমাণ করবেন। নিচের ব্লক উপপাদ্য ২.১ m = 3, 5, 7-এ আর টেবিলের তিনটি সারি দৈর্ঘ্য 12 পর্যন্ত সব string-এ মেলায়, সঙ্গে একটি ইচ্ছাকৃত বাগ। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
def shortlex(sigma, n):                  # all strings, length 0..n
    for k in range(n + 1):
        for t in product(sigma, repeat=k):
            yield "".join(t)
def accepts(dfa, w):
    delta, q, F = dfa
    for c in w:
        q = delta[q, c]
    return q in F
def first_bad(dfa, sigma, spec, n=12):   # shortest string where they differ
    for w in shortlex(sigma, n):
        if accepts(dfa, w) != spec(w):
            return repr(w)
    return "none up to length %d" % n
def mod_dfa(m):                          # binary value mod m, left to right
    delta = {(r, b): (2 * r + int(b)) % m for r in range(m) for b in "01"}
    return delta, 0, {0}
for m in (3, 5, 7):
    spec = lambda w, m=m: int(w or "0", 2) % m == 0
    print("divisible by", m, "->", first_bad(mod_dfa(m), "01", spec))
def count_dfa(top, F):                   # count a's, stop at top
    delta = {(i, c): min(i + (c == "a"), top)
             for i in range(top + 1) for c in "ab"}
    return delta, 0, F
k = 2
tests = [("at least 2", count_dfa(k, {k}), lambda w: w.count("a") >= k),
         ("at most 2", count_dfa(k + 1, {0, 1, 2}), lambda w: w.count("a") <= k),
         ("exactly 2", count_dfa(k + 1, {k}), lambda w: w.count("a") == k),
         ("exactly 2, bug", count_dfa(k, {k}), lambda w: w.count("a") == k)]
for name, dfa, spec in tests:
    states = len({q for q, _ in dfa[0]})
    print(f"{name:15} states {states}  first error: {first_bad(dfa, 'ab', spec)}")

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

divisible by 3 -> none up to length 12
divisible by 5 -> none up to length 12
divisible by 7 -> none up to length 12
at least 2      states 3  first error: none up to length 12
at most 2       states 4  first error: none up to length 12
exactly 2       states 4  first error: none up to length 12
exactly 2, bug  states 3  first error: 'aaa'

প্রতিটি m-এ দৈর্ঘ্য 0 থেকে 12-এর ৮,১৯১টি string-এ যন্ত্র আর int(w, 2) % m একমত। গোনার তিনটি নকশাও টেবিলের state সংখ্যায় (k = 2: ৩, ৪, ৪) নির্ভুল। শেষ লাইনের বাগওয়ালা যন্ত্রে মাত্র ৩টি state, গণক 2-তে থেমে যায়, তাই “aaa” আর “aa” আলাদা করতে পারে না; সবচেয়ে ছোট counterexample ঠিক “aaa”. লক্ষ করুন, int(w or "0", 2) লিখে ε-এর মান 0 ধরা হয়েছে, যা উপপাদ্যের শর্তের সঙ্গে মেলে। ε নিয়ে স্পষ্ট সিদ্ধান্ত না নিলে নকশা আর পরীক্ষা দুটিই অস্পষ্ট থাকে।

৩ · ধাঁচ খোঁজার কৌশল — prefix, suffix, substring আর শেষ k চিহ্ন

দ্বিতীয় বড় পরিবার হলো string-এর ভেতরে নির্দিষ্ট ধাঁচ খোঁজা। চারটি রূপ আছে, আর প্রতিটির state-এর অর্থ আলাদা।

  • Prefix (“BG দিয়ে শুরু”)। State মানে “ধাঁচের কতটুকু এ পর্যন্ত মিলেছে”: q0, q1 (B মিলেছে), q2 (BG মিলেছে)। প্রথম অমিলেই dead state, কারণ শুরু আর বদলানো যায় না। q2 সব চিহ্নে নিজের কাছে ফেরে: একবার শুরু ঠিক হলে বাকি যা খুশি।
  • Substring (“কোথাও SALE আছে”)। State মানে “পড়া অংশের এমন সবচেয়ে লম্বা suffix, যা SALE-এর prefix”. অমিল হলে dead state নয়, আংশিক মিলে ফেরা। শেষ state “পাওয়া গেছে” সব চিহ্নে নিজের কাছে ফেরে।
  • Suffix (“01 দিয়ে শেষ”)। Substring-এর মতোই state, কিন্তু শেষ state আটকে থাকে না: আরও চিহ্ন এলে আবার হিসাব চলে, কারণ শেষটাই গুরুত্বপূর্ণ।
  • শেষ k চিহ্ন (“শেষ থেকে দ্বিতীয় চিহ্ন 1”). শেষ k চিহ্নের পুরো জানালা মনে রাখতে হয়, তাই 2kটি state (শুরুর কয়েকটি অতিরিক্ত state লাগতে পারে)। পর্ব ১০-এ প্রমাণ হবে যে “শেষ থেকে k-তম চিহ্ন 1”-এর DFA-তে অন্তত 2kটি state লাগবেই, অথচ পর্ব ০৯-এর NFA মাত্র k + 1টি state-এ পারে।

বাজারঘরের কুপন: যেকোনো কোডে কোথাও “SALE” থাকলে ছাড় চালু হয়। হিসাব ছোট রাখতে Σ = {S, A, L, E, x}, যেখানে x মানে “অন্য যেকোনো অক্ষর”। State i (i = 0 … 4) মানে “শেষ i অক্ষর SALE-এর প্রথম i অক্ষরের সঙ্গে মেলে, আর এর চেয়ে বেশি মেলে না”। এই string matching automaton-এর নিয়ম: state i-তে c এলে, “SALE-এর প্রথম i অক্ষর + c”-এর যে সবচেয়ে লম্বা suffix আবার SALE-এর prefix, তার দৈর্ঘ্যই নতুন state.

stateSALEx
→ 0 (কিছু মেলেনি)10000
1 (S)12000
2 (SA)10300
3 (SAL)10040
∗ 4 (SALE পাওয়া)44444

টেবিলের S-কলামটি লক্ষ করুন: যেকোনো আংশিক মিলের মাঝে S এলে state 0 নয়, 1, কারণ এই S নিজেই নতুন একটি SALE-এর শুরু হতে পারে। নিচের stepper “SASALE” পড়ে দেখায় কেন এটি জরুরি।

1q = 0 (start)2read S: 0 → 13read A: 1 → 24read S: 2 → 15read A: 1 → 26read L: 2 → 37read E: 3 → 4, accept
পড়া অংশ আর আংশিক মিল
পড়া অংশ
মেলা prefix
state
  1. শুরু। কিছু পড়া হয়নি, মেলা অংশ ε, state 0.
  2. S. SALE-এর প্রথম অক্ষর মিলল: state 1.
  3. A. “SA” মিলল: state 2. এখন L চাই।
  4. আবার S. L আসেনি, তাই “SAL” হলো না। কিন্তু সব ফেলে state 0-তে ফেরা ভুল হতো: এইমাত্র পড়া S নিজেই একটি নতুন SALE-এর শুরু। “SAS”-এর সবচেয়ে লম্বা suffix যা SALE-এর prefix, তা “S”, তাই state 1.
  5. A. নতুন শুরু থেকে “SA”: state 2.
  6. L. “SAL”: state 3.
  7. E. “SALE” পূর্ণ: state 4, যা accepting আর সব চিহ্নে নিজের কাছে ফেরে। কুপন বৈধ। ধাপ ৪-এ state 0-তে ফিরলে এই কুপন বাতিল হয়ে যেত।

SALE-এর চারটি অক্ষর আলাদা, তাই এখানে শুধু S-এ ফেরা নিয়ে ভাবতে হয়। ধাঁচের ভেতরেই পুনরাবৃত্তি থাকলে ব্যাপারটি সূক্ষ্ম হয়। “aab” খুঁজতে গিয়ে কেউ লিখলেন: state 2 (“aa” মিলেছে)-এ a এলে যন্ত্র state 1-এ ফিরবে, যেন নতুন শুরু। কিন্তু “aaa”-এর শেষ দুটি অক্ষর এখনো “aa”, তাই সঠিক উত্তর state 2-তেই থাকা। সবচেয়ে ছোট যে string-এ ভুলটি ধরা পড়ে, তা “aaab”, যা §৬-এর ব্লক নিজে খুঁজে বের করবে। “সবচেয়ে লম্বা suffix যা prefix”, এই হিসাবই Knuth–Morris–Pratt (KMP) algorithm-এর failure function (১৯৭৭ সালে প্রকাশিত), যা পর্ব ২৩-এ আসবে; DSA কোর্সের পর্ব ৫৮-এ এর algorithm-এর দিক আছে।

৪ · Product construction — দুটি যন্ত্র একসঙ্গে

মেট্রোরেল স্টেশনের গেটে দুজন কর্মী: একজন টিকিট দেখেন, আরেকজন ব্যাগ। প্রত্যেকে নিজের খাতায় নিজের হিসাব রাখেন, কেউ অন্যের কাজে নাক গলান না। যাত্রী ঢুকবেন কি না, তা ঠিক হয় দুই খাতা মিলিয়ে: “দুজনেই রাজি” (and), “অন্তত একজন রাজি” (or), বা “টিকিট ঠিক কিন্তু ব্যাগে সমস্যা” (পার্থক্য)। দুই খাতার অবস্থা একসঙ্গে লিখলে পাওয়া যায় একটি জোড়া, আর সেটিই নতুন যন্ত্রের state.

গুদামের সেন্সর দুটি শর্ত একসঙ্গে চায়: বাক্সের সংখ্যা ৩ দিয়ে বিভাজ্য (DIV3, §২), আর binary লেখায় 1-এর সংখ্যা জোড় (EVEN1, parity-র DFA: state E মানে জোড়, O মানে বিজোড়)। DIV3 ∩ EVEN1-এর জন্য নতুন করে ভাবার দরকার নেই: দুটি যন্ত্র পাশাপাশি চালালেই হয়। এই নির্মাণের নাম product construction, কারণ নতুন state-এর সেট দুই state-সেটের Cartesian product.

সংজ্ঞা আর উপপাদ্য ৪.১ (product construction)

M1 = (Q1, Σ, δ1, s1, F1) আর M2 = (Q2, Σ, δ2, s2, F2) একই Σ-এর ওপর দুটি সম্পূর্ণ DFA. M = (Q1 × Q2, Σ, δ, (s1, s2), F), যেখানে

δ((p, q), a) = (δ1(p, a), δ2(q, a)).

তাহলে F-এর বাছাই অনুযায়ী:

  • F = F1 × F2 হলে L(M) = L(M1) ∩ L(M2)
  • F = (F1 × Q2) ∪ (Q1 × F2) হলে L(M) = L(M1) ∪ L(M2)
  • F = F1 × (Q2 ∖ F2) হলে L(M) = L(M1) ∖ L(M2) (set difference)
  • F = {(p, q) : p ∈ F1 আর q ∈ F2-এর ঠিক একটি সত্য} হলে symmetric difference

পুরো প্রমাণ একটি lemma-তে দাঁড়িয়ে: জোড়া যন্ত্র আসলেই দুটি যন্ত্রকে আলাদাভাবে চালায়।

Lemma ৪.২. সব w ∈ Σ∗ আর সব (p, q)-এর জন্য δ̂((p, q), w) = (δ̂1(p, w), δ̂2(q, w)).

  1. Base: w = ε. দুই দিকেই (p, q). — তিনটি δ̂-এর সংজ্ঞা
  2. Hypothesis: দৈর্ঘ্য n-এর v-এর জন্য δ̂((p, q), v) = (p′, q′), যেখানে p′ = δ̂1(p, v), q′ = δ̂2(q, v). w = va. — induction
  3. δ̂((p, q), va) = δ((p′, q′), a) = (δ1(p′, a), δ2(q′, a)). — δ̂-এর সংজ্ঞা, তারপর δ-এর সংজ্ঞা
  4. = (δ̂1(p, va), δ̂2(q, va)). ∎ — δ̂1, δ̂2-এর সংজ্ঞা

উপপাদ্যের প্রমাণ। Lemma অনুযায়ী w পড়ে M থামে (δ̂1(s1, w), δ̂2(s2, w))-এ। Intersection-এর ক্ষেত্রে: w ∈ L(M) ⇔ এই জোড়া F1 × F2-এ ⇔ δ̂1(s1, w) ∈ F1 আর δ̂2(s2, w) ∈ F2 ⇔ w ∈ L(M1) ∩ L(M2). বাকি তিনটি একই, শুধু “আর”-এর জায়গায় “অথবা”, “আর না” বা “ঠিক একটি”। প্রতিটি ⇔ একসঙ্গে দুই দিক দেয়। ∎

প্রমাণের একটি নীরব শর্ত আছে: δ1 আর δ2 দুটিই total. কোনো একটিতে কোনো transition না থাকলে জোড়ার transition-ও থাকে না, আর Lemma ৪.২ ভেঙে পড়ে। Intersection-এ এতে ক্ষতি হয় না (একটি আটকে গেলে এমনিতেই বাতিল), কিন্তু union আর পার্থক্যে হয়; অনুশীলন ২-এ সেটি ধরবেন। আর দুই যন্ত্রের Σ আলাদা হলে আগে দুটিকেই মিলিত alphabet-এ সম্পূর্ণ করতে হয়।

DIV3 × EVEN1: ছয়টি জোড়া state

উপরের সারি E (1-এর সংখ্যা জোড়), নিচের সারি O (বিজোড়)। আড়াআড়ি আর খাড়া তীরগুলো সব 1-এর; সারির ভেতরের তীর 0-এর। Intersection-এ শুধু (r0, E) accepting.

Product of the mod-3 DFA and the parity DFA r0,Er1,Er2,E r0,Or1,Or2,O 00 00 00 11
ছবি ৮.২ — 0 পড়লে বিট-গণনা বদলায় না বলে সারি একই থাকে, আর ভাগশেষ r → 2r mod 3 (r1 ⇄ r2); 1 পড়লে সারি উল্টায়, আর r → (2r + 1) mod 3 (r0 ⇄ r1, r2 → r2).

বাস্তবে Q1 × Q2-এর সব জোড়া লেখার দরকার নেই: শুরুর জোড়া থেকে reachable জোড়াগুলোই যথেষ্ট, আর সেগুলো breadth-first search দিয়ে একে একে বের করা যায় (graph-এর reachability, পর্ব ০২)। বাকি জোড়াগুলো কোনো string পড়ে পৌঁছানো যায় না, তাই language-এ তাদের কোনো ভূমিকা নেই। নিচের stepper সেই BFS চালায়, তারপর “1001” (মান 9) পড়ে।

1start = (0,E); queue = [start]2pop (0,E), write its row3pop (1,O)4pop (2,O)5pop (2,E)6pop (1,E)7pop (0,O): nothing new, stop8run 1001 on the pairs
BFS-এর অবস্থা
নতুন সারি
অপেক্ষমাণ
পাওয়া state
  1. শুরু। দুই যন্ত্রের শুরু r0 আর E, তাই জোড়া (0,E). এটিকে অপেক্ষমাণ তালিকায় (queue) রাখা হলো।
  2. (0,E)-এর সারি। 0 পড়লে r0 → r0, E → E: (0,E). 1 পড়লে r0 → r1, E → O: (1,O), যা নতুন।
  3. (1,O). 0-তে (2 mod 3 = 2, O): (2,O), নতুন। 1-এ (3 mod 3 = 0, O → E): (0,E), আগেই পাওয়া।
  4. (2,O). 0-তে (4 mod 3 = 1, O): (1,O). 1-এ (5 mod 3 = 2, E): (2,E), নতুন।
  5. (2,E). 0-তে (1,E), নতুন। 1-এ (2,O), আগেই পাওয়া।
  6. (1,E). 0-তে (2,E). 1-এ (0,O), নতুন। এখন ৬টি জোড়াই পাওয়া গেছে।
  7. (0,O) আর থামা। 0-তে (0,O), 1-এ (1,E), কোনোটি নতুন নয়, queue ফাঁকা। এখানে ৩ × ২ = ৬টি জোড়ার সবকটিই reachable.
  8. 1001 পড়া। (0,E) → (1,O) → (2,O) → (1,O) → (0,E). শেষ জোড়ায় r0 (9 ৩ দিয়ে বিভাজ্য) আর E (দুটি 1), তাই intersection-এ গৃহীত।

সব জোড়া সবসময় reachable হয় না। দুটি যন্ত্র ভাবুন: একটি জোড় দৈর্ঘ্য চেনে, অন্যটি বিজোড় দৈর্ঘ্য, দুটিই দুই state-এর। জোড়ার ৪টি সম্ভাবনার মধ্যে শুরু থেকে পৌঁছানো যায় মাত্র ২টিতে, কারণ দুই যন্ত্র সবসময় একসঙ্গে উল্টায়; আর intersection-এর কোনো accepting জোড়াই reachable নয়, অর্থাৎ language ∅, যা হওয়ারই কথা। নিচের ব্লক একটি সাধারণ product builder: যেকোনো দুটি সম্পূর্ণ DFA আর একটি বুলিয়ান operation নিয়ে BFS দিয়ে শুধু reachable জোড়া বানায়, আর চারটি operation-এর প্রতিটিকে দৈর্ঘ্য 12 পর্যন্ত সংজ্ঞার সঙ্গে মেলায়।

from itertools import product
from collections import deque
M3 = ({(r, b): (2 * r + int(b)) % 3 for r in range(3) for b in "01"}, 0, {0})
PAR = ({("E", "0"): "E", ("E", "1"): "O",
        ("O", "0"): "O", ("O", "1"): "E"}, "E", {"E"})
def product_dfa(A, B, sigma, keep):      # keep(in F1?, in F2?) -> accept?
    (dA, sA, FA), (dB, sB, FB) = A, B
    start = (sA, sB)
    delta, seen, todo = {}, [start], deque([start])
    while todo:                          # BFS: only reachable pairs
        s = todo.popleft()
        for c in sigma:
            t = (dA[s[0], c], dB[s[1], c])
            delta[s, c] = t
            if t not in seen:
                seen.append(t)
                todo.append(t)
    F = {s for s in seen if keep(s[0] in FA, s[1] in FB)}
    return delta, start, F, seen
def run(delta, q, w):
    for c in w:
        q = delta[q, c]
    return q
val3 = lambda w: int(w or "0", 2) % 3 == 0
even = lambda w: w.count("1") % 2 == 0
ops = {"and": lambda x, y: x and y, "or": lambda x, y: x or y,
       "minus": lambda x, y: x and not y, "xor": lambda x, y: x != y}
delta, start, F, seen = product_dfa(M3, PAR, "01", ops["and"])
for s in seen:
    print(s, "->", delta[s, "0"], delta[s, "1"], "*" if s in F else "")
words = [w for k in range(13) for w in map("".join, product("01", repeat=k))]
for name, op in ops.items():
    delta, start, F, seen = product_dfa(M3, PAR, "01", op)
    bad = sum((run(delta, start, w) in F) != op(val3(w), even(w)) for w in words)
    print(f"{name:5} |F| = {len(F)}  wrong on {bad} of {len(words)}")

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

(0, 'E') -> (0, 'E') (1, 'O') *
(1, 'O') -> (2, 'O') (0, 'E')
(2, 'O') -> (1, 'O') (2, 'E')
(2, 'E') -> (1, 'E') (2, 'O')
(1, 'E') -> (2, 'E') (0, 'O')
(0, 'O') -> (0, 'O') (1, 'E')
and   |F| = 1  wrong on 0 of 8191
or    |F| = 4  wrong on 0 of 8191
minus |F| = 1  wrong on 0 of 8191
xor   |F| = 3  wrong on 0 of 8191

প্রথম ছয় লাইন stepper-এর BFS-এর হুবহু একই ক্রম আর একই সারি; তারকা (*) চিহ্নিত (0,E) intersection-এর একমাত্র accepting state. তারপর চারটি operation: transition একই থাকে, শুধু F বদলায়। Union-এ |F| = 4: যেসব জোড়ায় r0 অথবা E আছে, অর্থাৎ (0,E), (0,O), (2,E), (1,E). পার্থক্যে শুধু (0,O): ৩ দিয়ে বিভাজ্য কিন্তু 1-এর সংখ্যা বিজোড়, যেমন 10101 = 21. চারটিতেই ৮,১৯১টি string-এ একটিও অমিল নেই। একটি কথা মনে রাখুন: op ফাংশনটি পরীক্ষার “সংজ্ঞা”, আর যন্ত্রটি কেবল F বাছতে keep ব্যবহার করে; দুটি একই ফাংশন বলে এই পরীক্ষা মূলত Lemma ৪.২ যাচাই করে, অর্থাৎ জোড়া যন্ত্র আসলেই দুই যন্ত্রকে আলাদাভাবে চালায়।

State-এর হিসাব: product-এ বড়জোর |Q1| · |Q2|টি state, আর k-টি যন্ত্রের intersection-এ গুণফল |Q1| · … · |Qk|, যা k বাড়লে exponential হারে বাড়ে। দুটি যন্ত্রের ক্ষেত্রে এটি সাধারণত কোনো সমস্যা নয়, কিন্তু অনেক যন্ত্র একসঙ্গে হলে এটিই verification-এর বিখ্যাত “state explosion” (ভাবনার প্রশ্ন ২)। নিচের JS সিমুলেটর দুই যন্ত্র পাশাপাশি চালায় আর প্রতিটি জোড়ার পথ ছাপে; আপনার নিজের string বসিয়ে আবার চালান।

// Run the mod-3 DFA and the parity DFA side by side.
// Edit the list of strings at the bottom and press Run again.
const m3 = (r, b) => (2 * r + Number(b)) % 3;
const par = (p, b) => (b === "1" ? (p === "E" ? "O" : "E") : p);
function runPair(w) {
  let r = 0, p = "E";
  const path = [`(${r},${p})`];
  for (const b of w) {
    r = m3(r, b);                      // both machines read the same bit
    p = par(p, b);
    path.push(`(${r},${p})`);
  }
  const div3 = r === 0, even = p === "E";
  console.log(JSON.stringify(w).padEnd(8) + path.join(">"));
  console.log("   and " + (div3 && even) + "  or " + (div3 || even) +
              "  minus " + (div3 && !even));
}
for (const w of ["", "1001", "111", "10101"]) runPair(w);

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

""      (0,E)
   and true  or true  minus false
"1001"  (0,E)>(1,O)>(2,O)>(1,O)>(0,E)
   and true  or true  minus false
"111"   (0,E)>(1,O)>(0,E)>(1,O)
   and false  or false  minus false
"10101" (0,E)>(1,O)>(2,O)>(2,E)>(1,E)>(0,O)
   and false  or true  minus true

ε-এর মান 0 আর তাতে 1-এর সংখ্যাও 0 (জোড়), তাই ফাঁকা string দুই যন্ত্রেই গৃহীত, এবং intersection-এও। 111 = 7: ভাগশেষ 1, তিনটি 1 বিজোড়, তাই কোনোটিতেই নয়। 10101 = 21: ৩ দিয়ে বিভাজ্য কিন্তু 1 তিনটি, তাই শুধু union আর পার্থক্যে। প্রতিটি পথ ছবি ৮.২-এর তীর ধরে আঙুল দিয়ে মেলানো যায়।

৫ · Complement — accepting state অদলবদল, আর partial DFA-র ফাঁদ

একটি language L ⊆ Σ∗-এর complement হলো L̄ = Σ∗ ∖ L. DFA-তে এটি পাওয়ার কৌশল প্রায় হাস্যকর রকম সহজ।

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

M = (Q, Σ, δ, q0, F) একটি সম্পূর্ণ DFA হলে M̄ = (Q, Σ, δ, q0, Q ∖ F) ঠিক Σ∗ ∖ L(M) চেনে।

প্রমাণ এক লাইনের, আর পর্ব ০৪-এ direct proof-এর উদাহরণ হিসেবে এসেছে: δ বদলায়নি, তাই যেকোনো w পড়ে দুই যন্ত্র একই state q = δ̂(q0, w)-এ থামে; q ∈ Q ∖ F ⇔ q ∉ F. ∎ কিন্তু “একই state-এ থামে” কথাটির পেছনে একটি অনুমান আছে: δ̂(q0, w) সংজ্ঞায়িত, অর্থাৎ যন্ত্র কোথাও আটকে যায় না। সেটিই “সম্পূর্ণ” শর্ত।

ছবি আঁকার সময় আমরা প্রায়ই dead state বাদ দিই: “যে transition আঁকা নেই, তা dead state-এ যায়” ধরে নিয়ে। এমন ছবিকে বলে partial DFA; এই কোর্সে partial ছবি আঁকলে সবসময় স্পষ্ট লেখা থাকবে, “না-আঁকা transition dead state qd-তে যায়”। গ্রহণের জন্য এটি নিরীহ, কারণ আটকে যাওয়া মানে বাতিল। কিন্তু complement-এ এই নিরীহ সংক্ষেপই সর্বনাশ ঘটায়।

1M: q0 -B-> q1 -G-> q2, q2 loops on B,G2naive: F' = {q0, q1}3test "G": no move from q04test "BB": no move from q15complete: add dead state d6swap: F' = {q0, q1, d}7test G, BB, BGB again
যন্ত্রের অবস্থা
Q
F′
“G”
“BB”
“BGB”
  1. দেওয়া যন্ত্র। Σ = {B, G}, L = “BG দিয়ে শুরু”। ছবিতে মাত্র চারটি তীর: q0 থেকে B, q1 থেকে G, আর q2-তে দুই চিহ্নে নিজের কাছে ফেরা। q0-তে G আর q1-এ B আঁকা নেই।
  2. সরল অদলবদল। F = {q2} উল্টে F′ = {q0, q1}. দেখতে ঠিক মনে হয়।
  3. “G” পরীক্ষা। “G” BG দিয়ে শুরু নয়, তাই complement-এ থাকার কথা। কিন্তু q0 থেকে G-এর কোনো তীর নেই: যন্ত্র আটকে গেল, আর আটকে যাওয়া মানে বাতিল। ভুল।
  4. “BB” পরীক্ষা। একই সমস্যা: q1-এ B নেই। যন্ত্র আসলে শুধু ε আর “B” গ্রহণ করে, অর্থাৎ শুধু সেই string যারা এখনো BG হয়ে উঠতে পারত।
  5. সম্পূর্ণ করা। নতুন dead state d: δ(q0, G) = d, δ(q1, B) = d, আর d-তে দুই চিহ্নে d. এখন প্রতিটি state-এ প্রতিটি চিহ্নে একটি তীর।
  6. এবার অদলবদল। F′ = Q ∖ {q2} = {q0, q1, d}. Dead state নিজেই complement-এ accepting হয়ে গেল: “শুরু ভুল হয়েছে” মানেই “BG দিয়ে শুরু নয়”।
  7. আবার পরীক্ষা। G আর BB পড়ে d-তে, গৃহীত; BGB পড়ে q2-তে, বাতিল। দৈর্ঘ্য 10 পর্যন্ত ২,০৪৭টি string-এর মধ্যে ভুল যন্ত্রটি ১,৫৩৪টিতে ভুল উত্তর দিত, সংশোধিতটি একটিতেও নয় (scratch-এ গুনে দেখা)।

Complement আর product মিলিয়ে difference আরেকভাবেও পাওয়া যায়: L1 ∖ L2 = L1 ∩ L̄2. M2-এর complement নিয়ে intersection-এর product বানালে F হয় F1 × (Q2 ∖ F2), ঠিক উপপাদ্য ৪.১-এর তৃতীয় সারি। De Morgan-এর সূত্রে L1 ∪ L2 = complement(L̄1 ∩ L̄2), তাই complement আর intersection থাকলেই সব বুলিয়ান operation পাওয়া যায়।

Closure-এর পরিভাষা: এই দুই উপপাদ্য থেকে বলা যায়, regular language-এর শ্রেণি union, intersection, complement আর difference-এ বদ্ধ: দুটি regular language-এর ওপর এগুলো চালালে ফল আবার regular. এই ধরনের বক্তব্যকে বলে closure property. Concatenation, star, reversal আর homomorphism-এর closure-সহ পুরো তালিকা পর্ব ১৬-এ, যেখানে NFA আর regex-এর সাহায্যে প্রমাণ সহজ হয়।

NFA-তে অদলবদল চলে না। পর্ব ০৯-এর NFA একটি string গ্রহণ করে যদি কোনো পথ accepting-এ শেষ হয়। accepting সেট উল্টালে নতুন যন্ত্র গ্রহণ করে যদি কোনো পথ non-accepting-এ শেষ হয়, যা “কোনো পথই accepting নয়” থেকে আলাদা। তাই NFA-র complement নিতে আগে পর্ব ১০-এর subset construction দিয়ে DFA বানাতে হয়।

৬ · নকশা যাচাই — brute force আর counterexample খোঁজা

একটি নকশা ঠিক কি না, তার পূর্ণ উত্তর দেয় প্রমাণ। কিন্তু প্রমাণের আগে, আর প্রমাণের পরেও, সবচেয়ে সস্তা পরীক্ষা হলো brute force: Σ-এর ওপর দৈর্ঘ্য 0 থেকে n-এর সব string shortlex ক্রমে (আগে দৈর্ঘ্য, তারপর অভিধানের ক্রম) তৈরি করে যন্ত্রের উত্তর আর সংজ্ঞার উত্তর মেলানো। Shortlex-এর সুবিধা: প্রথম যে অমিল পাওয়া যায়, সেটিই সবচেয়ে ছোট counterexample, আর ছোট উদাহরণ থেকে বাগ বোঝা সহজ।

তারপর লম্বা random string: কিছু বাগ শুধু লম্বা ইনপুটে দেখা দেয় (যেমন গণক বড় সংখ্যায় পৌঁছালে)। Random পরীক্ষায় seed বেঁধে দিন, যাতে আবার চালালে একই ফল আসে। সফটওয়্যার টেস্টিং কোর্সের পর্ব ৫৮-এ এই পদ্ধতির পূর্ণ রূপ, property-based testing, আছে; আর state machine-কে পরীক্ষার দিক থেকে দেখতে একই কোর্সের পর্ব ১০।

নিচের ব্লক একটি “আমার বাগ খুঁজুন” শিকারি: চারটি নকশা, প্রতিটির সঙ্গে সংজ্ঞাটি Python predicate হিসেবে। প্রথমে দৈর্ঘ্য 10 পর্যন্ত shortlex, তারপর দৈর্ঘ্য 11 থেকে 40-এর ২,০০০টি random string. Partial DFA-র না-থাকা transition মানে বাতিল, ঠিক ছবির নিয়মের মতো।

import random
from itertools import product
def accepts(delta, start, F, w):         # a missing transition = reject
    q = start
    for c in w:
        if (q, c) not in delta:
            return False
        q = delta[q, c]
    return q in F
def hunt(name, delta, start, F, sigma, spec, n=10):
    for k in range(n + 1):               # shortlex: shortest bug first
        for w in map("".join, product(sigma, repeat=k)):
            if accepts(delta, start, F, w) != spec(w):
                print(f"{name:14} counterexample {w!r}")
                return
    rng = random.Random(8)               # then 2000 long random strings
    for _ in range(2000):
        w = "".join(rng.choice(sigma) for _ in range(rng.randint(11, 40)))
        if accepts(delta, start, F, w) != spec(w):
            print(f"{name:14} random counterexample of length {len(w)}")
            return
    print(f"{name:14} no counterexample found")
aab_bug = {(0, "a"): 1, (0, "b"): 0, (1, "a"): 2, (1, "b"): 0,
           (2, "a"): 1, (2, "b"): 3, (3, "a"): 3, (3, "b"): 3}
aab_fix = dict(aab_bug); aab_fix[2, "a"] = 2
hunt("aab, reset", aab_bug, 0, {3}, "ab", lambda w: "aab" in w)
hunt("aab, fixed", aab_fix, 0, {3}, "ab", lambda w: "aab" in w)
starts = {("q0", "B"): "q1", ("q1", "G"): "q2",
          ("q2", "B"): "q2", ("q2", "G"): "q2"}   # partial DFA
hunt("not BG..", starts, "q0", {"q0", "q1"}, "BG",
     lambda w: not w.startswith("BG"))
par = {("E", "0"): "E", ("E", "1"): "O", ("O", "0"): "O", ("O", "1"): "E"}
hunt("nonempty even", par, "E", {"E"}, "01",
     lambda w: len(w) >= 1 and w.count("1") % 2 == 0)

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

aab, reset     counterexample 'aaab'
aab, fixed     no counterexample found
not BG..       counterexample 'G'
nonempty even  counterexample ''

চারটি নকশা, চারটি শিক্ষা। প্রথমটি §৩-এর “aab”-এ ভুল ফেরা: সবচেয়ে ছোট counterexample “aaab”. সংশোধিতটি (state 2-তে a এলে 2-তেই থাকা) দৈর্ঘ্য 10 পর্যন্ত আর ২,০০০টি লম্বা string-এ টিকে গেছে; এটি সঠিকতার প্রমাণ নয়, তবে ভালো প্রমাণ। তৃতীয়টি §৫-এর partial complement, প্রথম ভুল “G”-তেই। চতুর্থটি ε-এর ভুল: সেন্সর লাইনের নিয়ম বলে ফাঁকা বার্তা বৈধ নয়, অথচ parity-র DFA ε গ্রহণ করে, কারণ শুরুর state E accepting. সমাধান: একটি আলাদা শুরুর state, যা accepting নয় আর প্রথম চিহ্নেই E বা O-তে যায়।

পরীক্ষার ধাঁচের একটি পূর্ণ নকশা

প্রশ্ন: Σ = {a, b}. L = {w : w-এ a-এর সংখ্যা জোড় আর w b দিয়ে শেষ}-এর DFA নকশা করুন।

  1. বর্ণনা: ε b দিয়ে শেষ নয়, তাই ε ∉ L. ছোট সদস্য: b, bb, aab, bbb; “ab” নয় (a একটি), “ba” নয় (a-তে শেষ)।
  2. দুটি সহজ যন্ত্র: A = a-এর parity (জোড়/বিজোড়), B = “শেষ চিহ্ন b কি না” (হ্যাঁ/না)। প্রতিটিতে ২টি state.
  3. Product: state (p, ℓ), p ∈ {জোড়, বিজোড়}, ℓ ∈ {b-শেষ, না}. a পড়লে p উল্টায় আর ℓ = না; b পড়লে p একই আর ℓ = b-শেষ. শুরু (জোড়, না), F = {(জোড়, b-শেষ)}।
  4. পরীক্ষা: “abab”: (জোড়,না) → (বিজোড়,না) → (বিজোড়,b) → (জোড়,না) → (জোড়,b), গৃহীত: দুটি a, b-তে শেষ। দৈর্ঘ্য 12 পর্যন্ত সব string-এ সংজ্ঞার সঙ্গে মেলানো হয়েছে।
  5. সঠিকতা: উপপাদ্য ৪.১ (intersection) আর দুই ছোট যন্ত্রের invariant থেকে সরাসরি। ∎

উত্তরে ৪টি state. কিন্তু এটিই কি সবচেয়ে ছোট? §৮-এ দেখবেন, না।

৭ · সত্যিকারের run — automata-lib দিয়ে product, complement আর equivalence

নিজের হাতে লেখা সিমুলেটর ছোট আর স্বচ্ছ, কিন্তু একটি স্বাধীন library দিয়ে মেলালে নিজের কোডের বাগও ধরা পড়ে। automata-lib একটি Python library (MIT licence), যাতে DFA-র ওপর & (intersection), | (union), - (difference), ~ (complement), ^ (symmetric difference), <= (subset) আর == (একই language কি না) সরাসরি লেখা যায়। নিচের সব কমান্ড আর আউটপুট একটি সত্যিকারের run থেকে নেওয়া: automata-lib 9.2.0, Python 3.12, একটি আলাদা uv প্রকল্পে। Library-টি কোনো usage তথ্য পাঠায় না।

~/bazarghar-toc$ uv init --vcs none --author-from none
~/bazarghar-toc$ uv add automata-lib
 + automata-lib==9.2.0
~/bazarghar-toc$ uv run python real_ops.py
from importlib.metadata import version
from automata.fa.dfa import DFA

print("automata-lib", version("automata-lib"))
S = {"0", "1"}
mod3 = DFA(states={"r0", "r1", "r2"}, input_symbols=S,
           transitions={"r0": {"0": "r0", "1": "r1"},
                        "r1": {"0": "r2", "1": "r0"},
                        "r2": {"0": "r1", "1": "r2"}},
           initial_state="r0", final_states={"r0"})
even1 = DFA(states={"E", "O"}, input_symbols=S,
            transitions={"E": {"0": "E", "1": "O"},
                         "O": {"0": "O", "1": "E"}},
            initial_state="E", final_states={"E"})
both, either, only3 = mod3 & even1, mod3 | even1, mod3 - even1
print("states:", len(both.states), len(either.states), len(only3.states))
for w in ["", "110", "1001", "111", "10101"]:
    print(f"{w!r:8}", both.accepts_input(w), either.accepts_input(w),
          only3.accepts_input(w))
print("~mod3 == Sigma* - mod3:", ~mod3 == DFA.universal_language(S) - mod3)
print("both <= mod3:", both <= mod3, " mod3 <= both:", mod3 <= both)
print("minimal states of both:", len(both.minify().states))

bug = DFA(states={0, 1, 2, 3}, input_symbols={"a", "b"},
          transitions={0: {"a": 1, "b": 0}, 1: {"a": 2, "b": 0},
                       2: {"a": 1, "b": 3}, 3: {"a": 3, "b": 3}},
          initial_state=0, final_states={3})
ref = DFA.from_substring({"a", "b"}, "aab")     # library's reference
print("bug == ref:", bug == ref)
diff = bug ^ ref                                # where they disagree
n = diff.minimum_word_length()
print("shortest witnesses:", sorted(diff.words_of_length(n)))

part = DFA(states={"q0", "q1", "q2"}, input_symbols={"B", "G"},
           transitions={"q0": {"B": "q1"}, "q1": {"G": "q2"},
                        "q2": {"B": "q2", "G": "q2"}},
           initial_state="q0", final_states={"q2"}, allow_partial=True)
comp = ~part
print("complement of partial:", len(comp.states), "states,",
      [w for w in ["", "B", "G", "BB", "BG"] if comp.accepts_input(w)])

সত্যিকারের run-এর আউটপুট:

automata-lib 9.2.0
states: 6 6 6
''       True True False
'110'    True True False
'1001'   True True False
'111'    False False False
'10101'  False True True
~mod3 == Sigma* - mod3: True
both <= mod3: True  mod3 <= both: False
minimal states of both: 6
bug == ref: False
shortest witnesses: ['aaab']
complement of partial: 4 states, ['', 'B', 'G', 'BB']
  • Product: তিনটি operation-এই ৬টি state, আর উত্তরগুলো আমাদের JS আর Pyodide ব্লকের সঙ্গে হুবহু মেলে, একটি সম্পূর্ণ আলাদা implementation থেকে।
  • Complement আর equivalence: ~mod3 আর Σ∗ − DIV3 একই language. == এখানে string-এর তালিকা নয়, দুটি DFA-র language তুলনা করে; এটি সব দৈর্ঘ্যের জন্য নিশ্চিত উত্তর দেয়, কারণ DFA-র equivalence decidable (পর্ব ২০-এ এর algorithm).
  • Subset: DIV3 ∩ EVEN1 ⊆ DIV3 সত্য, উল্টোটা নয়: 10101 = 21 DIV3-এ আছে, কিন্তু তাতে 1 তিনটি, তাই intersection-এ নেই।
  • Minimal: intersection-এর ৬টি state-এর কোনোটি জোড়া লাগানো যায় না: ৬-ই সবচেয়ে কম (§৮)।
  • বাগ শিকার: library-র নিজস্ব “aab আছে” DFA-র সঙ্গে symmetric difference নিয়ে সবচেয়ে ছোট সাক্ষী খোঁজা হয়েছে: “aaab”, ঠিক আমাদের brute force-এর উত্তর, কিন্তু এবার কোনো দৈর্ঘ্যের সীমা ছাড়াই।
  • Partial complement: allow_partial=True দিয়ে partial DFA দিলে library নিজে একটি trap state যোগ করে তারপর অদলবদল করে: ৪টি state, আর “G”, “BB” ঠিকভাবে গৃহীত। ভালো library §৫-এর ফাঁদ নিজেই এড়ায়; হাতে লেখা কোডকে সেটা শেখাতে হয়।

৮ · সবচেয়ে কম state-এর অনুভূতি আর সাধারণ ভুল

§৬-এর নকশায় ৪টি state ছিল: (জোড়,না), (জোড়,b), (বিজোড়,না), (বিজোড়,b). এখন (বিজোড়,না) আর (বিজোড়,b)-এর ভবিষ্যৎ তুলনা করুন। দুটিতেই a-এর সংখ্যা বিজোড়। পরে যে string v আসুক, গ্রহণের শর্ত “মোট a জোড় আর শেষ চিহ্ন b”; v ফাঁকা হলে দুটিই বাতিল (a বিজোড়), আর v ফাঁকা না হলে শেষ চিহ্ন v-ই ঠিক করে, পুরনো ℓ নয়। তাই দুই state-এর ভবিষ্যৎ হুবহু এক, আর এদের একটিতে মেশানো যায়। ফল ৩টি state, আর এর কম সম্ভব নয়: ε, “b” আর “a” পরস্পর distinguishable (ε আর b-কে আলাদা করে ε নিজে; ε আর a-কে আলাদা করে “b”; b আর a-কে আলাদা করে ε)। Pyodide-এ partition refinement চালিয়ে মিলিয়ে দেখা হয়েছে: minimal ৩.

Product construction তাই সবসময় সঠিক, কিন্তু সবসময় সবচেয়ে ছোট নয়। DIV3 ∩ EVEN1-এর ক্ষেত্রে ৬টিই দরকার (automata-lib-এর minify() উপরে তা দেখিয়েছে)। এক যন্ত্রের অংশেও এমন হয়: binary-তে 4 দিয়ে বিভাজ্যতার mod-4 DFA-তে ৪টি state, অথচ সবচেয়ে ছোট DFA-তে ৩টি, কারণ শুধু শেষ দুটি bit গুরুত্বপূর্ণ (ভাবনার প্রশ্ন ৩)। দুটি state মেশানো যায় ঠিক তখন, যখন কোনো suffix তাদের আলাদা করে না; এই ধারণার পূর্ণ তত্ত্ব পর্ব ১৮ (Myhill–Nerode), আর algorithm পর্ব ১৯ (DFA minimization). নকশার সময় একটি ব্যবহারিক নিয়মই যথেষ্ট: দুটি state-এর বাক্য পড়ে যদি কোনো ভবিষ্যৎ ইনপুট খুঁজে না পান যা তাদের আলাদা করে, তবে সম্ভবত তারা এক।

নকশার সাধারণ ভুল

ভুলউদাহরণকীভাবে ধরবেন
ε ভুলে যাওয়া“ফাঁকা নয়, 1 জোড়”-তে শুরুর state acceptingBrute force সবসময় ε দিয়ে শুরু করে
Dead state বাদ“ঠিক 2টি a”-তে গণক 2-তে থামেTransition table-এ ফাঁকা বা সন্দেহজনক ঘর খুঁজুন
এক-কম-বেশি গোনা“অন্তত 2”-এর জায়গায় F = {3}সীমার দুই পাশ, k − 1, k, k + 1, পরীক্ষা করুন
ভুল জায়গায় ফেরা“aab”-এ অমিলে সবসময় শুরুতে ফেরাধাঁচের নিজের ভেতরের পুনরাবৃত্তি দেখুন; “সবচেয়ে লম্বা suffix যা prefix”
Partial DFA-র complement“BG দিয়ে শুরু নয়”-এ “G” বাতিলঅদলবদলের আগে সম্পূর্ণ করুন
Partial DFA-র union বা পার্থক্যএক যন্ত্র আটকে গেলে জোড়াও আটকায়Product-এর আগে দুটিকেই সম্পূর্ণ করুন
Alphabet না মেলাএক যন্ত্র {0, 1}, অন্যটি {0, 1, 2}মিলিত Σ-এ দুটিকেই সম্পূর্ণ করুন

আরও গভীরে: দুটি DFA-র product তুচ্ছ, কিন্তু k-টি DFA-র intersection ফাঁকা কি না, এই প্রশ্ন k-কে ইনপুটের অংশ ধরলে PSPACE-complete, যা Dexter Kozen ১৯৭৭ সালে দেখান; তাই এর polynomial-time algorithm থাকলে P = PSPACE হতো, যা অজানা (PSPACE-completeness আসবে পর্ব ৬৫-এ)। দুটি DFA-র ক্ষেত্রেও কাজটি আসলে |Q1| · |Q2| আকারের graph-এ reachability. গবেষণায় একটি বড় প্রশ্ন “state complexity”: একটি operation-এর ফলের minimal DFA-তে সবচেয়ে খারাপ ক্ষেত্রে কত state লাগে; intersection-এর জন্য উত্তর ঠিক mn, যা এই পর্বের ঊর্ধ্বসীমাকে আঁটসাঁট করে।

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

  • Binary সংখ্যা ৩ (বা ৫) দিয়ে বিভাজ্য কি না, তার DFA? m-টি state, δ(r, b) = (2r + b) mod m, শুরু আর F = {r0}.
  • m আর n state-এর দুটি DFA-র intersection-এর DFA-তে কত state? বড়জোর mn; product construction, F = F1 × F2.
  • DFA-র complement কীভাবে? সম্পূর্ণ করে accepting আর non-accepting অদলবদল; partial হলে আগে dead state.
  • “ঠিক k-টি a”-এর DFA-তে কত state? k + 2: 0 থেকে k, আর “k-এর বেশি”।
  • দুটি DFA একই language চেনে কি না কীভাবে পরীক্ষা করবেন? ছোট দৈর্ঘ্যে brute force; নিশ্চিত উত্তরের জন্য symmetric difference-এর product ফাঁকা কি না।

৯ · AI-এর যুগে — DFA নকশায় AI-কে কীভাবে ব্যবহার করবেন

AI সহকারীকে “এই language-এর DFA আঁকো” বললে প্রায় সবসময় একটি সুন্দর টেবিল আসে। সমস্যা হলো, টেবিলটি প্রায়ই একটু আলাদা language চেনে, আর চোখে দেখে তা ধরা কঠিন। এই পর্বের প্রতিটি বাগই AI-এর উত্তরে নিয়মিত দেখা যায়:

AI-এর ভুলকীভাবে ধরবেন
গোনায় এক কম-বেশি, “ঠিক k”-তে dead state নেইদৈর্ঘ্য 0 থেকে 10-এর সব string-এ predicate-এর সঙ্গে মেলান (§২, §৬-এর ব্লক)
ε-এর সিদ্ধান্ত ভুল বা অস্পষ্টআগে নিজে লিখুন ε ∈ L কি না; brute force ε দিয়েই শুরু হয়
Partial DFA-র complement, বা partial যন্ত্রে union-এর productপ্রতিটি state-এ |Σ|টি transition আছে কি না গুনুন
ধাঁচ খোঁজায় অমিলে ভুল state-এ ফেরাধাঁচের পুনরাবৃত্ত অংশ দিয়ে তৈরি string (aaab, SASALE) পরীক্ষা করুন
“সবচেয়ে ছোট DFA” দাবি, প্রমাণ ছাড়া; বানানো theorem বা referenceminify বা distinguishable string দিয়ে মেলান; Sipser বা Hopcroft–Motwani–Ullman-এ মেলান

AI-এর কাছে DFA চাইলে এমন কাঠামো দিন, যাতে উত্তর যাচাই করা যায়:

নিচের language-এর জন্য একটি DFA নকশা করো: Language: [যেমন "Σ = {a, b}, a-এর সংখ্যা জোড় আর w b দিয়ে শেষ"] ১. প্রথমে বলো ε এই language-এ আছে কি না, আর দৈর্ঘ্য ৩ পর্যন্ত সব সদস্যের তালিকা দাও। ২. প্রতিটি state-এর অর্থ এক বাক্যে লেখো ("এ পর্যন্ত ... ")। ৩. পূর্ণ transition table দাও: প্রতিটি state আর প্রতিটি চিহ্নের ঘর, dead state থাকলে স্পষ্ট নাম দিয়ে। ৪. Product construction ব্যবহার করলে দুই অংশ-যন্ত্র আর F কীভাবে বাছলে, তা লেখো। ৫. শুধু itertools দিয়ে একটি ছোট Python কোড দাও, যা দৈর্ঘ্য ১০ পর্যন্ত সব string-এ DFA আর সংজ্ঞা মিলিয়ে প্রথম অমিল ছাপে। ৬. DFA-টি সবচেয়ে ছোট বলে দাবি করলে distinguishable string দিয়ে কারণ দেখাও; নিশ্চিত না হলে সেটা বলো।

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

সবচেয়ে কাজের অভ্যাস: AI-এর DFA আর আপনার সংজ্ঞাকে আলাদা দুটি ফাংশন হিসেবে লিখুন, তারপর §৬-এর শিকারি চালান। Counterexample পেলে সেটিই AI-কে ফেরত দিন (“এই string-এ যন্ত্রটি ভুল উত্তর দেয়”); ঝাপসা অভিযোগের চেয়ে একটি নির্দিষ্ট string অনেক দ্রুত ঠিক উত্তর আনে।

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

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

প্র ০১Product construction আর closure property-র ধারণা কোথা থেকে এল, আর কেন তা আজও প্রতিটি পাঠ্যবইয়ের শুরুতে?

সসীম যন্ত্রের গাণিতিক অধ্যয়ন শুরু হয় ১৯৪০ আর ১৯৫০-এর দশকে, কয়েকটি আলাদা দিক থেকে। Warren McCulloch আর Walter Pitts ১৯৪৩ সালে স্নায়ুকোষের একটি সরল মডেল দেন; Stephen Kleene ১৯৫০-এর দশকের শুরুতে লেখা একটি প্রতিবেদনে (প্রকাশ ১৯৫৬) দেখান যে এমন জালের আচরণ “regular event” দিয়ে বর্ণনা করা যায়, যা আজকের regular expression-এর পূর্বসূরি। একই সময়ে প্রকৌশলীরা, যেমন George Mealy আর Edward Moore, switching circuit-কে সসীম যন্ত্র হিসেবে বিশ্লেষণ করছিলেন (পর্ব ১২)।

এই ধারাগুলোকে একটি পরিচ্ছন্ন গাণিতিক তত্ত্বে বাঁধেন Michael Rabin আর Dana Scott, ১৯৫৯ সালের “Finite Automata and Their Decision Problems” প্রবন্ধে। সেখানে DFA-র আজকের মতো সংজ্ঞা, nondeterministic automaton আর subset construction, আর regular language-এর বিভিন্ন operation-এ বদ্ধ থাকার ফলগুলো একসঙ্গে আসে; পাশাপাশি চালানো যন্ত্রের ধারণা, অর্থাৎ product, সেখানে বা সমসাময়িক লেখায় স্বাভাবিক হাতিয়ার হিসেবে ব্যবহৃত হয়। এই কাজের জন্য, বিশেষত nondeterminism-এর ধারণার জন্য, দুজনে ১৯৭৬ সালে Turing Award পান।

Closure property পাঠ্যবইয়ের শুরুতে থাকার কারণ ব্যবহারিক আর তাত্ত্বিক দুটিই। ব্যবহারিক: জটিল বর্ণনা ছোট ছোট শর্তে ভাঙা যায়, প্রতিটির জন্য ছোট যন্ত্র, তারপর যান্ত্রিকভাবে জোড়া। §৬-এর পরীক্ষার প্রশ্ন ঠিক এভাবে সমাধান হয়েছে। তাত্ত্বিক: closure থেকে non-regularity-র প্রমাণও আসে। যেমন EQ = {a আর b-এর সংখ্যা সমান} regular হলে EQ ∩ a∗b∗ = {anbn}-ও regular হতো, যা পর্ব ১৭-এ মিথ্যা প্রমাণিত হবে। একটি সহজ যন্ত্র দিয়ে কঠিন language-কে “ছেঁটে” পরিচিত non-regular language-এ নামানো একটি বহুল ব্যবহৃত কৌশল।

আরেকটি গভীর দিক: product construction একটি algorithm, তাই প্রতিটি closure প্রমাণ একই সঙ্গে প্রোগ্রাম। Regex library, lexer generator আর model checker এই রেসিপিগুলোই ব্যবহার করে।

মূল উপলব্ধি: Rabin–Scott ১৯৫৯-এর পর থেকে সসীম যন্ত্রের তত্ত্বের কেন্দ্রে আছে “যন্ত্র জোড়া দেওয়ার” রেসিপি; product construction ছোট শর্ত থেকে বড় যন্ত্র বানায়, আর একই closure যুক্তি উল্টো দিকে non-regularity প্রমাণেও কাজে লাগে।

প্র ০২দুটি যন্ত্রের product সহজ, কিন্তু অনেক যন্ত্রের product কেন software verification-এর সবচেয়ে বড় মাথাব্যথা?

দুটি DFA-র product-এ |Q1| · |Q2|টি state: ৩ আর ২ থেকে ৬. কিন্তু একটি বাস্তব software ব্যবস্থায় অনেক অংশ একসঙ্গে চলে। ধরুন বাজারঘরের checkout-এ ১০টি ছোট অংশ (cart, coupon, payment, stock, delivery…), প্রতিটি মাত্র ৪ state-এর যন্ত্র। পুরো ব্যবস্থার অবস্থা হলো ১০টির একটি জোড়া-তালিকা, তাই সম্ভাব্য অবস্থা ৪১০, প্রায় দশ লক্ষ। ২০টি অংশে তা দশ লক্ষের দশ লক্ষ গুণ। এই ঘটনার নাম “state explosion problem”, আর model checking গবেষণার বড় অংশ এর সঙ্গে লড়াই।

তাত্ত্বিক দিক থেকেও এটি অনিবার্য বলে মনে করা হয়। Dexter Kozen ১৯৭৭ সালে দেখান, k-টি DFA দেওয়া থাকলে “সবাই একসঙ্গে গ্রহণ করে এমন string আছে কি?” প্রশ্নটি PSPACE-complete. অর্থাৎ এর জন্য দ্রুত (polynomial-time) algorithm থাকলে P = PSPACE হতো, যা কেউ প্রমাণ বা খণ্ডন করতে পারেননি। তাই সাধারণভাবে explosion এড়ানোর সহজ পথ নেই বলেই ধারণা।

তবু model checking সফল, কারণ বাস্তবে পুরো product কখনো বানানো হয় না। Moshe Vardi আর Pierre Wolper ১৯৮৬ সালে “automata-theoretic approach” প্রস্তাব করেন: যাচাই করতে চাওয়া ধর্মের উল্টোকে একটি automaton হিসেবে লিখে ব্যবস্থার সঙ্গে product নেওয়া হয়, আর দেখা হয় product-এর language ফাঁকা কি না। ফাঁকা না হলে যে string পাওয়া যায়, সেটিই বাগের পথ, ঠিক §৬-এর counterexample-এর মতো। আর product তৈরি হয় চাহিদামতো, §৪-এর BFS-এর মতো শুধু reachable অংশ; সঙ্গে symbolic representation, partial-order reduction-এর মতো কৌশল। (এখানে automaton সাধারণত অসীম string-এর জন্য, Büchi automaton, তবে মূল ধারণা একই।)

§৪-এর stepper তাই একটি ক্ষুদ্র model checker: শুরুর জোড়া থেকে BFS, আর শেষে একটি জোড়া accepting কি না।

মূল উপলব্ধি: Product-এর আকার গুণফলে বাড়ে, তাই অনেক যন্ত্রের ক্ষেত্রে exponential; k-টি DFA-র intersection-এর ফাঁকা-পরীক্ষা PSPACE-complete, তবু চাহিদামতো reachable অংশ বানিয়ে আর counterexample খুঁজে বাস্তবের model checker কাজ চালায়।

প্র ০৩Binary-তে m দিয়ে বিভাজ্যতার DFA-তে m-টি state লাগে, নাকি কম? স্কুলের “অঙ্কের যোগফল” কৌশলের সঙ্গে এর সম্পর্ক কী?

স্কুলে শেখা নিয়ম: দশমিক সংখ্যা ৩ দিয়ে বিভাজ্য হয় যদি অঙ্কগুলোর যোগফল ৩ দিয়ে বিভাজ্য হয়। কারণ 10 ≡ 1 (mod 3), তাই প্রতিটি অঙ্কের অবস্থান-মূল্য mod 3-এ 1. এটি আসলে উপপাদ্য ২.১-এর দশমিক রূপ: r → (10r + d) mod 3 = (r + d) mod 3, অর্থাৎ ভাগশেষ মানে অঙ্কের যোগফলের ভাগশেষ। Binary-তে 2 ≡ −1 (mod 3), তাই একই যুক্তি দেয় “বিজোড় আর জোড় অবস্থানের 1-এর সংখ্যার পার্থক্য ৩ দিয়ে বিভাজ্য”। r → (2r + b) mod 3 প্রতিটি bit-এ ঠিক এই চিহ্ন-উল্টানো যোগই করে। প্রক্রিয়াটি Horner-এর নিয়ম, যাতে একটি polynomial-এর মান বাঁ থেকে ডানে গুণ আর যোগ দিয়ে বের করা হয়।

এখন প্রশ্ন: m-টি state কি সবসময় দরকার? একটি ছোট পরীক্ষায় (m = 1 থেকে 12, partition refinement দিয়ে minimal DFA-র আকার গুনে) দেখা গেছে, m বিজোড় হলে উত্তর ঠিক m: 3, 5, 7, 9, 11-এ যথাক্রমে ৩, ৫, ৭, ৯, ১১. কিন্তু m-এ 2-এর গুণনীয়ক থাকলে কম: m = 4-এ ৩, 6-এ ৪, 8-এ ৪, 10-এ ৬, 12-এ ৫. ধাঁচটি হলো m = 2k · t (t বিজোড়) হলে t + k. কারণটি অনুমান করা যায়: 2k দিয়ে বিভাজ্যতা মানে “শেষ k bit শূন্য”, যা ধাঁচ খোঁজার কাজ, গোনার নয়; আর বিজোড় t-এর অংশে ভাগশেষ লাগে। সাধারণ ভিত্তি আর সাধারণ m-এর জন্য minimal DFA-র আকারের সূত্র ২০০৪ সালের দিকে Boris Alexeev-এর একটি প্রবন্ধে প্রমাণিত বলে জানা যায়; আমরা এখানে শুধু ছোট m-এ গণনা দেখিয়েছি।

শিক্ষাটি নকশার জন্য গুরুত্বপূর্ণ: “সঠিক” আর “সবচেয়ে ছোট” আলাদা প্রশ্ন। mod-4 DFA সঠিক, কিন্তু তার state 1 আর state 3-এর ভবিষ্যৎ তুলনা করুন: দুটিই non-accepting, দুটিতেই শেষ bit 1, আর 0 এলে দুটিই state 2-তে, 1 এলে দুটিই state 3-তে যায় (2 · 1 + 1 = 3, 2 · 3 + 1 = 7 ≡ 3). তাই এদের মেশানো যায়, আর ৪ থেকে ৩টি state থাকে। Minimization ঠিক এই মিল খুঁজে বের করে।

মূল উপলব্ধি: বিভাজ্যতার DFA হলো Horner-এর নিয়মে ভাগশেষ গোনা, আর স্কুলের অঙ্ক-যোগের কৌশল তারই দশমিক রূপ; বিজোড় m-এ m-টি state-ই লাগে, কিন্তু m-এ 2-এর ঘাত থাকলে minimal DFA ছোট হয়, তাই সঠিক নকশা আর সবচেয়ে ছোট নকশা আলাদা প্রশ্ন।

প্র ০৪DFA-তে complement এক লাইনের কাজ, কিন্তু অন্য মডেলে কেন তা কঠিন, এমনকি অসম্ভব?

DFA-তে complement সহজ, কারণ প্রতিটি string-এর জন্য ঠিক একটি গণনা-পথ, আর সেটি সবসময় শেষ হয়। উত্তর “হ্যাঁ” বা “না” উল্টে দিলেই হয়। এই দুই ধর্ম, “একটি পথ” আর “সবসময় থামে”, অন্য মডেলে একসঙ্গে থাকে না, আর তখনই complement কঠিন হয়ে ওঠে।

প্রথমে nondeterminism. NFA-তে একটি string-এর অনেক পথ, আর গ্রহণ মানে “অন্তত একটি পথ accepting”. এর উল্টো হলো “সব পথ non-accepting”, যা “অন্তত একটি পথ non-accepting” থেকে আলাদা। তাই NFA-র complement-এর জন্য আগে subset construction দিয়ে DFA বানাতে হয় (পর্ব ১০), আর তাতে state-সংখ্যা সবচেয়ে খারাপ ক্ষেত্রে 2n পর্যন্ত যেতে পারে; গবেষণায় দেখানো হয়েছে যে NFA-র complement-এর ক্ষেত্রে এই exponential দাম আসলেই কিছু language-এ এড়ানো যায় না বলে জানা যায়।

তারপর stack. Context-free language-এর শ্রেণি complement-এ বদ্ধ নয় (পর্ব ৩৭): দুটি context-free language-এর intersection context-free না-ও হতে পারে, আর De Morgan দিয়ে তা থেকেই আসে। মজার ব্যাপার, deterministic PDA-র language-গুলো complement-এ বদ্ধ (পর্ব ৩৫), যদিও প্রমাণে DFA-র চেয়ে অনেক বেশি যত্ন লাগে, কারণ DPDA ε-move-এ অসীম চক্রে পড়তে পারে, অর্থাৎ “সবসময় থামে” শর্তটি আগে নিশ্চিত করতে হয়।

শেষে Turing machine. যে যন্ত্র কিছু ইনপুটে চিরকাল চলে, তার “না” উত্তর কখনো আসে না, তাই উল্টানোর কিছু নেই। Turing-recognizable language-এর শ্রেণি complement-এ বদ্ধ নয়: ATM recognizable, কিন্তু তার complement নয় (পর্ব ৫০–৫১)। Decidable language-এর শ্রেণি আবার বদ্ধ, কারণ decider সবসময় থামে, ঠিক সম্পূর্ণ DFA-র মতো। §৫-এর “partial DFA” আসলে এই বড় গল্পের ক্ষুদ্র রূপ: যেখানে যন্ত্র কোনো উত্তর না দিয়ে আটকে যায়, সেখানে উত্তর উল্টানো যায় না।

মূল উপলব্ধি: Complement সহজ হয় যখন প্রতিটি ইনপুটে একটি পথ আর সেটি সবসময় শেষ হয়; nondeterminism-এ দাম exponential, CFL-এ closure ভেঙে যায়, আর recognizable language-এ উত্তর-না-আসা থেকে complement অসম্ভব হয়, আর partial DFA-র ফাঁদ এরই প্রথম আভাস।

প্র ০৫“দৈর্ঘ্য 12 পর্যন্ত মিলেছে” কতটা ভরসার? একটি DFA-র জন্য কত দৈর্ঘ্য পর্যন্ত পরীক্ষা করলে নিশ্চিত হওয়া যায়?

সাধারণ প্রোগ্রামের ক্ষেত্রে সসীম পরীক্ষা কখনো পূর্ণ নিশ্চয়তা দেয় না। Edsger Dijkstra-র বহুল উদ্ধৃত কথা: testing বাগের উপস্থিতি দেখাতে পারে, অনুপস্থিতি নয়। কিন্তু DFA একটি বিশেষ ক্ষেত্র, যেখানে এই কথার একটি সুন্দর ব্যতিক্রম আছে।

ধরুন M1 আর M2 দুটি DFA, state যথাক্রমে m আর n. তাদের symmetric difference-এর product-এ বড়জোর mn-টি state. যদি দুটি যন্ত্র কোনো string-এ ভিন্নমত হয়, তবে product-এ শুরু থেকে একটি accepting জোড়ায় পৌঁছানোর পথ আছে, আর graph-এ সবচেয়ে ছোট পথ কোনো state দুবার ছোঁয় না, তাই তার দৈর্ঘ্য mn-এর কম। ফল: দৈর্ঘ্য mn − 1 পর্যন্ত সব string-এ দুটি একমত হলে তারা সব string-এ একমত। এটি একটি পূর্ণ প্রমাণ, pigeonhole-এর যুক্তি (পর্ব ০৪)। আরও সূক্ষ্ম যুক্তিতে সীমাটি m + n − 2-এ নামানো যায় বলে জানা আছে।

তাহলে §২-এর mod-3 পরীক্ষা কতটা নিশ্চিত? সেখানে “সংজ্ঞা” ছিল Python-এর int(w, 2) % 3, একটি DFA নয়, তাই উপরের যুক্তি সরাসরি খাটে না। কিন্তু §৭-এ automata-lib-এর == দুটি DFA তুলনা করে, তাই সেখানে উত্তর সব দৈর্ঘ্যের জন্য নিশ্চিত। এটাই brute force আর equivalence পরীক্ষার পার্থক্য: প্রথমটি দ্রুত বাগ খোঁজে, দ্বিতীয়টির জন্য দুই পক্ষকেই automaton হতে হয়।

ব্যবহারিক পরামর্শ: সংজ্ঞাটি নিজে একটি সরল DFA বা regex হিসেবে লেখা গেলে equivalence পরীক্ষা করুন; না গেলে (যেমন “মান ৩ দিয়ে বিভাজ্য” Python-এ) brute force-এর সঙ্গে invariant-এর প্রমাণ দিন। আর মনে রাখুন, পরীক্ষায় কোনো counterexample না পাওয়া মানে পরীক্ষিত পরিসরে বাগ নেই, তার বেশি কিছু নয়, যতক্ষণ না একটি যুক্তি সেই পরিসরকে যথেষ্ট প্রমাণ করে।

মূল উপলব্ধি: দুটি DFA তুলনায় সসীম পরীক্ষাই পূর্ণ প্রমাণ হতে পারে, কারণ ভিন্নমতের সবচেয়ে ছোট সাক্ষীর দৈর্ঘ্য product-এর state-সংখ্যার চেয়ে কম; কিন্তু সংজ্ঞা যখন automaton নয়, তখন brute force কেবল বাগ খোঁজে, নিশ্চয়তা দেয় প্রমাণ।

অনুশীলন

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

  1. নকশা: Σ = {a, b}-এর ওপর L = {w : |w| জোড় আর w-এ অন্তত একটি b}-এর DFA product construction দিয়ে নকশা করুন। State-এর অর্থ, পূর্ণ transition table, শুরু আর F লিখুন। যন্ত্রটি কি সবচেয়ে ছোট?

    অংশ-যন্ত্র: দৈর্ঘ্যের parity (জোড় J, বিজোড় B) আর “b দেখা গেছে?” (না N, হ্যাঁ Y). Product state: (J,N), (B,N), (J,Y), (B,Y); শুরু (J,N), F = {(J,Y)}.

    • (J,N): a → (B,N), b → (B,Y)
    • (B,N): a → (J,N), b → (J,Y)
    • (J,Y): a → (B,Y), b → (B,Y)
    • (B,Y): a → (J,Y), b → (J,Y)

    পরীক্ষা: “ab” → (B,N) → (J,Y), গৃহীত; “aa” → (J,N), বাতিল (b নেই); “b” → (B,Y), বাতিল (বিজোড়)। সবচেয়ে ছোট: হ্যাঁ, ৪টি state-ই লাগে। প্রতিটি জোড়া state-এর একটি আলাদা-করা suffix আছে: (J,N) বনাম (J,Y): ε; (J,N) বনাম (B,N): b; (J,N) বনাম (B,Y): a; (B,N) বনাম (J,Y): ε; (B,Y) বনাম (J,Y): ε; (B,N) বনাম (B,Y): a. দৈর্ঘ্য 12 পর্যন্ত সব string আর সব জোড়ার সাক্ষী scratch-এ গুনে মেলানো।

  2. প্রমাণের ভুল ধরুন: “দাবি: M1, M2 যেকোনো DFA (partial হতে পারে, না-থাকা transition মানে বাতিল)। Product-এ δ((p, q), a) সংজ্ঞায়িত হয় যখন দুটি অংশই সংজ্ঞায়িত, আর F = (F1 × Q2) ∪ (Q1 × F2). তাহলে L(M) = L(M1) ∪ L(M2). প্রমাণ: Lemma δ̂((p, q), w) = (δ̂1(p, w), δ̂2(q, w)) থেকে সরাসরি। ∎” ভুল কোথায়? একটি নির্দিষ্ট counterexample দিন।
    • ভুল ধাপ: Lemma-টি শুধু তখনই অর্থবহ, যখন δ̂1(p, w) আর δ̂2(q, w) দুটিই সংজ্ঞায়িত। M1 আটকে গেলে জোড়া যন্ত্রও আটকায়, তখন M2 গ্রহণ করলেও product বাতিল করে।
    • Counterexample: Σ = {B, G}. M1 = §৫-এর partial “BG দিয়ে শুরু” যন্ত্র; M2 = সম্পূর্ণ “G দিয়ে শেষ” যন্ত্র। w = GG ∈ L(M2), তাই union-এ আছে; কিন্তু M1 প্রথম G-তেই আটকায়, তাই product GG বাতিল করে। (“G” নিজেও একই কারণে counterexample.) Scratch-এ চালিয়ে মেলানো।
    • সংশোধন: আগে দুটি যন্ত্রকে dead state দিয়ে সম্পূর্ণ করুন; তখন উপপাদ্য ৪.১ হুবহু খাটে। Intersection-এ দাবিটি partial যন্ত্রেও সত্য, কারণ একটি আটকালে উত্তর এমনিতেই “না”।
  3. আউটপুট অনুমান: কোড না চালিয়ে বলুন কী ছাপা হবে। তারপর যেকোনো Python-এ চালিয়ে মেলান।
    M3 = {(r, b): (2*r + int(b)) % 3 for r in range(3) for b in "01"}
    PAR = {(p, b): p ^ int(b) for p in (0, 1) for b in "01"}
    for w in ["11", "101", "111"]:
        r, p = 0, 0
        for b in w:
            r, p = M3[r, b], PAR[p, b]
        print(w, (r, p), r == 0 and p == 0, r == 0 or p == 0)
    11 (0, 0) True True
    101 (2, 0) False True
    111 (1, 1) False False

    এখানে p = 0 মানে 1-এর সংখ্যা জোড়। 11 = 3: ভাগশেষ 0, দুটি 1, তাই দুই শর্তই সত্য। 101 = 5: ভাগশেষ 2, কিন্তু দুটি 1 (জোড়), তাই শুধু “or”. 111 = 7: ভাগশেষ 1, তিনটি 1, কোনোটিই নয়। r আর p একই লাইনে একসঙ্গে হালনাগাদ হওয়াই product construction: Python ডান পাশের দুটি মান আগে হিসাব করে, তারপর একসঙ্গে বসায়। (CPython 3.14-এ চালিয়ে মেলানো।)

  4. প্রমাণ: Σ = {a, b}-এর ওপর “ঠিক 2টি a”-এর যেকোনো DFA-তে অন্তত ৪টি state থাকতে হবে, প্রমাণ করুন। ইঙ্গিত: ε, a, aa, aaa string চারটি নিন।
    1. ধরি M একটি DFA, L(M) = {w : w-এ ঠিক 2টি a}, আর M-এ ৩ বা কম state. — contradiction-এর অনুমান
    2. চারটি string a0, a1, a2, a3 পড়ে M চারটি state-এ থামে; state ৩টির বেশি নয়, তাই কোনো i < j-এর জন্য δ̂(q0, ai) = δ̂(q0, aj). — pigeonhole
    3. i < j ≤ 3, তাই i ≤ 2. z = a2−i নিন। aiz-এ ঠিক 2টি a, তাই গৃহীত; ajz-এ j + 2 − i > 2টি a, তাই বাতিল হওয়ার কথা।
    4. কিন্তু একই state থেকে একই z পড়লে একই state-এ পৌঁছায়: δ̂(q0, aiz) = δ̂(q0, ajz). তাই দুটি একসঙ্গে গৃহীত বা একসঙ্গে বাতিল। বিরোধ। — δ̂(q, xz) = δ̂(δ̂(q, x), z)
    5. সুতরাং অন্তত ৪টি state লাগে, আর §২-এর টেবিলের k + 2 = ৪ state-এর যন্ত্রটি সবচেয়ে ছোট। ∎

    একই যুক্তি সাধারণ k-তে: ε, a, …, ak+1, এই k + 2টি string পরস্পর distinguishable. সবচেয়ে ছোট DFA-র আকার আসলেই k + 2, partition refinement দিয়ে k = 0 থেকে 3-এ scratch-এ মেলানো।

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

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

ক্রমদুটি DFA থেকে তাদের intersection-এর DFA বানানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. দুটি যন্ত্রের alphabet এক কি না দেখা, আর দরকার হলে dead state দিয়ে দুটিকেই সম্পূর্ণ করা
  2. শুরুর state হিসেবে দুই শুরুর state-এর জোড়া (s1, s2) নেওয়া
  3. প্রতিটি জোড়া আর চিহ্নে δ((p, q), a) = (δ1(p, a), δ2(q, a)) দিয়ে BFS-এ reachable জোড়াগুলো বের করা
  4. F = F1 × F2, অর্থাৎ দুটি অংশই accepting এমন জোড়াগুলো বাছা
  5. ছোট দৈর্ঘ্যের সব string-এ দুই মূল যন্ত্রের উত্তরের “and”-এর সঙ্গে মিলিয়ে দেখা

৩ state-এর একটি DFA আর ৪ state-এর একটি DFA (একই alphabet, দুটিই সম্পূর্ণ) থেকে product construction-এ intersection-এর DFA বানালে তাতে সর্বোচ্চ কয়টি state থাকতে পারে?

  • 7
  • 12
  • 81
  • 128

Σ = {B, G}-এর ওপর একটি ছবিতে আঁকা যন্ত্র: q0 থেকে B-তে q1, q1 থেকে G-তে q2, q2-তে B আর G দুটিতেই q2; আর কোনো তীর নেই (না-থাকা transition মানে বাতিল), F = {q2}. কেউ F′ = {q0, q1} করে “complement” পেলেন। এই নতুন যন্ত্র কোন string-গুলো গ্রহণ করে?

  • BG দিয়ে শুরু নয় এমন সব string
  • ε, B আর G
  • শুধু ε আর B
  • কোনো string নয়

Binary সংখ্যা (বাঁ থেকে ডানে পড়া) 5 দিয়ে বিভাজ্য কি না, তার DFA-তে state ri মানে “এ পর্যন্ত পড়া সংখ্যার ভাগশেষ i”. State r3 থেকে bit 1 পড়লে কোন state?

  • r4
  • r2
  • r0
  • r3

Σ = {a, b}-এর ওপর “w-এ ঠিক 2টি a” language-এর সবচেয়ে ছোট DFA-তে কয়টি state?

  • 3
  • 4
  • 5
  • 2

M1 = (Q1, Σ, δ1, s1, F1) আর M2 = (Q2, Σ, δ2, s2, F2) দুটি সম্পূর্ণ DFA. Product construction-এ L(M1) ∖ L(M2) পেতে accepting সেট কী হবে?

  • F1 × F2
  • (F1 × Q2) ∪ (Q1 × F2)
  • (Q1 ∖ F1) × F2
  • F1 × (Q2 ∖ F2)

“aab” substring খোঁজার একটি DFA: state 0–3, শুরু 0, F = {3}; δ(0,a)=1, δ(0,b)=0, δ(1,a)=2, δ(1,b)=0, δ(2,a)=1, δ(2,b)=3, আর 3-এ দুই চিহ্নেই 3. নিচের কোন string-এ যন্ত্রটি ভুল উত্তর দেয়?

  • aab
  • aaab
  • abab
  • baab

শব্দকোষ

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

মনে রাখুন

  1. State মানে সারাংশ: ভবিষ্যতের সিদ্ধান্তের জন্য যতটুকু অতীত লাগে, ঠিক ততটুকু; প্রতিটি state-এর বাক্যই প্রমাণের invariant.
  2. গোনা আর ধাঁচ: mod m-এ δ(r, b) = (2r + b) mod m; “ঠিক k”-তে k + 2টি state; substring-এ অমিলে “সবচেয়ে লম্বা suffix যা prefix”-এ ফেরা।
  3. Product: জোড়া state, δ((p, q), a) = (δ1(p, a), δ2(q, a)); শুধু F বদলে ∩, ∪, ∖, ⊕; state বড়জোর |Q1| · |Q2|, শুধু reachable জোড়া রাখলেই চলে।
  4. Complement: সম্পূর্ণ DFA-তে F আর Q ∖ F অদলবদল; partial হলে আগে dead state, নইলে আটকে যাওয়া string ভুল উত্তর পায়।
  5. যাচাই: shortlex brute force সবচেয়ে ছোট counterexample দেয়; দুটি DFA-র তুলনায় equivalence পরীক্ষা সব দৈর্ঘ্যের নিশ্চিত উত্তর দেয়; সঠিক আর সবচেয়ে ছোট আলাদা প্রশ্ন।

পরের পর্বে: পর্ব ০৯ “NFA — nondeterminism, একসঙ্গে অনেক পথ আর গ্রহণের নিয়ম”: যন্ত্র যখন একই চিহ্নে একাধিক পথে যেতে পারে, তখন “SALE দিয়ে শেষ” বা “শেষ থেকে তৃতীয় চিহ্ন 1”-এর মতো language অনেক ছোট যন্ত্রে লেখা যায়।

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

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