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

NFA থেকে DFA — subset construction আর state বিস্ফোরণ

From NFA to DFA — Subset Construction, Its Correctness Proof and the Exponential State Explosion

Taught in Bangla, this lesson converts an NFA into an equivalent DFA. It works the second-symbol-from-the-end example step by step, proves L(D) = L(N) by induction on |w|, builds only reachable subsets with ∅ as the dead state, and proves with distinguishing suffixes that the n-th-from-the-end language needs at least 2^n DFA states. In-page Python (Pyodide) runs the construction and measures the blow-up, a real automata-lib run reproduces the counts, and a browser demo builds a lazy DFA.

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

  • একটি NFA থেকে subset construction-এ DFA বানানো, টেবিল সারি ধরে ধরে, শুধু পৌঁছানো subset নিয়ে
  • দৈর্ঘ্যের ওপর induction দিয়ে নির্মাণটির সঠিকতা প্রমাণ করা
  • Dead state ∅ কোথা থেকে আসে, আর DFA-কে পূর্ণ (total) রাখা কেন জরুরি
  • Ln-এর জন্য 2n state যে লাগবেই, তার প্রমাণ, আর Python ও automata-lib-এ সেটি গুনে দেখা
  • বাস্তবে কখন পুরো DFA বানানো লাভজনক, কখন NFA সরাসরি চালানো বা lazy DFA ভালো

১ · কেন রূপান্তর দরকার — অনেক পথ, একটি খাতা

পর্ব ০৯-এ আপনি NFA দেখেছেন: এমন একটি finite automaton, যার একটি state থেকে একই চিহ্নে একাধিক পরের state থাকতে পারে, বা একটিও না। একটি string গৃহীত হয় যদি অন্তত একটি পথ accepting state-এ শেষ হয়। NFA নকশা করা প্রায়ই সহজ। “শেষ থেকে দ্বিতীয় চিহ্ন 1” language-এর জন্য তিন state-ই যথেষ্ট: যন্ত্রটি যেন “অনুমান” করে, এই 1-টিই শেষ থেকে দ্বিতীয়।

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

ঢাকার একটি বাস কাউন্টারের কথা ভাবুন। একজন যাত্রী জানেন না তাঁর বাস কোন প্ল্যাটফর্ম থেকে ছাড়বে। কাউন্টারের লোকটি একটি খাতায় লিখে রাখেন: “এই মুহূর্তে বাসটি ২ বা ৫ নম্বরে থাকতে পারে।” নতুন ঘোষণা এলে তিনি খাতার লেখা বদলান: “এখন ৫ বা ৭।” খাতার প্রতিটি পাতা একটি নিশ্চিত তথ্য: সম্ভাবনার একটি সেট। যাত্রীর মনে অনিশ্চয়তা, কিন্তু খাতার অবস্থা সবসময় একটিই। Subset construction ঠিক এই খাতা: NFA-র অনিশ্চয়তাকে একটি নিশ্চিত “সম্ভাবনার সেট”-এ বদলে দেয়।

খাতাটি সসীম কেন, সেটিই আসল কথা। NFA-তে n-টি state থাকলে সম্ভাব্য সেট বড়জোর 2nটি: Q-এর power set P(Q)-এর প্রতিটি সদস্য একটি সম্ভাব্য পাতা। 2n বিশাল হতে পারে, কিন্তু সসীম। তাই ফলাফলও একটি finite automaton. এই পর্বে দেখবেন নির্মাণটি কীভাবে কাজ করে, কেন সঠিক, আর কখন 2n সংখ্যাটি সত্যিই এড়ানো যায় না।

এই পর্বের notation: NFA N = (Q, Σ, δ, q0, F), যেখানে δ : Q × Σ → P(Q), অর্থাৎ প্রতিটি state আর চিহ্নের জন্য পরের state-গুলোর একটি সেট (ফাঁকাও হতে পারে)। এই পর্বে NFA-তে ε-transition নেই; ε-move থাকলে কী বদলায়, সেটি পর্ব ১১-এর বিষয়। DFA M = (Q, Σ, δ, q0, F)-এ δ : Q × Σ → Q একটি total ফাংশন। পুরো string-এর transition লেখা হয় δ̂ দিয়ে (কিছু বইয়ে δ∗)। State-এর নাম q0, q1, … ল্যাটিন অক্ষরে।

২ · Subset construction — formal সংজ্ঞা

প্রথমে NFA-র জন্য পুরো string-এর transition দরকার। একটি state q থেকে w পড়ে NFA যে যে state-এ পৌঁছাতে পারে, তাদের সেট δ̂N(q, w). সংজ্ঞাটি string-এর শেষ চিহ্ন ধরে, দৈর্ঘ্যের ওপর recursion:

δ̂N(q, ε) = {q},   δ̂N(q, xa) = ⋃p ∈ δ̂N(q, x) δ(p, a)

কথায়: কিছুই না পড়লে NFA যেখানে ছিল সেখানেই থাকে। x পড়ার পর যে state-গুলোতে থাকা সম্ভব, তাদের প্রতিটি থেকে a পড়ে যেখানে যাওয়া যায়, সব একসঙ্গে জুড়ে (union) পাওয়া যায় xa-এর পরের সেট। N-এর language L(N) = {w ∈ Σ∗ : δ̂N(q0, w) ∩ F ≠ ∅}, অর্থাৎ শেষ সেটে অন্তত একটি accepting state থাকলেই গ্রহণ।

সংজ্ঞা ২.১ (subset construction)

NFA N = (Q, Σ, δ, q0, F) থেকে DFA D = (QD, Σ, δD, {q0}, FD) বানানো হয় এভাবে:
State: QD = P(Q), অর্থাৎ Q-এর প্রতিটি subset একটি DFA state (ব্যবহারে শুধু শুরু থেকে পৌঁছানো subset রাখা হয়, অংশ ৫).
Transition: প্রতিটি S ⊆ Q আর a ∈ Σ-এর জন্য δD(S, a) = ⋃q ∈ S δ(q, a). বিশেষ করে δD(∅, a) = ∅.
শুরু: একক সেট {q0}.
গ্রহণ: FD = {S ⊆ Q : S ∩ F ≠ ∅}, অর্থাৎ যে subset-এ F-এর অন্তত একটি state আছে।

তিনটি বিষয় খেয়াল করুন। প্রথমত, δD সত্যিই একটি ফাংশন: প্রতিটি (S, a) জোড়ার জন্য ঠিক একটি ফল, একটি সেট। কোনো অনুমান নেই। দ্বিতীয়ত, δD total: δ(q, a) ফাঁকা হলেও union-এর একটি মান আছে, প্রয়োজনে ∅. তৃতীয়ত, গ্রহণের শর্ত “S ∩ F ≠ ∅”, “S ⊆ F” নয়। NFA-র একটি পথ সফল হলেই চলে; সব পথ সফল হতে হয় না। এই শেষ ভুলটি পরীক্ষার খাতায় আর AI-এর উত্তরে প্রায়ই দেখা যায়।

সংজ্ঞাটি কাগজে লেখা সহজ, কিন্তু হাতে কাজ করতে একটি টেবিল লাগে। টেবিলের প্রতিটি সারি একটি subset S, প্রতিটি কলাম একটি চিহ্ন a, আর ঘরে δD(S, a). একটি ঘর ভরতে S-এর প্রতিটি state-এর NFA সারি দেখে ফলগুলো জুড়তে হয়। পরের অংশে একটি পূর্ণ উদাহরণ।

৩ · ধাপে ধাপে — “শেষ থেকে দ্বিতীয় চিহ্ন 1”

Σ = {0, 1}-এর ওপর L2 = {w : |w| ≥ 2 আর w-এর শেষ থেকে দ্বিতীয় চিহ্ন 1}. যেমন 10 আর 0111 ∈ L2, কিন্তু 01, 1 আর ε ∉ L2. বাজারঘরের সেন্সর লাইনের ভাষায়: “শেষের ঠিক আগের সংকেতটি কি চালু ছিল?” NFA N2-এর তিনটি state: q0-তে যন্ত্র যেকোনো চিহ্নে নিজের কাছে ফেরে, আবার 1 পড়লে “এটিই শেষ থেকে দ্বিতীয়” অনুমান করে q1-এ যেতে পারে; q1 থেকে যেকোনো চিহ্নে q2; q2 accepting, আর সেখান থেকে কোনো তীর নেই।

NFA N2-এর state0 পড়লে1 পড়লে
→ q0 (শুরু){q0}{q0, q1}
q1{q2}{q2}
∗ q2 (accepting)∅∅

এখন subset construction চালানো হবে “অলসভাবে”: শুধু যে subset-এ সত্যিই পৌঁছানো যায়, সেগুলোই। একটি worklist (করণীয় তালিকা) রাখা হয়; সেখান থেকে একটি subset তুলে তার সারি ভরা হয়, আর নতুন কোনো subset পাওয়া গেলে সেটি তালিকায় ঢোকে। নিচের stepper-এ নতুন DFA state-গুলোর নাম A, B, C, D.

1A = {q0}, worklist = [A]2A, 0 পড়লে3A, 1 পড়লে4B = {q0,q1}, 0 পড়লে5B, 1 পড়লে6C = {q0,q2}-এর সারি7D = {q0,q1,q2}-এর সারি8accepting চিহ্নিত করা
এই ধাপের হিসাব
union
ফল
worklist
DFA state
  1. শুরু। DFA-র শুরু state হলো একক সেট {q0}, নাম দেওয়া হলো A. শুরুতে NFA নিশ্চিতভাবে q0-তেই আছে। A worklist-এ গেল।
  2. A-এর 0-সারি। worklist থেকে A তোলা হলো। A-তে একটিই state, q0, আর δ(q0, 0) = {q0}. ফল আবার A, যা আগেই আছে।
  3. A-এর 1-সারি। δ(q0, 1) = {q0, q1}. এটি নতুন subset, নাম B. B worklist-এ ঢুকল।
  4. B-এর 0-সারি। B = {q0, q1}, তাই দুই state-এর সারি জুড়তে হবে: δ(q0, 0) ∪ δ(q1, 0) = {q0} ∪ {q2} = {q0, q2}. নতুন, নাম C.
  5. B-এর 1-সারি। δ(q0, 1) ∪ δ(q1, 1) = {q0, q1} ∪ {q2} = {q0, q1, q2}. নতুন, নাম D. worklist এখন [C, D].
  6. C-এর সারি। C = {q0, q2}. q2 থেকে কোনো তীর নেই, তাই শুধু q0-এর সারি থাকে: 0-তে {q0} = A, 1-এ {q0, q1} = B. দুটিই পুরোনো।
  7. D-এর সারি। D = {q0, q1, q2}. 0-তে {q0} ∪ {q2} = C, 1-এ {q0, q1} ∪ {q2} = D, অর্থাৎ নিজের কাছে ফেরা। worklist খালি, নির্মাণ শেষ।
  8. গ্রহণ। q2 আছে C আর D-তে, তাই এরা accepting. মোট ৪টি state; P(Q)-এর বাকি ৪টি subset ({q1}, {q2}, {q1, q2} আর ∅) শুরু থেকে কখনো আসে না, তাই সেগুলো বানানোই হয়নি।

