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

Regular language-এর decision problem — emptiness, equivalence আর inclusion

Decision Problems for Regular Languages — Membership, Emptiness, Finiteness, Universality, Equivalence and Inclusion

Taught in Bangla, this lesson decides questions about regular languages mechanically: membership, emptiness by reachability with the shortest accepted string, finiteness via cycles on useful states, and equivalence, inclusion and universality reduced to emptiness of a product. It contrasts polynomial DFA algorithms with PSPACE-complete universality and equivalence for NFAs and regexes. In-page Python (Pyodide) runs the algorithms, and a real automata-lib run and a browser product BFS check them.

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

  • ছয়টি প্রশ্নকে language হিসেবে লেখা: ADFA, EDFA, INFINITEDFA, ALLDFA, EQDFA আর SUBSETDFA
  • প্রতিটির জন্য Sipser-ধাঁচের একটি decider, আর কেন সেটি সবসময় থামে ও সঠিক উত্তর দেয় তার প্রমাণ
  • Emptiness আর finiteness-কে graph-এর reachability আর চক্রের প্রশ্নে বদলানো, সঙ্গে দৈর্ঘ্যের সীমা (|w| < n আর n ≤ |w| < 2n)
  • Product আর BFS দিয়ে দুটি validator তুলনা করা, আর ভিন্ন হলে সবচেয়ে ছোট witness বের করা
  • DFA, NFA আর regex input-এ একই প্রশ্নের খরচ কেন এত আলাদা, আর কোন ফল প্রমাণিত, কোনটি খোলা

১ · একটি validator, ছয়টি প্রশ্ন

বাজারঘরের অর্ডার কোড BG-dddd: প্রথমে “BG-”, তারপর ঠিক চারটি অঙ্ক। পর্ব ০৭ থেকে এই format-এর একটি DFA আপনার চেনা; alphabet ছোট রাখতে চারটি চিহ্ন {B, G, -, d} ধরা হয়, যেখানে d মানে যেকোনো অঙ্ক। একদিন একজন সহকর্মী validator-টির কোড “পরিষ্কার” করলেন। নতুন কোডটি দেখতে প্রায় একই, পরীক্ষার দশটি কোডেও একই উত্তর দেয়। প্রশ্ন হলো, এটি কি সত্যিই আগেরটির সমান? নাকি এমন কোনো string আছে, যেখানে দুটি আলাদা উত্তর দেয়?

দশটি উদাহরণ দিয়ে সেটি নিশ্চিত হওয়া যায় না, কারণ string অসীম সংখ্যক। অথচ DFA-র ক্ষেত্রে আশ্চর্যজনকভাবে একটি নিশ্চিত উত্তর পাওয়া যায়, যা সব দৈর্ঘ্যের সব string-এর জন্য খাটে। এই পর্ব সেই পদ্ধতিগুলো নিয়ে। একটি automaton হাতে পেলে সাধারণত এই ছয়টি প্রশ্ন ওঠে:

প্রশ্নlanguage হিসেবেবাজারঘরের ভাষায়
MembershipADFA = {⟨M, w⟩ : M একটি DFA আর w ∈ L(M)}এই কোডটি কি বৈধ?
EmptinessEDFA = {⟨M⟩ : L(M) = ∅}কোনো কোড কি আদৌ পাস করতে পারে?
FinitenessINFINITEDFA = {⟨M⟩ : L(M) অসীম}বৈধ কোড কি সীমিত সংখ্যক?
UniversalityALLDFA = {⟨M⟩ : L(M) = Σ∗}Validator কি কিছুই আটকায় না?
EquivalenceEQDFA = {⟨A, B⟩ : L(A) = L(B)}নতুন validator কি পুরোনোটির সমান?
InclusionSUBSETDFA = {⟨A, B⟩ : L(A) ⊆ L(B)}নতুনটি যা নেয়, পুরোনোটিও কি তা নেয়?

প্রতিটি প্রশ্নের উত্তর হ্যাঁ বা না, তাই পর্ব ০৫-এর মতো প্রশ্নটিকে তার “হ্যাঁ”-উদাহরণগুলোর language হিসেবে লেখা হয়। ⟨M⟩ মানে DFA M-কে একটি নির্দিষ্ট নিয়মে string হিসেবে লেখা (encoding). একটি প্রশ্ন “decidable” মানে এমন একটি decider আছে: একটি যন্ত্র বা algorithm, যা প্রতিটি input-এ থামে আর সঠিক উত্তর দেয়। এই পর্বে ছয়টির প্রতিটির জন্য একটি decider বানানো হবে। Turing machine-এর formal সংজ্ঞা পর্ব ৪৩-এ আসবে; এখানে “algorithm” বলতে সাধারণ, সবসময় থামে এমন প্রোগ্রাম বুঝলেই চলে (Church–Turing thesis, পর্ব ৪৭)।

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

এই পর্বের notation: DFA M = (Q, Σ, δ, q0, F), যেখানে δ : Q × Σ → Q total; ছবিতে বা কোডে তীর না থাকলে সেটি একটি dead state-এ যায় (কোডে "dead", ছবিতে X). δ̂ পুরো string-এর transition (কিছু বইয়ে δ∗), আর n = |Q|. L̄ মানে Σ∗ − L. Regex-এ union লেখা হয় ∪ দিয়ে; বাস্তবের টুলে সেটি “|”, তাই কোড ব্লকে “|” দেখবেন। দুটি চলমান উদাহরণ পর্ব ০৮ থেকে: DIV3 (binary মান ৩ দিয়ে বিভাজ্য, ε ∈ DIV3) আর একটি “AI-এর অনুমান” (0 ∪ 11)∗, যাকে পর্ব ১৫-এ random testing ধরে ফেলেছিল।

২ · Membership — ADFA, ANFA আর AREX

প্রথম প্রশ্নটি সবচেয়ে সহজ, আর আগেই দেখা: একটি string w কি L(M)-এ আছে? DFA-র ক্ষেত্রে M-কে w-এর ওপর চালালেই হয়: প্রতিটি চিহ্নে একটি টেবিল-দেখা, মোট |w|টি ধাপ, তারপর শেষ state F-এ আছে কি না দেখা। লুপটি সবসময় থামে, কারণ w সসীম।

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

ADFA, ANFA = {⟨N, w⟩ : N একটি NFA আর w ∈ L(N)} আর AREX = {⟨R, w⟩ : R একটি regex আর w ∈ L(R)} তিনটিই decidable.
Decider (ADFA): “input ⟨M, w⟩ পেলে: ১. M-কে w-এর ওপর চালান, প্রতিটি চিহ্নে δ দেখে। ২. শেষ state F-এ থাকলে accept, নইলে reject.”
ANFA: N-কে subset construction দিয়ে DFA বানিয়ে (পর্ব ১০) ADFA-র decider চালান। AREX: R-কে Thompson construction দিয়ে ε-NFA বানিয়ে (পর্ব ১৪) ANFA-র decider চালান।

প্রমাণের মূল কথা হলো, প্রতিটি রূপান্তর নিজে একটি সবসময় থামে এমন algorithm আর language রাখে, তাই শেষ উত্তরটি সঠিক। এখানে একটি সূক্ষ্ম পার্থক্য আছে, যা এই পর্বের শেষ পর্যন্ত বারবার আসবে: decidable হওয়া আর দ্রুত হওয়া এক কথা নয়। Subset construction 2nটি state দিতে পারে, তাই উপরের ANFA decider-টি সবচেয়ে খারাপ ক্ষেত্রে ঘাতের হারে সময় নেয়। অথচ membership-এর জন্য পুরো DFA বানানোর দরকারই নেই: পর্ব ০৯-এর মতো “বর্তমান state-এর সেট” ধরে NFA চালালে প্রতিটি চিহ্নে বড়জোর |δ|-এর মাপের কাজ, মোট O(|w|·|δ|)। Regex-এর ক্ষেত্রেও Thompson-এর NFA-র আকার regex-এর দৈর্ঘ্যের রৈখিক মাপের, তাই একই কৌশলে O(|w|·|R|)। প্রমাণে যে পথ সবচেয়ে সহজ, বাস্তবে সেটি সবসময় সবচেয়ে সস্তা নয়।

৩ · Emptiness — reachability দিয়ে EDFA

এবার একটি সত্যিকারের নতুন প্রশ্ন: L(M) কি ফাঁকা? প্রথমে মনে হতে পারে, সব string পরীক্ষা না করে এটি বলা অসম্ভব। কিন্তু L(M)-এ একটি string থাকা মানে শুরু থেকে কোনো accepting state পর্যন্ত একটি পথ থাকা, আর পথটির তীরের লেবেলগুলো পরপর পড়লেই string-টি পাওয়া যায়। তাই প্রশ্নটি আসলে graph-এর reachability, যা পর্ব ০২-এ দেখেছেন।

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

L(M) ≠ ∅ ⇔ M-এর state diagram-এ q0 থেকে F-এর কোনো state-এ একটি পথ আছে। আর L(M) ≠ ∅ হলে M এমন একটি string গ্রহণ করে যার দৈর্ঘ্য < n, যেখানে n = |Q|.
Decider: “input ⟨M⟩ পেলে: ১. q0 চিহ্নিত করুন। ২. যতক্ষণ নতুন state চিহ্নিত হয়: কোনো চিহ্নিত state থেকে তীর আসে এমন প্রতিটি state চিহ্নিত করুন। ৩. কোনো accepting state চিহ্নিত না হলে accept (L(M) = ∅), নইলে reject.”

প্রমাণ:

  1. (⇒) ধরুন w = a1a2⋯ak ∈ L(M). তাহলে r0 = q0, ri = δ(ri−1, ai) ক্রমটি q0 থেকে rk ∈ F পর্যন্ত একটি পথ। — δ̂ আর L(M)-এর সংজ্ঞা
  2. (⇐) উল্টো দিকে, q0 থেকে f ∈ F পর্যন্ত যেকোনো পথের তীরের লেবেল পরপর লিখলে একটি string w পাওয়া যায়, যার জন্য δ̂(q0, w) = f, তাই w ∈ L(M). — একই সংজ্ঞা উল্টো দিকে
  3. এমন পথ থাকলে একটি সবচেয়ে ছোট পথ নিন। তাতে কোনো state দুবার আসে না, কারণ এলে মাঝের চক্রটি কেটে আরও ছোট পথ পাওয়া যেত। — ন্যূনতমতা
  4. পুনরাবৃত্তিহীন পথে বড়জোর nটি state, তাই বড়জোর n − 1টি তীর; সংশ্লিষ্ট string-এর দৈর্ঘ্য < n. — pigeonhole principle
  5. Decider-এর ধাপ ২ প্রতিবার অন্তত একটি নতুন state চিহ্নিত করে, নইলে থামে; তাই বড়জোর nবার চলে। শেষে চিহ্নিত state ঠিক reachable state-গুলো, আর ধাপ ৩ ধাপ ১–২-এর সমতুল্য শর্ত পরীক্ষা করে। ∎ — সসীম Q

ধাপ ৪ একটি দরকারি জিনিস দেয়: emptiness-এর জন্য brute force-ও একটি সঠিক decider, যদি দৈর্ঘ্য n − 1 পর্যন্ত সব string দেখা হয়। কিন্তু তাতে |Σ|n-এর মাপের string দেখতে হয়, আর BFS দেখে মাত্র O(|Q|·|Σ|)টি তীর। আরও ভালো, BFS প্রতিটি state-এ প্রথমবার পৌঁছানোর string মনে রাখলে প্রথম accepting state-এর string-টিই সবচেয়ে ছোট গৃহীত string. “ফাঁকা নয়” বললে সঙ্গে প্রমাণও দেওয়া যায়।

