এই পর্বে যা শিখবেন
- সমতুল্য state-এর সংজ্ঞা, আর জোড়া লাগানো DFA (quotient) কেন একই language চেনে তার প্রমাণ
- Table-filling algorithm হাতে পুরো টেবিলসহ, আর এর সঠিকতার প্রমাণ
- Moore-এর রাউন্ড-ভিত্তিক refinement আর Hopcroft-এর algorithm-এর মূল ধারণা ও খরচ
- Minimal DFA-র অনন্যতার প্রমাণ, আর প্রতিটি জোড়ার জন্য witness দিয়ে minimality যাচাই
- ব্রাউজারের Python ও JavaScript আর সত্যিকারের automata-lib run দিয়ে নিজের ফল মিলিয়ে দেখা
১ · কেন minimise — একই কাজ, কম state
একই language-এর অনেক DFA থাকে। পর্ব ০৮-এ দেখেছেন, product construction সবসময় সঠিক কিন্তু সবসময় সবচেয়ে ছোট নয়, আর binary-তে ৪ দিয়ে বিভাজ্যতার DFA-তে ৪টি state থাকলেও ৩টিই যথেষ্ট। পর্ব ০৭-এ দেখেছেন, কিছু state-এ শুরু থেকে পৌঁছানোই যায় না। এই পর্ব সেই প্রশ্নের পূর্ণ উত্তর দেয়: যেকোনো DFA থেকে DFA minimization দিয়ে সবচেয়ে কম state-এর সমতুল্য DFA বানানোর algorithm, আর তার প্রমাণ।
একটি রেলস্টেশনের টিকিট কাউন্টারের কথা ভাবুন। সাতটি জানালা, প্রতিটির নিজের নিয়মের খাতা। খাতাগুলো মিলিয়ে দেখা গেল, দুটি জানালা যেকোনো যাত্রীর যেকোনো অনুরোধে হুবহু একই উত্তর দেয়, আর একটি জানালার সামনে যাওয়ার কোনো রাস্তাই নেই। তাহলে রাস্তাহীন জানালাটি বন্ধ করা যায়, আর একই উত্তর দেওয়া জানালাগুলো এক করা যায়; যাত্রীরা কোনো পার্থক্য টের পাবেন না। Minimization ঠিক এই কাজ: বাইরে থেকে যে পার্থক্য দেখা যায় না, তা ভেতর থেকে মুছে ফেলা।
কেন দরকার? প্রথমত, ছোট DFA মানে ছোট টেবিল: lexer, validator বা hardware-এর state machine-এ মেমরি আর circuit কম লাগে (Computer Architecture কোর্সের পর্ব ১৭-এ hardware FSM-এর state কমানো দেখবেন)। দ্বিতীয়ত, minimal DFA অনন্য, তাই দুটি DFA একই language চেনে কি না জানতে দুটিকে minimise করে মিলিয়ে দেখলেই চলে। তৃতীয়ত, minimal DFA-র state-সংখ্যা language-টির একটি নিজস্ব মাপ, যন্ত্রের নয়।
এই পর্বের notation: DFA M = (Q, Σ, δ, q0, F), যেখানে δ : Q × Σ → Q total. কোনো DFA partial হলে আগে একটি dead state qd যোগ করে complete করুন; minimal DFA-র state গোনার সময় dead state-ও গোনা হয়। δ̂ হলো পুরো string-এর transition (কিছু বইয়ে δ∗)। n = |Q|.
এই পর্বের চলমান উদাহরণ DIV6: Σ = {0, 1}-এর ওপর সেই string, যাদের binary মান ৬ দিয়ে বিভাজ্য (ε-এর মান 0 ধরে)। পর্ব ০৮-এর ধাঁচে state qr মানে “এ পর্যন্ত পড়া মানের ৬ দিয়ে ভাগশেষ r”, আর δ(qr, b) = q(2r + b) mod 6. শুরু আর একমাত্র accepting state q0. বাজারঘরের একজন প্রকৌশলী আগের একটি সংস্করণ থেকে একটি বাড়তি state q6 রেখে দিয়েছেন: q6 থেকে 0-তে q0, 1-এ q6, কিন্তু q6-এ কোনো তীর ঢোকে না। মোট ৭টি state. শেষে দেখবেন, ৪টিই যথেষ্ট।
| state | 0 পড়লে | 1 পড়লে | accepting? |
|---|---|---|---|
| → q0 | q0 | q1 | হ্যাঁ |
| q1 | q2 | q3 | না |
| q2 | q4 | q5 | না |
| q3 | q0 | q1 | না |
| q4 | q2 | q3 | না |
| q5 | q4 | q5 | না |
| q6 | q0 | q6 | না |
২ · প্রথম ধাপ — unreachable state বাদ
যে state-এ q0 থেকে কোনো string পড়ে পৌঁছানো যায় না, কোনো run সেখানে যায় না, তাই মুছে দিলে language বদলায় না। খোঁজার উপায় graph-এর reachability: q0 থেকে BFS চালিয়ে যত state পাওয়া যায়, সেগুলোই reachable. খরচ O(n|Σ|). DIV6-এ BFS-এর ক্রম q0, q1, q2, q3, q4, q5; q6 কখনো আসে না, তাই সেটি বাদ।
এই ধাপ বাদ দিলে কী হয়? পরের ধাপ শুধু “সমতুল্য” state জোড়া লাগায়। q6 কিন্তু বাকি কোনো state-এর সমতুল্য নয়: q3 থেকে 10 পড়লে q2-এ (বাতিল), অথচ q6 থেকে 10 পড়লে q0-তে (গৃহীত)। তাই q6 নিজের একটি দলে থেকে যায়, আর ফল হয় ৫টি state, যা minimal নয়। অর্থাৎ সমতুল্যতা আর reachability দুটি আলাদা ধারণা, আর minimal DFA-র জন্য দুটিই লাগে।
৩ · সমতুল্য state আর জোড়া লাগানো DFA
DFA M-এর দুটি state p, q-কে সমতুল্য বলা হয়, লেখা p ≡ q, যদি
∀ w ∈ Σ∗ : δ̂(p, w) ∈ F ⇔ δ̂(q, w) ∈ F.
তা না হলে p আর q distinguishable, আর যে w-এর জন্য ঠিক একটি accepting-এ থামে, সেটি তাদের witness (পার্থক্যকারী string).
কথায়: p থেকে শুরু করা আর q থেকে শুরু করার “ভবিষ্যৎ” একই। এটি equivalence relation: reflexive আর symmetric স্পষ্ট, আর transitive কারণ ⇔ নিজেই transitive. তাই ≡ state-গুলোকে বিচ্ছিন্ন equivalence class-এ ভাগ করে (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫৫)। দুটি সহজ পর্যবেক্ষণ: w = ε নিলে দেখা যায়, p ≡ q হলে দুটিই accepting বা দুটিই নয়; আর accepting ও non-accepting state সবসময় distinguishable, witness ε.
p ≡ q হলে প্রতিটি a ∈ Σ-এর জন্য δ(p, a) ≡ δ(q, a).
প্রমাণ:
- যেকোনো w নিন। δ̂(δ(p, a), w) = δ̂(p, aw), আর একইভাবে q-এর জন্য। — δ̂-এর সংজ্ঞা
- p ≡ q, তাই string aw-এর জন্য δ̂(p, aw) ∈ F ⇔ δ̂(q, aw) ∈ F. — সংজ্ঞা ৩.১, w-এর জায়গায় aw
- দুটি মিলিয়ে δ̂(δ(p, a), w) ∈ F ⇔ δ̂(δ(q, a), w) ∈ F, সব w-এর জন্য। তাই δ(p, a) ≡ δ(q, a). ∎
Lemma-টির বিপরীত দিক (contrapositive) table-filling-এর ইঞ্জিন: δ(p, a) আর δ(q, a) distinguishable হলে p আর q-ও distinguishable; witness w হলে p-q-এর witness aw. এবার জোড়া লাগানো DFA-র সংজ্ঞা।
[p] দিয়ে p-এর class বোঝালে quotient DFA M/≡ = (Q/≡, Σ, δ′, [q0], F′), যেখানে δ′([p], a) = [δ(p, a)] আর F′ = {[p] : p ∈ F}. তাহলে L(M/≡) = L(M).
প্রমাণ:
- δ′ সুসংজ্ঞায়িত: [p] = [q] হলে p ≡ q, তাই [δ(p, a)] = [δ(q, a)]; কোন সদস্য দিয়ে হিসাব করা হলো তাতে ফল বদলায় না। — Lemma ৩.২
- F′ সুসংজ্ঞায়িত: একটি class-এর সব সদস্য একসঙ্গে accepting বা একসঙ্গে নয়। — w = ε
- |w|-এর ওপর induction-এ δ̂′([q0], w) = [δ̂(q0, w)]. ভিত্তি w = ε স্পষ্ট; ধাপে δ̂′([q0], va) = δ′([δ̂(q0, v)], a) = [δ̂(q0, va)]. — induction hypothesis আর δ′-এর সংজ্ঞা
- তাই w ∈ L(M/≡) ⇔ [δ̂(q0, w)] ∈ F′ ⇔ δ̂(q0, w) ∈ F ⇔ w ∈ L(M). ∎ — ধাপ ২
অর্থাৎ পুরো সমস্যাটি দাঁড়াল একটি প্রশ্নে: কোন state-জোড়া সমতুল্য? সংজ্ঞায় “সব w” আছে, যা অসীম। পরের তিনটি algorithm দেখায়, সসীম কয়েকটি ধাপেই উত্তর বের করা যায়।
৪ · Table-filling algorithm — পুরো টেবিল ধাপে ধাপে
Hopcroft–Motwani–Ullman-এর বইয়ে এর নাম table-filling; অনেক জায়গায় একে Myhill–Nerode পদ্ধতি বা “pair marking”-ও বলা হয়। ধারণাটি সোজা: পার্থক্য ধরা পড়লে টুকে রাখুন, আর পার্থক্য পেছনের দিকে ছড়িয়ে দিন।
ইনপুট: reachable state-সহ একটি complete DFA.
রাউন্ড 0: প্রতিটি জোড়া {p, q}, যেখানে ঠিক একটি accepting, চিহ্নিত করুন।
রাউন্ড k ≥ 1: প্রতিটি চিহ্নহীন জোড়া {p, q} আর প্রতিটি a ∈ Σ দেখুন; {δ(p, a), δ(q, a)} যদি আগের রাউন্ডগুলোতে চিহ্নিত হয়ে থাকে, তবে {p, q} চিহ্নিত করুন।
কোনো রাউন্ডে নতুন চিহ্ন না পড়লে থামুন। চিহ্নহীন জোড়া মানে সমতুল্য state.
DIV6-এর ৬টি reachable state-এ জোড়া 6C2 = ১৫টি। নিচের stepper প্রতিটি রাউন্ড দেখায়।
1BFS: reachable খোঁজা2রাউন্ড 0: F বনাম বাকি3রাউন্ড 1: চিহ্ন ছড়ানো4রাউন্ড 2: আবার ছড়ানো5রাউন্ড 3: নতুন নেই, থামা
| নতুন চিহ্ন | |
| কারণ | |
| চিহ্নিত | |
| চিহ্নহীন |
- Reachable state. q0 থেকে BFS: q0 → q1 → q2, q3 → q4, q5. q6 কখনো আসে না, তাই বাদ। এখন ৬টি state, ১৫টি জোড়া, সবগুলো চিহ্নহীন।
- রাউন্ড 0. শুধু q0 accepting, তাই q0-যুক্ত ৫টি জোড়া চিহ্নিত। এদের witness ফাঁকা string ε: q0 থেকে কিছু না পড়লে গৃহীত, অন্যটি থেকে বাতিল।
- রাউন্ড 1. 0 পড়লে q3 যায় q0-তে, কিন্তু q1, q2, q4, q5 যায় q2 বা q4-এ। তাই (q1, q3)-এর 0-পরের জোড়া (q2, q0), যা রাউন্ড 0-এ চিহ্নিত; একইভাবে q2q3, q3q4, q3q5. এদের witness “0”.
- রাউন্ড 2. 1 পড়লে q1 আর q4 যায় q3-এ, q2 আর q5 যায় q5-এ। তাই q1q2, q1q5, q2q4, q4q5-এর 1-পরের জোড়া (q3, q5), যা রাউন্ড 1-এ চিহ্নিত। Witness “1” জুড়ে “10”.
- রাউন্ড 3. চিহ্নহীন q1q4: 0-তে দুটিই q2-এ, 1-এ দুটিই q3-এ; q2q5: 0-তে দুটিই q4, 1-এ দুটিই q5. একই state-এ যাওয়া জোড়া কখনো চিহ্নিত হয় না। নতুন চিহ্ন নেই, তাই থামা। Class চারটি।
শেষ টেবিলটি প্রচলিত “সিঁড়ি” আকারে নিচে। প্রতিটি ঘরে লেখা আছে জোড়াটি কোন রাউন্ডে চিহ্নিত হয়েছে; “≡” মানে কখনো চিহ্নিত হয়নি। পরীক্ষার খাতায় সাধারণত ঘরে × দেওয়া হয়; রাউন্ড নম্বর লিখলে পরে witness-এর দৈর্ঘ্যও পড়া যায় (নিচের উপপাদ্য দেখুন)।
| q0 | q1 | q2 | q3 | q4 | |
|---|---|---|---|---|---|
| q1 | 0 | ||||
| q2 | 0 | 2 | |||
| q3 | 0 | 1 | 1 | ||
| q4 | 0 | ≡ | 2 | 1 | |
| q5 | 0 | 2 | ≡ | 1 | 2 |
Algorithm ৪.১ শেষে একটি জোড়া {p, q} চিহ্নিত ⇔ p আর q distinguishable. আরও সূক্ষ্মভাবে, জোড়াটি রাউন্ড k-তে চিহ্নিত ⇔ এর সবচেয়ে ছোট witness-এর দৈর্ঘ্য k.
প্রমাণ (প্রথম দাবি; দ্বিতীয়টি একই induction-এ আসে):
- (⇒) চিহ্নিত হলে distinguishable, রাউন্ডের ওপর induction. রাউন্ড 0-এর জোড়ার witness ε. — ঠিক একটি accepting
- রাউন্ড k-তে {p, q} চিহ্নিত হয়েছে কারণ কোনো a-তে {δ(p, a), δ(q, a)} আগে চিহ্নিত; induction অনুযায়ী তার witness w আছে, তাই aw হলো p-q-এর witness. — Lemma ৩.২-এর contrapositive
- (⇐) distinguishable হলে চিহ্নিত: ধরুন কিছু distinguishable জোড়া শেষ পর্যন্ত চিহ্নহীন। এদের মধ্যে যে জোড়ার সবচেয়ে ছোট witness সবচেয়ে ছোট, সেটি {p, q} নিন, witness w. — contradiction-এর জন্য ধরে নেওয়া
- w ≠ ε, কারণ তাহলে রাউন্ড 0-এই চিহ্নিত হতো। তাই w = av. — রাউন্ড 0-এর নিয়ম
- v হলো {δ(p, a), δ(q, a)}-এর witness, আর |v| < |w|; w-এর ন্যূনতমতা অনুযায়ী এই জোড়া চিহ্নিত। — ধাপ ৩-এর বাছাই
- তাহলে পরের রাউন্ডে {p, q}-ও চিহ্নিত হতো, আর algorithm সেই রাউন্ডের আগে থামতে পারে না, কারণ চিহ্ন পড়া রাউন্ডের পরই থামে। বিরোধ। ∎ — algorithm-এর নিয়ম
খরচ ও থামা: জোড়া সসীম, আর প্রতিটি কার্যকর রাউন্ডে অন্তত একটি নতুন চিহ্ন পড়ে, তাই algorithm থামবেই। আসলে কার্যকর রাউন্ড বড়জোর n − 2টি (অংশ ৫-এ কারণ দেখবেন)। সরল রূপে প্রতি রাউন্ডে O(n2|Σ|) কাজ, তাই মোট O(n3|Σ|). প্রতিটি জোড়ার সঙ্গে “আমার ওপর নির্ভরশীল জোড়া”-র তালিকা রেখে, চিহ্ন পড়লে শুধু সেই তালিকা ধরে পেছনে ছড়ালে খরচ O(n2|Σ|).
নিচের ব্লক ঠিক এই algorithm চালায়: আগে BFS, তারপর রাউন্ডে রাউন্ডে চিহ্ন। new তালিকাটি আগের রাউন্ডের চিহ্ন দেখে একবারে তৈরি হয়, তাই রাউন্ডগুলো stepper-এর মতো আলাদা থাকে। পরের দুটি Python ব্লক এই DFA ব্যবহার করবে (data-shared), তাই আগে এটি চালান।
from itertools import combinations
from collections import deque
# DIV6: binary value divisible by 6 (state = remainder), plus a leftover q6
delta = {(f"q{r}", b): f"q{(2 * r + int(b)) % 6}" for r in range(6) for b in "01"}
delta["q6", "0"], delta["q6", "1"] = "q0", "q6"
SIGMA, START, FINAL = "01", "q0", {"q0"}
def reachable(start): # step 1: BFS from the start state
seen, queue = [start], deque([start])
while queue:
p = queue.popleft()
for a in SIGMA:
if delta[p, a] not in seen:
seen.append(delta[p, a]); queue.append(delta[p, a])
return seen
def table_fill(Q): # step 2: mark distinguishable pairs
pairs = list(combinations(Q, 2))
mark = {pq: 0 for pq in pairs if (pq[0] in FINAL) != (pq[1] in FINAL)}
print("round 0:", *(f"{p}{q}" for p, q in mark))
for rnd in range(1, len(Q)):
new = [(p, q) for p, q in pairs if (p, q) not in mark and any(
tuple(sorted((delta[p, a], delta[q, a]))) in mark for a in SIGMA)]
if not new: break
for pq in new: mark[pq] = rnd
print(f"round {rnd}:", *(f"{p}{q}" for p, q in new))
return [pq for pq in pairs if pq not in mark]
Q = reachable(START)
print("reachable:", *Q, "| removed:", *sorted({p for p, _ in delta} - set(Q)))
print("never marked (equivalent):", table_fill(Q))আসল আউটপুট (ব্রাউজারের Python):
reachable: q0 q1 q2 q3 q4 q5 | removed: q6
round 0: q0q1 q0q2 q0q3 q0q4 q0q5
round 1: q1q3 q2q3 q3q4 q3q5
round 2: q1q2 q1q5 q2q4 q4q5
never marked (equivalent): [('q1', 'q4'), ('q2', 'q5')]
প্রতিটি লাইন stepper-এর একটি ধাপ আর টেবিলের একটি রাউন্ড। জোড়া রাখা হয় BFS-এর ক্রমে (q0 < q1 < …), আর sorted পরের জোড়াটিকেও একই ক্রমে আনে, যাতে (q3, q1) আর (q1, q3) একই চাবি হয়। এক state-এ যাওয়া জোড়া, যেমন (q2, q2), টেবিলে নেই, তাই কখনো “চিহ্নিত” পাওয়া যায় না; ঠিক এ কারণেই q1q4 আর q2q5 চিহ্নহীন থাকে।
৫ · Moore-এর algorithm — দল ভাঙা রাউন্ডে রাউন্ডে
Table-filling জোড়া ধরে ভাবে; Moore-এর পদ্ধতি দল ধরে। এর পেছনে একটি ধাপে ধাপে সমতুল্যতা।
p ≡k q, যদি |w| ≤ k এমন প্রতিটি w-এর জন্য δ̂(p, w) ∈ F ⇔ δ̂(q, w) ∈ F. তাহলে
p ≡0 q ⇔ (p ∈ F ⇔ q ∈ F), আর
p ≡k+1 q ⇔ p ≡k q এবং প্রতিটি a ∈ Σ-এ δ(p, a) ≡k δ(q, a).
দ্বিতীয় সূত্রের কারণ: দৈর্ঘ্য ≤ k + 1-এর string হয় ε, নয়তো a-র পরে দৈর্ঘ্য ≤ k-এর একটি string. Moore-এর algorithm ঠিক এই সূত্র দিয়ে partition P0, P1, P2, … বানায়: প্রতিটি state-এর একটি “সই” (signature) নিন, অর্থাৎ নিজের দল আর প্রতিটি চিহ্নে পরের state-এর দল; একই সই মানে পরের partition-এ একই দল।
Pk = Pk+1 হলে Pk = Pk+2 = ⋯, আর ≡k = ≡. তাই algorithm বড়জোর n − 2টি কার্যকর রাউন্ড পরে থামে (F আর Q − F দুটিই অশূন্য ধরে)।
প্রমাণ:
- Pk+2 তৈরি হয় Pk+1 থেকে, ঠিক যে নিয়মে Pk+1 তৈরি হয় Pk থেকে। ইনপুট একই হলে ফলও এক, তাই Pk+2 = Pk+1; induction-এ পরেরগুলোও। — সংজ্ঞা ৫.১-এর দ্বিতীয় সূত্র
- p ≡ q ⇔ সব k-তে p ≡k q, কারণ প্রতিটি w-এর কোনো না কোনো দৈর্ঘ্য আছে। সব k-তে ≡k একই, তাই ≡ = ≡k. — সংজ্ঞা
- P0-তে ২টি দল, আর থামার আগে প্রতিটি রাউন্ডে দলের সংখ্যা অন্তত ১ বাড়ে, অথচ n-এর বেশি দল হতে পারে না। তাই কার্যকর রাউন্ড ≤ n − 2. ∎ — প্রতিটি partition আগেরটির refinement
Table-filling-এর রাউন্ড k-তে যে জোড়া চিহ্নিত হয়, Moore-এর রাউন্ড k-তে ঠিক সেই জোড়াগুলো আলাদা দলে যায়: দুটি algorithm একই ≡k গোনে, শুধু লেখার ধরন আলাদা। DIV6-এ দেখুন।
1P0: accepting বনাম বাকি2P0 দিয়ে সই → P13P1 দিয়ে সই → P24P2 দিয়ে সই: বদল নেই
| দল | |
| q1 | |
| q2 | |
| q3 | |
| q4 | |
| q5 |
- P0. ≡0 শুধু দেখে কে accepting: A = {q0}, B = {q1, q2, q3, q4, q5}. এখনো কোনো সই হিসাব হয়নি।
- P0 দিয়ে সই। B-এর প্রতিটি সদস্যের (0-পরের দল, 1-পরের দল): q3-এর (A, B), কারণ 0 পড়লে q0; বাকি চারটির (B, B). সই আলাদা, তাই q3 নতুন দল C. P1-এ ৩টি দল। এটিই table-filling-এর রাউন্ড 1.
- P1 দিয়ে সই। এখন দলের নাম নতুন: B = {q1, q2, q4, q5}, C = {q3}. q1 আর q4-এর 1-পরের state q3 ∈ C, তাই সই (B, C); q2 আর q5-এর (B, B). B ভেঙে {q1, q4} আর {q2, q5}. P2-তে ৪টি দল।
- P2 দিয়ে সই। নাম আবার নতুন: B = {q1, q4}, C = {q2, q5}, D = {q3}. q1 আর q4-এর সই (C, D), q2 আর q5-এর (B, C): প্রতিটি দলের ভেতরে সই এক। কোনো দল ভাঙল না, তাই P3 = P2, আর উপপাদ্য ৫.২ অনুযায়ী থামা।
নিচের ব্লক Moore-এর algorithm চালিয়ে partition ছাপে, তারপর প্রতিটি দলকে একটি state বানিয়ে quotient DFA তৈরি করে, আর দৈর্ঘ্য 10 পর্যন্ত সব string-এ মূল আর ছোট DFA মেলায় (brute force). শেষে পর্ব ০৮-এর “binary মান m দিয়ে বিভাজ্য” DFA-গুলোর minimal আকার।
from itertools import product
def moore(Q, delta, final, sigma, show=True):
block = {q: int(q in final) for q in Q} # P0: accepting or not
for k in range(len(Q)):
if show:
groups = {}
for q in Q: groups.setdefault(block[q], []).append(q)
print(f"P{k}:", " ".join("{" + ",".join(g) + "}" for g in groups.values()))
sig = {q: (block[q],) + tuple(block[delta[q, a]] for a in sigma) for q in Q}
ids = {}
new = {q: ids.setdefault(sig[q], len(ids)) for q in Q}
if len(ids) == len(set(block.values())): return block # stable
block = new
def quotient(Q, delta, start, final, sigma): # one state per block
block = moore(Q, delta, final, sigma, show=False)
return ({(block[q], a): block[delta[q, a]] for q in Q for a in sigma},
block[start], {block[q] for q in final if q in block})
def accepts(d, q, f, w):
for c in w: q = d[q, c]
return q in f
moore(Q, delta, FINAL, SIGMA)
md, ms, mf = quotient(Q, delta, START, FINAL, SIGMA)
print("minimal:", " ".join(f"B{p}-{a}->B{t}" for (p, a), t in sorted(md.items())))
words = ["".join(t) for n in range(11) for t in product(SIGMA, repeat=n)]
bad = sum(accepts(delta, START, FINAL, w) != accepts(md, ms, mf, w) for w in words)
print(f"original vs minimal on {len(words)} strings: {bad} disagreements")
sizes = []
for m in range(2, 13): # binary divisible by m
d = {(r, b): (2 * r + int(b)) % m for r in range(m) for b in "01"}
sizes.append(f"{m}:{len(set(moore(range(m), d, {0}, '01', False).values()))}")
print("binary mod m, minimal size:", *sizes)আসল আউটপুট (ব্রাউজারের Python):
P0: {q0} {q1,q2,q3,q4,q5}
P1: {q0} {q1,q2,q4,q5} {q3}
P2: {q0} {q1,q4} {q2,q5} {q3}
minimal: B0-0->B0 B0-1->B1 B1-0->B2 B1-1->B3 B2-0->B1 B2-1->B2 B3-0->B0 B3-1->B1
original vs minimal on 2047 strings: 0 disagreements
binary mod m, minimal size: 2:2 3:3 4:3 5:5 6:4 7:7 8:4 9:9 10:6 11:11 12:5
Partition তিনটি stepper-এর সঙ্গে মেলে। দলের নম্বর আসে প্রথম দেখার ক্রমে: B0 = {q0}, B1 = {q1, q4}, B2 = {q2, q5}, B3 = {q3}. সই-এ নিজের দলও রাখা হয়েছে, তাই প্রতিটি নতুন partition আগেরটির refinement; দলের সংখ্যা না বাড়লেই থামা। ছোট DFA দৈর্ঘ্য 10 পর্যন্ত সব 2047টি string-এ মূলটির সঙ্গে একমত (q6 এখানে নেই, কারণ Q আগের ব্লকের reachable তালিকা)। শেষ লাইন পর্ব ০৮-এর পর্যবেক্ষণ নিশ্চিত করে: বিজোড় m-এ m-টি state, কিন্তু m = 2k·t (t বিজোড়) হলে t + k, যেমন 6 = 2·3-এ ৪টি, 12 = 4·3-এ ৫টি। মনে রাখবেন, brute force শুধু দৈর্ঘ্য 10 পর্যন্ত দেখে; সব দৈর্ঘ্যের নিশ্চয়তা দেয় উপপাদ্য ৩.৩।
৬ · Minimal DFA জোড়া লাগানো আর তার অনন্যতা
Class পাওয়া গেলে quotient DFA বানানো যান্ত্রিক কাজ: প্রতিটি class একটি state, আর তার transition যেকোনো একজন সদস্যের transition-এর class. Lemma ৩.২ নিশ্চয়তা দেয়, সদস্যরা একমত হবেই; হাতে কাজের সময় এটি একটি চমৎকার নিজস্ব পরীক্ষা।
1class-এর নাম দেওয়া2A-এর transition3B-এর transition4C-এর transition5D-এর transition6শুরু, accepting, যাচাই
| class | |
| সদস্যের তীর | |
| নতুন তীর | |
| সদস্যরা একমত? |
- নাম। চারটি class-এর নাম A = {q0}, B = {q1, q4}, C = {q2, q5}, D = {q3}. নতুন DFA-তে ঠিক চারটি state থাকবে।
- A. q0 থেকে 0-তে q0 ∈ A, 1-এ q1 ∈ B. তাই A→A লেবেল 0, A→B লেবেল 1.
- B. q1 আর q4 দুজনেই 0-তে q2 আর 1-এ q3-এ যায় (2·4 = 8 ≡ 2, 2·4 + 1 = 9 ≡ 3 mod 6). তাই B→C (0), B→D (1); দুই সদস্য একমত, যেমন Lemma ৩.২ বলে।
- C. q2 আর q5 দুজনেই 0-তে q4 ∈ B আর 1-এ q5 ∈ C. তাই C→B (0) আর C-তে নিজের কাছে ফেরা (1).
- D. q3 থেকে 0-তে q0 ∈ A, 1-এ q1 ∈ B. তাই D→A (0), D→B (1).
- শুরু ও accepting. শুরু [q0] = A, accepting class শুধু A. Python ব্লকে দৈর্ঘ্য 10 পর্যন্ত সব 2047টি string-এ মূল DFA আর এই DFA একমত হয়েছে।
DIV6-এর minimal DFA
প্রতিটি বৃত্ত মূল DFA-র একটি class; বৃত্তের পাশে সদস্যদের নাম। A শুরু (বাঁয়ের তীর) আর একমাত্র accepting (দুই দাগের বৃত্ত)।
কেন q1 ≡ q4? কমপক্ষে একটি চিহ্ন পড়লে মান হয় r·2|w| + val(w), আর r ও r + 3-এর পার্থক্য 3·2|w|, যা |w| ≥ 1 হলে ৬-এর গুণিতক। তাই অন্তত একটি চিহ্নের পর r আর r + 3 একই ভাগশেষে যায়; আর ε-এ দুটিই বাতিল। শুধু q0 আর q3-এর ক্ষেত্রে ε নিজেই পার্থক্য করে। এভাবেই “৩ দিয়ে ভাগশেষ” আর “এখনই কি ৬-এর গুণিতক” মিলে চারটি অবস্থা।
এখন সবচেয়ে গুরুত্বপূর্ণ প্রশ্ন: পাওয়া DFA কি সত্যিই সবচেয়ে ছোট, আর অন্য পথে minimise করলে কি অন্য কোনো DFA আসতে পারে? উত্তর দেয় এই উপপাদ্য। এর পেছনের তত্ত্ব পর্ব ১৮-এর Myhill–Nerode theorem: minimal DFA-র state-সংখ্যা ≡L-এর class-সংখ্যার সমান। এখানে সরাসরি একটি স্বয়ংসম্পূর্ণ প্রমাণ দেওয়া হলো।
M একটি DFA, আর M′ = M-এর reachable অংশের quotient. তাহলে (ক) L(M)-এর কোনো DFA-তে M′-এর চেয়ে কম state নেই; (খ) L(M)-এর যেকোনো DFA N, যার state-সংখ্যা M′-এর সমান, M′-এর সঙ্গে isomorphic, অর্থাৎ শুধু state-এর নাম আলাদা।
প্রমাণ:
- M′-এর প্রতিটি state reachable, আর যেকোনো দুটি ভিন্ন state distinguishable. — reachable অংশ নেওয়া হয়েছে; ভিন্ন class মানে অসমতুল্য
- M′-এর state k-টি হলে প্রতিটি state si-এর জন্য একটি string xi নিন, যা শুরু থেকে si-এ নেয়। i ≠ j হলে si, sj-এর witness z আছে, তাই xiz আর xjz-এর ঠিক একটি L-এ। — ধাপ ১
- (ক) L-এর একটি DFA N-এ k-এর কম state থাকলে, pigeonhole অনুযায়ী দুটি xi, xj N-এর একই state-এ পৌঁছায়; তখন xiz আর xjz-ও N-এ একই state-এ থামে, অথচ ঠিক একটি L-এ। বিরোধ। — DFA deterministic
- (খ) এখন N-এ ঠিক k-টি state. ধাপ ৩-এর যুক্তিতে x1, …, xk N-এর k-টি ভিন্ন state-এ যায়, তাই N-এর প্রতিটি state কোনো xi-এর গন্তব্য। f(si) = δ̂N(শুরু, xi) সংজ্ঞায়িত করুন; এটি bijection. — k-টি ভিন্ন মান, k-টি state
- N-এর দুটি ভিন্ন state সমতুল্য হতে পারে না: হলে তাদের জোড়া লাগিয়ে L-এর k-এর কম state-এর DFA পাওয়া যেত, যা (ক)-এর বিরোধী। — উপপাদ্য ৩.৩
- f transition মানে: δ′(si, a) = sj হলে xia আর xj M′-এ একই state-এ যায়, তাই প্রতিটি z-এ xiaz ∈ L ⇔ xjz ∈ L. ফলে N-এ xia আর xj-এর গন্তব্য state দুটি সমতুল্য, আর আগের ধাপ অনুযায়ী একই state: δN(f(si), a) = f(sj). — δ̂N(শুরু, xia) = δN(f(si), a)
- f শুরুকে শুরুতে নেয় (x = ε-এর গন্তব্য), আর si accepting ⇔ xi ∈ L ⇔ f(si) accepting. তাই f একটি isomorphism. ∎
ফলাফলটির ব্যবহারিক রূপ: যেকোনো algorithm (table-filling, Moore, Hopcroft) সঠিকভাবে চালালে একই DFA আসে, শুধু নাম আলাদা হতে পারে। আর minimality-র একটি সহজ প্রমাণপত্র আছে: প্রতিটি state reachable, আর প্রতিটি জোড়ার একটি witness. নিচের JavaScript ব্লক DIV6-এর সব জোড়ার সবচেয়ে ছোট witness খোঁজে, জোড়া-graph-এ BFS চালিয়ে: (p, q) থেকে একটি চিহ্ন পড়লে (δ(p, a), δ(q, a))-তে যাওয়া, যতক্ষণ না ঠিক একটি accepting হয়।
// Shortest distinguishing suffix for every pair of states (BFS over pairs).
const n = 6, SIGMA = ["0", "1"];
const delta = (r, b) => (2 * r + Number(b)) % n; // DIV6: remainder
const accept = r => r === 0;
function witness(p, q) { // shortest w with exactly one accepting
const seen = new Set([p + "," + q]);
const queue = [[p, q, ""]];
for (const [x, y, w] of queue) { // queue grows while we walk it = BFS
if (accept(x) !== accept(y)) return w === "" ? "ε" : w;
for (const b of SIGMA) {
const nx = delta(x, b), ny = delta(y, b), key = nx + "," + ny;
if (!seen.has(key)) { seen.add(key); queue.push([nx, ny, w + b]); }
}
}
return null; // no suffix separates them: equivalent
}
const rows = [];
for (let p = 0; p < n; p++)
for (let q = p + 1; q < n; q++) {
const w = witness(p, q);
rows.push(`q${p},q${q}: ${w === null ? "EQUIVALENT" : w}`);
}
for (let i = 0; i < rows.length; i += 3) console.log(rows.slice(i, i + 3).join(" "));
// An "AI answer" claims q2 and q4 can be merged. Check the claim:
const w = witness(2, 4);
const run = (r, s) => [...s].reduce(delta, r);
console.log(`claim q2 = q4? suffix ${w}: q2 -> q${run(2, w)}, q4 -> q${run(4, w)}`);আসল আউটপুট (ব্রাউজারের JavaScript):
q0,q1: ε q0,q2: ε q0,q3: ε
q0,q4: ε q0,q5: ε q1,q2: 10
q1,q3: 0 q1,q4: EQUIVALENT q1,q5: 10
q2,q3: 0 q2,q4: 10 q2,q5: EQUIVALENT
q3,q4: 0 q3,q5: 0 q4,q5: 10
claim q2 = q4? suffix 10: q2 -> q4, q4 -> q0
প্রতিটি witness-এর দৈর্ঘ্য টেবিলের রাউন্ড নম্বরের সমান (ε ↔ 0, “0” ↔ 1, “10” ↔ 2), ঠিক যেমন উপপাদ্য ৪.২ বলে। জোড়া-graph-এ বড়জোর ৩৬টি node, তাই BFS সসীম সময়ে থামে; কোনো accepting-অমিল জোড়ায় না পৌঁছালে উত্তর “EQUIVALENT”, আর এটি সব দৈর্ঘ্যের জন্য প্রমাণ, শুধু ছোট দৈর্ঘ্যের পরীক্ষা নয়। শেষ লাইন একটি ভুল দাবি খণ্ডন করে: q2 থেকে 10 পড়লে q4-এ (বাতিল), q4 থেকে q0-তে (গৃহীত)। Minimal DFA-র A, B, C, D-এর প্রতিনিধি q0, q1, q2, q3-এর ছয়টি জোড়ার প্রতিটির witness উপরে আছে, তাই ৪টির কম state অসম্ভব।
৭ · Hopcroft-এর algorithm — “ছোট অর্ধেক” নীতি
Moore-এর প্রতিটি রাউন্ড সব state ঘুরে দেখে, আর রাউন্ড n − 2টি পর্যন্ত লাগতে পারে, তাই সবচেয়ে খারাপে O(n2|Σ|). John Hopcroft ১৯৭১ সালে প্রকাশিত একটি প্রবন্ধে দেখান, দিক বদলে ভাবলে কাজ অনেক কমে। প্রশ্ন “এই state-এর সই কী” না করে প্রশ্ন করুন: “কোন state-গুলো a পড়ে দল A-তে ঢোকে?” এই সেট X = δ−1(A, a) প্রতিটি দল Y-কে দুই ভাগে কাটতে পারে, Y ∩ X আর Y − X. দল A-কে তখন বলা হয় splitter.
P ← {F, Q − F}; অপেক্ষার তালিকা W ← {F ও Q − F-এর ছোটটি}.
W ফাঁকা না হওয়া পর্যন্ত: W থেকে একটি A তুলুন; প্রতিটি a ∈ Σ-এ X = {q : δ(q, a) ∈ A}; প্রতিটি দল Y, যাকে X কাটে (Y ∩ X আর Y − X দুটিই অশূন্য):
• P-তে Y-এর জায়গায় Y ∩ X আর Y − X বসান;
• Y আগে থেকে W-তে থাকলে তার জায়গায় দুটি ভাগই রাখুন; না থাকলে শুধু ছোট ভাগটি W-তে দিন।
শেষ নিয়মটিই চাবি। কেন বড় ভাগ বাদ দেওয়া নিরাপদ? Y ইতিমধ্যে splitter হিসেবে ব্যবহার হয়ে থাকলে (বা পুরো Y-এর তথ্য আগেই কাজে লেগে থাকলে), Y দিয়ে কাটা আর ছোট ভাগ দিয়ে কাটা মিলে বড় ভাগ দিয়ে কাটার ফল এমনিই চলে আসে: একটি state “Y-তে ঢোকে কিন্তু ছোট ভাগে নয়” মানে “বড় ভাগে ঢোকে”। আর খরচের হিসাব: একটি state যতবার কোনো splitter-এর ভেতরে থাকে, প্রতিবার তার দলের আকার অন্তত অর্ধেক হয়েছে, তাই প্রতিটি state বড়জোর প্রায় log2 n বার splitter-এ আসে। ঠিকমতো data structure (প্রতিটি চিহ্নের উল্টো transition-এর তালিকা, দলের সদস্যদের দ্রুত সরানোর ব্যবস্থা) দিয়ে মোট সময় O(|Σ| n log n).
1P = {F, Q − F}, W = {F}2splitter {q0}3splitter {q3}4splitter {q1,q4}: থামা
| X (a = 0) | |
| X (a = 1) | |
| P | |
| W |
- শুরু। F = {q0} আর Q − F = {q1, …, q5}; ছোটটি {q0}, তাই W = {{q0}}. বড় দলটি splitter হিসেবে কখনো লাগবে না।
- Splitter {q0}. 0 পড়ে q0-তে ঢোকে q0 আর q3, তাই X = {q0, q3}; এটি {q1, …, q5}-কে কেটে {q3} আর {q1, q2, q4, q5} করে। কাটা দলটি W-তে ছিল না, তাই শুধু ছোট ভাগ {q3} W-তে। 1 পড়ে কেউ q0-তে ঢোকে না (2r + 1 বিজোড়), X = ∅.
- Splitter {q3}. 0 পড়ে কেউ q3-এ ঢোকে না (2r জোড়)। 1 পড়ে ঢোকে q1 আর q4 (2·1 + 1 = 3, 2·4 + 1 = 9 ≡ 3). X = {q1, q4} কেটে দেয় {q1, q2, q4, q5}-কে। দুই ভাগ সমান আকারের, তাই যেকোনো একটি, এখানে {q1, q4}, W-তে।
- Splitter {q1, q4}. 0-তে X = {q2, q5}, যা নিজেই একটি পুরো দল, তাই কাটে না; 1-এ X = {q0, q3}, যা {q0} আর {q3} দুটিকেই পুরো ধারণ করে। W ফাঁকা, থামা। মাত্র তিনটি splitter, আকার ১ + ১ + ২ = ৪, আর ফল Moore আর table-filling-এর মতোই ৪টি দল।
নিচের ব্লকে algorithm ৭.১-এর একটি সরল রূপ (X খুঁজতে এটি সব state ঘোরে, তাই আসল O(n log n) গতি দেয় না; গঠন দেখানোই লক্ষ্য)। ব্লকটি তিনটি কাজ করে: DIV6-এ চালানো, স্থির seed-এর ৩০০টি দৈব DFA-তে Moore-এর সঙ্গে মেলানো, আর একটি “শিকল” DFA-তে দুই algorithm-এর কাজের পরিমাণ তুলনা। শিকলে q0 → q1 → ⋯ → qn−1, যেকোনো চিহ্নে এক ধাপ এগোয়, শেষ state accepting আর সেখানেই থাকে; এর language “দৈর্ঘ্য অন্তত n − 1”.
import random
def hopcroft(Q, delta, final, sigma):
P = [set(final), set(Q) - set(final)]
P = [B for B in P if B]
W = [min(P, key=len)] # splitters still to use
pops = 0
while W:
A = W.pop(); pops += len(A)
for a in sigma:
X = {q for q in Q if delta[q, a] in A} # states that enter A on a
for Y in [B for B in P if B & X and B - X]:
P.remove(Y); P += [Y & X, Y - X]
if Y in W: W.remove(Y); W += [Y & X, Y - X]
else: W.append(min(Y & X, Y - X, key=len)) # smaller half
return P, pops
P, pops = hopcroft(Q, delta, FINAL, SIGMA)
print("DIV6 by Hopcroft:", sorted(sorted(B) for B in P), "| splitter sizes summed:", pops)
rng = random.Random(19) # fixed seed
same = 0
for trial in range(300): # random complete DFAs
n = rng.randint(2, 25)
d = {(q, a): rng.randrange(n) for q in range(n) for a in "ab"}
f = {q for q in range(n) if rng.random() < 0.4}
same += len(hopcroft(range(n), d, f, "ab")[0]) == len(set(moore(range(n), d, f, "ab", False).values()))
print("random DFAs where Hopcroft and Moore agree:", same, "of 300")
for n in (5, 10, 20, 40): # chain q0 -> q1 -> ... -> q(n-1)
d = {(q, a): min(q + 1, n - 1) for q in range(n) for a in "ab"}
blk, rounds = {q: int(q == n - 1) for q in range(n)}, 0
while len(set((blk[q], blk[d[q, "a"]]) for q in range(n))) > len(set(blk.values())):
ids = {}; blk = {q: ids.setdefault((blk[q], blk[d[q, "a"]]), len(ids)) for q in range(n)}; rounds += 1
print(f"chain n={n}: Moore rounds {rounds}, Moore work {rounds * n}, Hopcroft work {hopcroft(range(n), d, {n - 1}, 'ab')[1]}")আসল আউটপুট (ব্রাউজারের Python):
DIV6 by Hopcroft: [['q0'], ['q1', 'q4'], ['q2', 'q5'], ['q3']] | splitter sizes summed: 4
random DFAs where Hopcroft and Moore agree: 300 of 300
chain n=5: Moore rounds 3, Moore work 15, Hopcroft work 4
chain n=10: Moore rounds 8, Moore work 80, Hopcroft work 9
chain n=20: Moore rounds 18, Moore work 360, Hopcroft work 19
chain n=40: Moore rounds 38, Moore work 1520, Hopcroft work 39
DIV6-এ ফল আর “৪” সংখ্যাটি stepper-এর সঙ্গে মেলে। ৩০০টি দৈব DFA-র (২ থেকে ২৫ state, অনেকগুলোতে unreachable state-ও আছে) প্রতিটিতে দুই algorithm-এর দলের সংখ্যা এক, যা প্রত্যাশিত, কারণ দুটিই ≡ গোনে। শিকলে Moore-এর রাউন্ড ঠিক n − 2 (উপপাদ্য ৫.২-এর সীমা আঁটসাঁট), আর প্রতি রাউন্ডে n-টি state দেখা মানে কাজ বাড়ে প্রায় n2 হারে: n = 40-এ ১৫২০. Hopcroft-এর splitter-গুলোর আকারের যোগফল মাত্র n − 1, কারণ প্রতিবার একটিমাত্র state ভেঙে বেরোয় আর ছোট ভাগটিই splitter হয়। এখানে “work” একটি সরল মাপ, প্রকৃত সময় নয়।
State কমানোর ধারণা এসেছে switching circuit-এর জগৎ থেকে। David Huffman-এর ১৯৫৪ সালের sequential circuit-এর কাজে আর Edward Moore-এর ১৯৫৬ সালের “Gedanken-experiments on Sequential Machines” প্রবন্ধে (Automata Studies সংকলনে) পার্থক্যযোগ্য state আর ধাপে ধাপে refinement-এর ধারণা পাওয়া যায়; তাই রাউন্ড-ভিত্তিক algorithm-টি সাধারণত Moore-এর নামে পরিচিত। Myhill (১৯৫৭) আর Nerode (১৯৫৮) language-এর দিক থেকে একই কাঠামো দেখান। Hopcroft-এর “An n log n algorithm for minimizing states in a finite automaton” ১৯৭১ সালে একটি সম্পাদিত সংকলনে (Theory of Machines and Computations) প্রকাশিত হয় বলে জানা যায়; মূল লেখাটি বোঝা কঠিন বলে পরে David Gries (১৯৭৩) সহ কয়েকজন এর পরিষ্কার ব্যাখ্যা দেন।
৮ · সত্যিকারের run — automata-lib-এর minify()
নিজের কোডের ফল একটি স্বাধীন library-তে মেলানো দরকার। automata-lib (MIT licence) Python-এর একটি automata library; এর DFA.minify() আগে unreachable state সরায়, তারপর Hopcroft-এর algorithm দিয়ে সমতুল্য state জোড়া লাগায় (library-র নিজের কোডে তাই লেখা, আর scratch-এ কোডটি পড়ে দেখা হয়েছে; ছোট ভাগ W-তে দেওয়ার নিয়মটিও সেখানে আছে)। Library-তে কোনো network বা usage-reporting অংশ নেই (scratch-এ খুঁজে দেখা হয়েছে)। Script-টি ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে চালানো হয়েছে: automata-lib 9.2.0, Python 3.12. চারটি পরীক্ষা: DIV6 (q6 সহ), mod-m DFA-গুলো, বাজারঘরের অর্ডার কোড BG-dddd (alphabet {B, G, -, d}, d মানে যেকোনো অঙ্ক), আর “ab দিয়ে শেষ”-এর দুটি ভিন্ন DFA.
from importlib.metadata import version
from automata.fa.dfa import DFA
print("automata-lib", version("automata-lib"))
def canon(m): # rename states in BFS order: q0, q1, ...
names, queue = {m.initial_state: "q0"}, [m.initial_state]
for p in queue:
for a in sorted(m.input_symbols):
t = m.transitions[p].get(a)
if t is not None and t not in names:
names[t] = f"q{len(names)}"; queue.append(t)
return sorted((names[p], a, names[t]) for p in names
for a, t in m.transitions[p].items()), sorted(names[f] for f in m.final_states & names.keys())
# DIV6 plus a leftover unreachable state q6
t = {f"q{r}": {b: f"q{(2 * r + int(b)) % 6}" for b in "01"} for r in range(6)}
t["q6"] = {"0": "q0", "1": "q6"}
div6 = DFA(states=set(t), input_symbols={"0", "1"}, transitions=t,
initial_state="q0", final_states={"q0"})
m = div6.minify(retain_names=True)
print("DIV6:", len(div6.states), "->", len(m.states), "states, same language:", m == div6)
print(" classes:", sorted(sorted(s) for s in m.states))
print("binary mod m, states after minify:")
row = []
for k in range(2, 13):
t = {r: {b: (2 * r + int(b)) % k for b in "01"} for r in range(k)}
row.append(f"{k}:{len(DFA(states=set(t), input_symbols={'0', '1'}, transitions=t, initial_state=0, final_states={0}).minify().states)}")
print(" ", " ".join(row))
# order code BG-dddd over {B, G, -, d}: partial (8 states) and complete (+ dead)
t = {"q0": {"B": "q1"}, "q1": {"G": "q2"}, "q2": {"-": "q3"}, "q3": {"d": "q4"},
"q4": {"d": "q5"}, "q5": {"d": "q6"}, "q6": {"d": "q7"}, "q7": {}}
code = DFA(states=set(t), input_symbols={"B", "G", "-", "d"}, transitions=t,
initial_state="q0", final_states={"q7"}, allow_partial=True)
full = {q: {a: t[q].get(a, "qd") for a in "BG-d"} for q in t} | {"qd": {a: "qd" for a in "BG-d"}}
code_c = DFA(states=set(full), input_symbols={"B", "G", "-", "d"}, transitions=full,
initial_state="q0", final_states={"q7"})
print("order code: partial", len(code.states), "->", len(code.minify().states),
"| complete", len(code_c.states), "->", len(code_c.minify().states))
# two different DFAs for "ends with ab": do their minimal forms coincide?
a3 = DFA(states={"x", "y", "z"}, input_symbols={"a", "b"},
transitions={"x": {"a": "y", "b": "x"}, "y": {"a": "y", "b": "z"}, "z": {"a": "y", "b": "x"}},
initial_state="x", final_states={"z"})
t = {"s": {"a": "A1", "b": "B1"}, "A1": {"a": "A2", "b": "F"}, "A2": {"a": "A1", "b": "F"},
"B1": {"a": "A2", "b": "B2"}, "B2": {"a": "A1", "b": "B1"}, "F": {"a": "A1", "b": "B2"}}
a6 = DFA(states=set(t), input_symbols={"a", "b"}, transitions=t, initial_state="s", final_states={"F"})
print("ends-with-ab: sizes", len(a3.states), len(a6.states), "->",
len(a3.minify().states), len(a6.minify().states))
print(" identical after BFS renaming:", canon(a3.minify()) == canon(a6.minify()))
print(" minimal:", canon(a6.minify()))সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12):
~/bazarghar-toc$ uv run python minify_run.py
automata-lib 9.2.0
DIV6: 7 -> 4 states, same language: True
classes: [['q0'], ['q1', 'q4'], ['q2', 'q5'], ['q3']]
binary mod m, states after minify:
2:2 3:3 4:3 5:5 6:4 7:7 8:4 9:9 10:6 11:11 12:5
order code: partial 8 -> 8 | complete 9 -> 9
ends-with-ab: sizes 3 6 -> 3 3
identical after BFS renaming: True
minimal: ([('q0', 'a', 'q1'), ('q0', 'b', 'q0'), ('q1', 'a', 'q1'), ('q1', 'b', 'q2'), ('q2', 'a', 'q1'), ('q2', 'b', 'q0')], ['q2'])
DIV6-এ library-র class হুবহু আমাদের চারটি, আর m == div6 (library-র language-সমতা পরীক্ষা) True. Mod-m-এর সারি আমাদের Moore ব্লকের সারির সঙ্গে প্রতিটি m-এ মেলে। অর্ডার কোডের DFA আগে থেকেই minimal: partial রূপে ৮টি, dead state সহ complete রূপে ৯টি, আর minify কিছুই কমায়নি; উপপাদ্য ৬.১-এর প্রমাণপত্রও সহজ (অনুশীলন ৪)। লক্ষ করুন, library partial DFA-কে partial রেখেই গোনে, তাই “কয়টি state” প্রশ্নে dead state গোনা হচ্ছে কি না সবসময় জানিয়ে দিন। শেষ পরীক্ষাটি অনন্যতার উপপাদ্য চোখে দেখায়: ৩-state আর ৬-state দুটি ভিন্ন DFA minimise করে, state-গুলোকে BFS ক্রমে q0, q1, q2 নাম দিলে দুটি হুবহু একই transition-তালিকা।
আরও গভীরে: Hopcroft-এর O(n log n) সীমা আঁটসাঁট: কিছু বিশেষ DFA-পরিবারে (যেমন Berstel আর Carton-এর ২০০৪ সালের দিকের কাজে) algorithm-টি সত্যিই প্রায় n log n কাজ করে বলে দেখানো হয়েছে। আরেকটি সুন্দর পদ্ধতি Brzozowski-এর algorithm (১৯৬০-এর দশকের শুরু): automaton উল্টে subset construction (পর্ব ১০), আবার উল্টে আবার subset construction; ফল সরাসরি minimal DFA, যদিও মাঝে ঘাতের হারে বড় হতে পারে। NFA-র ক্ষেত্রে ছবিটি একেবারে আলাদা: একই language-এর একাধিক অ-isomorphic minimal NFA থাকতে পারে, আর NFA minimisation (ইনপুট DFA হলেও) PSPACE-complete, যা Jiang আর Ravikumar ১৯৯৩ সালে প্রমাণ করেন; তাই এর দ্রুত algorithm থাকলে P = PSPACE হতো, যা অজানা (পর্ব ৬৫)। একই partition refinement ধারণা model checking-এ bisimulation দিয়ে state space ছোট করতেও ব্যবহার হয় (Paige আর Tarjan, ১৯৮৭)।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Table-filling দিয়ে একটি DFA minimise করুন। আগে unreachable state বাদ, তারপর সিঁড়ি-টেবিল, প্রতিটি রাউন্ডের চিহ্ন, শেষে class আর নতুন transition table.
- দুটি state কখন সমতুল্য? সব w-এ δ̂(p, w) ∈ F ⇔ δ̂(q, w) ∈ F; একটি witness পেলেই অসমতুল্য।
- Minimise করার আগে unreachable state কেন সরাতে হয়? সেগুলো অন্য কারও সমতুল্য না হলে আলাদা class হয়ে থেকে যায়, আর ফল minimal হয় না।
- Hopcroft-এর algorithm-এর জটিলতা কত, আর কেন? O(|Σ| n log n); ভাঙা দলের ছোট অর্ধেকই splitter হয়, তাই প্রতিটি state বড়জোর প্রায় log n বার।
- Minimal DFA কি অনন্য? হ্যাঁ, state-এর নাম বাদ দিলে; minimal NFA অনন্য নয়।
৯ · AI-এর যুগে DFA minimization
AI assistant-কে একটি DFA দিয়ে minimise করতে বললে উত্তর প্রায়ই আত্মবিশ্বাসী আর ছোট হয়। কিন্তু ছোট হওয়া মানে সঠিক হওয়া নয়: ভুলভাবে দুটি state জোড়া লাগালে DFA ছোট হয়, আর language বদলে যায়। এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| শুধু “দেখতে একই রকম” বলে state জোড়া লাগানো, যেমন DIV6-এর q2 আর q4 | প্রতিটি জোড়ার witness খোঁজা: q2-q4-এর witness 10 |
| Unreachable state না সরানো, ফলে ৪-এর বদলে ৫টি state | আগে BFS; প্রতিটি state-এ পৌঁছানোর একটি string লিখে রাখা |
| Partial DFA-তে dead state ছাড়া কাজ করা, বা state গোনায় dead state নিয়ে অস্পষ্টতা | আগে complete করা, আর উত্তরে বলে দেওয়া dead state গোনা হলো কি না |
| Table-filling-এ এক রাউন্ডে থেমে যাওয়া, পরের রাউন্ডের চিহ্ন বাদ | যতক্ষণ নতুন চিহ্ন পড়ে ততক্ষণ চালানো; শেষ রাউন্ডে “নতুন নেই” দেখানো |
| “Minimal NFA-ও একই পদ্ধতিতে পাওয়া যায়” বা “minimal NFA অনন্য” দাবি | মনে রাখা: NFA minimisation PSPACE-complete, উত্তর অনন্য নয় |
| জটিলতা বা সাল ভুল, যেমন Hopcroft-কে O(n2) বলা বা বানানো রেফারেন্স | Hopcroft–Motwani–Ullman বা Sipser-এ নিজে খুঁজে দেখা |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু ছোট DFA নয়, প্রতিটি ধাপ, প্রতিটি জোড়ার witness আর একটি স্বাধীন যাচাইয়ের কোড চাওয়া, তারপর সেটি নিজে চালানো।
(নিজে যাচাই করুন: অনুশীলন ১-এ এই DFA-র পুরো হিসাব আছে। সঠিক উত্তরে ৩টি state, আর language “ab দিয়ে শেষ”; উপরের automata-lib run-ও একই কথা বলে।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Minimal DFA অনন্য আর দ্রুত পাওয়া যায়, অথচ minimal NFA অনন্য নয় আর খোঁজা PSPACE-complete. একই ধরনের যন্ত্রে এত বড় পার্থক্য কেন?
DFA-তে একটি string পড়ার পর যন্ত্র ঠিক একটি state-এ থাকে। তাই প্রতিটি state-কে একটি সুনির্দিষ্ট “ভবিষ্যৎ” দিয়ে চেনা যায়: সেখান থেকে কোন suffix গৃহীত হবে তার সেট। দুটি state-এর ভবিষ্যৎ এক হলে তারা সমতুল্য, আর minimal DFA মানে ঠিক প্রতিটি ভিন্ন ভবিষ্যতের জন্য একটি state. এই ভবিষ্যৎগুলো language-এরই বৈশিষ্ট্য (Myhill–Nerode-এর class), যন্ত্রের নয়। তাই উত্তর অনন্য, আর partition refinement দিয়ে polynomial সময়ে পাওয়া যায়।
NFA-তে একটি string পড়ার পর যন্ত্র একসঙ্গে অনেক state-এ থাকতে পারে, আর গ্রহণ নির্ভর করে পুরো সেটের ওপর। একটি state-এর নিজস্ব ভবিষ্যৎ আছে ঠিকই, কিন্তু language সেটি একার ওপর দাঁড়ায় না; কয়েকটি state-এর ভবিষ্যৎ মিলে কাজ করে। ফলে একই language-কে ভিন্ন ভিন্নভাবে “ভাগ” করে state-এ বসানো যায়, আর একাধিক অ-isomorphic minimal NFA থাকতে পারে। কোন ভাগ সবচেয়ে কম state দেয়, তা খুঁজতে কার্যত অনেক বিকল্প পরীক্ষা করতে হয়।
Tao Jiang আর B. Ravikumar-এর ১৯৯৩ সালের প্রবন্ধ “Minimal NFA Problems Are Hard” (SIAM Journal on Computing) দেখায়, “এই NFA-র সমতুল্য k-state NFA আছে কি?” প্রশ্নটি PSPACE-complete, এমনকি ইনপুট DFA হলেও। কারণের একটি অংশ সহজে বোঝা যায়: দুটি NFA একই language চেনে কি না, সেটিই PSPACE-complete (পর্ব ২০), আর minimisation-এর যেকোনো পদ্ধতিকে অন্তত এমন প্রশ্নের উত্তর জানতে হয়। DFA-র ক্ষেত্রে equivalence সহজ, তাই minimisation-ও সহজ।
বাস্তবে তাই NFA ছোট করতে heuristic ব্যবহার হয়: simulation সম্পর্ক দিয়ে কিছু state মেশানো, বা আগে DFA বানিয়ে minimise করা, যদিও DFA ঘাতের হারে বড় হতে পারে (পর্ব ১০)। বাজারঘরের validator-এর মতো ছোট ক্ষেত্রে DFA minimise করাই সবচেয়ে নিরাপদ পথ।
মূল উপলব্ধি: DFA-র প্রতিটি state language-এর একটি নির্দিষ্ট ভবিষ্যৎ, তাই minimal DFA language-এরই একটি ছবি এবং অনন্য। NFA-তে state-গুলো দল বেঁধে কাজ করে, তাই সবচেয়ে ছোট দল খোঁজা কঠিন আর উত্তর অনন্য নয়।
প্র ০২Hopcroft-এর “ছোট অর্ধেক” নীতি কেন log n দেয়? দৈনন্দিন কোন হিসাবে এমন যুক্তি দেখা যায়?
একটি state q-কে অনুসরণ করুন। Hopcroft-এর algorithm-এ খরচ হয় যখন q কোনো splitter A-র সদস্য: তখন q-এ ঢোকা তীরগুলো দেখা হয়। প্রশ্ন হলো, q কতবার splitter-এর সদস্য হতে পারে? প্রথমবার q যে splitter-এ থাকে, তার আকার বড়জোর n. পরেরবার q আবার W-তে আসে কেবল যদি q-এর দল ভেঙে ছোট ভাগে পড়ে, আর ছোট ভাগের আকার আগের দলের অর্ধেক বা কম। প্রতিবার আকার অন্তত অর্ধেক হয়, আর আকার ১-এর নিচে নামে না, তাই q বড়জোর প্রায় log2 n বার splitter-এ থাকে।
প্রতিবার q-এর জন্য খরচ q-তে ঢোকা তীরের সংখ্যা, আর সব state মিলিয়ে ঢোকা তীর মোট n|Σ|. তাই মোট খরচ O(|Σ| n log n). এতে লাগে উপযুক্ত data structure: প্রতিটি চিহ্নের উল্টো transition-এর তালিকা, আর দল থেকে সদস্য সরানো ও দল ভাঙা ধ্রুবক সময়ে করার ব্যবস্থা। Hopcroft-এর ১৯৭১ সালের প্রবন্ধে বিশ্লেষণটি থাকলেও লেখাটি কঠিন বলে পরিচিত, আর পরে Gries (১৯৭৩) ও আরও পরে Knuutila (২০০১)-এর মতো লেখকরা এর পরিষ্কার পুনর্ব্যাখ্যা দেন।
একই যুক্তি DSA-তে পরিচিত। DSA কোর্সের পর্ব ৩৩-এর union-find-এ “ছোট দলকে বড় দলের সঙ্গে জোড়া” (union by size) নিয়মে প্রতিটি উপাদানের দল বদলালে দলের আকার অন্তত দ্বিগুণ হয়, তাই একটি উপাদান বড়জোর log n বার সরে। Merge sort-এর log n স্তরও একই ধাঁচের। Hopcroft-এর যুক্তি এর উল্টো দিক: দল ভাঙার সময় ছোট টুকরোটি ধরে হিসাব।
দৈনন্দিন উদাহরণ হিসেবে একটি পরীক্ষার হলের রোল নম্বর মেলানোর কাজ ভাবুন। একটি বড় দলকে দুই ভাগ করলে আপনি ছোট ভাগের তালিকাটিই হাতে নিয়ে ঘোরেন, কারণ বড় ভাগ মানে “বাকি সবাই”। প্রতিবার হাতে থাকা তালিকা অর্ধেক বা কম, তাই একজন ছাত্রের নাম আপনার হাতের তালিকায় বেশিবার আসে না।
মূল উপলব্ধি: প্রতিবার ভাঙা দলের ছোট ভাগটি নিয়ে কাজ করলে প্রতিটি উপাদান বড়জোর log n বার কাজে আসে; বড় ভাগের তথ্য “বাকিটা” হিসেবে এমনিই পাওয়া যায়।
প্র ০৩Minimization কি শুধু পরীক্ষার অঙ্ক, নাকি বাস্তবের টুলেও এর ব্যবহার আছে? কোথায়, আর কোথায় এটি যথেষ্ট নয়?
ধারণাটির জন্মই প্রকৌশলে। ১৯৫০-এর দশকে Huffman, Mealy আর Moore switching circuit নিয়ে কাজ করছিলেন, যেখানে প্রতিটি state মানে flip-flop আর gate, অর্থাৎ খরচ। কম state মানে ছোট circuit. আজও hardware নকশার টুলে state machine-এর state কমানো একটি পরিচিত ধাপ, যদিও সেখানে output-সহ যন্ত্র (পর্ব ১২-এর Mealy ও Moore) আর অনির্দিষ্ট (don't-care) transition থাকায় সমস্যাটি কখনো কঠিনতর হয়ে যায়।
Software-এ lexer generator আর regex টুল regex থেকে NFA, তারপর DFA বানায় (পর্ব ১৪ ও ১০); subset construction-এর DFA প্রায়ই অপ্রয়োজনীয়ভাবে বড়, আর অনেক টুল টেবিল ছোট রাখতে minimisation বা অনুরূপ কৌশল ব্যবহার করে। এর একটি বড় সুবিধা: minimal DFA অনন্য বলে একে একটি “canonical form” হিসেবে ব্যবহার করা যায়। দুটি validator একই code গ্রহণ করে কি না জানতে দুটিকে minimise করে নাম মিলিয়ে দেখলেই চলে, যেমন অংশ ৮-এ “ab দিয়ে শেষ”-এর দুই DFA. Model checking-এ একই partition refinement ধারণা দিয়ে বিশাল state space-কে bisimulation অনুযায়ী ছোট করা হয়; Paige আর Tarjan-এর ১৯৮৭ সালের কাজ এর একটি ভিত্তি।
কিন্তু minimisation সবকিছুর সমাধান নয়। প্রথমত, এটি শুধু অপ্রয়োজনীয় state সরায়; language নিজেই যদি বড় DFA দাবি করে (যেমন পর্ব ১০-এর “শেষ থেকে n-তম চিহ্ন 1”, যার minimal DFA-তে 2n state), কিছুই করার নেই। দ্বিতীয়ত, বাস্তবের অনেক regex engine DFA-ই বানায় না, backtracking করে (পর্ব ২১)। তৃতীয়ত, বড় DFA-তে minimise করার আগেই subset construction-এর খরচ বেশি হতে পারে; তখন lazy DFA-র মতো কৌশল কাজে আসে।
বাজারঘরের দলের জন্য শিক্ষা: ছোট validator-এ minimise করা সস্তা আর নিরাপদ, আর পরীক্ষার কাজে canonical form হিসেবে চমৎকার। কিন্তু ধীর বা বিশাল automaton-এর মূল কারণ কখনো language-এর গঠন, যা minimisation বদলাতে পারে না।
মূল উপলব্ধি: Minimization circuit, lexer, equivalence পরীক্ষা আর model checking-এ সত্যিকারের কাজের টুল; কিন্তু এটি শুধু বাড়তি অংশ সরায়, language-এর নিজস্ব জটিলতা কমায় না।
প্র ০৪Binary-তে ৬ দিয়ে বিভাজ্যতার DFA-তে ৪টি state লাগে, ৭ দিয়ে বিভাজ্যতায় ৭টি। সংখ্যাতত্ত্ব আর minimization এখানে কীভাবে মেলে?
Horner-এর নিয়মে একটি binary string পড়ার সময় মান বাড়ে v → 2v + b. তাই “ভাগশেষ mod m” রাখলেই চলে, আর m-টি state যথেষ্ট (পর্ব ০৮)। প্রশ্ন হলো কোন ভাগশেষগুলো সমতুল্য। r থেকে w পড়লে নতুন মান r·2|w| + val(w). দুটি ভাগশেষ r আর s-এর পার্থক্য (r − s)·2|w| mod m. গ্রহণের প্রশ্ন শুধু এটি m দিয়ে বিভাজ্য কি না।
m বিজোড় হলে 2 আর m সহমৌলিক, তাই 2|w|-এর গুণ mod m-এ একটি bijection: ভিন্ন ভাগশেষ সবসময় ভিন্ন থাকে, আর কোনো না কোনো w একটিকে 0-তে নেয় কিন্তু অন্যটিকে নয়। তাই সব m-টি state পরস্পর distinguishable, minimal DFA-তে m-টি state. Moore ব্লকের আউটপুটে 3, 5, 7, 9, 11-এ ঠিক তাই।
m = 6 = 2·3-এ ছবিটি আলাদা। |w| ≥ 1 হলে 2|w| জোড়, তাই r আর r + 3-এর পার্থক্য 3·2|w| ৬-এর গুণিতক: অন্তত একটি চিহ্নের পর দুটি একই জায়গায়। শুধু w = ε-এ পার্থক্য হতে পারে, আর সেটি কেবল 0 বনাম 3-এর ক্ষেত্রে। ফলে class {0}, {3}, {1, 4}, {2, 5}. সাধারণভাবে m = 2k·t (t বিজোড়) হলে “শেষ k bit শূন্য কি না” মনে রাখতে k-টি অতিরিক্ত অবস্থা আর বিজোড় অংশের জন্য t-টি ভাগশেষ লাগে, আর গণনায় minimal আকার t + k এসেছে: 4-এ ৩, 8-এ ৪, 12-এ ৫. সাধারণ ভিত্তি আর m-এর জন্য minimal DFA-র আকারের সূত্র Boris Alexeev ২০০৪ সালের দিকে একটি প্রবন্ধে প্রমাণ করেন বলে জানা যায়; এখানে শুধু ছোট m-এ গণনা দেখানো হয়েছে।
এখানে minimization একটি গাণিতিক আবিষ্কারের যন্ত্র হয়ে উঠেছে। হাতে সংখ্যাতত্ত্ব না জেনেও Moore-এর algorithm চালিয়ে আকারের ধাঁচ দেখা যায়, তারপর ধাঁচটি প্রমাণ করা যায়। এই “আগে গণনা, পরে প্রমাণ” পদ্ধতি গণিতে আর তত্ত্বীয় কম্পিউটার বিজ্ঞানে খুব প্রচলিত, আর AI-এর দাবি যাচাইয়েও কাজের।
মূল উপলব্ধি: দুটি ভাগশেষ সমতুল্য কি না, তা ঠিক করে 2 আর m-এর সম্পর্ক; বিজোড় m-এ কেউ মেশে না, m-এ 2-এর ঘাত থাকলে মেশে। Minimization সেই সংখ্যাতত্ত্ব যন্ত্রে দেখিয়ে দেয়।
প্র ০৫দুটি DFA একই language চেনে কি না, তা minimise করে মেলানো যায়, আবার product construction দিয়েও। কোনটি কখন ভালো, আর Hopcroft–Karp-এর পদ্ধতি কী?
প্রথম পথ: দুটি DFA minimise করে isomorphism পরীক্ষা। উপপাদ্য ৬.১ বলে, একই language-এর minimal DFA শুধু নামে আলাদা, তাই শুরু থেকে BFS করে state-গুলোকে একটি নির্দিষ্ট ক্রমে নাম দিলে দুটি transition-তালিকা হুবহু মিলবে, যেমন অংশ ৮-এর canon. সুবিধা: ফলটি একটি canonical form, যা সংরক্ষণ করে পরে আরও অনেক DFA-র সঙ্গে মেলানো যায়; যেমন বাজারঘরের প্রতিটি validator সংস্করণের canonical form রেখে দিলে নতুন সংস্করণ language বদলেছে কি না সঙ্গে সঙ্গে ধরা পড়ে।
দ্বিতীয় পথ: পর্ব ০৮-এর product construction দিয়ে symmetric difference-এর DFA বানিয়ে দেখা, কোনো “একটি গ্রহণ করে, অন্যটি নয়” state reachable কি না (পর্ব ২০)। সুবিধা: উত্তর “না” হলে সঙ্গে একটি witness string পাওয়া যায়, যা বাগ রিপোর্টে সরাসরি লেখা যায়। খরচ দুটি DFA-র state-সংখ্যার গুণফলের অনুপাতে।
তৃতীয় পথটি এই দুইয়ের মাঝামাঝি: Hopcroft আর Richard Karp-এর ১৯৭১ সালের একটি প্রযুক্তিগত প্রতিবেদনে বর্ণিত পদ্ধতি। দুটি শুরুর state সমতুল্য ধরে নিয়ে union-find দিয়ে এক দলে রাখা হয়, তারপর প্রতিটি চিহ্নে পরের state-জোড়াকেও এক দলে টানা হয়; কোনো দলে accepting আর non-accepting একসঙ্গে পড়লেই উত্তর “ভিন্ন”। এটি প্রায় রৈখিক সময়ে চলে, কারণ union-find প্রায় ধ্রুবক সময়ে কাজ করে। অংশ ৮-এর automata-lib-এর == পরীক্ষাও এই ধরনের কৌশল ব্যবহার করে বলে তার কোডের মন্তব্যে উল্লেখ আছে।
কোনটি বাছবেন? একবারের প্রশ্নে, বিশেষ করে বাগ খোঁজায়, product বা Hopcroft–Karp ভালো, কারণ witness আসে আর পুরো minimisation লাগে না। বারবার তুলনা বা সংরক্ষণের কাজে minimal canonical form ভালো। পরীক্ষার খাতায় দুটি পথই গ্রহণযোগ্য, শুধু কারণ লিখতে হবে: অনন্যতার উপপাদ্য, অথবা symmetric difference ফাঁকা।
মূল উপলব্ধি: Minimal DFA-র অনন্যতা equivalence-কে isomorphism পরীক্ষায় নামিয়ে আনে; product আর Hopcroft–Karp একই প্রশ্নের উত্তর দেয় witness-সহ, আর প্রায়ই কম খরচে।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। নিজের DFA table_fill.py বা moore.py ব্লকে বসিয়ে যাচাই করতে পারেন।
-
নির্মাণ (table-filling): Σ = {a, b}-এর DFA: s (শুরু) a → A1, b → B1; A1: a → A2, b → F; A2: a → A1, b → F; B1: a → A2, b → B2; B2: a → A1, b → B1; F (accepting): a → A1, b → B2. Table-filling দিয়ে minimise করুন, minimal DFA-র transition table দিন, আর language-টি বলুন।
সব state reachable (s থেকে A1, B1; সেখান থেকে A2, F, B2). ১৫টি জোড়া।
- রাউন্ড 0: F-যুক্ত ৫টি জোড়া (sF, A1F, A2F, B1F, B2F), witness ε. — শুধু F accepting
- রাউন্ড 1: b পড়লে A1 আর A2 যায় F-এ, বাকিরা নয়। তাই sA1, sA2, A1B1, A1B2, A2B1, A2B2 চিহ্নিত, witness “b”. — b-পরের জোড়ায় F আছে
- রাউন্ড 2: চিহ্নহীন sB1, sB2, B1B2 (তিনজনই a-তে A1 বা A2, b-তে B1 বা B2) আর A1A2 (a-তে A2/A1, b-তে F/F). এদের পরের জোড়াগুলোও চিহ্নহীন, তাই নতুন চিহ্ন নেই, থামা। ∎
Class: X = {s, B1, B2}, Y = {A1, A2}, Z = {F}. Transition: X: a → Y, b → X; Y: a → Y, b → Z; Z: a → Y, b → X. শুরু X, accepting Z. Language “ab দিয়ে শেষ”: Y মানে শেষ চিহ্ন a, Z মানে শেষ দুটি ab. Scratch-এ দৈর্ঘ্য 10 পর্যন্ত সব string-এ মূল DFA আর w.endswith("ab") মিলেছে, আর অংশ ৮-এর automata-lib run-এ এই ৬-state DFA-ই ৩-state-এ নেমেছে।
-
প্রমাণ: প্রমাণ করুন: L আর এর complement L̄ = Σ∗ − L-এর minimal (complete) DFA-তে state-সংখ্যা সমান। কোথায় “complete” শর্তটি লাগে?
- L-এর minimal complete DFA M = (Q, Σ, δ, q0, F) নিন, |Q| = k. M̄ = (Q, Σ, δ, q0, Q − F) L̄ চেনে, কারণ δ total বলে প্রতিটি w-এর run ঠিক একটি state-এ শেষ হয়, আর সেটি F-এ না থাকা মানে w ∉ L. — complete শর্ত এখানেই লাগে (পর্ব ০৮)
- তাই L̄-এর minimal DFA-তে বড়জোর k-টি state. — M̄ একটি k-state DFA
- ধরুন L̄-এর k-এর কম state-এর complete DFA N আছে। N-এর accepting আর non-accepting অদলবদল করলে L̄-এর complement, অর্থাৎ L-এর একটি k-এর কম state-এর DFA. — ধাপ ১-এর যুক্তি N-এ
- এটি M-এর minimality-র বিরোধী। তাই L̄-এর minimal DFA-তে ঠিক k-টি state. ∎
Partial DFA-তে শুধু accepting অদলবদল করলে না-থাকা transition-এ পড়া string দুই DFA-তেই বাতিল হয়, তাই ধাপ ১ ভেঙে পড়ে। উদাহরণ: BG-dddd-এর partial ৮-state DFA-র accepting অদলবদল করলে “BB” string-টি মূলেও বাতিল, অদলবদলেও বাতিল, অথচ complement-এ এটি থাকার কথা।
-
হিসাব (Moore): Binary-তে ৪ দিয়ে বিভাজ্যতার DFA: qr থেকে b পড়লে q(2r + b) mod 4, শুরু ও accepting q0. Moore-এর partition P0, P1, … লিখুন। কয়টি রাউন্ড লাগবে আর minimal DFA-তে কয়টি state, আগে অনুমান করুন। q1 আর q2-এর সবচেয়ে ছোট witness কী?
Transition: q0: 0 → q0, 1 → q1; q1: 0 → q2, 1 → q3; q2: 0 → q0, 1 → q1; q3: 0 → q2, 1 → q3.
P0 = {q0} {q1, q2, q3}. P0 দিয়ে সই: q2-এর 0-পরের state q0, তাই (A, B); q1 আর q3-এর (B, B). P1 = {q0} {q2} {q1, q3}. P1 দিয়ে সই: q1 আর q3 দুজনেই 0-তে q2, 1-এ q3-এ যায়, তাই একই সই; কিছু ভাঙে না, P2 = P1. একটি কার্যকর রাউন্ড, minimal DFA-তে ৩টি state: “মান ৪-এর গুণিতক”, “শেষ bit 0 কিন্তু গুণিতক নয়” আর “শেষ bit 1”.
q1 আর q2-এর witness “0”: q1 থেকে q2 (বাতিল), q2 থেকে q0 (গৃহীত)। Scratch-এর table-filling-এ q1q2 রাউন্ড 1-এ চিহ্নিত আর q1q3 কখনো নয়, যা এই হিসাবের সঙ্গে মেলে; Moore ব্লকের আউটপুটে “4:3”.
-
প্রমাণপত্র (minimality): বাজারঘরের অর্ডার কোড BG-dddd-এর complete DFA-তে state q0 … q7 (qi মানে কোডের প্রথম i অক্ষর ঠিকঠাক পড়া হয়েছে) আর dead state qd, মোট ৯টি। উপপাদ্য ৬.১-এর প্রমাণপত্র দিয়ে দেখান যে এটি minimal: প্রতিটি state reachable, আর প্রতিটি জোড়ার একটি witness দিন।
- Reachable: qi-তে পৌঁছায় “BG-dddd”-এর প্রথম i অক্ষর; qd-তে পৌঁছায় যেমন “G”. — প্রতিটির জন্য একটি string
- qi বনাম qj, i < j ≤ 7: qj-এর বাকি অংশ, অর্থাৎ কোডের শেষ 7 − j অক্ষর, qj-কে q7-এ নেয় (গৃহীত)। একই string qi থেকে পড়লে মোট দৈর্ঘ্য 7-এর কম হয়, তাই q7-এ পৌঁছায় না (বাতিল)। — witness: কোডের শেষ 7 − j অক্ষর
- qi বনাম qd: qi-এর বাকি অংশ qi-কে q7-এ নেয়, কিন্তু qd থেকে কোনো string গৃহীত হয় না। — dead state-এর সংজ্ঞা
- সব ৩৬টি জোড়ার witness আছে আর সব state reachable, তাই উপপাদ্য ৬.১ অনুযায়ী ৯টির কম state অসম্ভব। ∎
অংশ ৮-এর automata-lib run-ও “complete 9 -> 9” দেখিয়েছে। Partial রূপে state ৮টি, তাই উত্তর দেওয়ার সময় বলে দিন dead state গোনা হচ্ছে কি না।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি DFA-কে table-filling দিয়ে minimise করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- DFA partial হলে dead state যোগ করে complete করা
- শুরুর state থেকে BFS চালিয়ে unreachable state সরানো
- যে জোড়ায় ঠিক একটি accepting, তা চিহ্নিত করা
- কোনো চিহ্নে চিহ্নিত জোড়ায় যায় এমন জোড়া চিহ্নিত করা, যতক্ষণ নতুন চিহ্ন পড়ে
- চিহ্নহীন জোড়াগুলো থেকে class বানিয়ে প্রতিটি class-কে একটি state করা
- Class-এর transition, শুরু আর accepting state লিখে ফল যাচাই করা
Table-filling algorithm-এর প্রথম রাউন্ডে (রাউন্ড 0) কোন জোড়াগুলো চিহ্নিত হয়?
- যেসব জোড়া কোনো চিহ্নে একই state-এ যায়
- যেসব জোড়ার ঠিক একটি state accepting
- যেসব জোড়ার দুটি state-ই accepting
- যেসব জোড়ার একটি state unreachable
একটি DFA-র table-filling-এ জোড়া {p, q} রাউন্ড 2-তে চিহ্নিত হয়েছে। এ থেকে কী নিশ্চিতভাবে বলা যায়?
- p আর q সমতুল্য
- p আর q-কে দৈর্ঘ্য 1-এর কোনো string আলাদা করে
- p আর q-এর সবচেয়ে ছোট witness-এর দৈর্ঘ্য ঠিক 2
- p আর q-এর ঠিক একটি accepting
একটি DFA-তে একটি unreachable state আছে, যা অন্য কোনো state-এর সমতুল্য নয়। Unreachable state না সরিয়ে শুধু সমতুল্য state জোড়া লাগালে ফল কী হবে?
- একই language, কিন্তু minimal-এর চেয়ে বেশি state
- ভিন্ন language
- ঠিক minimal DFA, কারণ table-filling নিজেই unreachable state সরায়
- Algorithm কখনো থামবে না
Σ = {0, 1}-এর ওপর “binary মান ৬ দিয়ে বিভাজ্য (ε-এর মান 0)” language-এর minimal complete DFA-তে কয়টি state?
- ৬
- ৩
- ২
- ৪
n-state DFA আর alphabet Σ-এর জন্য Hopcroft-এর minimisation algorithm-এর সবচেয়ে খারাপ ক্ষেত্রের সময় কোনটি?
- O(n2|Σ|)
- O(|Σ| n log n)
- O(2n)
- O(n3|Σ|)
একটি regular language-এর minimal DFA সম্পর্কে কোনটি সত্য?
- ভিন্ন algorithm ভিন্ন minimal DFA দিতে পারে
- Minimal NFA-ও একইভাবে অনন্য
- State-এর নাম বাদ দিলে এটি অনন্য
- এর অস্তিত্ব এখনো একটি খোলা প্রশ্ন
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Minimization দুই ধাপ: BFS দিয়ে unreachable state সরানো, তারপর সমতুল্য state (p ≡ q ⇔ সব w-এ একই গ্রহণ-বর্জন) জোড়া লাগানো। আগে DFA complete করুন।
- p ≡ q হলে δ(p, a) ≡ δ(q, a); তাই quotient DFA সুসংজ্ঞায়িত আর একই language চেনে।
- Table-filling: রাউন্ড 0-এ accepting বনাম বাকি, তারপর চিহ্ন পেছনে ছড়ানো; রাউন্ড k-তে চিহ্নিত ⇔ সবচেয়ে ছোট witness-এর দৈর্ঘ্য k.
- Moore একই কাজ দল ভেঙে করে, বড়জোর n − 2টি কার্যকর রাউন্ড; Hopcroft “ছোট অর্ধেক” নীতিতে O(|Σ| n log n).
- Minimal DFA নাম বাদ দিলে অনন্য; প্রমাণপত্র: সব state reachable আর প্রতিটি জোড়ার witness. Minimal NFA অনন্য নয়, খোঁজা PSPACE-complete.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০৮ · DFA নকশা — product construction, complement আর গণনার কৌশলফিরে দেখুনMod-m DFA, product construction আর minimal state-এর প্রথম অন্তর্দৃষ্টি।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ২০ regular language-এর decision problem.
- পর্ব ১০ · NFA থেকে DFA — subset construction আর state বিস্ফোরণপটভূমিকোথা থেকে বড় DFA আসে, আর কোন language-এ minimal DFA-ও ঘাতের হারে বড়।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৫৫ — Equivalence relation আর partitionপটভূমিEquivalence class আর partition, যার ওপর পুরো minimization দাঁড়িয়ে।
- DSA · পর্ব ৩৩ — Disjoint set union (union-find)পাশের ট্র্যাকHopcroft–Karp equivalence পরীক্ষা আর “ছোট-বড়” যুক্তির data structure.
- কম্পিউটার আর্কিটেকচার · পর্ব ১৭ — Finite state machineহাতে-কলমেHardware FSM-এ state minimisation আর circuit-এ তার প্রভাব।