নিচের ছবিতে উপরে NFA N2, নিচে তৈরি হওয়া DFA. খেয়াল করুন, DFA-র প্রতিটি state থেকে প্রতিটি চিহ্নে ঠিক একটি তীর বেরিয়েছে।

NFA N2 (৩টি state) থেকে DFA (৪টি state)

দুই দাগের বৃত্ত accepting state. DFA-র নামগুলোর অর্থ ছবির নিচে লেখা; প্রতিটি নাম NFA-র state-এর একটি সেট।

Subset construction: the NFA for "second symbol from the end is 1" and its 4-state DFA NFA N₂ ↓ subset construction ↓ q0q1q2 ABCD 0,1 1 0,1 0 1 0 1 1 0 0 1 A = {q0}, B = {q0,q1} C = {q0,q2}, D = {q0,q1,q2}
ছবি ১০.১ — DFA-র state D থেকে 1 পড়লে D-তেই ফেরা: শেষ দুই চিহ্ন 11 হলে যন্ত্র সবসময় D-তে থাকে।

DFA-টির একটি সুন্দর ব্যাখ্যা আছে। চারটি state আসলে শেষ দুটি চিহ্ন মনে রাখে (string-এ দুটির কম চিহ্ন থাকলে বাঁ দিকে কাল্পনিক 0 ধরে): A মানে শেষ দুটি 00, B মানে 01, C মানে 10, D মানে 11. শেষ থেকে দ্বিতীয় চিহ্ন 1 ঠিক C আর D-তে, তাই এরা accepting. নির্মাণ কোনো ব্যাখ্যা না জেনেই যন্ত্রিকভাবে এই উত্তরে পৌঁছেছে। এটাই construction proof-এর শক্তি: রেসিপিটি নিজেই algorithm.

৪ · সঠিকতার প্রমাণ — দৈর্ঘ্যের ওপর induction

উদাহরণে নির্মাণটি কাজ করেছে, কিন্তু সব NFA-তে করবে কি? প্রমাণের মূল কথা একটি lemma: DFA একটি string পড়ে যে subset-এ পৌঁছায়, সেটি ঠিক NFA-র সম্ভাব্য state-গুলোর সেট। DFA-র পুরো string-এর transition সাধারণ নিয়মে: δ̂D(S, ε) = S, আর δ̂D(S, xa) = δD(δ̂D(S, x), a).

Lemma ৪.১

Subset construction-এ N থেকে D বানানো হলে প্রতিটি string w ∈ Σ∗-এর জন্য δ̂D({q0}, w) = δ̂N(q0, w).

প্রমাণ (|w|-এর ওপর induction; পদ্ধতিটি পর্ব ০৪-এর মতো, যেখানে string-এর ওপর induction বিস্তারিত আছে):

  1. ভিত্তি, |w| = 0: তখন w = ε. δ̂D({q0}, ε) = {q0} = δ̂N(q0, ε). — দুই δ̂-এর সংজ্ঞার প্রথম লাইন
  2. ধাপ: |w| = k + 1 ধরুন, k ≥ 0. তাহলে w = xa, যেখানে |x| = k আর a ∈ Σ. — শেষ চিহ্নটি আলাদা করা
  3. Hypothesis: δ̂D({q0}, x) = δ̂N(q0, x). এই সেটের নাম P. — দৈর্ঘ্য k-এর string-এ দাবিটি সত্য ধরা
  4. δ̂D({q0}, xa) = δD(δ̂D({q0}, x), a) = δD(P, a). — δ̂D-এর সংজ্ঞা, তারপর ধাপ ৩
  5. δD(P, a) = ⋃p ∈ P δ(p, a). — δD-এর সংজ্ঞা (সংজ্ঞা ২.১)
  6. ⋃p ∈ P δ(p, a) = δ̂N(q0, xa), কারণ P = δ̂N(q0, x). — δ̂N-এর সংজ্ঞার দ্বিতীয় লাইন
  7. ধাপ ৪–৬ জুড়ে δ̂D({q0}, w) = δ̂N(q0, w). Induction-এ সব দৈর্ঘ্যে সত্য। ∎
উপপাদ্য ৪.২ (Rabin–Scott)

প্রতিটি NFA N-এর জন্য একটি DFA D আছে যাতে L(D) = L(N). ফলে একটি language কোনো DFA-র language ⇔ কোনো NFA-র language: দুই মডেল ঠিক একই শ্রেণি, অর্থাৎ regular language, চেনে।

প্রমাণ:

  1. w ∈ L(D) ⇔ δ̂D({q0}, w) ∈ FD. — DFA-র language-এর সংজ্ঞা
  2. ⇔ δ̂D({q0}, w) ∩ F ≠ ∅. — FD-এর সংজ্ঞা
  3. ⇔ δ̂N(q0, w) ∩ F ≠ ∅. — Lemma ৪.১
  4. ⇔ w ∈ L(N). — NFA-র language-এর সংজ্ঞা
  5. উল্টো দিক সহজ: প্রতিটি DFA নিজেই একটি NFA, δN(q, a) = {δ(q, a)} নিলে। তাই DFA-র প্রতিটি language NFA-রও language. ∎

প্রমাণটি ছোট, কারণ সংজ্ঞাগুলো ঠিকভাবে বাছা হয়েছে। δD হুবহু δ̂N-এর recursive ধাপটি নকল করে, তাই induction-এর ধাপ প্রায় নিজে থেকেই মিলে যায়। একটি সূক্ষ্ম কথা: lemma-টি প্রমাণ করে কোন subset-এ DFA পৌঁছায়; পৌঁছানো যায় না এমন subset-এর আচরণ language-এ কোনো প্রভাব ফেলে না। এ কারণেই অংশ ৫-এর “শুধু পৌঁছানো subset” কৌশল নিরাপদ।

NFA আর এই রূপান্তর সাধারণত Michael Rabin আর Dana Scott-এর ১৯৫৯ সালের প্রবন্ধ “Finite Automata and Their Decision Problems” (IBM Journal of Research and Development)-এর সঙ্গে যুক্ত করা হয়; সেখানে nondeterministic যন্ত্রের ধারণা আর তার সমতুল্য deterministic যন্ত্র বানানোর পদ্ধতি দেওয়া হয়েছিল। ১৯৭৬ সালে দুজনে Turing Award পান, আর পুরস্কারের উল্লেখে এই প্রবন্ধ আর nondeterministic machine-এর ধারণার কথা আছে। একই সময়ে আরও কয়েকজন গবেষক কাছাকাছি ধারণা নিয়ে কাজ করছিলেন, তাই কৃতিত্বের পুরো ইতিহাস এক লাইনে বলা কঠিন। Finite automaton-এর আরও পুরোনো উৎস McCulloch–Pitts (১৯৪৩) আর Kleene (১৯৫৬), যা পর্ব ০১-এর সময়রেখায় আছে।

৫ · শুধু পৌঁছানো subset আর dead state ∅

সংজ্ঞা অনুযায়ী D-তে 2|Q|টি state, কিন্তু অংশ ৩-এ ৮টির মধ্যে মাত্র ৪টি লেগেছে। বাকিগুলো পৌঁছানো যায় না: শুরু {q0} থেকে কোনো string পড়েই সেখানে যাওয়া যায় না। সেগুলো রাখলেও language বদলায় না, শুধু টেবিল বড় হয়। তাই ব্যবহারে নির্মাণটি সবসময় lazy বা “চাহিদামতো”: শুরু থেকে graph-এর breadth-first search-এর মতো এগোয় (BFS আর reachability-র বিস্তারিত DSA কোর্সে)। Algorithm-টি ছোট:

  1. S0 = {q0} নিন; QD = {S0}, worklist = [S0].
  2. worklist খালি না হওয়া পর্যন্ত: একটি S তুলুন; প্রতিটি a ∈ Σ-এর জন্য T = ⋃q ∈ S δ(q, a) হিসাব করুন, δD(S, a) = T লিখুন; T নতুন হলে QD-তে আর worklist-এ যোগ করুন।
  3. শেষে QD-এর যে সেটে F-এর কোনো state আছে, সেগুলো accepting.

একটি subset একবারই worklist-এ ঢোকে, তাই loop থামে। প্রতিটি সারিতে |Σ|টি union, প্রতিটি union-এ বড়জোর |Q|টি state-এর সারি জোড়া। সবচেয়ে খারাপ ক্ষেত্রে মোট কাজ মোটামুটি 2n · |Σ| · n2-এর অনুপাতে (n = |Q|), কিন্তু পৌঁছানো subset কম হলে খরচও তত কম।

এবার dead state. কোনো NFA-তে কিছু state আর চিহ্নের জন্য তীর না থাকলে union ফাঁকা হতে পারে: T = ∅. ∅ একটি বৈধ subset, তাই একটি DFA state. এর আচরণ সংজ্ঞা থেকেই আসে: δD(∅, a) = ∅ সব a-তে, আর ∅ ∩ F = ∅, তাই এটি কখনো গ্রহণ করে না। একবার ঢুকলে আর বের হওয়া যায় না, এ জন্যই নাম dead বা trap state. এর অর্থ: “NFA-র সব পথ মারা গেছে।”

বাজারঘরের অর্ডার কোড দিয়ে দেখা যাক। কোডের গঠন BG- তারপর চারটি অঙ্ক; পর্ব ০৭-এর মতো alphabet-কে সংক্ষেপে {B, G, -, d} ধরা হলো, যেখানে d মানে যেকোনো অঙ্ক। NFA-টি একটি সরল শিকল: q0 থেকে B-তে q1, G-তে q2, - -তে q3, তারপর চারটি d-তে q7 (accepting). প্রতিটি state থেকে মাত্র একটি তীর; বাকি সব চিহ্নে কোনো তীর নেই। নিচের ব্লক দুটি NFA-তেই lazy subset construction চালায়।

def subset_construction(delta, start, finals, sigma):
    # lazy: only subsets reachable from {start} are ever built
    S0 = frozenset([start])
    order, todo, rows = [S0], [S0], {}
    while todo:
        S = todo.pop(0)
        for a in sigma:
            T = frozenset(p for q in S for p in delta.get((q, a), ()))
            rows[S, a] = T
            if T not in order:
                order.append(T)
                todo.append(T)
    return order, rows, {S for S in order if S & finals}

def show(S):
    return "{" + ",".join(sorted(S)) + "}" if S else "∅"

# NFA for L2: the 2nd symbol from the end is 1
L2 = {("q0", "0"): {"q0"}, ("q0", "1"): {"q0", "q1"},
      ("q1", "0"): {"q2"}, ("q1", "1"): {"q2"}}