একটি বাস্তব প্রয়োগ দেখা যাক। বাজারঘরের একটি প্রচারণায় দুটি নিয়ম একসঙ্গে বসানো হলো: কুপনের binary নম্বর ৩ দিয়ে বিভাজ্য হতে হবে (DIV3), আর তাতে ঠিক একটি 1 থাকতে হবে (ONE1, state e0, e1, e2 মানে এ পর্যন্ত শূন্য, এক, দুই-বা-বেশি 1). কোনো কুপন কি দুটি নিয়ম একসঙ্গে মানতে পারে? প্রশ্নটি হলো L(DIV3) ∩ L(ONE1) = ∅ কি না। Product construction (পর্ব ০৮) intersection-এর একটি DFA দেয়, যার state জোড়া (q, e), আর accepting শুধু (q0, e1). এবার সেই product-এ BFS:

1শুরু (q0,e0) চিহ্নিত2(q0,e0) থেকে তীর3স্তর ১ থেকে তীর4স্তর ২ থেকে তীর5স্তর ৩: নতুন কিছু নেই6সিদ্ধান্ত
এই ধাপের হিসাব
দেখা হচ্ছে
নতুন জোড়া: string
চিহ্নিত মোট
(q0,e1) পাওয়া গেল?
  1. শুরু। Product-এর শুরু (q0, e0): DIV3 ভাগশেষ 0, ONE1-এ এখনো কোনো 1 নেই। মোট সম্ভাব্য জোড়া ৩ × ৩ = ৯টি; accepting শুধু (q0, e1), কারণ intersection-এ দুই যন্ত্রকেই গ্রহণ করতে হয়।
  2. (q0, e0) থেকে। 0 পড়লে দুই যন্ত্রই নিজের কাছে ফেরে, তাই নতুন কিছু নয়। 1 পড়লে (q1, e1), প্রথমবার পৌঁছানোর string “1”. এটি accepting নয়: মান 1, ৩-এর গুণিতক নয়।
  3. (q1, e1) থেকে। 0 পড়লে (q2, e1), string “10” (মান 2); 1 পড়লে (q0, e2), string “11” (মান 3, কিন্তু দুটি 1). দুটিই নতুন, কোনোটিই accepting নয়।
  4. স্তর ২ থেকে। (q2, e1) 0 পড়ে আবার (q1, e1)-এ যায়, যা আগেই চিহ্নিত; 1 পড়ে নতুন (q2, e2), string “101”. (q0, e2) 1 পড়ে নতুন (q1, e2), string “111”. এখন ৬টি জোড়া চিহ্নিত।
  5. স্তর ৩। (q2, e2) আর (q1, e2)-এর চারটি তীরই আগে চিহ্নিত জোড়ায় যায়। Queue খালি, তাই BFS থামে। মোট কাজ: ৬টি জোড়া × ২টি চিহ্ন = ১২টি তীর দেখা।
  6. সিদ্ধান্ত। (q0, e1) কখনো চিহ্নিত হয়নি, তাই L(DIV3) ∩ L(ONE1) = ∅. গণিতের ভাষায়: ঠিক একটি 1 মানে মান 2k, আর 2k mod 3 সবসময় 1 বা 2, কখনো 0 নয়। BFS এই সংখ্যাতত্ত্ব না জেনেই একই উত্তর দিয়েছে, সব দৈর্ঘ্যের জন্য।

নিচের ব্লক একই কাজ কোডে করে। bfs প্রতিটি reachable state-এর জন্য সবচেয়ে ছোট string মনে রাখে; emptiness ফাঁকা হলে None, নইলে সবচেয়ে ছোট গৃহীত string দেয়; product শুধু reachable জোড়াগুলো বানায়, আর একটি rule দিয়ে ঠিক করে কোন জোড়া accepting. এই function-গুলো পরের দুটি ব্লকও ব্যবহার করবে (data-shared), তাই আগে এটি চালান।

from collections import deque
def step(M, q, c):                       # a missing arrow goes to a dead state
    return M["delta"].get((q, c), "dead")
def bfs(M, start):                       # shortest word to each reachable state
    word, queue = {start: ""}, deque([start])
    while queue:
        q = queue.popleft()
        for c in M["sigma"]:
            p = step(M, q, c)
            if p not in word:
                word[p] = word[q] + c; queue.append(p)
    return word
def emptiness(M):                        # E_DFA: None means L(M) is empty
    w = bfs(M, M["start"])
    hits = [w[q] for q in w if q in M["final"]]
    return min(hits, key=lambda s: (len(s), s)) if hits else None
def product(A, B, rule):                 # rule(A accepts, B accepts) -> bool
    start = (A["start"], B["start"])
    delta, seen, todo = {}, {start}, [start]
    while todo:
        a, b = todo.pop()
        for c in A["sigma"]:
            p = delta[(a, b), c] = (step(A, a, c), step(B, b, c))
            if p not in seen: seen.add(p); todo.append(p)
    final = {(a, b) for a, b in seen if rule(a in A["final"], b in B["final"])}
    return {"sigma": A["sigma"], "delta": delta, "start": start, "final": final}
def dfa(start, final, *rows):            # rows: "state next-on-0 next-on-1"
    return {"sigma": "01", "start": start, "final": set(final.split()), "delta":
            {(r.split()[0], c): r.split()[i + 1] for r in rows for i, c in enumerate("01")}}
D3 = dfa("q0", "q0", "q0 q0 q1", "q1 q2 q0", "q2 q1 q2")      # value mod 3 == 0
ONE1 = dfa("e0", "e1", "e0 e0 e1", "e1 e1 e2", "e2 e2 e2")    # exactly one 1
both = product(D3, ONE1, lambda a, b: a and b)
print("reachable pairs:", sorted(bfs(both, both["start"])))
print("accepting pairs among them:", both["final"], "-> witness:", emptiness(both))
print("DIV3 alone:", repr(emptiness(D3)), "| ONE1 alone:", repr(emptiness(ONE1)))

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

reachable pairs: [('q0', 'e0'), ('q0', 'e2'), ('q1', 'e1'), ('q1', 'e2'), ('q2', 'e1'), ('q2', 'e2')]
accepting pairs among them: set() -> witness: None
DIV3 alone: '' | ONE1 alone: '1'

Reachable জোড়া ঠিক stepper-এর ছয়টি; বাকি তিনটি, (q0, e1), (q1, e0) আর (q2, e0), কোনো string-এ পৌঁছানো যায় না। Accepting জোড়ার সেট ফাঁকা (set()), তাই witness None: দুই নিয়ম একসঙ্গে মানে এমন কুপন নেই। আলাদাভাবে দুটি language-ই ফাঁকা নয়: DIV3-এর সবচেয়ে ছোট string ε (মান 0), ONE1-এর “1”. অর্থাৎ প্রতিটি নিয়ম আলাদাভাবে ঠিক আছে, শুধু দুটি একসঙ্গে অসম্ভব। বাস্তবে এটিই “মৃত নিয়ম” ধরার পরীক্ষা। product নিজে todo.pop() দিয়ে DFS-এর মতো ঘোরে; ক্রম আলাদা হলেও reachable জোড়ার সেট একই, আর সবচেয়ে ছোট string-এর কাজটি bfs করে।

৪ · Finiteness — useful state-এর চক্র

তৃতীয় প্রশ্ন: L(M) কি সসীম? বাজারঘরের মূল validator শুধু একটি “আকার” নেয়, BG-dddd (আসল অঙ্ক বসালে ১০৪টি কোড)। সহকর্মীর নতুন validator-এ শেষ state q7-এ d পড়লে q7-এই থাকার একটি তীর যোগ হয়েছে, তাই সেটি BG-ddddd, BG-dddddd, … সবই নেয়। একটি অসীম, অন্যটি সসীম, তাই দুটি সমান হতে পারে না। কিন্তু একটি DFA দেখে কীভাবে যান্ত্রিকভাবে বলবেন যে তার language অসীম?

স্বাভাবিক প্রথম অনুমান: “state diagram-এ চক্র থাকলে language অসীম।” এটি ভুল। Total DFA-তে প্রায় সবসময় একটি dead state থাকে, যার প্রতিটি চিহ্নে নিজের কাছে ফেরার চক্র আছে, অথচ সেই চক্র কোনো গৃহীত string তৈরি করে না। চক্রটি কাজে লাগে শুধু তখন, যখন তাতে শুরু থেকে পৌঁছানো যায় আর তা থেকে accepting state-এও যাওয়া যায়।

সংজ্ঞা ৪.১ (Useful state)

DFA M-এর একটি state q useful (কিছু বইয়ে “trim”-এর অংশ), যদি q0 থেকে q-তে একটি পথ থাকে (q reachable) আর q থেকে F-এর কোনো state-এ একটি পথ থাকে (q co-reachable). দুটির একটি না থাকলে q মুছে ফেললেও L(M) বদলায় না।

উপপাদ্য ৪.২ (INFINITEDFA decidable — দুই রূপ)

n = |Q| হলে নিচের তিনটি কথা সমতুল্য:
(ক) L(M) অসীম; (খ) কোনো useful state একটি চক্রের ওপর আছে; (গ) M এমন একটি string গ্রহণ করে যার দৈর্ঘ্য n ≤ |w| < 2n.
Decider: “input ⟨M⟩ পেলে: ১. সামনের দিকে BFS করে reachable state, আর তীর উল্টে F থেকে BFS করে co-reachable state বের করুন। ২. দুটির ছেদ U নিন। ৩. U-র ভেতরের তীর নিয়ে গঠিত graph-এ চক্র খুঁজুন (DFS). চক্র পেলে accept, নইলে reject.”

প্রমাণ:

  1. (খ) ⇒ (ক): useful state q একটি চক্রে আছে। তাহলে q0 থেকে q-তে একটি string x, q থেকে q-তে ফেরার একটি অশূন্য string y, আর q থেকে F-এ একটি string z আছে। প্রতিটি i ≥ 0-তে xyiz ∈ L(M), আর এরা সবাই ভিন্ন দৈর্ঘ্যের। — |y| ≥ 1
  2. (ক) ⇒ (খ): L(M) অসীম, অথচ দৈর্ঘ্য < n-এর string সসীম সংখ্যক, তাই কোনো w ∈ L(M)-এর |w| ≥ n. w পড়ার সময় n + 1টি state দেখা হয়, তাই কোনো state q দুবার আসে। — pigeonhole
  3. এই q শুরু থেকে পৌঁছানো যায় (w-এর শুরুর অংশ পড়ে), আর q থেকে accepting state-এ যাওয়া যায় (w-এর বাকি অংশ পড়ে); তাই q useful, আর দুবার আসার মাঝের অংশটি একটি চক্র। — useful-এর সংজ্ঞা
  4. (গ) ⇒ (ক): |w| ≥ n হলে ধাপ ২–৩-এর মতো w = xyz, |y| ≥ 1, আর সব xyiz ∈ L(M). — pumping-এর যুক্তি (পর্ব ১৭)
  5. (ক) ⇒ (গ): |w| ≥ n এমন গৃহীত string-গুলোর মধ্যে সবচেয়ে ছোটটি w নিন। যদি |w| ≥ 2n হয়, তাহলে w-এর প্রথম n অক্ষরের মধ্যেই একটি state দুবার আসে, তাই w = xyz যেখানে |xy| ≤ n, |y| ≥ 1, আর xz ∈ L(M). — প্রথম n + 1টি state-এ pigeonhole
  6. |xz| = |w| − |y| ≥ 2n − n = n, অথচ |xz| < |w|, যা w-এর ন্যূনতমতার বিরোধী। তাই |w| < 2n. ∎ — contradiction