order, rows, acc = subset_construction(L2, "q0", {"q2"}, "01")
print("state        on 0         on 1")
for S in order:
    mark = "*" if S in acc else " "
    print(mark, show(S).ljust(11), show(rows[S, "0"]).ljust(12), show(rows[S, "1"]))
print("reachable:", len(order), "of", 2 ** 3, "subsets")

# bazarghar order code BG-dddd over {B, G, -, d}, d = any digit
code = {("q0", "B"): {"q1"}, ("q1", "G"): {"q2"}, ("q2", "-"): {"q3"},
        ("q3", "d"): {"q4"}, ("q4", "d"): {"q5"}, ("q5", "d"): {"q6"},
        ("q6", "d"): {"q7"}}
order, rows, acc = subset_construction(code, "q0", {"q7"}, "BG-d")
print("order code:", len(order), "of", 2 ** 8, "subsets:", *map(show, order))
print("from {q0} on G:", show(rows[frozenset({"q0"}), "G"]),
      "  from ∅ on d:", show(rows[frozenset(), "d"]))

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

state        on 0         on 1
  {q0}        {q0}         {q0,q1}
  {q0,q1}     {q0,q2}      {q0,q1,q2}
* {q0,q2}     {q0}         {q0,q1}
* {q0,q1,q2}  {q0,q2}      {q0,q1,q2}
reachable: 4 of 8 subsets
order code: 9 of 256 subsets: {q0} {q1} ∅ {q2} {q3} {q4} {q5} {q6} {q7}
from {q0} on G: ∅   from ∅ on d: ∅

প্রথম টেবিলটি হুবহু stepper-এর টেবিল: ৪টি state, তারকা-চিহ্নিত দুটি accepting. Python-এর frozenset ব্যবহার করা হয়েছে কারণ সাধারণ set dictionary-র key হতে পারে না; subset-কেই key বানানো এই নির্মাণের মূল কৌশল। দ্বিতীয় NFA-তে ৮টি state, তাই সম্ভাব্য subset 256টি, কিন্তু এসেছে মাত্র ৯টি: আটটি একক সেট আর ∅. NFA-টি আসলে “প্রায় deterministic” ছিল (প্রতিটি সারিতে বড়জোর একটি state), তাই কোনো বিস্ফোরণ হয়নি। ∅ এসেছে প্রথম ভুল চিহ্নেই: {q0} থেকে G পড়লে কোনো তীর নেই। শেষ লাইন দেখায়, ∅ থেকে যা-ই পড়ুন, ∅-ই থাকে। বাস্তবের validator-এ এই state-টিই “কোড বাতিল, আর পড়ার দরকার নেই” সিদ্ধান্ত।

∅ বাদ দিলে কী হয়? অনেক বই আর library ছবি পরিষ্কার রাখতে ∅ আঁকে না; তখন যন্ত্রটি একটি partial DFA, যেখানে “তীর নেই” মানে “বাতিল”। Simulation-এর জন্য এটি ঠিক আছে। কিন্তু complement (পর্ব ০৮) নিতে accepting আর non-accepting অদলবদল করলে, যে string আগে “তীর নেই” বলে বাতিল হতো, সেটি এখনো বাতিল থাকে, অথচ complement-এ তার গৃহীত হওয়ার কথা। তাই complement বা product construction-এর আগে DFA-কে total করতে হয়: ∅ state ফিরিয়ে আনা।

৬ · State বিস্ফোরণ — Ln-এর জন্য 2n state লাগবেই

অংশ ৩-এর language সাধারণ করা যাক। প্রতিটি n ≥ 1-এর জন্য

Ln = { w ∈ {0, 1}∗ : |w| ≥ n আর w-এর শেষ থেকে n-তম চিহ্ন 1 }

NFA Nn-এ n + 1টি state: q0 সব চিহ্নে নিজের কাছে ফেরে আর 1 পড়লে q1-এ যেতে পারে; তারপর q1 → q2 → ⋯ → qn একটি শিকল, প্রতিটি ধাপ যেকোনো চিহ্নে; qn accepting. যন্ত্রটি অনুমান করে “এই 1-টিই শেষ থেকে n-তম”, আর তারপর ঠিক n − 1টি চিহ্ন বাকি আছে কি না গোনে। N2 ছিল এর n = 2 রূপ। Subset construction-এ কতটি state আসে? নিচের ব্লক n = 1 থেকে 10 পর্যন্ত গোনে, আর n = 3-এর DFA-কে দৈর্ঘ্য 10 পর্যন্ত সব string-এ সংজ্ঞার সঙ্গে মেলায়।

from itertools import product
def nfa_Ln(n):           # states 0..n; the n-th symbol from the end is 1
    d = {(0, "0"): {0}, (0, "1"): {0, 1}}
    for i in range(1, n):
        d[i, "0"] = d[i, "1"] = {i + 1}
    return d

def determinize(d, sigma="01"):
    start = frozenset({0})
    seen, todo, delta = {start}, [start], {}
    while todo:
        S = todo.pop()
        for a in sigma:
            T = frozenset(p for q in S for p in d.get((q, a), ()))
            delta[S, a] = T
            if T not in seen:
                seen.add(T); todo.append(T)
    return seen, delta

for n in range(1, 11):
    seen, _ = determinize(nfa_Ln(n))
    acc = sum(n in S for S in seen)
    print(f"n={n:2}  NFA {n+1:2}  DFA {len(seen):4}  accepting {acc:3}"
          f"  all subsets {2 ** (n + 1)}")

n = 3                    # brute force: the DFA vs the definition of L3
seen, delta = determinize(nfa_Ln(n))
def dfa_accepts(w):
    S = frozenset({0})
    for c in w:
        S = delta[S, c]
    return n in S
words = ["".join(t) for k in range(11) for t in product("01", repeat=k)]
bad = sum(dfa_accepts(w) != (len(w) >= n and w[-n] == "1") for w in words)
print("strings checked:", len(words), " disagreements:", bad)

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

n= 1  NFA  2  DFA    2  accepting   1  all subsets 4
n= 2  NFA  3  DFA    4  accepting   2  all subsets 8
n= 3  NFA  4  DFA    8  accepting   4  all subsets 16
n= 4  NFA  5  DFA   16  accepting   8  all subsets 32
n= 5  NFA  6  DFA   32  accepting  16  all subsets 64
n= 6  NFA  7  DFA   64  accepting  32  all subsets 128
n= 7  NFA  8  DFA  128  accepting  64  all subsets 256
n= 8  NFA  9  DFA  256  accepting 128  all subsets 512
n= 9  NFA 10  DFA  512  accepting 256  all subsets 1024
n=10  NFA 11  DFA 1024  accepting 512  all subsets 2048
strings checked: 2047  disagreements: 0

NFA-র state এক এক করে বাড়ে (2, 3, 4, …), কিন্তু DFA-র state প্রতিবার দ্বিগুণ: ঠিক 2n. সম্ভাব্য 2n+1 subset-এর ঠিক অর্ধেক এসেছে; কারণ q0 সব চিহ্নে নিজের কাছে থাকে, তাই প্রতিটি পৌঁছানো subset-এ q0 আছে (অনুশীলন ৪-এ প্রমাণ)। Accepting state-ও ঠিক অর্ধেক, 2n−1. শেষ লাইনে দৈর্ঘ্য 0 থেকে 10-এর সব 2047টি string-এ n = 3-এর DFA আর সংজ্ঞা w[-n] == "1" একমত। এখানে todo.pop() শেষ থেকে তোলে (DFS-এর মতো), আগের ব্লকে pop(0) ছিল (BFS); ক্রম বদলালে নাম বদলায়, কিন্তু পৌঁছানো subset-এর সেট একই থাকে।

কিন্তু এতে শুধু দেখা গেল subset construction 2nটি state দেয়। হয়তো অন্য কোনো চালাক DFA কম state-এ কাজটি পারে? উত্তর: না। এটিই এই পর্বের দ্বিতীয় বড় উপপাদ্য।

উপপাদ্য ৬.১ (Ln-এর নিম্নসীমা)

প্রতিটি n ≥ 1-এর জন্য, Ln চেনে এমন যেকোনো DFA-তে অন্তত 2nটি state আছে। অথচ Nn NFA-তে মাত্র n + 1টি।

প্রমাণ (মূল অস্ত্র: আলাদা করা যায় এমন string, আর পর্ব ০৪-এর pigeonhole নীতি):

  1. ধরুন M = (Q, {0, 1}, δ, q0, F) একটি DFA আর L(M) = Ln. দৈর্ঘ্য ঠিক n-এর 2nটি binary string নিন। — |Σn| = 2n, পর্ব ০৩
  2. দাবি: দুটি ভিন্ন string x ≠ y (দুটিই দৈর্ঘ্য n) কখনো একই state-এ পৌঁছায় না, অর্থাৎ δ̂(q0, x) ≠ δ̂(q0, y). — যা প্রমাণ করতে হবে
  3. x ≠ y আর দৈর্ঘ্য সমান, তাই কোনো অবস্থান i-তে (বাঁ থেকে, 1 ≤ i ≤ n) এরা আলাদা। নাম বদলে ধরা যায় xi = 1, yi = 0. — দুটি string-এর সংজ্ঞা; প্রয়োজনে x আর y অদলবদল
  4. z = 0i−1 নিন। xz-এর দৈর্ঘ্য n + i − 1, তাই তার শেষ থেকে n-তম চিহ্ন বাঁ থেকে (n + i − 1) − n + 1 = i-তম, অর্থাৎ xi = 1. তাই xz ∈ Ln; একই হিসাবে yz-এর সেই চিহ্ন yi = 0, তাই yz ∉ Ln. — Ln-এর সংজ্ঞা, অবস্থান গোনা
  5. যদি δ̂(q0, x) = δ̂(q0, y) = r হতো, তাহলে δ̂(q0, xz) = δ̂(r, z) = δ̂(q0, yz): একই state, তাই M xz আর yz দুটিকেই গ্রহণ করত, বা দুটিকেই বাতিল করত। — DFA-তে ভবিষ্যৎ শুধু বর্তমান state-এর ওপর নির্ভর করে: δ̂(q, uv) = δ̂(δ̂(q, u), v)
  6. কিন্তু ধাপ ৪ অনুযায়ী ঠিক একটি গৃহীত হওয়ার কথা। বিরোধ। তাই ২-এর দাবি সত্য। — contradiction
  7. 2nটি string, প্রতিটি আলাদা state-এ, তাই |Q| ≥ 2n. ∎ — pigeonhole: কম state হলে দুটি string একই state-এ পড়ত

যুক্তিটির হৃদয় ধাপ ৪-এর suffix z: এমন একটি ভবিষ্যৎ, যা x আর y-কে আলাদা করে। এই ধরনের string-সেটকে কখনো fooling set বা distinguishing set বলা হয়। পর্ব ১৮-এর Myhill–Nerode theorem এই ধারণাকে পূর্ণ রূপ দেয়: যত জোড়া-জোড়া আলাদা করা যায় এমন string, minimal DFA-তে ঠিক তত state. এখানে উপরের আর নিচের সীমা মিলে গেছে: subset construction 2nটি দেয়, আর 2n-এর কমে অসম্ভব। তাই সেই DFA-টিই Ln-এর সবচেয়ে ছোট DFA. নিচে n = 3-এ যুক্তিটি হাতে-কলমে।