রূপ (গ) সরাসরি একটি brute-force decider দেয়: দৈর্ঘ্য n থেকে 2n − 1 পর্যন্ত সব string চালিয়ে দেখা। পরীক্ষার খাতায় এটি সুন্দর, কিন্তু বাজারঘরের validator-এ n = 9 (আটটি useful state আর X), আর {B, G, -, d}-এর ওপর দৈর্ঘ্য 9 থেকে 17-এর string কোটি কোটি। রূপ (খ)-এর graph পদ্ধতি একই উত্তর দেয় O(|Q|·|Σ|)-এর মাপের কাজে। নিচের ছবিতে নতুন validator-এর DFA, সঙ্গে dead state X.

নতুন validator: কোন চক্র language-কে অসীম করে?

সবুজ ঘেরা অংশে আটটি useful state. q7-এর নিজের চক্র (কমলা) useful state-এ, তাই language অসীম। X-এর চক্র useful নয়, কারণ X থেকে q7-এ যাওয়া যায় না।

Refactored order-code DFA: the loop on useful state q7 makes the language infinite; the dead state's loop does not q0q1q2q3 q4q5q6q7 X BG- d ddd d B,G,-,d সবুজ ঘের: useful state চক্র ⇒ অসীম বাকি সব তীর X-এ (আঁকা হয়নি)
ছবি ২০.১ — q7-এর কমলা চক্র মুছে ফেললে এটি মূল validator: তখন useful অংশে কোনো চক্র থাকে না, আর language-এ ঠিক একটি string, BG-dddd. X-এর চক্র দুই ক্ষেত্রেই আছে, কিন্তু কিছু বদলায় না।
1graph: q0…q7 আর X2সামনে BFS: reachable3উল্টো BFS: co-reachable4ছেদ: useful state5মূল validator: চক্র?6নতুন validator: চক্র?
এই ধাপের হিসাব
reachable
co-reachable
useful
চক্র
ফল
  1. Graph. দুই validator-এর state একই: q0 থেকে q7 একটি শিকল, আর total করার জন্য dead state X, যেখানে প্রতিটি অনুপস্থিত তীর যায়। X-এ চার চিহ্নেই নিজের কাছে ফেরার চক্র আছে। পার্থক্য শুধু নতুনটির q7 → q7 (d) তীরে।
  2. Reachable. q0 থেকে সামনের দিকে BFS. শিকল ধরে q1…q7, আর ভুল চিহ্ন পড়লে X (যেমন “G” পড়ে), তাই নয়টি state-ই reachable. শুধু এই তথ্যে X-এর চক্র বাদ যায় না।
  3. Co-reachable. সব তীর উল্টে q7 থেকে BFS: q6, q5, … পেছনে হেঁটে q0 পর্যন্ত আটটি state. X-এর সব তীর X-এই ফেরে, তাই X থেকে q7-এ কোনো পথ নেই; X co-reachable নয়।
  4. Useful. দুই সেটের ছেদ q0…q7. এখন থেকে শুধু এই আটটি state আর তাদের নিজেদের মধ্যের তীর দেখা হবে। X আর তার চক্র বাদ, আর এটিই “চক্র থাকলেই অসীম” ভুলটি ঠেকায়।
  5. মূল validator. Useful অংশে তীর শুধু qi থেকে qi+1-এ, কোনো চক্র নেই। তাই language সসীম। প্রতিটি গৃহীত string একটি সরল পথ, দৈর্ঘ্য বড়জোর ৮টি useful state − ১ = 7, আর আসলে একটিই: BG-dddd.
  6. নতুন validator. q7 → q7 (d) একটি useful state-এ চক্র। উপপাদ্যের প্রমাণের মতো x = BG-dddd (q0 থেকে q7), y = d (চক্র), z = ε (q7 নিজেই accepting). তাই BG-dddd·di সবই গৃহীত, language অসীম, আর দুই validator অবশ্যই ভিন্ন।

নিচের ব্লক আগের ব্লকের bfs আর step ব্যবহার করে। Co-reachable বের করতে এখানে সরল পথ নেওয়া হয়েছে: প্রতিটি reachable state থেকে আলাদা BFS চালিয়ে দেখা হয়, কোনো accepting state পাওয়া যায় কি না (উল্টো graph-এ একটি BFS দ্রুততর, কিন্তু কোড লম্বা হতো)। চক্র পাওয়া গেলে function-টি প্রমাণের x, y, z ফেরত দেয়।

def finiteness(M):                       # None = finite, else (x, y, z): x y^i z in L
    reach = bfs(M, M["start"])
    useful = sorted(q for q in reach if any(f in M["final"] for f in bfs(M, q)))
    for q in useful:
        for c in M["sigma"]:
            back = bfs(M, step(M, q, c))
            if q in back:                # q --c--> ... --> q: a loop on a useful state
                z = min((w for f, w in bfs(M, q).items() if f in M["final"]), key=len)
                return reach[q], c + back[q], z
    return None

def code(loop):                          # BG-dddd over {B, G, -, d}, d = any digit
    d = {("q0", "B"): "q1", ("q1", "G"): "q2", ("q2", "-"): "q3", ("q3", "d"): "q4",
         ("q4", "d"): "q5", ("q5", "d"): "q6", ("q6", "d"): "q7"}
    if loop: d["q7", "d"] = "q7"         # the "refactored" validator
    return {"sigma": "BG-d", "start": "q0", "final": {"q7"}, "delta": d}

for name, M in [("spec", code(False)), ("new", code(True)), ("DIV3", D3)]:
    reach = bfs(M, M["start"])
    useful = [q for q in reach if any(f in M["final"] for f in bfs(M, q))]
    print(f"{name:4} reached {len(reach)}, useful {len(useful)}, loop (x, y, z):",
          finiteness(M))

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

spec reached 9, useful 8, loop (x, y, z): None
new  reached 9, useful 8, loop (x, y, z): ('BG-dddd', 'd', '')
DIV3 reached 3, useful 3, loop (x, y, z): ('', '0', '')

দুই validator-এ নয়টি state reachable (আটটি আর "dead"), কিন্তু useful আটটি: dead state বাদ। মূলটিতে চক্র নেই, তাই None, অর্থাৎ সসীম। নতুনটিতে ঠিক stepper-এর x, y, z: BG-dddd, d আর ফাঁকা string. DIV3-এর ক্ষেত্রে q0 নিজেই useful আর 0 পড়ে নিজের কাছে ফেরে, তাই x = ε, y = 0, z = ε: 0, 00, 000, … সবই ৩ দিয়ে বিভাজ্য (মান 0). লক্ষ করুন, “dead” state-এর চক্র কোড কখনো দেখেই না, কারণ সেটি useful-এ নেই। কোডটি সরল রাখার মূল্য হলো গতি: প্রতিটি state থেকে আলাদা BFS মানে O(n·(n + |δ|))-এর মাপের কাজ, যা ছোট DFA-তে কিছুই নয়।

৫ · Equivalence, inclusion আর universality — সবই emptiness-এ নামে

এবার শুরুর প্রশ্ন: দুটি DFA কি একই language চেনে? মূল কৌশলটি হলো নতুন কোনো algorithm না বানিয়ে প্রশ্নটিকে আগের প্রশ্নে বদলে ফেলা। দুটি language সমান ঠিক তখন, যখন তাদের symmetric difference, অর্থাৎ ঠিক একটিতে আছে এমন string-এর সেট, ফাঁকা:

L(A) = L(B) ⇔ (L(A) ∩ L̄(B)) ∪ (L̄(A) ∩ L(B)) = ∅

Regular language intersection, union আর complement-এ বদ্ধ (পর্ব ০৮-এ product আর complement-এর নির্মাণ; সব closure property-র পূর্ণ তালিকা পর্ব ১৬-এ)। তাই ডান পাশের সেটটিও regular, আর তার DFA C সরাসরি বানানো যায়: A আর B-এর product, যেখানে জোড়া (a, b) accepting ঠিক তখন, যখন দুই যন্ত্রের একটি গ্রহণ করে আর অন্যটি করে না।

উপপাদ্য ৫.১ (EQDFA decidable)

Decider: “input ⟨A, B⟩ পেলে: ১. A আর B-এর product C বানান, যেখানে (a, b) ∈ FC ⇔ (a ∈ FA) ≠ (b ∈ FB). ২. EDFA-র decider ⟨C⟩-এর ওপর চালান। ৩. সেটি accept করলে (L(C) = ∅) accept, নইলে reject.”
আর L(A) ≠ L(B) হলে এমন একটি witness w আছে (একটি যন্ত্র গ্রহণ করে, অন্যটি করে না), যার দৈর্ঘ্য < |QA|·|QB|.

প্রমাণ:

  1. Product construction অনুযায়ী প্রতিটি w-এর জন্য δ̂C((qA, qB), w) = (δ̂A(qA, w), δ̂B(qB, w)). — |w|-এর ওপর induction, পর্ব ০৮
  2. তাই w ∈ L(C) ⇔ A আর B-এর ঠিক একটি w গ্রহণ করে ⇔ w ∈ L(A) ⊕ L(B). — FC-এর সংজ্ঞা
  3. ফলে L(C) = ∅ ⇔ L(A) = L(B); আর EDFA-র decider সবসময় থামে, তাই এই decider-ও থামে। — উপপাদ্য ৩.১
  4. L(C) ≠ ∅ হলে উপপাদ্য ৩.১ অনুযায়ী L(C)-এ দৈর্ঘ্য < |QC| = |QA|·|QB|-এর একটি string আছে; সেটিই witness. ∎ — BFS-এর সবচেয়ে ছোট পথ

একই ছাঁচে বাকি দুটি প্রশ্নও নামে। Inclusion: L(A) ⊆ L(B) ⇔ L(A) ∩ L̄(B) = ∅, অর্থাৎ product-এ accepting শুধু সেই জোড়া, যেখানে A গ্রহণ করে কিন্তু B করে না। Universality: L(M) = Σ∗ ⇔ L̄(M) = ∅, অর্থাৎ M-এর accepting আর non-accepting state অদলবদল করে (M total হতে হবে, পর্ব ০৮-এর ফাঁদ মনে রাখুন) emptiness পরীক্ষা। আর equivalence আসলে দুই দিকের inclusion: L(A) = L(B) ⇔ L(A) ⊆ L(B) আর L(B) ⊆ L(A). দুই দিক আলাদা চালালে আরও তথ্য মেলে: কোন যন্ত্র “বেশি” নেয়, সেটিও জানা যায়।

এখন DIV3 আর AI-এর অনুমান (0 ∪ 11)∗ তুলনা করা যাক। (0 ∪ 11)∗-এর DFA-তে তিনটি state: p0 (শুরু, accepting), p1 (একটি 1 পড়া হয়েছে, জোড়ার অপেক্ষা), আর pd (dead, যখন p1-এ 0 আসে)। Product-এ BFS, যেখানে লক্ষ্য একটি “ভিন্নমতের” জোড়া:

1শুরু (q0,p0)21 পড়ে (q1,p1)30 পড়ে (q2,pd)40 পড়ে (q1,pd)51 পড়ে (q0,pd)6BFS শেষ: inclusion
এই ধাপের হিসাব
নতুন জোড়া
প্রথম string
DIV3 / AI
মত
  1. শুরু। জোড়া (q0, p0): দুই যন্ত্রই ε গ্রহণ করে, তাই একমত। ভিন্নমতের জোড়া মানে যেখানে ঠিক একটি accepting, যেমন (q0, p1) বা (q1, p0). (q0, p0) থেকে 0 পড়লে আবার (q0, p0), তাই নতুন কিছু নয়।
  2. (q1, p1). 1 পড়ে: DIV3-এ ভাগশেষ 1, AI-তে “একটি 1, জোড়া বাকি”। দুটিই গ্রহণ করে না, একমত। এখান থেকে 1 পড়লে (q0, p0)-এ ফেরা (“11” = 3), যা আগেই দেখা।
  3. (q2, pd). (q1, p1) থেকে 0 পড়ে: “10”, মান 2. AI-এর যন্ত্র p1-এ 0 পেয়ে dead state-এ গেছে, আর কখনো গ্রহণ করবে না। DIV3-ও এখন গ্রহণ করে না, তাই এখনো একমত।
  4. (q1, pd). (q2, pd) থেকে 0 পড়ে: “100”, মান 4, ভাগশেষ 1. (q2, pd)-এ 1 পড়লে নিজের কাছেই ফেরা। এখনো একমত, কিন্তু DIV3 এখন q0-এর এক ধাপ দূরে।
  5. (q0, pd). (q1, pd) থেকে 1 পড়ে: “1001”, মান 9 = 3 × 3. DIV3 গ্রহণ করে, AI-এর যন্ত্র dead state-এ। প্রথম ভিন্নমত, আর BFS বলে এটিই সবচেয়ে ছোট witness. সীমা ছিল 3 × 3 − 1 = 8; witness-এর দৈর্ঘ্য 4.
  6. Inclusion. BFS চালিয়ে গেলে (q0, pd) থেকে কোনো নতুন জোড়া আসে না; মোট ৫টি reachable জোড়া। AI গ্রহণ করে শুধু (q0, p0)-তে, আর সেখানে DIV3-ও গ্রহণ করে। তাই (0 ∪ 11)∗ ⊆ DIV3, কিন্তু উল্টোটি নয়: AI-এর অনুমান খুব কড়া, ভুল দিকে নয়।

ধাপ ৫-এর সীমাটি একটি গুরুত্বপূর্ণ সত্য বলে: DFA-র equivalence-এর জন্য brute force-ও একটি সম্পূর্ণ decider, যদি দৈর্ঘ্য |QA|·|QB| − 1 পর্যন্ত সব string দেখা হয়। “দৈর্ঘ্য ১০ পর্যন্ত মিলেছে” কথাটি সাধারণত শুধু ইঙ্গিত, কিন্তু দুটি ৩-state DFA-র জন্য দৈর্ঘ্য ৮ পর্যন্ত মিললে সেটি প্রমাণ। একটি তৃতীয় পথও আছে: দুটি DFA-কে minimise করে (পর্ব ১৯) দেখা যে ফল দুটি নাম বদলের পর একই কি না, কারণ minimal DFA অনন্য (পর্ব ১৮)। আর Hopcroft ও Karp-এর ১৯৭১ সালের একটি প্রতিবেদনে বর্ণিত union-find পদ্ধতি product-এর সব জোড়া না বানিয়েই প্রায় রৈখিক সময়ে একই উত্তর দেয়; পরের অংশের library ঠিক এর একটি রূপ ব্যবহার করে।

from itertools import product as strings

AI = dfa("p0", "p0", "p0 p0 p1", "p1 pd p0", "pd pd pd")    # (0 ∪ 11)*
ALL = dfa("u", "u", "u u u")                                # Σ*

def equivalent(A, B):                    # EQ_DFA: None = same language
    return emptiness(product(A, B, lambda a, b: a != b))
def subset(A, B):                        # L(A) ⊆ L(B)?  None = yes
    return emptiness(product(A, B, lambda a, b: a and not b))
show = lambda w: "yes" if w is None else f"no, witness {w!r}"

print("DIV3 = (0∪11)* ?", show(equivalent(D3, AI)))
print("(0∪11)* ⊆ DIV3 ?", show(subset(AI, D3)))
print("DIV3 ⊆ (0∪11)* ?", show(subset(D3, AI)))
print("DIV3 = Σ* ?     ", show(subset(ALL, D3)))
print("spec = new ?    ", show(equivalent(code(False), code(True))))

def accepts(M, w):
    q = M["start"]
    for c in w: q = step(M, q, c)
    return q in M["final"]
diff = product(D3, AI, lambda a, b: a != b)
n = len(bfs(diff, diff["start"]))        # reachable pairs in the product
bad = [w for k in range(n) for w in map("".join, strings("01", repeat=k))
       if accepts(D3, w) != accepts(AI, w)]
print(f"{n} reachable pairs; brute force up to length {n - 1}:",
      f"{len(bad)} witnesses, first {bad[0]!r}")

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

DIV3 = (0∪11)* ? no, witness '1001'
(0∪11)* ⊆ DIV3 ? yes
DIV3 ⊆ (0∪11)* ? no, witness '1001'
DIV3 = Σ* ?      no, witness '1'
spec = new ?     no, witness 'BG-ddddd'
5 reachable pairs; brute force up to length 4: 1 witnesses, first '1001'

প্রথম তিন লাইন stepper-এর ফল: সমান নয়, witness 1001, আর inclusion শুধু এক দিকে। চতুর্থ লাইনে universality-কে inclusion হিসেবে লেখা হয়েছে, Σ∗ ⊆ L(DIV3)? উত্তর না, আর সবচেয়ে ছোট বাদ পড়া string “1” (মান 1). পঞ্চম লাইন শুরুর প্রশ্নের উত্তর: সহকর্মীর validator আলাদা, আর সবচেয়ে ছোট witness BG-ddddd, পাঁচ অঙ্কের কোড, যা নতুনটি নেয় কিন্তু মূলটি নেয় না। শেষ লাইনে সীমাটির ব্যবহার: product-এ মাত্র ৫টি reachable জোড়া, তাই দৈর্ঘ্য 4 পর্যন্ত brute force-ই যথেষ্ট ছিল, আর সেখানে ঠিক একটি witness, 1001. সীমা হিসাবে ৩ × ৩ = ৯-এর বদলে reachable জোড়ার সংখ্যা নেওয়া ঠিক, কারণ উপপাদ্য ৩.১-এর যুক্তি শুধু reachable state-এর ওপর চলে।

৬ · Input-এর রূপ আর খরচ — DFA, NFA আর regex

Kleene-এর উপপাদ্য (পর্ব ১৫) বলে DFA, NFA আর regex একই শ্রেণির language বর্ণনা করে, তাই উপরের সব প্রশ্ন তিন রূপেই decidable: দরকার হলে আগে DFA বানিয়ে নিন। কিন্তু algorithm-এর খরচ মাপা হয় input-এর আকারে, আর একই language-এর NFA বা regex DFA-র চেয়ে ঘাতের হারে ছোট হতে পারে (পর্ব ১০-এর Ln). ফলে একই প্রশ্নের খরচ input-এর রূপ অনুযায়ী খুব বদলায়:

প্রশ্নDFA inputNFA inputregex input
MembershipO(|w|)O(|w|·|δ|), state-সেট ধরেO(|w|·|R|), Thompson-এর পর
EmptinessO(|Q| + |δ|), BFSএকই, BFSরৈখিক, গঠন দেখে
Finitenesspolynomial: useful + চক্রpolynomial, একই পদ্ধতিpolynomial
Universalitypolynomial: complement + BFSPSPACE-completePSPACE-complete
Equivalencepolynomial: product + BFSPSPACE-completePSPACE-complete
InclusionpolynomialPSPACE-completePSPACE-complete

প্রথম তিনটি প্রশ্নে NFA বা regex থাকলেও সমস্যা হয় না, কারণ এরা শুধু “কোনো একটি পথ আছে কি না” জানতে চায়, আর NFA-র graph-এ পথ খোঁজা DFA-র মতোই সহজ। Regex-এর emptiness তো গঠন দেখেই বলা যায়: ∅ ফাঁকা; R1 ∪ R2 ফাঁকা যদি দুটিই ফাঁকা; R1R2 ফাঁকা যদি একটি ফাঁকা; আর R∗ কখনো ফাঁকা নয়, কারণ তাতে ε আছে। Structural induction-এ (পর্ব ১৩) এটি প্রমাণ হয়।

শেষ তিনটি প্রশ্নে “সব string” বা “কোনো string-এ ভিন্নমত নেই” জানতে হয়, যার জন্য complement লাগে। DFA-তে complement বিনা খরচে (accepting সেট অদলবদল), কিন্তু NFA-তে accepting state অদলবদল করলে complement আসে না, কারণ NFA-তে একটি string-এর জন্য অনেক পথ থাকে আর একটি গ্রহণকারী পথই যথেষ্ট (পর্ব ০৯)। সঠিক complement-এর জন্য আগে subset construction, আর তাতে 2nটি state আসতে পারে। “PSPACE-complete” মানে সমস্যাটি PSPACE শ্রেণির সবচেয়ে কঠিনগুলোর একটি (পর্ব ৬৫): polynomial পরিমাণ মেমরিতে সমাধান করা যায়, কিন্তু polynomial সময়ের কোনো algorithm জানা নেই, আর থাকলে P = PSPACE হতো। P ≠ PSPACE কিনা, সেটি খোলা প্রশ্ন; বেশিরভাগ বিশেষজ্ঞ বিশ্বাস করেন P ≠ PSPACE, কিন্তু কেউ প্রমাণ করেননি। Regex আর NFA-র universality ও equivalence PSPACE-complete হওয়ার ফলটি সাধারণত Meyer আর Stockmeyer-এর ১৯৭২–৭৩ সালের কাজের সঙ্গে যুক্ত করা হয়।

Membership এড়ায় কীভাবে? একটি NFA-কে পুরো DFA বানাতে হয় না; একটি string পড়ার সময় শুধু সেই পথে আসা subset-গুলো দরকার, যা বড়জোর |w| + 1টি। Universality-তে কিন্তু সব reachable subset দেখতে হতে পারে, কারণ যেকোনো একটিতে accepting state না থাকলেই উত্তর “না”। তবে PSPACE-এর মধ্যে থাকার কারণও এখান থেকেই বোঝা যায়: একটি subset মনে রাখতে n বিট লাগে, তাই সব subset একসঙ্গে না রেখে একটি একটি করে nondeterministic ভাবে হেঁটে দেখা যায়, আর Savitch-এর উপপাদ্য (পর্ব ৬৪) সেটিকে deterministic polynomial মেমরিতে আনে।

আরও গভীরে: Regex-এ বাড়তি operation দিলে জটিলতা লাফিয়ে বাড়ে। Squaring (R2 = RR সংক্ষেপে লেখা) যোগ করলে equivalence EXPSPACE-complete হয় বলে Meyer আর Stockmeyer দেখিয়েছিলেন, আর complement যোগ করলে (“generalized regex”) সমস্যাটি non-elementary, অর্থাৎ কোনো নির্দিষ্ট উচ্চতার 22⋯ সীমায় পড়ে না (Stockmeyer, ১৯৭৪ সালের দিকে)। উল্টো দিকে, এক-চিহ্নের alphabet-এ NFA-র universality “শুধু” coNP-complete বলে পরিচিত। DFA-র emptiness নিজেই directed graph-এর reachability, যা NL-complete (পর্ব ৬৬)। আর দুটি DFA-র সবচেয়ে ছোট witness-এর দৈর্ঘ্যের একটি তীক্ষ্ণ সীমা আছে, |QA| + |QB| − 2, যা Moore-এর ১৯৫৬ সালের state-আলাদা-করার পরীক্ষার কাজের সঙ্গে যুক্ত; product-এর সীমা |QA|·|QB| − 1 সহজে প্রমাণ হয় কিন্তু ঢিলা।

৭ · সত্যিকারের run — automata-lib আর ব্রাউজারে BFS

নিজের কোডের ফল একটি স্বাধীন library দিয়ে মেলানো দরকার। automata-lib (MIT licence) Python-এর একটি automata library, যার DFA-তে isempty(), isfinite(), cardinality(), == (language-সমতা), <= (inclusion), ^ (symmetric difference) আর minimum_word_length() সরাসরি আছে। Library-র কোডে network বা usage-reporting-এর কোনো অংশ নেই (scratch-এ উৎস কোড খুঁজে দেখা হয়েছে)। নিচের script ডেস্কটপে uv দিয়ে বানানো একটি আলাদা প্রকল্পে চালানো হয়েছে: automata-lib 9.2.0, Python 3.12. একটি খুঁটিনাটি: এই সংস্করণে (div3 & one1).isempty() সরাসরি লিখলে একটি RuntimeError আসে (cache-করা method-এর সঙ্গে অস্থায়ী object-এর সমস্যা), তাই ফলটি আগে একটি variable-এ রাখা হয়েছে।

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