1দাবি: L₃-এর DFA-তে ≥ 8 state2দৈর্ঘ্য 3-এর ৮টি string3জোড়া: 110 বনাম 0104জোড়া: 101 বনাম 1005জোড়া: 011 বনাম 0016সাধারণ নিয়ম7উপসংহার
এই ধাপের হিসাব
x, y
প্রথম পার্থক্য i
suffix z
xz, yz
  1. দাবি। যেকোনো DFA M যদি L3 চেনে, তবে M-এ অন্তত 23 = 8টি state. ধরে নিন M-এ ৭টি বা কম state, তারপর বিরোধ খুঁজুন।
  2. আটটি string. 000, 001, 010, 011, 100, 101, 110, 111. ৭টি বা কম state হলে pigeonhole নীতিতে দুটি string একই state-এ পৌঁছাবে। দেখাতে হবে, কোনো জোড়াই তা পারে না।
  3. 110 বনাম 010. প্রথম অবস্থানে (i = 1) আলাদা। z = 00 = ε. 110-এর শেষ থেকে তৃতীয় চিহ্ন 1, তাই 110 ∈ L3; 010-এর সেটি 0, তাই ∉. একই state হলে দুটির ফল এক হতো।
  4. 101 বনাম 100. তৃতীয় অবস্থানে (i = 3) আলাদা। z = 00. 10100-এর দৈর্ঘ্য 5, শেষ থেকে তৃতীয় মানে বাঁ থেকে তৃতীয়: 1. আর 10000-এ সেটি 0. তাই 10100 ∈ L3, 10000 ∉.
  5. 011 বনাম 001. দ্বিতীয় অবস্থানে (i = 2) আলাদা। z = 0. 0110-এর শেষ থেকে তৃতীয় চিহ্ন বাঁ থেকে দ্বিতীয়, অর্থাৎ 1; 0010-এ 0. আবার একটি গৃহীত, একটি বাতিল।
  6. সাধারণ নিয়ম। x আর y প্রথম যেখানে আলাদা, সেই অবস্থান i হলে i − 1টি 0 জুড়ুন। তখন সেই পার্থক্যের চিহ্নটিই ঠিক শেষ থেকে n-তম জায়গায় সরে আসে, আর বাকি সব জোড়ায় একই কৌশল খাটে।
  7. উপসংহার। C(8, 2) = 28টি জোড়ার প্রতিটি আলাদা করা যায়, তাই আটটি string আটটি ভিন্ন state-এ যায়। ৮-এর কম state-এর DFA অসম্ভব, আর subset construction-এর ৮ state-এর DFA তাই সবচেয়ে ছোট।

উল্টো দিকটি সহজ: “শুরু থেকে n-তম চিহ্ন 1” language-এর জন্য DFA-তে মাত্র n + 2টি state লাগে: প্রথম n − 1টি চিহ্ন গুনে যাওয়ার nটি state, তারপর একটি “গৃহীত” আর একটি “বাতিল” ফাঁদ। Ln তারই reversal. Regular language reversal-এ regular থাকে (পর্ব ১৬), কিন্তু DFA-র আকার নাটকীয়ভাবে বদলে যেতে পারে। DFA সামনে থেকে পড়ে; “শেষ থেকে” গুনতে হলে যতক্ষণ না string শেষ হয়, শেষ n-টি চিহ্নের পুরো তথ্য মনে রাখতে হয়, আর তাতেই 2nটি সম্ভাবনা।

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

নিজের লেখা কোডে নিজের লেখা তত্ত্ব মেলানো ভালো, কিন্তু একটি স্বাধীন, পরিচিত library-তে মেলানো আরও ভালো। automata-lib হলো finite automaton, PDA আর Turing machine-এর একটি Python library (MIT licence). নিচের কোডটি ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে চালানো হয়েছে: automata-lib 9.2.0, Python 3.12. Library-র কোডে কোনো network বা usage-reporting অংশ নেই (scratch-এ খুঁজে দেখা হয়েছে)। এখানে DFA.from_nfa subset construction চালায়; minify=False দিলে কাঁচা DFA, আর ডিফল্টে (minify=True) তার minimal রূপ।

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

print("automata-lib", version("automata-lib"))

def nth_from_end(n):          # L_n: the n-th symbol from the end is 1
    t = {f"q{i}": {} for i in range(n + 1)}
    t["q0"] = {"0": {"q0"}, "1": {"q0", "q1"}}
    for i in range(1, n):
        t[f"q{i}"] = {"0": {f"q{i+1}"}, "1": {f"q{i+1}"}}
    return NFA(states=set(t), input_symbols={"0", "1"}, transitions=t,
               initial_state="q0", final_states={f"q{n}"})

for n in range(1, 9):
    nfa = nth_from_end(n)
    raw = DFA.from_nfa(nfa, minify=False)
    small = DFA.from_nfa(nfa)              # minify=True is the default
    print(f"n={n}  NFA {len(nfa.states):2}  DFA {len(raw.states):4}"
          f"  minimal {len(small.states):4}  2^n = {2**n}")

nfa3 = nth_from_end(3)
d3 = DFA.from_nfa(nfa3, retain_names=True, minify=False)
for w in ["100", "0110", "10110", "011"]:
    print(w, nfa3.accepts_input(w), d3.accepts_input(w))
print("same language:", d3 == DFA.from_nfa(nfa3))

t = {"q0": {"B": {"q1"}}, "q1": {"G": {"q2"}}, "q2": {"-": {"q3"}},
     "q3": {"d": {"q4"}}, "q4": {"d": {"q5"}}, "q5": {"d": {"q6"}},
     "q6": {"d": {"q7"}}, "q7": {}}
order = NFA(states=set(t), input_symbols={"B", "G", "-", "d"}, transitions=t,
            initial_state="q0", final_states={"q7"})
od = DFA.from_nfa(order, minify=False)
print("order code: DFA", len(od.states), "states, partial:", od.allow_partial)

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

~/bazarghar-toc$ uv run python blowup.py
automata-lib 9.2.0
n=1  NFA  2  DFA    2  minimal    2  2^n = 2
n=2  NFA  3  DFA    4  minimal    4  2^n = 4
n=3  NFA  4  DFA    8  minimal    8  2^n = 8
n=4  NFA  5  DFA   16  minimal   16  2^n = 16
n=5  NFA  6  DFA   32  minimal   32  2^n = 32
n=6  NFA  7  DFA   64  minimal   64  2^n = 64
n=7  NFA  8  DFA  128  minimal  128  2^n = 128
n=8  NFA  9  DFA  256  minimal  256  2^n = 256
100 True True
0110 True True
10110 True True
011 False False
same language: True
order code: DFA 8 states, partial: True

তিনটি জিনিস মিলেছে, একটি নতুন শেখা গেছে। প্রথমত, library-র কাঁচা DFA-ও ঠিক 2n state, ব্রাউজারের ব্লকের মতো। দ্বিতীয়ত, minimisation-এর পরেও সংখ্যা কমেনি: উপপাদ্য ৬.১-এর ঠিক এটাই ভবিষ্যদ্বাণী। তৃতীয়ত, চারটি নমুনা string-এ NFA আর DFA একমত, আর == (library-র language-সমতা পরীক্ষা, পর্ব ২০-এর বিষয়) True. নতুন জিনিসটি শেষ লাইনে: অর্ডার কোডের জন্য আমাদের নিজের নির্মাণে ৯টি state এসেছিল, library-তে ৮টি, আর partial: True. অর্থাৎ এই version-এ library ∅ state বাদ দিয়ে partial DFA বানায়। অংশ ৫-এর সতর্কবার্তাটি তাই বাস্তব: কোনো library-র ফল নিয়ে complement করার আগে দেখে নিন, DFA-টি total কি না।

৮ · বাস্তবের খরচ — on-the-fly, পুরো DFA আর lazy DFA

তাহলে বাস্তবে কি সবসময় আগে DFA বানিয়ে নেওয়া উচিত? নির্ভর করে। একটি NFA-কে string w-এর ওপর চালানোর তিনটি উপায় আছে, আর প্রতিটির খরচ আলাদা (n = NFA-র state-সংখ্যা):

উপায়আগাম কাজপ্রতি চিহ্নে কাজমেমরি
On-the-fly: state-এর সেট ধরে NFA চালানোনেইবড়জোর n2-এর অনুপাতে (সেটের প্রতিটি state-এর সারি জোড়া)n-এর অনুপাতে
পুরো DFA আগে বানানোসবচেয়ে খারাপে 2n-এর অনুপাতেধ্রুবক: একটি টেবিল দেখাসবচেয়ে খারাপে 2nটি সারি
Lazy DFA: দরকার হলে সারি বানিয়ে cache-এ রাখানেইপ্রথমবার on-the-fly-এর মতো, পরে ধ্রুবকযত subset সত্যিই এসেছে

একই NFA দিয়ে যদি লাখ লাখ string পরীক্ষা করতে হয় আর DFA ছোট থাকে, তাহলে আগে পুরো DFA বানানো লাভজনক। বাজারঘরের অর্ডার কোডের validator এর আদর্শ উদাহরণ: ৯ state-এর টেবিল একবার বানালে প্রতিটি কোড পরীক্ষা কয়েকটি টেবিল-দেখা মাত্র। কিন্তু L30-এর মতো কিছু হলে 230, অর্থাৎ এক শ কোটির বেশি state, যা আগে বানানো বাস্তবসম্মত নয়। তখন NFA সরাসরি চালানো, বা মাঝামাঝি পথ lazy DFA: পড়ার সময় যে subset সত্যিই আসে, শুধু তার সারি বানানো আর মনে রাখা। একটি string-এর দৈর্ঘ্য m হলে সে বড়জোর m + 1টি subset-এ যায়, তাই একটি string-এর জন্য কখনো 2nটি সারি লাগে না।

নিচের stepper-এ L3-এর NFA “10110” পড়ছে on-the-fly. প্রতিটি ধাপে সেটের অর্থ লক্ষ করুন: qi (i ≥ 1) সেটে আছে ঠিক তখন, যখন এ পর্যন্ত পড়া অংশের শেষ থেকে i-তম চিহ্ন 1. অর্থাৎ সেটটি শেষ তিনটি চিহ্নের একটি সংকেত; এ কারণেই 23টি সম্ভাব্য সেট।

1শুরু: S = {q0}2পড়া হলো 13পড়া হলো 04পড়া হলো 15পড়া হলো 16পড়া হলো 0 (শেষ)
এই ধাপের অবস্থা
এ পর্যন্ত পড়া
S
cache-এ সারি
q3 আছে?
  1. শুরু। S = {q0}. কিছু পড়া হয়নি, তাই কোনো 1-এর খবর নেই। cache ফাঁকা।
  2. 1 পড়া। q0 নিজের কাছে থাকে, আবার 1 বলে q1-এও যায়: S = {q0, q1}. সারি ({q0}, 1) প্রথমবার হিসাব হয়ে cache-এ গেল।
  3. 0 পড়া। q1 এগিয়ে q2 হলো; q0 থেকে 0-তে শুধু q0. S = {q0, q2}: “শেষ থেকে দ্বিতীয় চিহ্ন 1”, সত্যিই 10-এ তাই।
  4. 1 পড়া। q2 এগিয়ে q3, আর নতুন 1-এর জন্য q1. S = {q0, q1, q3}. 101-এর শেষ থেকে তৃতীয় চিহ্ন 1, তাই এখানে থামলে string গৃহীত হতো।
  5. 1 পড়া। q3 থেকে কোনো তীর নেই, তাই সেটি ঝরে পড়ে; q1 এগিয়ে q2; নতুন q1. S = {q0, q1, q2}. 1011-এর শেষ থেকে তৃতীয় চিহ্ন 0, তাই এখানে থামলে বাতিল।
  6. 0 পড়া, শেষ। S = {q0, q2, q3}. q3 আছে, তাই 10110 ∈ L3. পাঁচটি চিহ্নে মাত্র ৫টি সারি বানাতে হলো, পুরো DFA-র 8 × 2 = 16টি নয়।

এবার একই কৌশল ব্রাউজারের JavaScript-এ, আরও বড় n দিয়ে। প্রথম অংশ stepper-এর হিসাবটিই ছাপে। দ্বিতীয় অংশ n = 12 নিয়ে একটি স্থির ছদ্ম-দৈব 0/1 লেখা পড়ে (Park–Miller সূত্রে বানানো, তাই প্রতিবার একই), আর দেখায় দৈর্ঘ্য বাড়ার সঙ্গে cache-এ কত সারি জমে।

// NFA for L_n (n-th symbol from the end is 1), simulated on the fly.
// A cache keeps every DFA row we have computed: a "lazy DFA".
function makeRunner(n) {
  const step = (S, c) => {             // one NFA step on a set of states
    const T = new Set();
    for (const q of S) if (q === 0) { T.add(0); if (c === "1") T.add(1); }
                       else if (q < n) T.add(q + 1);
    return [...T].sort((a, b) => a - b);
  };
  const cache = new Map();              // "0,2|1" -> next set
  const next = (S, c) => {
    const key = S.join(",") + "|" + c;
    if (!cache.has(key)) cache.set(key, step(S, c));
    return cache.get(key);
  };
  return { next, rows: () => cache.size };
}
const r3 = makeRunner(3);
let S = [0];
for (const c of "10110") {
  S = r3.next(S, c);
  console.log("read", c, "-> {" + S.map(q => "q" + q).join(",") + "}");
}
console.log("accept:", S.includes(3), " rows built:", r3.rows());

let x = 7, text = "";                    // fixed pseudo-random 0/1 text
for (let i = 0; i < 20000; i++) { x = (x * 48271) % 2147483647; text += x % 2; }
const n = 12, r = makeRunner(n), t0 = performance.now();
let T = [0], hits = 0, pos = 0;
for (const stop of [100, 1000, 20000]) {
  for (; pos < stop; pos++) { T = r.next(T, text[pos]); if (T.includes(n)) hits++; }
  console.log("n = 12, chars", stop, " DFA rows built:", r.rows(), "of", 2 * 2 ** n);
}
console.log("accepting positions:", hits, " under 1 s:", performance.now() - t0 < 1000);

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

read 1 -> {q0,q1}
read 0 -> {q0,q2}
read 1 -> {q0,q1,q3}
read 1 -> {q0,q1,q2}
read 0 -> {q0,q2,q3}
accept: true  rows built: 5
n = 12, chars 100  DFA rows built: 99 of 8192
n = 12, chars 1000  DFA rows built: 935 of 8192
n = 12, chars 20000  DFA rows built: 7442 of 8192
accepting positions: 9937  under 1 s: true

প্রথম ছয় লাইন stepper-এর সঙ্গে হুবহু মেলে। n = 12-এ পুরো DFA-তে 212 = 4096টি state আর দুই চিহ্নে 8192টি সারি। ১০০ চিহ্ন পড়তে ৯৯টি সারি লেগেছে: প্রায় প্রতিটি চিহ্নেই নতুন সারি, কারণ এই language-এর সেট শেষ ১২টি চিহ্নের পুরো সংকেত, আর দৈব লেখায় সেগুলো সহজে পুনরাবৃত্তি হয় না। ২০,০০০ চিহ্নে cache 7442-এ পৌঁছেছে, পুরো DFA-র কাছাকাছি। অর্থাৎ Ln lazy DFA-র জন্যও কঠিন উদাহরণ: দীর্ঘ দৈব ইনপুটে প্রায় পুরো DFA-ই তৈরি হয়ে যায়। “accepting positions” মানে কতগুলো prefix L12-এ পড়েছে; দৈব লেখায় প্রায় অর্ধেক, যেমনটা আশা করা যায়। বাস্তব regex-এ সাধারণত অল্প কিছু subset বারবার আসে, তখন cache ছোট থাকে আর গতি প্রায় DFA-র মতো। কিছু engine cache-এর আকারের একটি সীমা রাখে; সীমা ছাড়ালে cache মুছে আবার শুরু করে।

বাস্তবের regex engine এই তিন পথের বিভিন্ন মিশ্রণ ব্যবহার করে। Ken Thompson ১৯৬৮ সালে একটি প্রবন্ধে regex থেকে NFA বানিয়ে state-এর সেট ধরে চালানোর পদ্ধতি দেখান (Thompson construction, পর্ব ১৪)। grep-জাতীয় কিছু টুল lazy DFA ব্যবহার করে বলে তাদের নথি আর বিশ্লেষণে উল্লেখ আছে। অন্যদিকে Python-এর re আর JavaScript-এর RegExp হলো backtracking engine: তারা state-এর সেট রাখে না, একটি একটি পথ চেষ্টা করে ব্যর্থ হলে ফিরে আসে। তাতে backreference-এর মতো সুবিধা মেলে, কিন্তু কিছু pattern-এ সময় ঘাতের হারে বাড়ে। এই তুলনা আর ReDoS-এর বিস্তারিত পর্ব ২১-এ।

আরও গভীরে: 2n সীমাটি সাধারণভাবেও নিখুঁত: এমন n-state NFA আছে যার সবচেয়ে ছোট DFA-তে ঠিক 2nটি state লাগে; এই ধরনের উদাহরণ সাধারণত F. R. Moore (১৯৭১) আর Meyer–Fischer (১৯৭১)-এর কাজের সঙ্গে যুক্ত করা হয়। এক চিহ্নের alphabet-এ (unary) বিস্ফোরণ কম, মোটামুটি e√(n ln n)-এর মাপে; এটি Chrobak-এর ১৯৮৬ সালের ফল হিসেবে পরিচিত। অসীম string-এর automaton-এ (Büchi automaton, পর্ব ৭৭) সাধারণ subset construction কাজই করে না; Safra ১৯৮৮ সালে আরও জটিল একটি নির্মাণ দেন। আর NFA-র minimisation কঠিন সমস্যা (PSPACE-complete বলে প্রমাণিত, পর্ব ৬৫-এর শ্রেণি), যেখানে DFA minimisation দ্রুত করা যায় (পর্ব ১৯)।

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

  • একটি দেওয়া NFA-কে DFA-তে রূপান্তর করুন। {q0} থেকে শুরু করে সারি ধরে union, শুধু পৌঁছানো subset, ∅ লাগলে dead state, আর F-এর সঙ্গে ছেদ আছে এমন সব subset accepting.
  • n-state NFA থেকে DFA-তে সর্বোচ্চ কত state? 2n; Ln-এর মতো উদাহরণে প্রায় এই সীমা সত্যিই লাগে।
  • NFA কি DFA-র চেয়ে শক্তিশালী? না; দুটি একই regular language চেনে (Rabin–Scott). পার্থক্য শুধু আকারে।
  • “শেষ থেকে n-তম চিহ্ন 1”-এর DFA-তে 2n-এর কম state কেন অসম্ভব? দৈর্ঘ্য n-এর যেকোনো দুটি ভিন্ন string-কে 0i−1 suffix আলাদা করে, তাই সবার জন্য আলাদা state লাগে।
  • NFA-র accepting state অদলবদল করলে কি complement পাওয়া যায়? সাধারণভাবে না; আগে total DFA বানিয়ে তারপর অদলবদল করতে হয়।

৯ · AI-এর যুগে NFA থেকে DFA রূপান্তর

AI assistant subset construction-এর সংজ্ঞা সুন্দর করে লিখে দিতে পারে, কিন্তু নির্দিষ্ট NFA-তে টেবিল ভরতে গেলে প্রায়ই ছোট ভুল করে, আর টেবিল দেখতে পরিপাটি হয় বলে ভুল চোখে পড়ে না। এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:

AI-এর ভুলকীভাবে ধরবেন
Accepting শর্ত “S ⊆ F” লেখা, “S ∩ F ≠ ∅”-এর জায়গায়{q0, q2}-এর মতো মিশ্র subset গৃহীত হচ্ছে কি না দেখা
∅ state বাদ দেওয়া, তারপর সেই partial DFA-র complement নেওয়াপ্রতিটি সারিতে প্রতিটি চিহ্নের ঘর ভরা আছে কি না গোনা
Union-এ একটি state-এর সারি ভুলে যাওয়া, যেমন {q0, q1}-এ শুধু q0 দেখাPython-এ ছোট simulator চালিয়ে প্রতিটি সারি মেলানো
সব 2n subset লিখে ফেলা, বা উল্টো, পৌঁছানো একটি subset বাদ দেওয়াworklist ধরে নিজে BFS করা; অপ্রয়োজনীয় সারির কোনো আগত তীর আছে কি না দেখা
“DFA সবসময় ঘাতের হারে বড় হয়” বা “2n কখনো লাগে না” — দুই চরম দাবিঅর্ডার কোড (৯ state) আর Ln (2n) দুটি উদাহরণ মনে রাখা
নিম্নসীমার “প্রমাণ”-এ শুধু subset construction-এর state গোনাপ্রশ্ন করা: অন্য কোনো DFA কি কম state-এ পারে? সব DFA-র কথা বলা যুক্তি চাই
বানানো রেফারেন্স বা ভুল সাল (যেমন Rabin–Scott-কে অন্য দশকে বসানো)Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখা

AI-কে ভালোভাবে কাজে লাগানোর উপায়: রূপান্তরের সঙ্গে একটি স্বাধীন যাচাইয়ের কোডও চাওয়া, যা NFA আর DFA-কে সব ছোট string-এ মিলিয়ে দেখে, আর সেটি নিজে চালানো।