print("automata-lib", version("automata-lib"))
S4 = {"B", "G", "-", "d"}                     # d = any digit

def chain(loop_at_end):                       # BG-dddd, partial DFA
    t = {"q0": {"B": "q1"}, "q1": {"G": "q2"}, "q2": {"-": "q3"},
         "q3": {"d": "q4"}, "q4": {"d": "q5"}, "q5": {"d": "q6"},
         "q6": {"d": "q7"}, "q7": {"d": "q7"} if loop_at_end else {}}
    return DFA(states=set(t), input_symbols=S4, transitions=t,
               initial_state="q0", final_states={"q7"}, allow_partial=True)

spec, new = chain(False), chain(True)         # new = "refactored" validator
print("spec: empty", spec.isempty(), "| finite", spec.isfinite(),
      "| words", spec.cardinality())
print("new:  empty", new.isempty(), "| finite", new.isfinite())
print("spec == new:", spec == new, "| spec <= new:", spec <= new,
      "| new <= spec:", new <= spec)
diff = spec ^ new                             # symmetric difference
k = diff.minimum_word_length()
print("shortest witnesses:", sorted(diff.words_of_length(k)))

B = {"0", "1"}
div3 = DFA(states={"q0", "q1", "q2"}, input_symbols=B,
           transitions={"q0": {"0": "q0", "1": "q1"}, "q1": {"0": "q2", "1": "q0"},
                        "q2": {"0": "q1", "1": "q2"}},
           initial_state="q0", final_states={"q0"})
one1 = DFA(states={"e0", "e1", "e2"}, input_symbols=B,
           transitions={"e0": {"0": "e0", "1": "e1"}, "e1": {"0": "e1", "1": "e2"},
                        "e2": {"0": "e2", "1": "e2"}},
           initial_state="e0", final_states={"e1"})
both = div3 & one1                            # product construction
print("DIV3 & ONE1 empty:", both.isempty())

guess = DFA.from_nfa(NFA.from_regex("(0|11)*", input_symbols=B))
print("DIV3 == (0|11)*:", div3 == guess, "| (0|11)* <= DIV3:", guess <= div3,
      "| DIV3 <= (0|11)*:", div3 <= guess)
gap = div3 - guess
k = gap.minimum_word_length()
print("shortest in DIV3 - (0|11)*:", sorted(gap.words_of_length(k)),
      "| how many of length 10:", gap.count_words_of_length(10))

# regex-level questions (the library builds automata inside)
print("(0|1)* == (0*1*)*:", rx.isequal("(0|1)*", "(0*1*)*", input_symbols=B))
print("(01|1)*0* universal:", rx.isequal("(01|1)*0*", "(0|1)*", input_symbols=B))
miss = DFA.universal_language(B) - DFA.from_nfa(NFA.from_regex("(01|1)*0*", input_symbols=B))
print("shortest non-member:", sorted(miss.words_of_length(miss.minimum_word_length())))
print("(1|0)*1 <= (0|1)*:", rx.issubset("(1|0)*1", "(0|1)*", input_symbols=B))

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

~/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 decide.py
automata-lib 9.2.0
spec: empty False | finite True | words 1
new:  empty False | finite False
spec == new: False | spec <= new: True | new <= spec: False
shortest witnesses: ['BG-ddddd']
DIV3 & ONE1 empty: True
DIV3 == (0|11)*: False | (0|11)* <= DIV3: True | DIV3 <= (0|11)*: False
shortest in DIV3 - (0|11)*: ['1001'] | how many of length 10: 253
(0|1)* == (0*1*)*: True
(01|1)*0* universal: False
shortest non-member: ['001']
(1|0)*1 <= (0|1)*: True

প্রতিটি লাইন আমাদের ব্রাউজারের কোডের সঙ্গে মেলে, একটি সম্পূর্ণ আলাদা implementation থেকে। মূল validator ফাঁকা নয়, সসীম, আর তাতে ঠিক ১টি string (abstract alphabet-এ BG-dddd); নতুনটি অসীম। মূলটি নতুনটির ভেতরে আছে, উল্টোটি নয়, আর একমাত্র সবচেয়ে ছোট witness BG-ddddd. DIV3 ∩ ONE1 ফাঁকা। AI-এর অনুমান DIV3-এর ভেতরে, witness 1001, আর দৈর্ঘ্য 10-এর ২৫৩টি string DIV3-এ আছে কিন্তু (0 ∪ 11)∗-এ নেই। হিসাবটি হাতেও মেলে: দৈর্ঘ্য 10-এর binary string-এর মধ্যে ৩৪২টির মান ৩ দিয়ে বিভাজ্য (0 থেকে 1023-এর মধ্যে ৩-এর গুণিতক), আর (0 ∪ 11)∗-এ দৈর্ঘ্য 10-এর string ৮৯টি (1 আর 2 দৈর্ঘ্যের টুকরো দিয়ে 10 ভরার উপায়, একটি Fibonacci সংখ্যা); 342 − 89 = 253.

Regex-এর তিনটি লাইনে library ভেতরে automaton বানিয়ে উত্তর দিয়েছে। (0 ∪ 1)∗ আর (0∗1∗)∗ সমান, পর্ব ১৩-এর একটি অভেদ। (01 ∪ 1)∗0∗ universal নয়, আর সবচেয়ে ছোট বাদ পড়া string 001: শেষের 0-খণ্ডের আগে প্রতিটি 0-এর পরে 1 আসতে হয়, কিন্তু এখানে দুটি 0 পাশাপাশি। Library-র DFA-সমতা (==) Hopcroft–Karp ধরনের union-find পদ্ধতিতে চলে (উৎস কোডের মন্তব্য অনুযায়ী), product-এর সব জোড়া বানিয়ে নয়; উত্তর তবু একই।

Product-এর BFS ঠিক কীভাবে ছড়ায়, তা চোখে দেখতে নিচের JavaScript ব্লক দুই order-code validator-এর জোড়াগুলো স্তরে স্তরে ছাপে (X মানে dead state). কোড বদলে নিজে পরীক্ষা করুন: যেমন neu-এর q7: { d: "q7" } মুছে দিলে দুটি যন্ত্র সমান হয়ে যায়, আর BFS “queue empty” বলে থামে।

// BFS on the product of two order-code validators: where do they first differ?
// Edit spec / neu (e.g. delete the q7 loop) and press Run again.
const chain = { q0: { B: "q1" }, q1: { G: "q2" }, q2: { "-": "q3" }, q3: { d: "q4" },
                q4: { d: "q5" }, q5: { d: "q6" }, q6: { d: "q7" } };
const spec = { delta: chain, start: "q0", final: ["q7"] };
const neu = { delta: { ...chain, q7: { d: "q7" } }, start: "q0", final: ["q7"] };
const sigma = ["B", "G", "-", "d"];
const step = (M, q, c) => (M.delta[q] && M.delta[q][c]) || "X";   // X = dead state
const acc = (M, q) => M.final.includes(q);

let layer = [[spec.start, neu.start]];
const word = new Map([[layer[0].join(","), ""]]);
for (let depth = 0; layer.length > 0; depth++) {
  console.log(`depth ${depth}: ` + layer.map(([a, b]) => `(${a},${b})`).join(" "));
  const bad = layer.find(([a, b]) => acc(spec, a) !== acc(neu, b));
  if (bad) { console.log(`differ at (${bad}), witness "${word.get(bad.join(","))}"`); break; }
  const next = [];
  for (const [a, b] of layer)
    for (const c of sigma) {
      const p = [step(spec, a, c), step(neu, b, c)];
      if (!word.has(p.join(","))) { word.set(p.join(","), word.get(a + "," + b) + c); next.push(p); }
    }
  layer = next;
  if (layer.length === 0) console.log("queue empty: the two validators agree on every string");
}
console.log("pairs discovered:", word.size, "of", 9 * 9, "possible");

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

depth 0: (q0,q0)
depth 1: (q1,q1) (X,X)
depth 2: (q2,q2)
depth 3: (q3,q3)
depth 4: (q4,q4)
depth 5: (q5,q5)
depth 6: (q6,q6)
depth 7: (q7,q7)
depth 8: (X,q7)
differ at (X,q7), witness "BG-ddddd"
pairs discovered: 10 of 81 possible

প্রতিটি স্তরে একটি নতুন জোড়া, কারণ সঠিক অক্ষর পড়লে দুই যন্ত্র একসঙ্গে শিকল ধরে এগোয়, আর ভুল অক্ষর পড়লে দুটিই X-এ যায়, (X, X), যা একবারই আসে। গভীরতা 8-এ প্রথম ভিন্নমতের জোড়া (X, q7): মূল validator পঞ্চম অঙ্কে dead state-এ পড়েছে, নতুনটি q7-এ থেকে গেছে। Witness BG-ddddd, ঠিক automata-lib-এর উত্তর। সম্ভাব্য ৮১টি জোড়ার মধ্যে মাত্র ১০টি তৈরি হয়েছে: বাস্তবে product-এর বেশিরভাগ জোড়া reachable-ই নয়, তাই “শুধু reachable জোড়া” কৌশলটি বড় সাশ্রয় দেয়।

৮ · বাস্তবে decision problem — regression test, token-এর সংঘাত আর সীমানা

এই algorithm-গুলো শুধু পরীক্ষার খাতার জন্য নয়। কয়েকটি বাস্তব ব্যবহার:

Validator-এর regression test

একটি regex বা state machine “পরিষ্কার” করার পর পুরোনো আর নতুন রূপের equivalence যাচাই। ভিন্ন হলে সবচেয়ে ছোট witness সরাসরি একটি নতুন test case হয়ে যায়, যেমন BG-ddddd.

মৃত নিয়ম ধরা

কয়েকটি শর্ত একসঙ্গে বসালে intersection-এর emptiness দেখায়, কোনো input আদৌ পাস করতে পারে কি না। DIV3 ∩ ONE1-এর মতো “অসম্ভব প্রচারণা” আগেই ধরা পড়ে।

Token-এর সংঘাত

Lexer-এ (পর্ব ২২) দুটি token-এর regex-এর intersection ফাঁকা না হলে একই string দুই রকম token হতে পারে; witness দেখায় কোন string-এ অগ্রাধিকারের নিয়ম লাগবে।

Model checking

সিস্টেমের আচরণ একটি automaton, আর “খারাপ ঘটনা”-র বর্ণনা আরেকটি। দুটির product-এর emptiness মানে খারাপ ঘটনা কখনো ঘটে না; witness হলো একটি বাগের পথ (পর্ব ৭৭)।

বাজারঘরের দলের জন্য এর একটি সরল নিয়ম দাঁড়ায়: validator-এর নিয়ম বদলালে শুধু কয়েকটি উদাহরণ নয়, পুরোনো আর নতুন automaton-এর equivalence চালান, আর inclusion দুই দিকে দেখুন। “নতুনটি বেশি নেয়” আর “নতুনটি কম নেয়” দুটি আলাদা ঝুঁকি: প্রথমটিতে ভুল কোড ঢোকে, দ্বিতীয়টিতে সঠিক গ্রাহক আটকে যান। Software testing কোর্সের পর্ব ১০-এ state machine থেকে test বানানোর পদ্ধতি আছে; এখানের equivalence পরীক্ষা সেই test-এর পরিপূরক, কারণ এটি সব string-এর ওপর নিশ্চয়তা দেয়।