আমি গণনার তত্ত্ব শিখছি। Σ = {a, b}-এর ওপর এই NFA-কে subset construction দিয়ে DFA-তে রূপান্তর করো: q0 (শুরু): a পড়লে {q0, q1}, b পড়লে {q0} q1: b পড়লে {q2}, a পড়লে ∅ q2 (accepting): a পড়লে {q2}, b পড়লে {q2} ১. শুধু {q0} থেকে পৌঁছানো যায় এমন subset নিয়ে টেবিল দাও, প্রতিটি ঘরের union কীভাবে এল তা লেখো। ২. কোন subset accepting এবং কেন (S ∩ F ≠ ∅ শর্ত দিয়ে), সেটা বলো। ∅ এলে আলাদা করে দেখাও। ৩. NFA আর তোমার DFA দৈর্ঘ্য ≤ 8-এর সব string-এ একই উত্তর দেয় কি না, তা যাচাইয়ের একটি ছোট Python কোড দাও (শুধু standard library). ৪. DFA-র কোনো দুটি state একীভূত করা যায় কি না বলো, আর সেই দাবির পক্ষে একটি যুক্তি দাও।

(নিজে যাচাই করুন: এই NFA “ab substring হিসেবে আছে” language চেনে। সঠিক DFA-তে ৪টি পৌঁছানো subset: {q0}, {q0, q1}, {q0, q2}, {q0, q1, q2}; শেষ দুটি accepting, কোনো ∅ আসে না, আর শেষ দুটি একীভূত করা যায়। অনুশীলন ১-এ পুরো টেবিল আছে।)

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

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

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

প্র ০১Finite automaton-এ nondeterminism কোনো নতুন শক্তি দেয় না। অন্য যন্ত্রেও কি তাই? কোথায় দেয়, কোথায় দেয় না, আর কোথায় আমরা এখনো জানি না?

এই পর্বের ফল বলে, finite automaton-এ “অনুমান করার ক্ষমতা” language-শ্রেণি বাড়ায় না: প্রতিটি NFA-র সমতুল্য DFA আছে। কিন্তু খরচ আছে, state-সংখ্যা ঘাতের হারে বাড়তে পারে। এই নকশা, “শক্তি সমান, কিন্তু খরচ কত”, পুরো কোর্সে বারবার ফিরে আসবে, আর প্রতিটি মডেলে উত্তর আলাদা।

Pushdown automaton-এ (পর্ব ৩২) nondeterminism সত্যিই শক্তি বাড়ায়। “জোড় দৈর্ঘ্যের palindrome” language-টি একটি nondeterministic PDA চিনতে পারে: যন্ত্রটি অনুমান করে মাঝখান কোথায়। কিন্তু কোনো deterministic PDA এটি পারে না; deterministic CFL-এর শ্রেণি কঠোরভাবে ছোট (পর্ব ৩৫)। কারণটি স্বজ্ঞাতভাবে বোঝা যায়: stack একটিই, তাই subset construction-এর মতো “সব সম্ভাব্য stack একসঙ্গে” রাখা যায় না; সম্ভাব্য stack-এর সংখ্যা অসীম।

Turing machine-এ আবার শক্তি সমান: প্রতিটি nondeterministic TM-কে একটি deterministic TM সব শাখা পালাক্রমে চেষ্টা করে simulate করতে পারে (পর্ব ৪৬)। কিন্তু সেই simulation-এ সময় ঘাতের হারে বাড়ে। প্রশ্ন হলো, এই ঘাতের বৃদ্ধি কি এড়ানো যায়? এটাই P বনাম NP প্রশ্ন (পর্ব ৬৩), যা এখনো খোলা; কেউ প্রমাণ করেননি যে NP-এর প্রতিটি সমস্যা polynomial time-এ সমাধান করা যায়, আবার যায় না তাও না। Space-এর ক্ষেত্রে ছবিটি ভিন্ন: Savitch ১৯৭০ সালে দেখান, f(n) ≥ log n হলে f(n) জায়গার nondeterministic যন্ত্রকে f(n)2 জায়গায় deterministic যন্ত্র simulate করতে পারে, অর্থাৎ বড়জোর বর্গের পার্থক্য; তাই NPSPACE = PSPACE (পর্ব ৬৪)।

Finite automaton-এর ক্ষেত্রটি তাই একটি নিরাপদ পরীক্ষাগার: এখানে আমরা প্রশ্নের দুই অংশই পুরো জানি। শক্তি সমান (subset construction), আর খরচ সবচেয়ে খারাপ ক্ষেত্রে ঘাতের হারে, যা এড়ানো যায় না (Ln-এর নিম্নসীমা)। Rabin আর Scott-এর ১৯৫৯ সালের প্রবন্ধ এই ধরনের প্রশ্ন পরিষ্কারভাবে তোলার প্রথম দিকের উদাহরণ, আর ১৯৭৬ সালের Turing Award-এ এই অবদানের কথা বলা হয়েছিল।

মূল উপলব্ধি: Nondeterminism-এর প্রশ্ন দুটি স্তরে: শক্তি (কোন language চেনা যায়) আর দক্ষতা (কত state, সময় বা জায়গা লাগে)। Finite automaton-এ দুটির উত্তরই জানা; PDA-তে শক্তি বাড়ে; Turing machine-এ শক্তি সমান, কিন্তু সময়ের দক্ষতার প্রশ্নটি P বনাম NP হয়ে এখনো খোলা।

প্র ০২বাস্তব regex engine কেন সবসময় পুরো DFA বানায় না? আর backtracking engine কেন অন্য পথ বেছে নেয়?

একটি regex থেকে NFA বানানো সহজ আর দ্রুত: regex-এর দৈর্ঘ্যের অনুপাতে state (Thompson construction, পর্ব ১৪)। কিন্তু সেই NFA থেকে পুরো DFA বানালে, এই পর্বের Ln-এর মতো pattern-এ, state ঘাতের হারে বাড়তে পারে। (0|1)*1(0|1)(0|1)-এর মতো একটি ছোট regex-ই শুধু দৈর্ঘ্য বাড়িয়ে হাজার হাজার state দাবি করতে পারে। তাই একটি engine-কে তিনটি জিনিসের ভারসাম্য রাখতে হয়: আগাম খরচ, প্রতি অক্ষরের খরচ আর মেমরি।

Ken Thompson ১৯৬৮ সালে Communications of the ACM-এ প্রকাশিত একটি প্রবন্ধে regex থেকে NFA বানিয়ে state-এর সেট ধরে চালানোর পদ্ধতি দেখান; তাঁর বাস্তবায়ন সেই সময়ের একটি IBM কম্পিউটারের জন্য সরাসরি machine code তৈরি করত বলে উল্লেখ আছে। এই পদ্ধতিতে সময় ইনপুটের দৈর্ঘ্য আর pattern-এর আকারের গুণফলের অনুপাতে, কোনো ঘাতের বিস্ফোরণ নেই। পরে grep-জাতীয় টুল আর কিছু আধুনিক regex library lazy DFA বেছে নেয়: চলার সময় যে subset আসে শুধু তার সারি বানিয়ে cache-এ রাখা, আর cache খুব বড় হলে মুছে ফেলা। এতে বেশিরভাগ বাস্তব ইনপুটে গতি DFA-র কাছাকাছি, অথচ মেমরি নিয়ন্ত্রণে।

Python-এর re, JavaScript-এর RegExp বা Perl-এর engine অন্য পথে হাঁটে: backtracking. এরা state-এর সেট রাখে না; একটি পথ বেছে এগোয়, ব্যর্থ হলে ফিরে এসে আরেকটি চেষ্টা করে, যেন DFS. এর বড় সুবিধা হলো এমন বৈশিষ্ট্য সহজে যোগ করা যায় যা গণিতের অর্থে regular নয়, যেমন backreference ((a+)b\1). কিন্তু মূল্য হলো, কিছু pattern আর ইনপুটে চেষ্টা করা পথের সংখ্যা ঘাতের হারে বাড়ে। (a+)+b-তে শুধু a-এর একটি লম্বা string দিলে এমনটা ঘটে। সার্ভারে এটি ReDoS নামের নিরাপত্তা সমস্যা, যা Cybersecurity কোর্সের পর্ব ৪৬-এ নিরাপদ কোডিংয়ের অংশ হিসেবে আছে।

লক্ষ করুন, এখানে ঘাতের বিস্ফোরণ দুই জায়গায় দুই রূপে আসে। Subset construction-এ বিস্ফোরণ জায়গায় (state-সংখ্যা), আর সেটি pattern-এর ওপর নির্ভর করে, ইনপুটের ওপর নয়। Backtracking-এ বিস্ফোরণ সময়ে, আর সেটি নির্ভর করে ইনপুটের ওপর, যা আক্রমণকারী বেছে নিতে পারে। এ কারণেই অবিশ্বস্ত ইনপুটের জন্য automaton-ভিত্তিক engine নিরাপদ বলে ধরা হয়। পর্ব ২১-এ দুই ধরনের engine পাশাপাশি সময় মেপে দেখা হবে।

মূল উপলব্ধি: On-the-fly NFA, পুরো DFA আর lazy DFA একই তত্ত্বের তিনটি প্রকৌশলী রূপ। কোনটি বেছে নেবেন তা নির্ভর করে pattern কত বড়, ইনপুট কত লম্বা আর কে সেই ইনপুট বেছে দেয় তার ওপর।

প্র ০৩“শুরু থেকে n-তম চিহ্ন” সহজ, “শেষ থেকে n-তম চিহ্ন” কঠিন। দিক বদলালেই DFA-র আকার এত বদলায় কেন, আর এই অসমতা কোথায় কাজে লাগে?

দুটি language একে অপরের reversal: Ln-এর প্রতিটি string উল্টালে “শুরু থেকে n-তম চিহ্ন 1” language-এর সদস্য পাওয়া যায়। Regular language reversal-এ regular থাকে (পর্ব ১৬): একটি DFA-র সব তীর উল্টে, শুরু আর accepting state অদলবদল করলে একটি NFA পাওয়া যায়, যা reversal চেনে। কিন্তু সেই NFA-কে আবার DFA বানাতে subset construction লাগে, আর সেখানেই আকার বদলায়।

সংখ্যাগুলো scratch-এ automata-lib দিয়ে মেলানো হয়েছে। “শুরু থেকে n-তম চিহ্ন 1”-এর minimal DFA-তে library দেখায় n + 1টি state, কারণ এটি ∅-ধরনের বাতিল-ফাঁদ বাদ দেয়; total DFA-তে n + 2. আর Ln-এ 2n. n = 20 হলে একদিকে ২২টি state, অন্যদিকে দশ লাখের বেশি। কারণটি তথ্যের: সামনে থেকে পড়লে n-তম চিহ্ন দেখে সঙ্গে সঙ্গে সিদ্ধান্ত নিয়ে বাকিটা ভুলে যাওয়া যায়; কিন্তু শেষ থেকে গুনতে হলে কখন string শেষ হবে তা জানা নেই, তাই প্রতিটি মুহূর্তে শেষ n-টি চিহ্নের পুরো তথ্য রাখতে হয়।

এই অসমতা থেকে একটি চমৎকার algorithm আসে, যা সাধারণত Janusz Brzozowski-এর ১৯৬০-এর দশকের শুরুর কাজের সঙ্গে যুক্ত করা হয়: একটি automaton-কে উল্টানো, subset construction, আবার উল্টানো, আবার subset construction (শুধু পৌঁছানো subset নিয়ে)। ফল হয় সবচেয়ে ছোট DFA. শুনতে জাদুর মতো, আর সবচেয়ে খারাপ ক্ষেত্রে মাঝের ধাপে ঘাতের হারে বড় যন্ত্র আসতে পারে; তবু কিছু বাস্তব ক্ষেত্রে এটি ভালো কাজ করে বলে গবেষণায় দেখা গেছে। পর্ব ১৯-এ Hopcroft-এর algorithm-এর সঙ্গে এর তুলনা আসবে।

বাস্তবেও এই দিকের প্রশ্ন আসে। একটি log ফাইলের শেষ থেকে কিছু খুঁজতে হলে কখনো ফাইলটি উল্টো দিক থেকে পড়া সস্তা। কিছু regex engine “শেষে মিলতে হবে” ধরনের pattern-এ ইনপুট উল্টো দিক থেকে স্ক্যান করে বলে জানা যায়। আর বাজারঘরের সেন্সর লাইনে “শেষের আগের সংকেত” পরীক্ষায় ৪টি state যথেষ্ট; কিন্তু “শেষ থেকে ২০-তম” চাইলে নকশাই বদলাতে হবে, যেমন একটি circular buffer রাখা।

মূল উপলব্ধি: Regular language-এর শ্রেণি reversal-এ বন্ধ, কিন্তু DFA-র আকার নয়। একটি language কতটা “কঠিন”, তা নির্ভর করে যন্ত্রটি কোন দিক থেকে পড়ে আর কত তথ্য মনে রাখতে বাধ্য হয় তার ওপর।

প্র ০৪নিম্নসীমা প্রমাণ এত মূল্যবান কেন? “আমি ছোট DFA খুঁজে পাইনি” আর “ছোট DFA নেই”-এর পার্থক্য কী, আর NFA-র ক্ষেত্রে এই প্রশ্ন কতটা কঠিন?

Algorithm-এর জগতে বেশিরভাগ ফল উপরের সীমা: “এই কাজ এত সময়ে করা যায়”, একটি পদ্ধতি দেখিয়ে। নিম্নসীমা অনেক বেশি দাবি করে: “কোনো পদ্ধতিই এর চেয়ে ভালো পারবে না।” সেটি দেখাতে সব সম্ভাব্য যন্ত্রের কথা একসঙ্গে বলতে হয়। উপপাদ্য ৬.১ ঠিক তাই করেছে: M-এর ভেতরের গঠন সম্পর্কে কিছু না ধরে শুধু DFA-র মৌলিক ধর্ম ব্যবহার করেছে, যে একই state থেকে একই ভবিষ্যৎ একই ফল দেয়।

“আলাদা করার suffix” কৌশলটি পর্ব ১৮-এর Myhill–Nerode theorem-এ পূর্ণ রূপ পায় (১৯৫৭–৫৮ সালের Myhill আর Nerode-এর কাজ)। সেখানে দেখানো হয়, সব string-কে “ভবিষ্যতে একই আচরণ” অনুযায়ী ভাগ করলে ভাগের সংখ্যাই minimal DFA-র state-সংখ্যা, ঠিক সমান, শুধু নিম্নসীমা নয়। ফলে DFA-র ক্ষেত্রে প্রশ্নটি পুরো সমাধান করা যায়: একটি DFA দিলে তার সবচেয়ে ছোট রূপ দ্রুত বের করা যায়; Hopcroft-এর ১৯৭১ সালের algorithm সময় নেয় n log n-এর অনুপাতে (পর্ব ১৯)।

NFA-র ক্ষেত্রে ছবি সম্পূর্ণ আলাদা। একই language-এর সবচেয়ে ছোট NFA অনন্য নাও হতে পারে, আর তা খুঁজে বের করা কঠিন: সাধারণ NFA দিলে সমতুল্য সবচেয়ে ছোট NFA খোঁজার সমস্যা PSPACE-complete বলে প্রমাণিত (Jiang আর Ravikumar-এর ১৯৯৩ সালের ফল হিসেবে উল্লেখ করা হয়)। নিম্নসীমার জন্য fooling set-এর একটি NFA-রূপ আছে, যা সাধারণত Glaister আর Shallit-এর ১৯৯৬ সালের কাজের সঙ্গে যুক্ত; কিন্তু সেটি সবসময় নিখুঁত সংখ্যা দেয় না, শুধু একটি সীমা।

একটি ব্যবহারিক শিক্ষাও আছে। ইন্টারভিউতে বা কাজে কেউ যদি বলেন, “আমি এর চেয়ে ছোট সমাধান পাইনি, তাই এটিই সেরা”, সেটি প্রমাণ নয়। AI assistant-ও প্রায়ই এভাবে যুক্তি দেয়: subset construction-এ 2n এসেছে, তাই 2n লাগবেই। সঠিক যুক্তি সব DFA-র জন্য খাটতে হবে, যেমন জোড়ায় জোড়ায় আলাদা-করা string দেখিয়ে। আর minimisation চালিয়ে সংখ্যা না কমলে সেটিও একটি শক্ত প্রমাণ, কারণ minimisation algorithm নিজেই Myhill–Nerode-এর ওপর দাঁড়ানো।

মূল উপলব্ধি: উপরের সীমা একটি উদাহরণ দেখায়, নিম্নসীমা সব সম্ভাবনা বাতিল করে। DFA-তে এই দুই সীমা মিলিয়ে দেওয়ার পূর্ণ তত্ত্ব আছে; NFA-তে প্রশ্নটি অনেক কঠিন।

প্র ০৫দুটি NFA একই language চেনে কি না জানতে হলে কি আগে দুটিকেই DFA বানাতে হয়? বিস্ফোরণের ভয় থাকলে বাস্তবে কী করা হয়?

সরল পথ: দুটি NFA-কে subset construction-এ DFA বানানো, তারপর product construction দিয়ে দেখা কোনো string একটিতে গৃহীত আর অন্যটিতে বাতিল হয় কি না (পর্ব ০৮ আর ২০)। দুটি DFA-র জন্য এই পরীক্ষা দ্রুত, state-সংখ্যার গুণফলের অনুপাতে। সমস্যা একটাই: subset construction-এর ধাপে state 2n হয়ে যেতে পারে। সেই খরচ কি এড়ানো যায়?

তত্ত্ব বলছে, সাধারণভাবে সম্ভবত না। NFA-র equivalence, এমনকি তার সরল রূপ “এই NFA কি সব string গ্রহণ করে?” (universality), PSPACE-complete বলে প্রমাণিত; ফলটি সাধারণত Meyer আর Stockmeyer-এর ১৯৭০-এর দশকের শুরুর কাজের সঙ্গে যুক্ত করা হয়। PSPACE-complete মানে এটি polynomial সময়ে সমাধান হলে PSPACE-এর সব সমস্যাই polynomial সময়ে সমাধান হতো, যা বেশিরভাগ বিশেষজ্ঞ অসম্ভব মনে করেন, যদিও P ≠ PSPACE এখনো প্রমাণিত নয়। এই শ্রেণির বিস্তারিত পর্ব ৬৫-এ।

তবু বাস্তবে ভালো কৌশল আছে। প্রথমত, lazy পদ্ধতি: দুটি DFA পুরো না বানিয়ে, product-এর state-গুলো (subset-জোড়া) শুধু চাহিদামতো তৈরি করা আর প্রথম পার্থক্য পেলেই থামা। দুটি language আলাদা হলে প্রায়ই ছোট একটি পাল্টা-উদাহরণ দ্রুত মেলে। দ্বিতীয়ত, antichain কৌশল (২০০৬ সালের দিকে De Wulf, Doyen, Henzinger আর Raskin-এর কাজ হিসেবে পরিচিত): কোনো subset S দেখা হয়ে গেলে, S-এর চেয়ে বড় subset আর দেখার দরকার নেই, কারণ বড় সেট বেশি string গ্রহণ করে। এতে অনেক বাস্তব উদাহরণে বেশিরভাগ subset বাদ পড়ে। Model checking টুলে (পর্ব ৭৭) এই ধরনের পদ্ধতি ব্যবহার হয়।

তৃতীয় আর সবচেয়ে সহজ কৌশলটি এই পর্বেই করেছেন: ছোট দৈর্ঘ্যের সব string-এ brute force. এটি প্রমাণ নয়, কিন্তু ভুল ধরার সবচেয়ে সস্তা উপায়। আর একটি সত্যিকারের নিশ্চয়তাও আছে: দুটি DFA-র state যথাক্রমে m আর k হলে, তারা আলাদা হলে দৈর্ঘ্য m·k-এর কম একটি পার্থক্যকারী string থাকবেই, কারণ product DFA-র একটি পৌঁছানো state থেকে সবচেয়ে ছোট পথ m·k-এর কম। তাই যথেষ্ট লম্বা brute force আসলে একটি পূর্ণ algorithm, শুধু ধীর।