সীমানা কোথায়? এই পর্বের প্রতিটি ফল নির্ভর করে একটি তথ্যের ওপর: যন্ত্রটির সসীম state graph. যন্ত্রে একটি stack যোগ করলেই (pushdown automaton, পর্ব ৩২) ছবি বদলায়। Context-free grammar-এর membership আর emptiness এখনো decidable, এমনকি finiteness-ও; কিন্তু দুটি CFG-র equivalence আর একটি CFG-র universality undecidable (পর্ব ৩৭, প্রমাণ পর্ব ৫৪)। আর Turing machine-এর ক্ষেত্রে emptiness-ও undecidable; Rice-এর উপপাদ্য (পর্ব ৫৩) বলে, program-এর language নিয়ে কোনো অ-তুচ্ছ প্রশ্নই decidable নয়। অর্থাৎ “দুটি validator কি সমান?” প্রশ্নটি DFA হলে যন্ত্র দিয়ে নিশ্চিত উত্তর পাওয়া যায়, কিন্তু সাধারণ program হলে কোনো algorithm সব ক্ষেত্রে পারে না।

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

  • EDFA decidable, প্রমাণ করুন। শুরু থেকে চিহ্নিত করতে থাকুন; কোনো accepting state চিহ্নিত না হলে accept. ধাপ বড়জোর |Q|বার।
  • EQDFA decidable, প্রমাণ করুন। Symmetric difference-এর DFA বানিয়ে (closure) তার ওপর EDFA-র decider.
  • একটি regular language সসীম কি না কীভাবে বলবেন? Useful state-এ চক্র আছে কি না; অথবা n ≤ |w| < 2n দৈর্ঘ্যের কোনো string গৃহীত কি না।
  • NFA-র universality কেন DFA-র চেয়ে কঠিন? NFA-তে accepting অদলবদলে complement আসে না; subset construction লাগে, আর সমস্যাটি PSPACE-complete.
  • দুটি DFA ভিন্ন হলে witness কত ছোট হতে পারে? Product-এর state-সংখ্যার চেয়ে ছোট: |w| < |QA|·|QB|.

৯ · AI-এর যুগে regular language-এর decision problem

AI assistant-কে দুটি regex বা DFA দিয়ে “এরা কি সমান?” জিজ্ঞেস করলে সে প্রায়ই আত্মবিশ্বাসী উত্তর দেয়, কখনো কয়েকটি উদাহরণ দেখিয়ে। এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:

AI-এর ভুলকীভাবে ধরবেন
কয়েকটি উদাহরণে মিলেছে বলে “সমান” দাবিProduct-এর BFS চালানো, অথবা অন্তত দৈর্ঘ্য |QA|·|QB| − 1 পর্যন্ত সব string-এ brute force
“State diagram-এ চক্র আছে, তাই language অসীম”Dead state-এর চক্র বাদ দিয়ে শুধু useful state দেখা; মূল order-code validator একটি পাল্টা-উদাহরণ
NFA-তে accepting state অদলবদল করে complement, আর তা দিয়ে universalityআগে subset construction; ছোট উদাহরণে দুই রূপ brute force-এ মেলানো
Partial DFA-র complement নিয়ে inclusion পরীক্ষাআগে dead state যোগ করে DFA total করা (পর্ব ০৮)
“DFA equivalence-ও undecidable” বা “NFA equivalence polynomial” ধরনের দাবিমনে রাখা: DFA-তে polynomial, NFA/regex-এ decidable কিন্তু PSPACE-complete, CFG-তে undecidable
Reduction-এর দিক উল্টো: “EQDFA ≤ EDFA, তাই EDFA কঠিন”A-কে B-তে নামালে B-এর decider A-কে decide করে; কঠিনতা উল্টো দিকে যায় (পর্ব ৫২)
বানানো রেফারেন্স বা ভুল সালSipser-এর বই (অধ্যায় ৪) বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখা

AI-কে ভালোভাবে কাজে লাগানোর উপায়: “সমান কি না” না জিজ্ঞেস করে product আর witness চাওয়া, তারপর সেটি নিজে চালিয়ে দেখা।

আমি গণনার তত্ত্ব শিখছি। Σ = {0, 1}-এর ওপর দুটি DFA: A: a0 (শুরু, accepting) 0 পড়লে a0, 1 পড়লে a1; a1: 0 পড়লে a1, 1 পড়লে a0. B: b0 (শুরু, accepting) 0 পড়লে b0, 1 পড়লে b1; b1: 0 পড়লে b1, 1 পড়লে b2; b2 (accepting): 0 পড়লে b2, 1 পড়লে b1. ১. A আর B কোন language চেনে, এক লাইনে বলো। ২. A আর B-এর product-এর সব reachable জোড়া BFS দিয়ে বের করো, প্রতিটির প্রথম string সহ। ৩. L(A) = L(B) কি না বলো; না হলে সবচেয়ে ছোট witness দাও। ৪. L(A) ⊆ L(B) আর L(B) ⊆ L(A) আলাদা করে বিচার করো। ৫. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা product-এর BFS করে, আর দৈর্ঘ্য ≤ 5-এর সব string-এ brute force দিয়ে তোমার উত্তর মিলিয়ে দেখে। কেন দৈর্ঘ্য 5 যথেষ্ট, তাও বলো।

(নিজে যাচাই করুন: A “1-এর সংখ্যা জোড়”, B-ও আসলে একই language, কারণ b0 আর b2 দুটিই “জোড় সংখ্যক 1” অবস্থা। Product-এর reachable জোড়া (a0, b0), (a1, b1), (a0, b2); কোথাও ভিন্নমত নেই, তাই L(A) = L(B), আর দুই দিকের inclusion-ই সত্য। Product-এ ৩টি reachable জোড়া, তাই দৈর্ঘ্য 2 পর্যন্তই যথেষ্ট; 2 × 3 − 1 = 5 একটি নিরাপদ সীমা। AI যদি “B-তে বেশি state, তাই ভিন্ন” বলে, সেটি একটি পরিচিত ভুল।)

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

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

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

প্র ০১DFA-র প্রায় সব প্রশ্ন decidable, অথচ সাধারণ program-এর প্রায় কোনো প্রশ্ন নয়। পার্থক্যটি ঠিক কোথা থেকে আসে?

Michael Rabin আর Dana Scott-এর ১৯৫৯ সালের বিখ্যাত প্রবন্ধের শিরোনামই ছিল “Finite Automata and Their Decision Problems”. সেখানে nondeterministic automaton-এর ধারণার পাশাপাশি তাঁরা দেখান, emptiness, finiteness আর equivalence-এর মতো প্রশ্ন finite automaton-এর জন্য যান্ত্রিকভাবে সমাধান করা যায়। প্রবন্ধটির গুরুত্ব পরে স্বীকৃত হয়; এই কাজের জন্য দুজন ১৯৭৬ সালের Turing Award পান। শিরোনামেই বোঝা যায়, শুরু থেকেই automaton-এর আকর্ষণের একটি বড় কারণ ছিল এই “বিশ্লেষণযোগ্যতা”।

পার্থক্যের মূল হলো সসীমতা। একটি DFA-র পুরো আচরণ একটি সসীম graph-এ লেখা: প্রতিটি সম্ভাব্য “অবস্থা” একটি state, আর অসীম সংখ্যক string শুধু সেই graph-এ হাঁটার অসীম সংখ্যক উপায়। তাই “কোনো string কি গৃহীত?” প্রশ্নটি অসীম অনুসন্ধান নয়, বরং সসীম graph-এ পথ খোঁজা। Pigeonhole principle প্রতিটি প্রশ্নের জন্য একটি দৈর্ঘ্যের সীমা দেয়: emptiness-এ |Q| − 1, finiteness-এ 2|Q| − 1, equivalence-এ product-এর আকার। সীমার বাইরে নতুন কিছু ঘটে না, শুধু পুরোনো চক্রের পুনরাবৃত্তি।

একটি সাধারণ program-এর মেমরি সীমাহীনভাবে বাড়তে পারে, তাই তার “অবস্থা” অসীম। Turing machine-এর tape-এ অবস্থার সংখ্যার কোনো সীমা নেই, আর তাই কোনো pigeonhole সীমা কাজ করে না। পর্ব ৫১-এ দেখবেন, “এই program কি থামে?” প্রশ্নটিই undecidable, আর পর্ব ৫৩-এর Rice-এর উপপাদ্য বলে, program-এর language নিয়ে কোনো অ-তুচ্ছ প্রশ্ন decidable নয়। মাঝামাঝি একটি স্তরও আছে: pushdown automaton-এর stack অসীম হতে পারে, কিন্তু গঠনটি সীমিত (শুধু ওপরের চিহ্ন দেখা যায়)। তাই CFG-র emptiness decidable থাকে, কিন্তু equivalence হারিয়ে যায়।

বাস্তবেও এই রেখাটি কাজে লাগে। যেসব জিনিস সত্যিই সসীম অবস্থার, যেমন একটি network protocol-এর বার্তার ক্রম, একটি UI-এর মেনু, বা একটি checkout workflow, সেগুলোকে finite automaton হিসেবে লিখলে তাদের সম্পর্কে নিশ্চিত প্রশ্ন করা যায়। এজন্যই নিরাপত্তা-গুরুত্বপূর্ণ সিস্টেমে অনেক সময় ইচ্ছা করে সরল, সসীম মডেল বেছে নেওয়া হয়।

মূল উপলব্ধি: Decidability-র উৎস সসীম state graph আর pigeonhole-এর দৈর্ঘ্যের সীমা। মেমরি সীমাহীন হলেই এই সীমা ভাঙে, আর প্রশ্নগুলো undecidable হতে শুরু করে।

প্র ০২DFA equivalence-এর তিনটি পদ্ধতি দেখলেন: product আর BFS, minimise করে তুলনা, আর Hopcroft–Karp-এর union-find. কোনটি কখন ভালো?

Product আর BFS সবচেয়ে সহজে প্রমাণ করা যায়, আর একটি বড় সুবিধা দেয়: সবচেয়ে ছোট witness. দুটি যন্ত্র ভিন্ন হলে প্রকৌশলী শুধু “না” শুনতে চান না, জানতে চান কোন input-এ ভিন্ন। BFS প্রথম ভিন্নমতের জোড়ায় থেমে সেই string দেয়, আর সেটি সরাসরি একটি test case হয়ে যায়। খরচ সবচেয়ে খারাপ ক্ষেত্রে |QA|·|QB|·|Σ|, যা দুটি বড় DFA-তে অনেক হতে পারে, যদিও বাস্তবে reachable জোড়া প্রায়ই অনেক কম (order-code উদাহরণে ৮১-এর মধ্যে ১০)।

Minimise করে তুলনা করার পদ্ধতি minimal DFA-র অনন্যতার ওপর দাঁড়িয়ে (Myhill–Nerode, পর্ব ১৮)। দুটি language সমান হলে তাদের minimal DFA নাম বদলের পর হুবহু এক, আর নাম বদলের মিল শুরু থেকে একসঙ্গে হেঁটে রৈখিক সময়ে যাচাই করা যায়। Hopcroft-এর minimisation O(n log n) সময়ে চলে বলে পরিচিত (পর্ব ১৯)। পদ্ধতিটি তখন ভালো, যখন অনেকগুলো DFA একে অপরের সঙ্গে তুলনা করতে হয়: প্রতিটিকে একবার minimise করে একটি “canonical রূপ” রাখলেই চলে।

Hopcroft আর Karp-এর ১৯৭১ সালের প্রতিবেদনের পদ্ধতিটি দুই যন্ত্রের শুরুর state-কে “সমান ধরে নেয়”, তারপর প্রতিটি চিহ্নে পরের state-গুলোকেও সমান ধরে union-find দিয়ে দলে জোড়ে। কোনো দলে একটি accepting আর একটি non-accepting state একসঙ্গে পড়লেই উত্তর “ভিন্ন”। প্রতিটি সফল জোড়া দলের সংখ্যা এক কমায়, তাই কাজ প্রায় রৈখিক, |QA| + |QB|-এর মাপের, product-এর গুণফলের মাপের নয়। automata-lib ঠিক এর একটি রূপ ব্যবহার করে। NFA-র জন্য এই ধারণা বড় করে Bonchi আর Pous ২০১৩ সালে “bisimulation up to congruence” নামে একটি পদ্ধতি দেন, যা অনেক বাস্তব উদাহরণে খুব দ্রুত চলে বলে জানা যায়।