মূল উপলব্ধি: NFA-র সমতা যাচাই তত্ত্বে কঠিন (PSPACE-complete), কিন্তু বাস্তবে lazy নির্মাণ, antichain আর brute-force পাল্টা-উদাহরণ খোঁজা মিলিয়ে প্রায়ই দ্রুত উত্তর পাওয়া যায়। “সবচেয়ে খারাপ ক্ষেত্র” আর “সাধারণ ক্ষেত্র” দুটি আলাদা প্রশ্ন।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। টেবিলগুলো চাইলে উপরের subset.py ব্লকে NFA বদলে বসিয়েও যাচাই করতে পারেন।

  1. রূপান্তর ও নকশা: Σ = {a, b}-এর ওপর NFA: q0 (শুরু) a পড়লে {q0, q1}, b পড়লে {q0}; q1 b পড়লে {q2}, a পড়লে ∅; q2 (accepting) a বা b পড়লে {q2}. (ক) কোন language? (খ) Subset construction-এ DFA বানান, শুধু পৌঁছানো subset নিয়ে। (গ) DFA-র কোনো দুটি state কি একীভূত করা যায়?

    (ক) যে string-এ ab একটি substring হিসেবে আছে। q0 অপেক্ষা করে, a পড়লে অনুমান করে “এখান থেকে ab শুরু”, তারপর b পেলে q2-তে পৌঁছে বাকি সব পড়ে থেকে যায়।

    (খ) {q0}: a → {q0, q1}, b → {q0}. {q0, q1}: a → {q0, q1} ∪ ∅ = {q0, q1}, b → {q0} ∪ {q2} = {q0, q2}. {q0, q2}: a → {q0, q1} ∪ {q2} = {q0, q1, q2}, b → {q0} ∪ {q2} = {q0, q2}. {q0, q1, q2}: a → {q0, q1, q2}, b → {q0, q2}. মোট ৪টি state; q2 আছে বলে {q0, q2} আর {q0, q1, q2} accepting. কোনো ঘর ∅ হয়নি, কারণ q0 সবসময় থাকে। Scratch-এ এই টেবিল subset.py-এর মতো কোডে হুবহু মিলেছে।

    (গ) হ্যাঁ: দুটি accepting state. দুটি থেকেই যেকোনো চিহ্নে আবার একটি accepting state-এ যাওয়া যায়, তাই যেকোনো ভবিষ্যতে দুটিই গ্রহণ করে; এদের আলাদা করার কোনো suffix নেই। একীভূত করলে ৩ state-এর DFA: “ab দেখা হয়নি, শেষে a নেই”, “ab দেখা হয়নি, শেষে a”, “ab দেখা হয়েছে”। automata-lib-এর minimisation-ও scratch-এ ৩টি state দিয়েছে। অর্থাৎ subset construction সঠিক DFA দেয়, কিন্তু সবসময় সবচেয়ে ছোটটি নয়; minimisation পর্ব ১৯-এ।

  2. প্রমাণের ভুল ধরুন: দাবি: “যেকোনো NFA N-এর accepting আর non-accepting state অদলবদল করলে যে NFA N′ পাওয়া যায়, তার language L(N)-এর complement.” যুক্তি: “w ∈ L(N) মানে w পড়ে N accepting state-এ শেষ হয়। N′-এ সেই state non-accepting, তাই w ∉ L(N′). একইভাবে উল্টো দিক। ∎” ভুল কোথায়? একটি পাল্টা-উদাহরণ দিন আর সঠিক পদ্ধতি বলুন।

    ভুল “w পড়ে N accepting state-এ শেষ হয়” বাক্যে: NFA একটি state-এ শেষ হয় না, একটি সেট-এ শেষ হয়। w ∈ L(N) মানে শেষ সেটে অন্তত একটি accepting state আছে, কিন্তু একই সেটে non-accepting state-ও থাকতে পারে। অদলবদলের পর সেই non-accepting state-টি accepting হয়ে যায়, তাই w ∈ L(N′)-ও হতে পারে। যুক্তিটি DFA-র জন্য সঠিক, NFA-র জন্য নয়।

    পাল্টা-উদাহরণ (Σ = {a}): q0 (শুরু) a পড়লে {q0, q1}, q1 accepting, q1 থেকে কোনো তীর নেই। L(N) = {a, aa, aaa, …} = a+, তাই complement = {ε}. অদলবদলে q0 accepting হয়। কিন্তু q0 সব string পড়ার পরেই সেটে থাকে, তাই L(N′) = a∗, যাতে a-ও আছে। a দুই language-এই আছে, তাই N′ complement চেনে না। Scratch-এ automata-lib-এ দুটি যন্ত্র চালিয়ে ε, a, aa, aaa-তে এই ফল মিলেছে।

    সঠিক পদ্ধতি: আগে subset construction-এ DFA বানান, প্রয়োজনে ∅ state রেখে DFA-কে total করুন, তারপর অদলবদল করুন। এখানে DFA-র state {q0} (non-accepting) আর {q0, q1} (accepting); অদলবদলের পর শুধু ε গৃহীত হয়, যা সঠিক complement.

  3. Trace ও আউটপুট অনুমান: L3-এর NFA N3-এ (q0 সব চিহ্নে নিজের কাছে, 1-এ q1-এও; q1 → q2 → q3 যেকোনো চিহ্নে; q3 accepting) “0110” পড়ার প্রতিটি ধাপে state-এর সেট লিখুন। string-টি কি গৃহীত? আর blowup.py ব্লকের determinize(nfa_Ln(5)) চালালে len(seen) কত হবে?

    শুরু {q0}. 0 পড়ে {q0}. 1 পড়ে {q0, q1}. 1 পড়ে {q0, q1, q2}. 0 পড়ে {q0, q2, q3}. শেষ সেটে q3 আছে, তাই গৃহীত। পরীক্ষা: 0110-এর শেষ থেকে তৃতীয় চিহ্ন বাঁ থেকে দ্বিতীয়, 1. সেটটি নিয়মও মানে: শেষ থেকে প্রথম চিহ্ন 0 (q1 নেই), দ্বিতীয় 1 (q2 আছে), তৃতীয় 1 (q3 আছে)।

    len(seen) হবে 25 = 32, ব্লকের আউটপুটে n = 5-এর সারির মতো। Scratch-এ লেখা একটি ছোট simulator-ও 0110-এ {q0, q2, q3} দিয়েছে।

  4. প্রমাণ (গোনা): Nn-এর state q0, q1, …, qn. প্রমাণ করুন: (ক) subset construction-এ প্রতিটি পৌঁছানো subset-এ q0 আছে; (খ) q0 আছে এমন প্রতিটি subset পৌঁছানো যায়, তাই পৌঁছানো subset ঠিক 2nটি; (গ) এর মধ্যে accepting ঠিক 2n−1টি।
    1. (ক) |w|-এর ওপর induction. ভিত্তি: δ̂D({q0}, ε) = {q0}. ধাপ: x-এর সেটে q0 থাকলে, δ(q0, a)-তে q0 আছে সব a-তে, তাই xa-এর সেটেও q0. — δD-এর সংজ্ঞা আর q0-এর নিজের কাছে ফেরা
    2. Invariant: |w| ≥ 0 হলে δ̂D({q0}, w) = {q0} ∪ {qi : 1 ≤ i ≤ n, i ≤ |w|, আর w-এর শেষ থেকে i-তম চিহ্ন 1}. একই induction-এ: a পড়লে প্রতিটি qi (i < n) সরে qi+1 হয় (চিহ্নটি এক ঘর পিছিয়ে যায়), qn ঝরে পড়ে, আর a = 1 হলে নতুন q1 আসে। — Nn-এর transition
    3. (খ) q0 ∈ T এমন যেকোনো T নিন। দৈর্ঘ্য n-এর w বানান যাতে শেষ থেকে i-তম চিহ্ন 1 ⇔ qi ∈ T. Invariant অনুযায়ী δ̂D({q0}, w) = T. এমন T-এর সংখ্যা {q1, …, qn}-এর subset-এর সংখ্যা, 2n, আর (ক) বলে এর বাইরে কিছু পৌঁছায় না। — invariant আর power set গোনা
    4. (গ) Accepting মানে qn ∈ T. বাকি n − 1টি state (q1 থেকে qn−1) যা খুশি, তাই 2n−1টি। ∎ — FD-এর সংজ্ঞা

    blowup.py-এর আউটপুটে n = 1 থেকে 10 পর্যন্ত DFA 2n আর accepting 2n−1, এই প্রমাণের সঙ্গে হুবহু মেলে।

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

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

ক্রমশুধু পৌঁছানো subset নিয়ে NFA থেকে DFA বানানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. শুরুর DFA state হিসেবে একক সেট {q0} নিয়ে worklist-এ রাখা
  2. worklist থেকে একটি subset S তোলা
  3. প্রতিটি চিহ্ন a-এর জন্য S-এর সব state-এর δ(q, a)-এর union হিসাব করা
  4. ফলটি নতুন subset হলে DFA-তে যোগ করে worklist-এ রাখা
  5. worklist খালি হলে, F-এর কোনো state আছে এমন subset-গুলোকে accepting চিহ্নিত করা

ε-move ছাড়া ৫টি state-এর একটি NFA থেকে subset construction-এ পাওয়া DFA-তে সর্বোচ্চ কতটি state থাকতে পারে?

  • 5
  • 10
  • 25
  • 32

একটি NFA-তে δ(q0, a) = {q0, q1}, δ(q1, a) = {q2} আর δ(q2, a) = ∅. Subset construction-এ δD({q0, q1}, a) কী?

  • {q0, q1, q2}
  • {q2}
  • {q0, q1}
  • ∅

NFA N = (Q, Σ, δ, q0, F) থেকে subset construction-এ পাওয়া DFA-র accepting state কোনগুলো?

  • শুধু F-এর প্রতিটি state-এর একক সেট
  • যে subset-এ F-এর অন্তত একটি state আছে
  • যে subset F-এর subset
  • শুধু F নিজে, একটি subset হিসেবে

Subset construction-এ ফাঁকা সেট ∅ একটি DFA state হিসেবে এলে সেটি কেমন আচরণ করে?

  • এটি DFA-র শুরু state
  • এখানে পৌঁছালে string গৃহীত হয়
  • এটি dead state: সব চিহ্নে নিজের কাছে ফেরে আর কখনো গ্রহণ করে না
  • এটি কখনো আসতে পারে না

Σ = {0, 1}-এর ওপর Ln = “দৈর্ঘ্য অন্তত n আর শেষ থেকে n-তম চিহ্ন 1”. n ≥ 1 হলে Ln-এর সবচেয়ে ছোট DFA-তে কতটি state?

  • n + 1
  • 2n
  • 2n
  • n2

একটি NFA-র language-এর complement চেনে এমন যন্ত্র পেতে কোন পদ্ধতি সবসময় সঠিক?

  • NFA-র accepting আর non-accepting state সরাসরি অদলবদল করা
  • আগে subset construction-এ total DFA বানিয়ে, তারপর তার accepting আর non-accepting state অদলবদল করা
  • NFA-র সব তীর উল্টে দেওয়া
  • DFA বানিয়ে ∅ state মুছে তারপর অদলবদল করা

শব্দকোষ

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

মনে রাখুন

  1. Subset construction: state = Q-এর subset, δD(S, a) = ⋃q ∈ S δ(q, a), শুরু {q0}, accepting মানে S ∩ F ≠ ∅.
  2. |w|-এর ওপর induction-এ δ̂D({q0}, w) = δ̂N(q0, w); তাই NFA আর DFA একই regular language চেনে (Rabin–Scott, ১৯৫৯)।
  3. ব্যবহারে শুধু পৌঁছানো subset বানানো হয়; ∅ হলো dead state, আর complement-এর আগে DFA-কে total রাখতে হয়।
  4. Ln-এর NFA-তে n + 1টি state, কিন্তু যেকোনো DFA-তে অন্তত 2nটি: দৈর্ঘ্য n-এর প্রতিটি জোড়াকে 0i−1 suffix আলাদা করে।
  5. বাস্তবে তিন পথ: on-the-fly NFA (কম মেমরি), পুরো DFA (দ্রুততম পড়া), lazy DFA (চাহিদামতো সারি, cache-এ)।

পরের পর্বে: NFA-কে আরেকটু স্বাধীনতা: কোনো চিহ্ন না পড়েই state বদলানোর ε-transition. দেখবেন ε-closure কীভাবে হিসাব করতে হয়, আর subset construction-এ শুরু state ও প্রতিটি ধাপে closure নেওয়া কেন জরুরি।

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

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