পরীক্ষার খাতায় product পদ্ধতি লেখাই নিরাপদ, কারণ প্রমাণটি সরাসরি closure আর emptiness থেকে আসে। Library বা বড় সিস্টেমে Hopcroft–Karp ধরনের পদ্ধতি, আর অনেক যন্ত্র একসঙ্গে থাকলে minimisation. তিনটিই একই প্রশ্নের সঠিক উত্তর দেয়; পার্থক্য খরচে আর বাড়তি তথ্যে।

মূল উপলব্ধি: Product-BFS সবচেয়ে সহজ আর witness দেয়; minimisation canonical রূপ দেয়; union-find প্রায় রৈখিক সময়ে উত্তর দেয়। কাজের প্রয়োজন অনুযায়ী পদ্ধতি বাছুন।

প্র ০৩NFA-র universality PSPACE-complete, অথচ বাস্তবের টুলগুলো প্রায়ই বড় NFA-তে দ্রুত উত্তর দেয়। এই দুটি কথা কীভাবে একসঙ্গে সত্য?

PSPACE-complete একটি সবচেয়ে খারাপ ক্ষেত্রের কথা। এটি বলে, এমন NFA-র পরিবার আছে যাদের জন্য কোনো পরিচিত algorithm polynomial সময়ে চলে না (আর P ≠ PSPACE হলে কোনো algorithm-ই চলবে না)। কিন্তু বাস্তবের input প্রায়ই সেই কঠিন পরিবারের মতো নয়। Subset construction-এ তাত্ত্বিকভাবে 2nটি subset আসতে পারে, অথচ অনেক বাস্তব NFA-তে reachable subset অনেক কম, যেমন order-code-এর product-এ ৮১-এর মধ্যে ১০টি জোড়া।

দ্বিতীয় কৌশল হলো চালাক অনুসন্ধান। De Wulf, Doyen, Henzinger আর Raskin ২০০৬ সালে universality-র জন্য “antichain” পদ্ধতি দেন। মূল ধারণা: subset S থেকে যদি কোনো non-accepting subset-এ পৌঁছানো যায়, তাহলে S-এর যেকোনো ছোট subset থেকেও যায়, কারণ কম state মানে কম সম্ভাবনা। তাই শুধু “সবচেয়ে ছোট” subset-গুলো মনে রাখলেই চলে, বড়গুলো বাদ। অনেক উদাহরণে এটি সাধারণ subset construction-এর চেয়ে বহুগুণ কম subset দেখে বলে তাঁরা পরীক্ষায় দেখান। Bonchi–Pous-এর পদ্ধতিও একই রকম “বাদ দেওয়ার” যুক্তি ব্যবহার করে।

তৃতীয় কথা: সমস্যাটি কঠিন হলেও PSPACE-এর মধ্যে, অর্থাৎ মেমরি polynomial-এই থাকে। একটি subset মনে রাখতে n বিট যথেষ্ট, আর একটি non-accepting subset পর্যন্ত পথ একটি একটি ধাপে অনুমান করে হাঁটা যায়; Savitch-এর উপপাদ্য (পর্ব ৬৪) এই nondeterministic হাঁটাকে deterministic polynomial মেমরিতে আনে। সময় অনেক লাগতে পারে, কিন্তু মেমরি ফুরিয়ে যায় না।

এটি জটিলতা তত্ত্বের একটি সাধারণ শিক্ষা, যা SAT solver-এর ক্ষেত্রেও দেখবেন (পর্ব ৭৩): NP-complete বা PSPACE-complete মানে “সব input-এ ধীর” নয়, মানে “সব input-এ দ্রুত হওয়ার নিশ্চয়তা নেই”। কোন রকম input-এ টুলটি ভালো চলে, তা পরীক্ষা দিয়ে জানতে হয়, আর কঠিন উদাহরণ থাকবেই।

মূল উপলব্ধি: সবচেয়ে খারাপ ক্ষেত্রের কঠিনতা আর গড় বাস্তব input-এর সহজতা পরস্পরবিরোধী নয়। Antichain-এর মতো কৌশল অপ্রয়োজনীয় অনুসন্ধান ছাঁটে, কিন্তু তাত্ত্বিক সীমা সরায় না।

প্র ০৪“দৈর্ঘ্য ১০ পর্যন্ত সব string-এ মিলেছে” কখন একটি প্রমাণ, আর কখন শুধু ইঙ্গিত? Testing আর decision procedure-এর সম্পর্ক কী?

Edsger Dijkstra ১৯৭০ সালের দিকে লিখেছিলেন, program testing বাগের উপস্থিতি দেখাতে পারে, কিন্তু কখনো তাদের অনুপস্থিতি নয়। সাধারণ program-এর জন্য কথাটি পুরোপুরি সত্য: কোনো সসীম test-সেট অসীম সংখ্যক input-এর নিশ্চয়তা দেয় না। কিন্তু DFA-র জগতে এর একটি আশ্চর্য ব্যতিক্রম আছে। দুটি DFA-র product-এ k টি reachable জোড়া থাকলে, তারা ভিন্ন হলে দৈর্ঘ্য < k-এর একটি witness থাকবেই (উপপাদ্য ৫.১)। তাই দৈর্ঘ্য k − 1 পর্যন্ত সব string-এ মিললে সেটি একটি পূর্ণ প্রমাণ।

অর্থাৎ testing তখনই প্রমাণ, যখন একটি “ছোট মডেল” উপপাদ্য থাকে: যদি ভুল থাকে, তাহলে একটি ছোট উদাহরণেই থাকবে। Emptiness-এ সীমা |Q| − 1, finiteness-এ 2|Q| − 1, equivalence-এ product-এর আকার (আর তীক্ষ্ণভাবে |QA| + |QB| − 2). সীমা না জানলে “দৈর্ঘ্য ১০ পর্যন্ত মিলেছে” শুধু ইঙ্গিত। পর্ব ১৫-এ ঠিক এই সতর্কতা ছিল: brute force দৈর্ঘ্য ১০ পর্যন্ত মেলায়, সব দৈর্ঘ্যে নয়।

তবে সীমা জানা থাকলেও brute force বাস্তবে প্রায়ই অচল। দুটি ২০-state DFA-র product-এর সীমা ৪০০-এর কাছে; binary alphabet-এ দৈর্ঘ্য ৩৯৯ পর্যন্ত সব string মানে প্রায় 2400টি, যা মহাবিশ্বের পরমাণুর সংখ্যার চেয়ে অনেক বেশি। BFS একই প্রমাণ দেয় মাত্র কয়েকশো জোড়া দেখে, কারণ এটি একই state-জোড়ায় পৌঁছানো সব string-কে একসঙ্গে একবার বিবেচনা করে। এখানেই decision procedure-এর শক্তি: এটি অসীম string-কে সসীম শ্রেণিতে ভাগ করে কাজ করে।

Software testing-এর দিক থেকে দুটি পদ্ধতি একে অপরের পরিপূরক। Random বা property-based testing (Software testing কোর্সের পর্ব ৫৮) দ্রুত, যেকোনো program-এ চলে, আর প্রায়ই বাগ ধরে। Decision procedure ধীর হতে পারে আর শুধু সীমিত মডেলে চলে, কিন্তু “বাগ নেই” বলার অধিকার দেয়। বাজারঘরের validator-এর মতো ক্ষেত্রে দুটি একসঙ্গে ব্যবহার করাই বুদ্ধিমানের কাজ।

মূল উপলব্ধি: Testing প্রমাণ হয় শুধু তখন, যখন “ভুল থাকলে ছোট উদাহরণেই থাকবে” ধরনের একটি সীমা প্রমাণিত। DFA-তে সেই সীমা আছে; সাধারণ program-এ নেই।

প্র ০৫Model checking কীভাবে এই পর্বের emptiness প্রশ্নে নেমে আসে? আর এই সংযোগ বাস্তব সিস্টেম যাচাইয়ে কতটা গুরুত্বপূর্ণ?

Model checking-এর প্রশ্নটি হলো: একটি সিস্টেমের সব সম্ভাব্য আচরণ কি একটি নির্দিষ্ট নিয়ম মানে? যেমন, বাজারঘরের checkout workflow-তে “পেমেন্ট নিশ্চিত হওয়ার আগে কখনো ডেলিভারি শুরু হবে না”। সিস্টেমের আচরণগুলো একটি automaton S-এর language, আর নিয়ম ভাঙে এমন সব আচরণ আরেকটি automaton B-এর language. তাহলে প্রশ্নটি দাঁড়ায় L(S) ∩ L(B) = ∅ কি না, ঠিক এই পর্বের DIV3 ∩ ONE1-এর মতো একটি product-এর emptiness. ফাঁকা না হলে BFS-এর witness হলো একটি বাস্তব বাগের ঘটনাক্রম, যা প্রকৌশলীকে সরাসরি দেখানো যায়।

বাস্তব সিস্টেম কখনো কখনো থামে না, যেমন একটি সার্ভার বা একটি protocol. তাদের আচরণ অসীম দৈর্ঘ্যের ক্রম, তাই সাধারণ finite automaton-এর বদলে Büchi automaton লাগে, যা অসীম ক্রম গ্রহণ করে যদি একটি accepting state অসীমবার আসে। সেখানে emptiness-এর প্রশ্নটি একটু বদলায়: একটি reachable accepting state খোঁজা নয়, বরং এমন একটি reachable accepting state খোঁজা যা একটি চক্রের ওপর আছে। এটি এই পর্বের finiteness পরীক্ষার খুব কাছের আত্মীয়: useful state-এর চক্র।

এই “automata-theoretic” দৃষ্টিভঙ্গি সাধারণত Moshe Vardi আর Pierre Wolper-এর ১৯৮৬ সালের কাজের সঙ্গে যুক্ত করা হয়। এর আগে Edmund Clarke, Allen Emerson আর Joseph Sifakis ১৯৮০-এর দশকের শুরুতে model checking-এর ভিত্তি দেন, যার জন্য তাঁরা ২০০৭ সালের Turing Award পান। SPIN-এর মতো টুল ঠিক এই পদ্ধতিতে কাজ করে: নিয়মের negation থেকে একটি automaton, তারপর product আর চক্রসহ emptiness পরীক্ষা।

বড় বাধা হলো আকার: S-এর state সংখ্যা সিস্টেমের সব variable-এর সব মানের সমন্বয়, যা খুব দ্রুত বাড়ে (“state explosion”). তাই বাস্তবে product পুরোটা না বানিয়ে on-the-fly অনুসন্ধান, symmetry ব্যবহার, আর BDD-র মতো সংক্ষিপ্ত উপস্থাপনা লাগে। পর্ব ৭৭-এ এই কৌশলগুলোর পরিচয় পাবেন।

মূল উপলব্ধি: “সিস্টেম কি নিয়ম মানে?” প্রশ্নটি product-এর emptiness-এ নামে, আর witness হলো বাগের পথ। এই পর্বের ছোট BFS-ই শিল্পে ব্যবহৃত model checker-এর হৃদয়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। DFA বদলে উপরের Python ব্লকে বসিয়ে নিজের উত্তরও যাচাই করতে পারেন।

  1. নির্মাণ (inclusion): Σ = {0, 1}. A = “1-এর সংখ্যা জোড়” (state E, O), B = “1-এর সংখ্যা ৪ দিয়ে বিভাজ্য” (state r0, r1, r2, r3, মানে 1-এর সংখ্যা mod 4). (ক) A × B-এর product-এর reachable জোড়াগুলো বের করুন। (খ) L(B) ⊆ L(A) আর L(A) ⊆ L(B) বিচার করুন; যেটি মিথ্যা, তার সবচেয়ে ছোট witness দিন।

    (ক) শুরু (E, r0). 0 পড়লে কোনো যন্ত্র নড়ে না; 1 পড়লে দুটিই এক ধাপ এগোয়। তাই reachable জোড়া ঠিক চারটি: (E, r0), (O, r1), (E, r2), (O, r3), তারপর আবার (E, r0). (E, r1) বা (O, r0)-এর মতো বাকি চারটি জোড়া unreachable, কারণ 1-এর সংখ্যার জোড়-বিজোড় আর mod 4-এর ভাগশেষের জোড়-বিজোড় সবসময় এক।

    (খ) L(B) ⊆ L(A)-এর জন্য দরকার এমন জোড়া, যেখানে B গ্রহণ করে (r0) কিন্তু A করে না (O): (O, r0) unreachable, তাই inclusion সত্য। L(A) ⊆ L(B)-এর জন্য খুঁজতে হয় A গ্রহণ করে (E) কিন্তু B করে না: (E, r2) reachable, প্রথম string “11”. তাই L(A) ⊄ L(B), witness 11 (দুটি 1: জোড়, কিন্তু ৪-এর গুণিতক নয়)। Scratch-এ দৈর্ঘ্য 10 পর্যন্ত brute force-এ দুটি ফলই মিলেছে।

  2. প্রমাণের ভুল ধরুন: দাবি: “একটি DFA M-এর language অসীম ⇔ M-এর state diagram-এ একটি চক্র আছে।” প্রমাণ: “(⇒) অসীম হলে লম্বা string-এ pigeonhole-এ একটি state দুবার আসে, তাই চক্র আছে। (⇐) চক্র থাকলে সেটি যতবার খুশি ঘোরা যায়, তাই অসীম সংখ্যক string. ∎” কোন দিকটি ভুল? একটি পাল্টা-উদাহরণ দিন আর দাবিটি ঠিক করে প্রমাণ করুন।

    (⇒) দিকটি ঠিক। (⇐) ভুল: চক্রটি ঘুরে পাওয়া string-গুলো গৃহীত হতে হবে, আর তার জন্য চক্রে শুরু থেকে পৌঁছাতে হয় এবং চক্র থেকে accepting state-এ যেতে হয়। পাল্টা-উদাহরণ: মূল order-code validator-কে total করলে dead state X-এ চার চিহ্নেই চক্র আছে, অথচ language-এ শুধু একটি string, BG-dddd. আরও সরল: Σ = {0}, একটি state q0, non-accepting, 0 পড়লে q0: চক্র আছে, language ∅.

    ঠিক দাবি: L(M) অসীম ⇔ কোনো useful state একটি চক্রের ওপর আছে। প্রমাণ উপপাদ্য ৪.২-এর ধাপ ১–৩: চক্রসহ useful state থেকে x, y, z নিয়ে xyiz সবই গৃহীত আর ভিন্ন; উল্টো দিকে দৈর্ঘ্য ≥ |Q|-এর একটি গৃহীত string-এর run-এ একটি state দুবার আসে, আর সেই state reachable ও co-reachable, তাই useful. ∎

  3. Trace আর অনুমান: Σ = {0, 1}. সঠিক DFA C “01 দিয়ে শেষ”: c0 (শুরু) 0 পড়লে c1, 1 পড়লে c0; c1: 0 → c1, 1 → c2; c2 (accepting): 0 → c1, 1 → c0. একজন শিক্ষার্থীর DFA S হুবহু একই, শুধু s2-তে 0 পড়লে s1-এর বদলে s0-তে যায়। Product-এ BFS চালিয়ে (প্রতিটি জোড়ায় আগে 0, তারপর 1) কোন জোড়াগুলো কোন ক্রমে আসে আর প্রথম witness কী, অনুমান করুন।
    1. (c0, s0), string ε: দুটিই reject. 0 পড়ে (c1, s1); 1 পড়ে আবার (c0, s0). — একমত
    2. (c1, s1), string 0: 0 পড়ে নিজের কাছে; 1 পড়ে (c2, s2), string 01. — দুটিই reject, একমত
    3. (c2, s2), string 01: দুটিই accept. 0 পড়ে (c1, s0), string 010 — এখানেই বাগ ঢুকল; 1 পড়ে (c0, s0), আগে দেখা। — একমত
    4. (c1, s0), string 010: দুটিই reject. 0 পড়ে (c1, s1), আগে দেখা; 1 পড়ে (c2, s0), string 0101. — এখনো একমত
    5. (c2, s0): C accept, S reject. প্রথম witness 0101. ∎ — ভিন্নমত

    Scratch-এ একই BFS কোডে হুবহু এই ক্রম আর witness 0101 এসেছে; দৈর্ঘ্য 10 পর্যন্ত মোট ১০২টি string-এ দুই যন্ত্র ভিন্ন, আর সবচেয়ে ছোট পাঁচটি 0101, 00101, 10101, 000101, 100101. কারণটি সহজ: “…010”-এর পরে S শেষ 0-টি ভুলে যায়, তাই পরের 1-এ “01” চিনতে পারে না।

  4. Decider নকশা: ODD1DFA = {⟨M⟩ : M একটি DFA (Σ = {0, 1}) আর M অন্তত একটি এমন string গ্রহণ করে, যাতে 1-এর সংখ্যা বিজোড়}. প্রমাণ করুন যে ODD1DFA decidable, Sipser-ধাঁচে একটি decider লিখে। তারপর M = DIV3 হলে আপনার decider কী উত্তর দেবে, আর কোন সবচেয়ে ছোট string দেখাবে?

    Decider: “input ⟨M⟩ পেলে: ১. ODD নামের ২-state DFA নিন (O মানে বিজোড়, accepting). ২. M আর ODD-এর product C বানান, accepting = দুটিই গ্রহণ করে (intersection). ৩. EDFA-র decider ⟨C⟩-এ চালান। ৪. সেটি accept করলে (L(C) = ∅) reject, নইলে accept.” — closure আর উপপাদ্য ৩.১

    সঠিকতা: L(C) = L(M) ∩ L(ODD), তাই L(C) ≠ ∅ ⇔ M এমন একটি string গ্রহণ করে যাতে 1 বিজোড় সংখ্যক। প্রতিটি ধাপ সসীম, তাই decider থামে। ∎

    DIV3: উত্তর “accept”. Product-এ BFS-এর সবচেয়ে ছোট string 10101, মান 21 = 3 × 7, তাতে তিনটি 1. ছোট কোনোটি নেই: 11 (3), 110 (6), 1001 (9), 1100 (12), 1111 (15) সবার 1-এর সংখ্যা জোড়। Scratch-এ brute force-এ এটি নিশ্চিত করা হয়েছে।

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

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

ক্রমদুটি DFA A আর B একই language চেনে কি না, product আর BFS দিয়ে বিচার করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. দুটি DFA total কি না দেখা, দরকার হলে dead state যোগ করা
  2. শুরুর জোড়া (qA, qB) থেকে product-এর reachable জোড়াগুলো বানানো
  3. যে জোড়ায় ঠিক একটি যন্ত্র গ্রহণ করে, সেগুলোকে accepting চিহ্নিত করা
  4. শুরু থেকে BFS চালিয়ে কোনো accepting জোড়ায় পৌঁছানো যায় কি না দেখা
  5. পৌঁছানো না গেলে “সমান” বলা, গেলে সেই জোড়ার প্রথম string-কে witness হিসেবে দেওয়া

একটি DFA M-এর language ফাঁকা কি না (EDFA) বিচারের সঠিক পদ্ধতি কোনটি?

  • দৈর্ঘ্য 10 পর্যন্ত সব string চালিয়ে দেখা
  • শুরুর state থেকে কোনো accepting state-এ পৌঁছানো যায় কি না, graph-এ BFS দিয়ে দেখা
  • F ফাঁকা কি না দেখা
  • State diagram-এ চক্র আছে কি না দেখা

একটি DFA-র language অসীম হওয়ার সঠিক শর্ত কোনটি?

  • State diagram-এ অন্তত একটি চক্র আছে
  • একাধিক accepting state আছে
  • শুরু থেকে পৌঁছানো যায় আর accepting state-এ যেতে পারে এমন কোনো state একটি চক্রের ওপর আছে
  • DFA-তে ১০-এর বেশি state আছে

দুটি DFA A আর B-এর জন্য L(A) ⊆ L(B) প্রশ্নটি কোন emptiness প্রশ্নের সমতুল্য?

  • L(A) ∩ L̄(B) = ∅
  • L(A) ∩ L(B) = ∅
  • L̄(A) ∩ L(B) = ∅
  • L̄(A) ∩ L̄(B) = ∅

Σ = {0, 1}-এর ওপর NFA দেওয়া থাকলে “L(N) = Σ∗ কি না” (universality) প্রশ্নটির জটিলতা সম্পর্কে কোনটি প্রমাণিত?

  • Accepting state অদলবদল করে emptiness দেখলেই polynomial সময়ে হয়
  • সমস্যাটি undecidable
  • সমস্যাটি NP-complete বলে প্রমাণিত
  • সমস্যাটি decidable আর PSPACE-complete

দুটি DFA-র product-এ শুরু থেকে মোট 6টি জোড়া reachable. দুটি DFA ভিন্ন language চিনলে নিচের কোন কথাটি অবশ্যই সত্য?

  • সবচেয়ে ছোট witness-এর দৈর্ঘ্য ঠিক 6
  • দৈর্ঘ্য 5 বা তার কম একটি witness আছে
  • Witness অসীম লম্বা হতে পারে, তাই brute force কখনো যথেষ্ট নয়
  • সবচেয়ে ছোট witness সবসময় ফাঁকা string ε

নিচের কোন প্রশ্নটি undecidable?

  • দুটি DFA একই language চেনে কি না
  • একটি string একটি regex-এর language-এ আছে কি না
  • দুটি context-free grammar একই language তৈরি করে কি না
  • একটি NFA-র language ফাঁকা কি না

শব্দকোষ

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

মনে রাখুন

  1. Membership, emptiness, finiteness, universality, equivalence আর inclusion: regular language-এর ছয়টি প্রশ্নই decidable, কারণ DFA-র state graph সসীম।
  2. Emptiness = শুরু থেকে accepting state-এ reachability; ফাঁকা না হলে দৈর্ঘ্য < |Q|-এর একটি গৃহীত string আছে, আর BFS সবচেয়ে ছোটটি দেয়।
  3. Finiteness: অসীম ⇔ কোনো useful state চক্রে আছে ⇔ n ≤ |w| < 2n দৈর্ঘ্যের কোনো string গৃহীত। Dead state-এর চক্র গোনা হয় না।
  4. Equivalence, inclusion, universality সবই product আর complement দিয়ে emptiness-এ নামে; ভিন্ন হলে witness-এর দৈর্ঘ্য product-এর reachable জোড়ার সংখ্যার চেয়ে কম।
  5. DFA input-এ সব প্রশ্ন polynomial; NFA বা regex input-এ universality, equivalence আর inclusion PSPACE-complete; CFG-তে equivalence undecidable, আর Turing machine-এ emptiness-ও।

পরের পর্বে: মডিউল ৪ শুরু, বাস্তবের regex engine: Python, JavaScript আর grep-এর engine কীভাবে কাজ করে, backtracking বনাম automaton-ভিত্তিক matching, backreference কেন regular নয়, আর একটি নিরীহ regex কীভাবে একটি সার্ভার থামিয়ে দিতে পারে (ReDoS).

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

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