এই পর্বে যা শিখবেন
- ≡L relation-এর সংজ্ঞা, কেন এটি equivalence relation আর right-invariant, আর “index” মানে কী
- Myhill–Nerode theorem-এর তিনটি সমতুল্য রূপ আর দুই দিকের পূর্ণ প্রমাণ
- Class থেকে minimal DFA বানানো, আর minimal DFA কেন নাম বদল ছাড়া অনন্য
- ক্লাসিক language-এর class গোনা, আর fooling set দিয়ে anbn, সুষম বন্ধনী, palindrome ধরনের language non-regular প্রমাণ
- Python আর JavaScript-এ class খোঁজা ও বিচ্ছিন্নকারী suffix বের করা, আর সেই পরীক্ষার সীমা বোঝা
১ · একটি string-এর “ভবিষ্যৎ” — মূল ধারণা
এ পর্যন্ত আমরা DFA বানিয়েছি হাতে, অন্তর্দৃষ্টি দিয়ে: “শেষ দুটি চিহ্ন মনে রাখা”, “ভাগশেষ মনে রাখা”। পর্ব ০৮-এ একটি গভীর কথা উঁকি দিয়েছিল: একটি state আসলে এমন সব string-এর দল, যাদের ভবিষ্যৎ এক। এই পর্বে কথাটিকে একটি পূর্ণ উপপাদ্যে রূপ দেওয়া হবে। এর ফলে তিনটি প্রশ্নের একসঙ্গে উত্তর মিলবে: একটি language কখন regular, তার সবচেয়ে ছোট DFA-তে ঠিক কয়টি state, আর একটি language regular নয় তা কীভাবে নিশ্চিতভাবে প্রমাণ করা যায়।
ক্রিকেটে একটি দল ১৬০ রান তাড়া করছে। দশ ওভার শেষে স্কোরবোর্ডে লেখা ৮০/২. এই ৮০ রান কীভাবে এল, চার-ছক্কায় না এক-দুই রানে, তাতে ম্যাচের বাকিটার কিছু যায় আসে না। বাকি দশ ওভারে যা-ই ঘটুক, “জিতবে কি না” প্রশ্নের উত্তর নির্ভর করে শুধু তিনটি তথ্যের ওপর: আরও কত রান দরকার, কত উইকেট হাতে, কত বল বাকি। দুটি ভিন্ন ইনিংসের প্রথম দশ ওভার যদি এই তিনটি তথ্যে মিলে যায়, তাহলে ভবিষ্যতের প্রতিটি ঘটনাক্রমে দুটির ফল এক। স্কোরবোর্ড পুরো ইতিহাস রাখে না, রাখে শুধু ভবিষ্যতের জন্য যা দরকার। DFA-র state ঠিক এই স্কোরবোর্ড।
এবার একটি ছোট উদাহরণ। বাজারঘরের একটি পরীক্ষামূলক ফিল্টার Σ = {a, b}-এর ওপর সেই string-গুলো গ্রহণ করে যেগুলো ab দিয়ে শেষ হয়; নাম দিই Lab. এখন দুটি string নিন: a আর b. এদের পরে কেউ b জুড়ে দিলে ফল ab আর bb: প্রথমটি Lab-এ আছে, দ্বিতীয়টি নেই। তাই a আর b-এর ভবিষ্যৎ আলাদা, এবং যেকোনো DFA এদের পড়ার পর ভিন্ন state-এ থাকতে বাধ্য। অন্যদিকে ab আর bab নিন। এদের পরে যা-ই জুড়ুন, দুটির শেষ দুটি চিহ্ন সবসময় এক, তাই উত্তরও সবসময় এক। এদের আলাদা state-এ রাখার কোনো দরকার নেই।
এই পর্বের মূল প্রশ্ন তাই একটি গোনার প্রশ্ন: Σ∗-এর সব string-কে “একই ভবিষ্যৎ” অনুযায়ী দলে ভাগ করলে কয়টি দল হয়? দল সসীম হলে প্রতিটি দলকে একটি state বানিয়ে DFA পাওয়া যায়। দল অসীম হলে কোনো সসীম যন্ত্র কাজটি পারে না। এই দুই বাক্যই Myhill–Nerode theorem, আর এর প্রমাণ এই পর্বের কেন্দ্র।
এই পর্বের notation: DFA M = (Q, Σ, δ, q0, F), যেখানে δ : Q × Σ → Q total (পর্ব ০৭)। পুরো string-এর transition δ̂ (কিছু বইয়ে δ∗): δ̂(q, ε) = q আর δ̂(q, wa) = δ(δ̂(q, w), a). ε হলো ফাঁকা string (কিছু বই λ লেখে)। xz মানে x-এর ঠিক পরে z জুড়ে দেওয়া। Equivalence relation, equivalence class আর partition-এর মৌলিক কথা পর্ব ০২-এর অংশ ৩-এ আছে, আর বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫৫-এ। কোডে state-এর নাম Latin অক্ষরে, যেমন q0.
২ · সংজ্ঞা — ≡L, right-invariance আর index
L ⊆ Σ∗ একটি language, আর x, y ∈ Σ∗. একটি string z হলো x আর y-এর distinguishing extension (বিচ্ছিন্নকারী suffix), যদি xz আর yz-এর ঠিক একটি L-এ থাকে। এমন z থাকলে x আর y distinguishable. কোনো z না থাকলে লিখি
এই relation-কে বলা হয় L-এর Nerode equivalence.
z = ε নিলে একটি সহজ পরিণাম পাওয়া যায়: x ≡L y হলে x ∈ L ⇔ y ∈ L. অর্থাৎ একটি class-এর সব string হয় সবাই L-এ, নয়তো সবাই বাইরে। আর ≡L নাম যে “equivalence”, সেটি প্রমাণ করা দরকার।
(ক) ≡L একটি equivalence relation. (খ) এটি right-invariant: x ≡L y হলে প্রতিটি w ∈ Σ∗-এর জন্য xw ≡L yw.
প্রমাণ:
- Reflexive: প্রতিটি z-এ xz ∈ L ⇔ xz ∈ L, তাই x ≡L x. — ⇔ নিজের সঙ্গে সবসময় সত্য
- Symmetric: x ≡L y হলে প্রতিটি z-এ xz ∈ L ⇔ yz ∈ L, যা yz ∈ L ⇔ xz ∈ L-এর একই কথা; তাই y ≡L x. — ⇔ symmetric
- Transitive: x ≡L y আর y ≡L u হলে প্রতিটি z-এ xz ∈ L ⇔ yz ∈ L ⇔ uz ∈ L, তাই x ≡L u. — ⇔ transitive
- Right-invariant: x ≡L y আর w যেকোনো string. যেকোনো z নিন; z′ = wz লিখলে x ≡L y থেকে xz′ ∈ L ⇔ yz′ ∈ L, অর্থাৎ (xw)z ∈ L ⇔ (yw)z ∈ L. z ইচ্ছামতো, তাই xw ≡L yw. ∎ — concatenation associative
কথায় right-invariance মানে: আজ যাদের ভবিষ্যৎ এক, একই ঘটনা ঘটার পরও তাদের ভবিষ্যৎ এক থাকবে। কিন্তু বাঁ দিকে জুড়লে এটি খাটে না। Lab-এ ε ≡ b (দুটিরই শেষে ab নেই, আর দুটিই একই রকম আচরণ করে), অথচ বাঁয়ে a জুড়লে a আর ab, যাদের z = ε-ই আলাদা করে। তাই নামটি “right”-invariant.
একটি equivalence relation-এর মোট equivalence class-এর সংখ্যাকে তার index বলা হয়; এটি সসীম বা অসীম হতে পারে। x-এর class লেখা হয় [x] = {y : y ≡L x}. Class-গুলো Σ∗-এর একটি partition: প্রতিটি string ঠিক একটি class-এ পড়ে।
এবার Lab-এর class হাতে খোঁজা যাক। পদ্ধতিটি সরল: string-গুলো shortlex ক্রমে (আগে ছোট, তারপর অভিধান ক্রমে) একটি একটি করে নিন। প্রতিটির জন্য দেখুন, আগে পাওয়া কোনো class-এর প্রতিনিধির সঙ্গে সে সমতুল্য কি না। কোনো প্রতিনিধির সঙ্গে না মিললে সে নতুন class খোলে।
1x = ε : প্রথম class2x = a : ε-এর সঙ্গে তুলনা3x = b : ε আর a-এর সঙ্গে4x = ab : নতুন?5aa, ba, bb, aab …6আর নতুন class নেই কেন
| x | |
| তুলনা | |
| বিচ্ছিন্নকারী z | |
| ফল |
- ε নেওয়া। সবচেয়ে ছোট string ε. আগে কোনো class নেই, তাই ε প্রথম class খোলে: C0 = [ε]. ε ∉ Lab, তাই এই class-এর সবাই L-এর বাইরে।
- a আর ε. z = b নিলে ab ∈ L কিন্তু εb = b ∉ L. একটি বিচ্ছিন্নকারী suffix পাওয়া গেল, তাই a ≢ ε, আর a নতুন class খোলে: C1 = [a].
- b আর ε. যেকোনো z-এ bz আর z দুটিই ab দিয়ে শেষ হয়, বা দুটিই হয় না। কারণ |z| ≥ 2 হলে দুটির শেষ দুই চিহ্ন z-এরই; z = a বা b হলে ba, bb, a, b, কোনোটিই ab নয়; আর z = ε হলে b আর ε দুটিই বাইরে। তাই b ≡ ε, b যায় C0-তে।
- ab. z = ε-ই যথেষ্ট: ab ∈ L, অথচ ε আর a দুটিই L-এর বাইরে। তাই ab আগের দুই class-এর কোনোটিতেই নেই, আর নতুন class খোলে: C2 = [ab].
- বাকি string. aa আর ba শেষে a, তাই a-এর মতো আচরণ করে; bb আর abb-এর শেষে ab নেই আর a-ও নেই, তাই ε-এর মতো; aab, bab শেষে ab. একই যুক্তি (শেষ দুই চিহ্নই ভবিষ্যৎ ঠিক করে) প্রতিটিতে খাটে।
- সমাপ্তি। প্রতিটি string হয় ab দিয়ে শেষ, নয়তো a দিয়ে শেষ, নয়তো এর কোনোটিই নয়। প্রতিটি দলের ভেতরে সবাই সমতুল্য (ধাপ ৩ আর ৫-এর যুক্তি), আর তিন দলের প্রতিনিধি জোড়ায় জোড়ায় আলাদা (ধাপ ২ আর ৪)। তাই ঠিক ৩টি class.
Lab: Σ∗-এর তিন ভাগ, আর প্রতিটি ভাগ একটি state
উপরে তিনটি class, প্রতিটিতে কয়েকটি সদস্য। নিচে সেই class-গুলোকে state ধরে বানানো DFA; দুই দাগের বৃত্ত accepting.
৩ · Myhill–Nerode theorem আর তার পূর্ণ প্রমাণ
প্রমাণের আগে আরেকটি relation লাগবে, যা একটি DFA থেকে আসে। DFA M = (Q, Σ, δ, q0, F) দিলে
অর্থাৎ x আর y পড়ার পর M একই state-এ থামে। এটিও equivalence relation, কারণ “একটি function-এর মান সমান” সবসময় reflexive, symmetric আর transitive. প্রতিটি class একটি reachable state-এর সঙ্গে মেলে, তাই index(≡M) ≤ |Q|. আর M-এর language হলো সেই class-গুলোর union, যাদের state F-এ আছে।
L ⊆ Σ∗-এর জন্য নিচের তিনটি কথা সমতুল্য:
(১) L একটি regular language, অর্থাৎ কোনো DFA L চেনে।
(২) Σ∗-এর ওপর এমন একটি right-invariant equivalence relation E আছে যার index সসীম, আর L হলো E-এর কয়েকটি class-এর union.
(৩) ≡L-এর index সসীম।
রূপ (২)-টি একটু বিমূর্ত শোনায়, কিন্তু এটিই দুই প্রান্তের সেতু: DFA থেকে এমন E পাওয়া সহজ, আর এমন E থেকে ≡L-এর সসীমতা পাওয়াও সহজ। প্রমাণ তাই একটি চক্র: (১) ⇒ (২) ⇒ (৩) ⇒ (১). Hopcroft–Ullman-এর পাঠ্যবই ঠিক এই রূপে লেখে।
প্রমাণ, (১) ⇒ (২):
- ধরুন DFA M, আর L(M) = L. E = ≡M নিন। এটি equivalence relation, আর index ≤ |Q|, তাই সসীম। — উপরের পর্যবেক্ষণ
- Right-invariant: x ≡M y হলে δ̂(q0, xz) = δ̂(δ̂(q0, x), z) = δ̂(δ̂(q0, y), z) = δ̂(q0, yz), তাই xz ≡M yz. — δ̂(q, xz) = δ̂(δ̂(q, x), z), যা |z|-এর ওপর induction-এ প্রমাণিত (পর্ব ০৭)
- L = {w : δ̂(q0, w) ∈ F} = ⋃q ∈ F {w : δ̂(q0, w) = q}, আর প্রতিটি অশূন্য অংশ একটি ≡M-class. — L(M)-এর সংজ্ঞা
প্রমাণ, (২) ⇒ (৩):
- ধরুন E (২)-এর শর্ত মানে, আর x E y. যেকোনো z নিন। Right-invariance-এ xz E yz, অর্থাৎ xz আর yz একই E-class-এ। — (২)-এর অনুমান
- L কয়েকটি E-class-এর union, তাই একটি E-class হয় পুরোটা L-এ, নয়তো পুরোটা বাইরে। ফলে xz ∈ L ⇔ yz ∈ L. — union-এর সংজ্ঞা
- z ইচ্ছামতো, তাই x ≡L y. অর্থাৎ প্রতিটি E-class একটি ≡L-class-এর ভেতরে আছে: E হলো ≡L-এর একটি refinement. — সংজ্ঞা ২.১
- প্রতিটি ≡L-class অন্তত একটি E-class ধারণ করে, আর ভিন্ন ≡L-class-এ ভিন্ন E-class, তাই index(≡L) ≤ index(E) < ∞. — partition-এর গোনা
প্রমাণ, (৩) ⇒ (১): এখানে class-গুলো থেকে সরাসরি একটি DFA বানানো হয়।
- ML = (Q′, Σ, δ′, q′0, F′) নিন, যেখানে Q′ = ≡L-এর সব class (সসীম, (৩) অনুযায়ী), q′0 = [ε], δ′([x], a) = [xa], আর F′ = {[x] : x ∈ L}. — নির্মাণ
- δ′ সুসংজ্ঞিত: [x] = [y] হলে x ≡L y, তাই right-invariance-এ xa ≡L ya, অর্থাৎ [xa] = [ya]. ফল প্রতিনিধি বাছাইয়ের ওপর নির্ভর করে না। — Lemma ২.২ (খ)
- F′ সুসংজ্ঞিত: x ≡L y হলে z = ε নিয়ে x ∈ L ⇔ y ∈ L. তাই একটি class হয় পুরোটা L-এ, নয়তো পুরোটা বাইরে। — সংজ্ঞা ২.১-এ z = ε
- Invariant: প্রতিটি w-এ δ̂′([ε], w) = [w]. |w|-এর ওপর induction: w = ε হলে δ̂′([ε], ε) = [ε]. w = va হলে δ̂′([ε], va) = δ′(δ̂′([ε], v), a) = δ′([v], a) = [va]. — δ̂-এর সংজ্ঞা আর induction hypothesis
- তাই w ∈ L(ML) ⇔ [w] ∈ F′ ⇔ w ∈ L. ML একটি DFA, আর L(ML) = L, তাই L regular. ∎ — ধাপ ৩ আর ৪
লক্ষ করুন, প্রমাণে কোথাও “চালাক অনুমান” নেই। প্রতিটি ধাপ সংজ্ঞা থেকে আসে, আর ভারী কাজটি করে right-invariance. এই কারণেই উপপাদ্যটি এত শক্তিশালী: একটি language-এর ভেতরেই তার সবচেয়ে ভালো যন্ত্রটি লুকিয়ে আছে, বাইরে থেকে কিছু আনতে হয় না।
উপপাদ্যটির নাম দুজন গণিতবিদের নামে। John Myhill ১৯৫৭ সালে মার্কিন বিমানবাহিনীর একটি গবেষণা প্রতিবেদনে (WADD Technical Report হিসেবে উল্লেখ পাওয়া যায়) finite automaton আর “event”-এর সম্পর্ক নিয়ে লেখেন; তাঁর রূপটি দুই দিক থেকে জোড়ার (two-sided congruence) ভাষায়, যা পরে syntactic monoid-এর ধারণায় গিয়েছে। Anil Nerode ১৯৫৮ সালে Proceedings of the American Mathematical Society-তে “Linear automaton transformations” প্রবন্ধে ডান দিকের relation-টি দেন, যা আজ ≡L নামে পরিচিত। Rabin আর Scott-এর ১৯৫৯ সালের বিখ্যাত প্রবন্ধও (পর্ব ১০) একই ধরনের ফল ব্যবহার করে। কোন রূপ কার, এ নিয়ে বইভেদে বর্ণনা একটু আলাদা; সাধারণ নামটি তাই দুজনের যৌথ।
৪ · Class থেকে minimal DFA — নির্মাণ আর অনন্যতা
(৩) ⇒ (১)-এর যন্ত্রটির একটি নাম আছে: quotient automaton, বা Myhill–Nerode automaton. এটি শুধু একটি DFA নয়, বরং সবচেয়ে ছোট DFA. কারণটি (২) ⇒ (৩)-এর প্রমাণেই লুকিয়ে আছে।
L regular আর index(≡L) = k হলে (ক) L চেনে এমন প্রতিটি DFA-তে অন্তত k-টি state আছে; (খ) ML-এ ঠিক k-টি state, তাই এটি একটি minimal DFA; (গ) k state-এর যেকোনো DFA, যা L চেনে, ML-এর সঙ্গে isomorphic, অর্থাৎ state-এর নাম বদল ছাড়া হুবহু এক।
প্রমাণের রূপরেখা:
- (ক): M যেকোনো DFA আর L(M) = L. (১) ⇒ (২)-এ ≡M right-invariant, সসীম index, আর L তার class-এর union; তাই (২) ⇒ (৩) অনুযায়ী ≡M হলো ≡L-এর refinement, আর |Q| ≥ index(≡M) ≥ index(≡L) = k. — অংশ ৩-এর দুই ধাপ
- (খ): ML-এর state ঠিক ≡L-এর class, তাই k-টি। (ক) বলে এর কমে অসম্ভব। — নির্মাণ
- (গ): M-এ k-টি state থাকলে ধাপ ১-এর অসমতা সমতা হয়, তাই প্রতিটি state reachable আর ≡M = ≡L. এখন φ(δ̂(q0, x)) = [x] দিয়ে একটি মিল সংজ্ঞায়িত করুন। δ̂(q0, x) = δ̂(q0, y) হলে x ≡L y, তাই φ সুসংজ্ঞিত; এটি এক-এক ও সবগুলোর ওপর, শুরুকে শুরুতে, accepting-কে accepting-এ, আর δ(q, a)-কে δ′(φ(q), a)-তে পাঠায়। তাই φ একটি isomorphism. ∎ — ≡M = ≡L
এই ফলের একটি সুন্দর ব্যবহারিক দিক: একটি regular language-এর “সঠিক” DFA একটিই। দুজন প্রকৌশলী দুই রকম নকশা করলেও, দুটিকে minimise করলে একই যন্ত্র আসবে। কোনো DFA-কে minimal-এ নামানোর algorithm (unreachable state মোছা, তারপর আলাদা করা যায় না এমন state জোড়া লাগানো) পর্ব ১৯-এর বিষয়। এখানে আমরা language-এর সংজ্ঞা থেকে সরাসরি নির্মাণটি দেখি।
1Q′ = class, শুরু [ε]2[ε]-এর দুই তীর3[a]-এর দুই তীর4[ab]-এর দুই তীর5F′ আর সুসংজ্ঞা যাচাই6abab পড়ে দেখা
| হিসাব | |
| নতুন তীর | |
| মোট তীর | |
| state ক্রম |
- State. অংশ ২-এর তিনটি class-ই state: [ε], [a], [ab]. শুরুর state [ε], কারণ কিছু না পড়লে আমরা ε-এর class-এ।
- [ε] থেকে। প্রতিনিধি ε-এর পরে a জুড়লে a, যা [a]-তে; b জুড়লে b, যা অংশ ২-এর ধাপ ৩ অনুযায়ী [ε]-তে। তাই [ε] থেকে a-তে [a], b-তে নিজের কাছে।
- [a] থেকে। aa শেষে a, তাই [a]; ab-এর class [ab]. প্রতিনিধি হিসেবে a-র বদলে ba নিলেও baa ∈ [a] আর bab ∈ [ab], একই উত্তর। এটিই δ′-এর সুসংজ্ঞা, right-invariance থেকে।
- [ab] থেকে। aba শেষে a, তাই [a]; abb-এর শেষে ab নেই, a-ও নেই, তাই [ε]. লক্ষ করুন, ab দিয়ে শেষ হওয়ার পর একটি b এলে “অগ্রগতি” পুরো মুছে যায়।
- Accepting. ab ∈ Lab, তাই [ab] ∈ F′; ε আর a L-এর বাইরে। প্রতিনিধি bab নিলেও baba ∈ [a], babb ∈ [ε]: একই তীর, তাই নির্মাণ প্রতিনিধির ওপর নির্ভর করে না।
- Run. abab পড়লে [ε] → [a] → [ab] → [a] → [ab]: শেষ state accepting, আর সত্যিই abab ab দিয়ে শেষ। নিচের Python ব্লক এই যন্ত্রটিকেই নিজে বানিয়ে দৈর্ঘ্য 10 পর্যন্ত সব 2047টি string-এ সংজ্ঞার সঙ্গে মেলায়: একটিও অমিল নেই।
এই DFA-টি ছবি ১৮.১-এর নিচের অংশ। আগে কেউ হয়তো “শেষ দুটি চিহ্ন মনে রাখা দরকার” ভেবে ৭টি state-এর DFA বানাতেন: ε, a, b, aa, ab, ba, bb. সেটিও সঠিক, কিন্তু তার ≡M হলো ≡L-এর একটি সূক্ষ্মতর ভাগ: b, bb আর ε তিনটি আলাদা state-এ, অথচ তাদের ভবিষ্যৎ এক। অংশ ৮-এর সত্যিকারের run দেখাবে, minimisation সেই ৭টিকে ঠিক ৩টিতে নামায়।
৫ · ক্লাসিক language-এর class গোনা
পরীক্ষায় সবচেয়ে বেশি আসে এই কাজ: একটি language দিয়ে তার Nerode class বর্ণনা করতে বলা, আর তা থেকে minimal DFA-র state-সংখ্যা বলা। পদ্ধতি সবসময় একই: (ক) প্রতিটি class-কে একটি বাক্যে বর্ণনা করুন (“এ পর্যন্ত কী জানা আছে যা ভবিষ্যতের জন্য দরকার”); (খ) দেখান যে প্রতিটি বর্ণনার ভেতরের সবাই সমতুল্য; (গ) প্রতি জোড়া বর্ণনার জন্য একটি বিচ্ছিন্নকারী suffix দিন। নিচের টেবিলের প্রতিটি সংখ্যা অংশ ৭-এর Python ব্লক দৈর্ঘ্য 6 পর্যন্ত string আর দৈর্ঘ্য 5 পর্যন্ত suffix নিয়ে মিলিয়েছে, আর অংশ ৮-এ automata-lib-এর minimisation-ও কয়েকটি মিলিয়েছে।
| Language | Class-এর বর্ণনা | Index |
|---|---|---|
| 1-এর সংখ্যা জোড় (Σ = {0, 1}) | এ পর্যন্ত 1 জোড় / বিজোড়; বিচ্ছিন্নকারী z = ε | ২ |
| ab দিয়ে শেষ (Σ = {a, b}) | শেষে ab / শেষে a / কোনোটিই নয় | ৩ |
| DIV3: binary মান ৩ দিয়ে বিভাজ্য | এ পর্যন্ত মান mod 3 = 0, 1, 2; [ε] = [0], কারণ val(ε) = 0 ধরা হয় | ৩ |
| binary মান ৪ দিয়ে বিভাজ্য | মান 0 বা শেষে 00 / শেষে 1 / শেষে 10 (শুধু শেষ দুই bit দরকার) | ৩ |
| 01 আর 10 substring সমান সংখ্যক | ফাঁকা / প্রথম 0, শেষ 0 / প্রথম 0, শেষ 1 / প্রথম 1, শেষ 1 / প্রথম 1, শেষ 0 | ৫ |
| শেষ থেকে n-তম চিহ্ন 1 (Ln) | শেষ n-টি চিহ্ন (বাঁয়ে 0 বসিয়ে পূরণ করে) | 2n |
| বাজারঘরের অর্ডার কোড BG-dddd (Σ = {B, G, -, d}) | সঠিক prefix ε, B, BG, BG-, BG-d, …, BG-dddd (৮টি) / “আর সম্ভব নয়” | ৯ |
| anbn (n ≥ 0) | [ai] প্রতিটি i-এর জন্য আলাদা, আরও কিছু | অসীম |
কয়েকটি সারি আলাদা করে দেখার মতো। DIV3 আর “৪ দিয়ে বিভাজ্য” দুটিরই index ৩, কিন্তু কারণ ভিন্ন। DIV3-এ ভাগশেষ সত্যিই তিনটি অবস্থা। ৪-এর ক্ষেত্রে ভাগশেষ চারটি (0, 1, 2, 3), কিন্তু ভাগশেষ 1 আর 3-এর ভবিষ্যৎ এক: দুটিই বিজোড়, আর পরে দুটি bit এলেই মান 4-এর গুণিতক হবে কি না তা ঠিক হয় শুধু সেই দুই bit দিয়ে। পর্ব ০৮-এর mod-4 DFA-র ৪টি state তাই একটি বেশি; Myhill–Nerode দেখায় ঠিক কোন দুটি এক।
Ln-এর 2n সংখ্যাটির প্রমাণ (দৈর্ঘ্য n-এর যেকোনো দুটি ভিন্ন string-কে একটি 0i−1 suffix আলাদা করে) পর্ব ১০-এ আছে, এখানে আর পুনরাবৃত্তি নয়। Myhill–Nerode-এর ভাষায় সেই যুক্তি বলে, index(≡Ln) ≥ 2n, আর subset construction-এর DFA দেখায় ≤ 2n; তাই ঠিক 2n. যে যুক্তি পর্ব ১০-এ একটি বিশেষ কৌশল মনে হয়েছিল, সেটি আসলে এই উপপাদ্যের একটি সাধারণ প্রয়োগ।
অর্ডার কোডের সারিটিও শিক্ষণীয়। BG-dddd-এর সঠিক prefix আটটি, আর প্রতিটির ভবিষ্যৎ আলাদা: BG- আর BG-d-কে ddd আলাদা করে (BG-ddd-এ একটি অঙ্ক কম)। বাকি সব string, যেমন G বা BB বা BG-ddddd, একটি class-এ: “যা-ই আসুক, আর গৃহীত হবে না”। এই শেষ class-টিই total DFA-র dead state. তাই minimal total DFA-তে ৯টি state; dead state বাদ দেওয়া partial DFA-তে ৮টি।
৬ · Non-regular প্রমাণ — অসীম জোড়া-জোড়া আলাদা string
(১) ⇔ (৩) উল্টো দিক থেকে পড়লে: ≡L-এর index অসীম হলে L regular নয়। অসীম index দেখানোর সহজতম উপায় হলো অসীম একটি string-সেট দেওয়া, যার প্রতিটি জোড়া distinguishable. এমন সেটকে fooling set বলা হয়, যা পর্ব ১০-এ দেখেছেন।
S ⊆ Σ∗-এর প্রতিটি ভিন্ন জোড়া x, y ∈ S-এর জন্য একটি z থাকলে, যাতে xz আর yz-এর ঠিক একটি L-এ, তাহলে (ক) L চেনে এমন প্রতিটি DFA-তে অন্তত |S|টি state; (খ) S অসীম হলে L regular নয়।
প্রমাণ:
- S-এর ভিন্ন দুটি সদস্য কখনো একই ≡L-class-এ নেই, কারণ তাদের একটি বিচ্ছিন্নকারী suffix আছে। তাই index(≡L) ≥ |S|. — সংজ্ঞা ২.১
- (ক) Corollary ৪.১ (ক) থেকে প্রতিটি DFA-তে ≥ index(≡L) ≥ |S| state. — Corollary ৪.১
- (খ) S অসীম হলে index অসীম, তাই উপপাদ্য ৩.১-এর (৩) মিথ্যা, ফলে (১)-ও মিথ্যা: L regular নয়। ∎ — উপপাদ্য ৩.১
এবার কোর্সের সবচেয়ে পরিচিত non-regular language, L = {anbn : n ≥ 0}, নিচের stepper-এ।
1S = {ε, a, aa, aaa, …}2একটি জোড়া: aa বনাম aaa3সাধারণ জোড়া: aⁱ বনাম aʲ4উপসংহার5k-state DFA কোথায় ভুল করে6Python-এর গোনা
| জোড়া | |
| z | |
| xz, yz | |
| ফল |
- সেট বাছাই। S = {ai : i ≥ 0}. অন্তর্দৃষ্টি: ai পড়ার পর যন্ত্রকে মনে রাখতে হবে ঠিক কয়টি b লাগবে, আর সেই সংখ্যা যেকোনো বড় হতে পারে।
- একটি জোড়া। aa আর aaa. z = bb নিলে aabb ∈ L, কিন্তু aaabb-এ ৩টি a আর ২টি b, তাই ∉ L. এদের ভবিষ্যৎ আলাদা।
- সাধারণ জোড়া। যেকোনো i ≠ j-এ z = bi: aibi ∈ L, আর ajbi-এ a আর b-এর সংখ্যা অসমান, তাই ∉ L. তাই S-এর প্রতিটি জোড়া distinguishable.
- উপসংহার। S অসীম fooling set, তাই index(≡L) অসীম, আর উপপাদ্য ৬.১ (খ) অনুযায়ী anbn regular নয়। প্রমাণে কোনো ক্ষেত্রভাগ লাগেনি।
- যন্ত্রের দিক থেকে। k-state যেকোনো DFA নিন। a0, …, ak এই k + 1টি string-এর দুটি, ai আর aj (i < j ≤ k), pigeonhole নীতিতে একই state-এ থামে। তখন aibi আর ajbi-কে যন্ত্র একই উত্তর দেয়, অথচ সঠিক উত্তর আলাদা: দৈর্ঘ্য 2k-এর কম একটি string-এ ভুল।
- Python-এ গোনা। অংশ ৭-এর class finder দৈর্ঘ্য m পর্যন্ত string আর suffix নিয়ে m = 2, 4, 6, 8-এ পায় 5, 9, 13, 17টি class, অর্থাৎ 2m + 1. Regular language-এ সংখ্যাটি কোনো এক সময় থেমে যেত; এখানে থামে না। এটি প্রমাণ নয়, শুধু ধাপ ৩-এর প্রমাণের সঙ্গে মিল।
একই কৌশলে আরও কয়েকটি ক্লাসিক language. প্রতিটিতে S আর বিচ্ছিন্নকারী z দেওয়াই পুরো প্রমাণ:
- সুষম বন্ধনী (Σ = {(, )}): S = {(i : i ≥ 0}, আর i ≠ j হলে z = )i. (i)i সুষম, (j)i নয়। বাজারঘরের order query language-এর বন্ধনী যাচাই তাই কোনো regex দিয়ে সম্পূর্ণভাবে করা যায় না।
- Palindrome (Σ = {0, 1}): S = {0i1 : i ≥ 0}, z = 0i. 0i10i palindrome, কিন্তু i ≠ j হলে 0j10i নয়, কারণ উল্টালে 0i10j.
- {aibjck : i = 0 অথবা j = k}: এই language pumping lemma-র শর্ত পূরণ করে, তাই pumping lemma দিয়ে একে non-regular প্রমাণ করা যায় না (পর্ব ১৭ এটি বিস্তারিত দেখায়)। Myhill–Nerode সহজে পারে: S = {abj : j ≥ 0}, z = cj. abjcj ∈ L (j = k), কিন্তু i ≠ j হলে abicj ∉ L, কারণ a-র সংখ্যা 1 ≠ 0 আর b-c সংখ্যা অসমান।
শেষ উদাহরণটিই দুই পদ্ধতির মূল পার্থক্য দেখায়। Pumping lemma শুধু একটি প্রয়োজনীয় শর্ত: regular হলে pump হয়, কিন্তু pump হলেই regular নয়। Myhill–Nerode একটি “যদি এবং কেবল যদি”: L non-regular হলে একটি অসীম fooling set সবসময় আছে, কারণ index অসীম মানেই অসীম সংখ্যক class, আর প্রতিটি class থেকে একটি করে প্রতিনিধি নিলেই সেটি পাওয়া যায়। কঠিন কাজ শুধু সেটি খুঁজে পাওয়া।
| দিক | Pumping lemma (পর্ব ১৭) | Myhill–Nerode |
|---|---|---|
| যুক্তির ধরন | প্রয়োজনীয় শর্ত মাত্র | প্রয়োজনীয় ও যথেষ্ট (⇔) |
| non-regular প্রমাণে কী দেখাতে হয় | একটি s, আর প্রতিটি সম্ভাব্য split-এ একটি i | একটি অসীম সেট আর প্রতি জোড়ায় একটি z |
| ক্ষেত্রভাগ | প্রায়ই লাগে (y কোথায় পড়ল) | সাধারণত লাগে না |
| সবসময় কাজ করে? | না, কিছু non-regular language pump হয় | হ্যাঁ, অন্তত তত্ত্বে |
| বাড়তি ফল | নেই | minimal DFA-র state-সংখ্যা আর গঠন |
৭ · ব্রাউজারের Python-এ class খোঁজা
≡L-এর সংজ্ঞায় “প্রতিটি z” আছে, আর z অসীম সংখ্যক। কম্পিউটার তাই সংজ্ঞাটি সরাসরি পরীক্ষা করতে পারে না। একটি সৎ approximation: দৈর্ঘ্য ≤ m-এর প্রতিটি x-এর জন্য দৈর্ঘ্য ≤ k-এর সব z-এ উত্তরের একটি “স্বাক্ষর” (tuple) বানানো, আর একই স্বাক্ষরের x-গুলোকে এক দলে রাখা। নিচের ব্লক ঠিক তা করে, আর language দেওয়া হয় একটি সাধারণ Python predicate হিসেবে, যেমন w.endswith("ab"). পরের ব্লক এর function-গুলো ব্যবহার করবে (data-shared), তাই আগে এটি চালান।
from itertools import product
def words(sigma, n): # all strings of length 0..n, shortlex
return ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
def classes(L, sigma, m, k):
"""Group strings of length <= m by their answers on every suffix of length <= k."""
sufs, groups = words(sigma, k), {}
for x in words(sigma, m):
sig = tuple(L(x + z) for z in sufs)
groups.setdefault(sig, []).append(x)
return list(groups.values())
val = lambda w: int(w, 2) if w else 0
langs = {
"ends with ab": (lambda w: w.endswith("ab"), "ab"),
"even number of 1s": (lambda w: w.count("1") % 2 == 0, "01"),
"DIV3 (binary)": (lambda w: val(w) % 3 == 0, "01"),
"#01 = #10": (lambda w: w.count("01") == w.count("10"), "01"),
"3rd from end is 1": (lambda w: len(w) >= 3 and w[-3] == "1", "01"),
}
for name, (L, sigma) in langs.items():
cl = classes(L, sigma, 6, 5)
print(f"{name:18} {len(cl)} classes:", " ".join(c[0] or "ε" for c in cl))
for c in classes(langs["ends with ab"][0], "ab", 3, 2):
print(" ends ab class:", " ".join(w or "ε" for w in c))
L5 = lambda w: len(w) >= 5 and w[-5] == "1"
print("5th from end, suffixes up to k = 0..5:",
[len(classes(L5, "01", 6, k)) for k in range(6)])আসল আউটপুট (ব্রাউজারের Python):
ends with ab 3 classes: ε a ab
even number of 1s 2 classes: ε 1
DIV3 (binary) 3 classes: ε 1 10
#01 = #10 5 classes: ε 0 1 01 10
3rd from end is 1 8 classes: ε 1 10 11 100 101 110 111
ends ab class: ε b bb abb bbb
ends ab class: a aa ba aaa aba baa bba
ends ab class: ab aab bab
5th from end, suffixes up to k = 0..5: [2, 4, 8, 16, 32, 32]
প্রথম পাঁচ লাইনের সংখ্যা অংশ ৫-এর টেবিলের সঙ্গে মেলে, আর প্রতিটি class-এর নাম তার shortlex-এ প্রথম সদস্য। “3rd from end”-এর ৮টি প্রতিনিধি ঠিক দৈর্ঘ্য ≤ 3-এর সেই string-গুলো যাদের প্রথম চিহ্ন 1 বা যারা ফাঁকা: “শেষ তিনটি চিহ্ন, বাঁয়ে 0 বসিয়ে” বর্ণনার সঙ্গে হুবহু এক। পরের তিন লাইন stepper-এর তিনটি class, দৈর্ঘ্য ৩ পর্যন্ত সব সদস্যসহ।
শেষ লাইনটি পদ্ধতির সীমা দেখায়। “শেষ থেকে ৫ম চিহ্ন 1”-এর আসল index 25 = 32, কিন্তু suffix-এর দৈর্ঘ্য k = 0 নিলে মাত্র ২টি দল (শুধু “L-এ আছে কি না”), k = 1-এ ৪টি, এভাবে দ্বিগুণ হয়ে k = 4-এ পূর্ণ ৩২. ছোট k-তে বহু ভিন্ন class এক দলে মিশে যায়, কারণ তাদের আলাদা করার মতো লম্বা suffix পরীক্ষা করা হয়নি। তাই এই পদ্ধতির একটি নিরাপদ ব্যাখ্যা আছে: পাওয়া দলগুলোর প্রতিনিধিরা সত্যিই জোড়ায় জোড়ায় আলাদা (একটি বিচ্ছিন্নকারী z পাওয়া গেছে), তাই দলের সংখ্যা index-এর একটি নিম্নসীমা. সমান কি না তা জানতে আলাদা যুক্তি লাগে।
সেই আলাদা যুক্তি কখন পাওয়া যায়? যদি জানা থাকে L-এর কোনো n-state DFA আছে, তাহলে একটি পরিচিত ফল বলে: n-state DFA-র দুটি আলাদা state-কে দৈর্ঘ্য বড়জোর n − 2-এর একটি string আলাদা করে (ফলটি সাধারণত E. F. Moore-এর ১৯৫৬ সালের কাজের সঙ্গে যুক্ত, আর পর্ব ১৯-এর refinement round গুনে প্রমাণ করা যায়), আর প্রতিটি reachable state-এ দৈর্ঘ্য বড়জোর n − 1-এর string দিয়ে পৌঁছানো যায়। তাই m ≥ n − 1 আর k ≥ n − 2 নিলে class finder ঠিক index পায়। কিন্তু L যদি শুধু একটি predicate হয়, আর কোনো DFA-র আকার জানা না থাকে, তাহলে কোনো সসীম m, k নিশ্চয়তা দেয় না। এটি “কালো বাক্স পরীক্ষা”-র একটি মৌলিক সীমা।
পরের ব্লক এই দলগুলো থেকে অংশ ৪-এর quotient automaton বানায়: প্রতিটি দলের প্রথম সদস্য নাম, আর δ([x], a) = x + a-র দল। তারপর যন্ত্রটিকে দৈর্ঘ্য 10 পর্যন্ত সব string-এ মূল predicate-এর সঙ্গে মেলায়। শেষে anbn-এর জন্য m বাড়িয়ে দলের সংখ্যা গোনে।
def quotient(L, sigma, m, k):
sufs = words(sigma, k)
sig = lambda x: tuple(L(x + z) for z in sufs)
name = {sig(c[0]): c[0] for c in classes(L, sigma, m, k)} # shortest member
delta = {(x, a): name[sig(x + a)] for x in name.values() for a in sigma}
return list(name.values()), delta, {x for x in name.values() if L(x)}
def check(L, sigma, m, k, n=10):
Q, delta, F = quotient(L, sigma, m, k)
def run(w):
q = "" # start state [ε]
for a in w: q = delta[q, a]
return q
bad = sum((run(w) in F) != L(w) for w in words(sigma, n))
return Q, delta, F, bad, len(words(sigma, n))
Q, delta, F, bad, total = check(langs["ends with ab"][0], "ab", 4, 3)
for q in Q:
print(f"[{q or 'ε'}]", " ".join(f"{a}→[{delta[q, a] or 'ε'}]" for a in "ab"),
"accepting" if q in F else "")
print(f"quotient DFA vs definition: {bad} wrong of {total}")
Q, delta, F, bad, total = check(langs["DIV3 (binary)"][0], "01", 4, 3)
print("DIV3:", len(Q), "states, wrong:", bad, "of", total)
anbn = lambda w: w == "a" * (len(w) // 2) + "b" * (len(w) // 2)
for m in (2, 4, 6, 8):
print(f"a^n b^n, strings up to length {m}: {len(classes(anbn, 'ab', m, m))} classes found")
print("a^2 vs a^3 with suffix bb:", anbn("aa" + "bb"), anbn("aaa" + "bb"))আসল আউটপুট (ব্রাউজারের Python):
[ε] a→[a] b→[ε]
[a] a→[a] b→[ab]
[ab] a→[a] b→[ε] accepting
quotient DFA vs definition: 0 wrong of 2047
DIV3: 3 states, wrong: 0 of 2047
a^n b^n, strings up to length 2: 5 classes found
a^n b^n, strings up to length 4: 9 classes found
a^n b^n, strings up to length 6: 13 classes found
a^n b^n, strings up to length 8: 17 classes found
a^2 vs a^3 with suffix bb: True False
প্রথম তিন লাইন stepper-এর ছয়টি তীর, হুবহু। Code নিজে class থেকে যন্ত্রটি বানিয়েছে, কোনো DFA হাতে লিখে দেওয়া হয়নি, আর 2047টি string-এ একটিও ভুল নেই। DIV3-এর quotient-ও ৩ state-এর আর নিখুঁত। delta বানানোর লাইনে name[sig(x + a)] একটি নীরব পরীক্ষাও: x + a-র স্বাক্ষর যদি আগে পাওয়া কোনো দলের না হতো, Python KeyError দিত, অর্থাৎ m যথেষ্ট বড় নয়।
anbn-এ দলের সংখ্যা 5, 9, 13, 17, অর্থাৎ 2m + 1: a0 থেকে am (m + 1টি), “আরও d-টি b দরকার” ধরনের aibj (j ≥ 1) দল (m − 1টি), আর একটি “আর সম্ভব নয়” দল। সংখ্যাটি m-এর সঙ্গে বাড়তেই থাকে। শেষ লাইন stepper-এর ধাপ ২: aabb ∈ L, aaabb ∉ L.
এবার উল্টো দিকের প্রশ্ন: দুটি নির্দিষ্ট string দিলে সবচেয়ে ছোট বিচ্ছিন্নকারী suffix কী? নিচের JavaScript ব্লক z-গুলো দৈর্ঘ্য অনুযায়ী স্তরে স্তরে (breadth-first) পরীক্ষা করে, তাই প্রথম যেটি পায় সেটিই সবচেয়ে ছোট। পরীক্ষায় “x আর y একই class-এ নয়, দেখান” প্রশ্নের উত্তর এই z.
// Shortest suffix z with exactly one of xz, yz in L (breadth-first over z).
function separate(L, sigma, x, y, maxLen) {
let layer = [""];
for (let n = 0; n <= maxLen; n++) {
for (const z of layer) if (L(x + z) !== L(y + z)) return z;
layer = layer.flatMap(z => [...sigma].map(c => z + c));
}
return null; // none up to maxLen: a hint, not a proof
}
const count = (w, p) => [...w].filter((c, i) => w.startsWith(p, i)).length;
const langs = {
"ends ab": [w => w.endsWith("ab"), "ab"],
"#01=#10": [w => count(w, "01") === count(w, "10"), "01"],
"DIV3": [w => w === "" || BigInt("0b" + w) % 3n === 0n, "01"],
"anbn": [w => w === "a".repeat(w.length / 2) + "b".repeat(w.length / 2), "ab"],
};
const pairs = [["ends ab", "ab", "bab"], ["ends ab", "a", "b"], ["ends ab", "", "ab"],
["#01=#10", "0", "1"], ["DIV3", "1", "100"], ["DIV3", "1", "10"],
["anbn", "aa", "aaa"], ["anbn", "aaab", "aab"], ["anbn", "ab", "aabb"]];
const t0 = performance.now();
for (const [name, x, y] of pairs) {
const [L, sigma] = langs[name];
const z = separate(L, sigma, x, y, 8);
const show = s => s === "" ? "ε" : s;
console.log(name.padEnd(8), show(x).padStart(4), "vs", show(y).padEnd(4), "→",
z === null ? "no separator up to length 8" : "z = " + show(z));
}
console.log("all pairs in under 1 s:", performance.now() - t0 < 1000);আসল আউটপুট (ব্রাউজারের JavaScript):
ends ab ab vs bab → no separator up to length 8
ends ab a vs b → z = b
ends ab ε vs ab → z = ε
#01=#10 0 vs 1 → z = 0
DIV3 1 vs 100 → no separator up to length 8
DIV3 1 vs 10 → z = 1
anbn aa vs aaa → z = bb
anbn aaab vs aab → z = b
anbn ab vs aabb → no separator up to length 8
all pairs in under 1 s: true
প্রতিটি লাইন হাতে মিলিয়ে দেখার মতো। 0 আর 1 প্রথম নজরে “সমান” মনে হতে পারে (দুটিই language-এ, কারণ কোনো 01 বা 10 নেই), কিন্তু z = 0 দিলে 00 language-এ থাকে আর 10 থাকে না। DIV3-এ 1 আর 100-এর মান 1 আর 4, দুটিরই ভাগশেষ 1, তাই কোনো z তাদের আলাদা করে না; 1 আর 10-কে z = 1 আলাদা করে, কারণ 11 = 3 আর 101 = 5. anbn-এ aaab-এর আরও দুটি b লাগে, aab-এর একটি, তাই z = b. আর ab ও aabb দুটিই সম্পূর্ণ: আর একটি চিহ্নও এলে দুটিই বাইরে, তাই একই class.
সতর্কতা: “no separator up to length 8” কোনো প্রমাণ নয়। ab আর bab-এর সমতা অংশ ২-এর যুক্তি প্রমাণ করে; DIV3-এর ক্ষেত্রে প্রমাণ হলো ভাগশেষের যুক্তি। Code শুধু সেই প্রমাণের সঙ্গে দ্বিমত করেনি।
৮ · সত্যিকারের run — automata-lib-এর minimisation বনাম class গোনা
নিজের কোডের ফল একটি স্বাধীন library-তে মেলানো ভালো অভ্যাস। automata-lib (MIT licence) একটি Python automata library, যার DFA.minify() একটি DFA-কে minimal-এ নামায়। Library-র কোডে কোনো network বা usage-reporting অংশ নেই (scratch-এ খুঁজে দেখা হয়েছে)। নিচের script uv দিয়ে বানানো একটি ছোট প্রকল্পে চালানো হয়েছে: automata-lib 9.2.0, Python 3.12. প্রতিটি ক্ষেত্রে ইচ্ছা করে একটি বড় (non-minimal) DFA দিয়ে শুরু, তারপর minimise করে state গোনা, আর একই DFA-র language-এ suffix-পরীক্ষায় class গোনা। Corollary ৪.১ বলে দুটি সংখ্যা সমান হতে হবে।
from itertools import product
from importlib.metadata import version
from automata.fa.dfa import DFA
print("automata-lib", version("automata-lib"))
def words(sigma, n):
return ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
def nerode_count(dfa, m, k): # classes seen by suffix testing
sufs = words(sorted(dfa.input_symbols), k)
sigs = {tuple(dfa.accepts_input(x + z) for z in sufs)
for x in words(sorted(dfa.input_symbols), m)}
return len(sigs)
def mod_dfa(m, accept): # binary value mod m
t = {f"r{r}": {b: f"r{(2 * r + int(b)) % m}" for b in "01"} for r in range(m)}
return DFA(states=set(t), input_symbols={"0", "1"}, transitions=t,
initial_state="r0", final_states={f"r{r}" for r in accept})
# "ends with ab": remember the last two symbols (7 states, not minimal)
last2 = ["", "a", "b", "aa", "ab", "ba", "bb"]
t = {s: {c: (s + c)[-2:] for c in "ab"} for s in last2}
ends_ab = DFA(states={s or "e" for s in last2}, input_symbols={"a", "b"},
transitions={s or "e": {c: d or "e" for c, d in m.items()} for s, m in t.items()},
initial_state="e", final_states={"ab"})
cases = [("ends ab (last two)", ends_ab, 6, 4),
("div3 via mod 6", mod_dfa(6, {0, 3}), 6, 5),
("div4 via mod 4", mod_dfa(4, {0}), 6, 5),
("div3 via mod 3", mod_dfa(3, {0}), 6, 5)]
for name, d, m, k in cases:
small = d.minify()
print(f"{name:20} states {len(d.states)} -> minify {len(small.states)}"
f" | Nerode classes found {nerode_count(d, m, k)} | same language: {small == d}")
# order code BG-dddd over {B, G, -, d}, total DFA with dead state "x"
nxt = {"q0": "B", "q1": "G", "q2": "-", "q3": "d", "q4": "d", "q5": "d", "q6": "d"}
t = {q: {c: (f"q{i + 1}" if nxt.get(q) == c else "x") for c in "BG-d"}
for i, q in enumerate(["q0", "q1", "q2", "q3", "q4", "q5", "q6", "q7"])}
t["x"] = {c: "x" for c in "BG-d"}
code = DFA(states=set(t), input_symbols=set("BG-d"), transitions=t,
initial_state="q0", final_states={"q7"})
print("order code: states", len(code.states), "-> minify", len(code.minify().states))
big = mod_dfa(6, {0, 3}).minify(retain_names=True)
print("merged blocks:", sorted(sorted(s) for s in big.states))সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12):
~/bazarghar-toc$ uv run python nerode_vs_minify.py
automata-lib 9.2.0
ends ab (last two) states 7 -> minify 3 | Nerode classes found 3 | same language: True
div3 via mod 6 states 6 -> minify 3 | Nerode classes found 3 | same language: True
div4 via mod 4 states 4 -> minify 3 | Nerode classes found 3 | same language: True
div3 via mod 3 states 3 -> minify 3 | Nerode classes found 3 | same language: True
order code: states 9 -> minify 9
merged blocks: [['r0', 'r3'], ['r1', 'r4'], ['r2', 'r5']]
প্রতিটি সারিতে দুই স্বাধীন হিসাব একমত: library-র minimisation আর আমাদের suffix-পরীক্ষা। “শেষ দুটি চিহ্ন” DFA-র ৭টি state ৩-এ নামে, যেমন অংশ ৪-এ আশা করা হয়েছিল। “div3 via mod 6” একটি মজার ক্ষেত্র: মান mod 6 মনে রেখে, ভাগশেষ 0 বা 3 হলে গ্রহণ। এটি DIV3-এরই আরেকটি DFA, ৬টি state-এর। শেষ লাইন দেখায় library কোন state জোড়া লাগিয়েছে: r0 আর r3, r1 আর r4, r2 আর r5, অর্থাৎ যাদের ভাগশেষ mod 3-এ এক। Nerode class-এর ভাষায়, x mod 6 = 1 আর x mod 6 = 4-এর ভবিষ্যৎ এক, কারণ ৩ দিয়ে বিভাজ্যতা শুধু mod 3 দেখে। “div3 via mod 3” আগে থেকেই minimal, তাই 3 → 3.
অর্ডার কোডের total DFA (৮টি prefix-state আর dead state x) আগে থেকেই minimal: 9 → 9, অংশ ৫-এর টেবিলের সঙ্গে হুবহু। small == d library-র নিজস্ব language-সমতা পরীক্ষা (পর্ব ২০-এর বিষয়), যা দেখায় minimisation language বদলায়নি। এখানে suffix-পরীক্ষার m, k প্রতিটি ক্ষেত্রে state-সংখ্যা n থেকে n − 1 আর n − 2-এর বেশি রাখা হয়েছে, তাই অংশ ৭-এর Moore-সীমা অনুযায়ী গোনাটি নির্ভরযোগ্য।
একটি ব্যবহারিক দিক মনে রাখার মতো। Class গোনা আসলে একটি মেমরির হিসাব: একটি validator-কে স্ট্রিম হিসেবে অক্ষর পড়ে উত্তর দিতে হলে তাকে ঠিক index(≡L)টি অবস্থা আলাদা রাখতে হবে, অর্থাৎ অন্তত ⌈log2 k⌉ bit মেমরি। বাজারঘরের অর্ডার কোড যাচাইয়ে ৯টি অবস্থা, তাই ৪ bit যথেষ্ট; কিন্তু বন্ধনী-যাচাইয়ে কোনো সসীম মেমরি যথেষ্ট নয়, কারণ index অসীম। এই ধরনের নিম্নসীমা যেকোনো algorithm-এর জন্য খাটে, শুধু একটি নির্দিষ্ট নকশার জন্য নয়, যতক্ষণ algorithm-টি একবার বাঁ থেকে ডানে পড়ে আর সসীম মেমরি ব্যবহার করে।
আরও গভীরে: ≡L-এর দুই-দিকের রূপ, x ~ y ⇔ ∀ u, v (uxv ∈ L ⇔ uyv ∈ L), দিয়ে class-গুলো একটি সসীম monoid গঠন করে, যার নাম syntactic monoid; এর গঠন দিয়ে language-এর ধর্ম চেনা যায়, যেমন Schützenberger-এর ১৯৬৫ সালের ফল হিসেবে পরিচিত উপপাদ্য: একটি regular language star ছাড়া (union, concatenation আর complement দিয়ে) লেখা যায় ঠিক তখন, যখন এর syntactic monoid-এ কোনো অতুচ্ছ group নেই। আরেকটি প্রয়োগ automaton শেখা: Dana Angluin-এর ১৯৮৭ সালের L* algorithm একটি “শিক্ষক”-কে membership প্রশ্ন (“এই string কি L-এ?”) আর equivalence প্রশ্ন (“এই DFA কি সঠিক?”) করে, prefix-এর সারি আর suffix-এর কলামের একটি টেবিলে ঠিক অংশ ৭-এর স্বাক্ষর বানিয়ে Nerode class খোঁজে, আর শেষে minimal DFA দেয়; network protocol বা software-এর আচরণ থেকে model শেখার গবেষণায় এর নানা রূপ ব্যবহৃত হয়। Myhill–Nerode-ধরনের উপপাদ্য context-free language-এর জন্য নেই বললেই চলে: সেখানে class-সংখ্যা সাধারণত অসীম, আর minimal PDA বা grammar খোঁজার প্রশ্ন অনেক কঠিন (পর্ব ৩৭-এর সীমা)।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Myhill–Nerode theorem বলুন আর প্রমাণ করুন। L regular ⇔ ≡L-এর index সসীম; (১) ⇒ (২) ⇒ (৩) ⇒ (১) চক্র, আর (৩) ⇒ (১)-এ δ([x], a) = [xa]-এর সুসংজ্ঞা right-invariance থেকে।
- একটি language-এর equivalence class বের করুন আর minimal DFA আঁকুন। প্রতিটি class-এর এক বাক্যের বর্ণনা, প্রতি জোড়ার জন্য একটি বিচ্ছিন্নকারী z, তারপর class থেকে তীর।
- Myhill–Nerode দিয়ে anbn বা palindrome non-regular প্রমাণ করুন। অসীম S = {ai} আর z = bi, বা S = {0i1} আর z = 0i.
- Pumping lemma আর Myhill–Nerode-এর পার্থক্য কী? প্রথমটি শুধু প্রয়োজনীয় শর্ত, দ্বিতীয়টি ⇔; {aibjck : i = 0 অথবা j = k} pump হয়, তবু non-regular.
- Minimal DFA কি অনন্য? হ্যাঁ, state-এর নাম বদল ছাড়া; কারণ যেকোনো minimal DFA-র ≡M ঠিক ≡L.
৯ · AI-এর যুগে Myhill–Nerode
AI assistant-কে একটি language-এর equivalence class জিজ্ঞেস করলে সে প্রায়ই আত্মবিশ্বাসী একটি তালিকা দেয়। তালিকাটি দেখতে গোছানো, কিন্তু প্রতিটি দাবি দুটি প্রশ্নে পরীক্ষা করা যায়: একই class-এর সবাই কি সত্যিই সমতুল্য, আর ভিন্ন class-এর প্রতিনিধিরা কি সত্যিই আলাদা? এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| দুটি class-কে এক বলা, যেমন “#01 = #10”-এ 0 আর 1-কে একই class-এ রাখা | JavaScript ব্লকের মতো সবচেয়ে ছোট বিচ্ছিন্নকারী z খোঁজা: z = 0 |
| Dead state-এর class ভুলে যাওয়া, যেমন অর্ডার কোডে ৮টি class বলা | “আর কখনো গৃহীত হবে না” এমন string, যেমন G, কোন class-এ তা জিজ্ঞেস করা |
| “bi দিয়ে ai আলাদা হয়” বলে a∗b∗-কে non-regular দাবি | ajbi-ও a∗b∗-এ আছে কি না দেখা: আছে, তাই z আলাদা করে না |
| বাঁ দিকে জুড়ে right-invariance ব্যবহার, বা উল্টো দিকে প্রমাণ | ε ≡ b কিন্তু a ≢ ab (Lab) পাল্টা-উদাহরণ মনে রাখা |
| “দৈর্ঘ্য 8 পর্যন্ত কোনো z পাইনি, তাই সমতুল্য” ধরনের দাবি | একটি প্রমাণ চাওয়া (যেমন ভাগশেষের যুক্তি), বা DFA-র আকারের সীমা থেকে Moore-সীমা ব্যবহার |
| “Myhill–Nerode শুধু একটি প্রয়োজনীয় শর্ত” বা উল্টো, “pumping lemma ⇔” | উপপাদ্যের ঠিক বক্তব্য পাঠ্যবইয়ে দেখা: M–N ⇔, pumping শুধু ⇒ |
| বানানো সাল বা রেফারেন্স, যেমন উপপাদ্যটিকে ১৯৭০-এর দশকে বসানো | Hopcroft–Motwani–Ullman বা Sipser-এর অনুশীলন অংশে নিজে খুঁজে দেখা |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু class-এর তালিকা নয়, প্রতি জোড়ার বিচ্ছিন্নকারী suffix আর একটি স্বাধীন যাচাইয়ের কোড চাওয়া, তারপর সেটি নিজে চালানো।
(নিজে যাচাই করুন: সঠিক উত্তরে ৩টি class, প্রতিনিধি ε, a আর aa; অনুশীলন ১-এ পুরো হিসাব আছে, আর উপরের nerode_classes.py ব্লকে predicate বদলে lambda w: "aa" in w বসিয়ে নিজেই গুনে দেখতে পারেন।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Pumping lemma থাকতে Myhill–Nerode কেন দরকার? একটি “প্রয়োজনীয় শর্ত” আর একটি “পূর্ণ বর্ণনা”-র পার্থক্য বাস্তবে কতটা বড়?
Pumping lemma বলে: L regular হলে একটি p আছে, যাতে লম্বা প্রতিটি string-এর একটি ছোট অংশ বারবার “পাম্প” করা যায়। এটি একমুখী: regular ⇒ pump হয়। উল্টোটি সত্য নয়। {aibjck : i = 0 অথবা j = k} এর পরিচিত উদাহরণ: প্রথম চিহ্নটি পাম্প করলে সবসময় language-এই থাকা যায়, কারণ a-র সংখ্যা বদলালেও হয় j = k শর্ত অক্ষত থাকে, নয়তো a-র সংখ্যা 0-তে নেমে অন্য শর্তটি খাটে। তাই pumping lemma দিয়ে এই language-এর বিরুদ্ধে কোনো যুক্তি দাঁড়ায় না, অথচ এটি regular নয়।
Myhill–Nerode এখানে এক লাইনে কাজ সারে: abj ধরনের string-গুলো জোড়ায় জোড়ায় cj দিয়ে আলাদা। পার্থক্যের মূলে আছে উপপাদ্যের রূপ। Myhill–Nerode একটি “যদি এবং কেবল যদি”: non-regular হলে অসীম fooling set সবসময় আছে, কারণ index অসীম আর প্রতিটি class থেকে একজন প্রতিনিধি নিলেই সেট পাওয়া যায়। তাই কোনো non-regular language-এর বিরুদ্ধে এই পদ্ধতি নীতিগতভাবে ব্যর্থ হয় না; ব্যর্থ হতে পারে শুধু আমাদের খোঁজার দক্ষতা।
বাস্তবে পার্থক্যটি আরও দুই জায়গায় চোখে পড়ে। প্রথমত, pumping প্রমাণে প্রায়ই ক্ষেত্রভাগ লাগে: y কোথায় পড়ল, শুধু a-তে, নাকি সীমানা পেরিয়ে। Myhill–Nerode প্রমাণে সাধারণত একটি সেট আর একটি suffix-সূত্রই যথেষ্ট, যা ভুলের সুযোগ কমায়। দ্বিতীয়ত, Myhill–Nerode শুধু “না” বলে না, “হ্যাঁ”-ও বলে, আর সঙ্গে একটি সংখ্যা দেয়: regular হলে minimal DFA-তে ঠিক কয়টি state. Pumping lemma regular language-এর কোনো যন্ত্রের আকার সম্পর্কে প্রায় কিছুই বলে না।
তবু pumping lemma ফেলে দেওয়ার মতো নয়। কিছু language-এ, যেমন an² বা ap (p prime), pumping-এর যুক্তি খুব স্বাভাবিক, আর context-free language-এর জন্য pumping lemma-র একটি রূপ আছে (পর্ব ৩৬), কিন্তু Myhill–Nerode-এর মতো সরল পূর্ণ বর্ণনা নেই। পরীক্ষায় দুটিই জানা ভালো, আর একটি দিয়ে আটকে গেলে অন্যটি চেষ্টা করা।
মূল উপলব্ধি: Pumping lemma একটি পরীক্ষা যা কিছু non-regular language ফসকে যায়; Myhill–Nerode একটি পূর্ণ সংজ্ঞা যা কাউকে ফসকায় না, আর সঙ্গে minimal DFA-র আকারও দেয়।
প্র ০২“একটি state = যাদের ভবিষ্যৎ এক এমন অতীতের দল” — এই ধারণা DFA নকশার বাইরে আর কোথায় দেখা যায়?
ধারণাটির শিকড় পুরোনো। E. F. Moore-এর ১৯৫৬ সালের “Gedanken-experiments on sequential machines” প্রবন্ধের প্রশ্ন ছিল প্রায় দার্শনিক: একটি যন্ত্রকে কালো বাক্স হিসেবে পেলে, শুধু input দিয়ে আর output দেখে তার ভেতরের অবস্থা সম্পর্কে কী জানা যায়? উত্তরের কেন্দ্রে ছিল “দুটি state কি কোনো পরীক্ষায় আলাদা করা যায়?”, অর্থাৎ বিচ্ছিন্নকারী suffix. কোনো পরীক্ষায় আলাদা করা না গেলে বাইরের দুনিয়ার কাছে দুটি state একই।
পদার্থবিজ্ঞান আর নিয়ন্ত্রণতত্ত্বেও একই কথা “state”-এর সংজ্ঞায় আছে: একটি system-এর state হলো অতীতের সেই সংক্ষিপ্তসার, যা ভবিষ্যতের আচরণ নির্ধারণে যথেষ্ট। সম্ভাবনাতত্ত্বে Markov ধর্ম বলে, বর্তমান state জানলে অতীতের বাকি ইতিহাস ভবিষ্যৎ সম্পর্কে কিছু যোগ করে না। Myhill–Nerode এই ধারণাকে সবচেয়ে কঠোর রূপে দেয়: ভবিষ্যৎ মানে “প্রতিটি সম্ভাব্য suffix-এ হ্যাঁ বা না”, আর সবচেয়ে ছোট পর্যাপ্ত সংক্ষিপ্তসার হলো Nerode class.
Software-এও এটি সরাসরি কাজে লাগে। Software Testing কোর্সের পর্ব ১০-এর state-transition testing-এ প্রশ্ন ওঠে: কোন দুটি screen বা অবস্থা আসলে একই, আর কোনগুলো আলাদা করে পরীক্ষা করতে হবে? দুটি অবস্থাকে যদি কোনো ক্রমের input আলাদা ফল দেয়, তারা আলাদা; সেই ক্রমটিই একটি test case. বাজারঘরের checkout flow-এ “কার্টে পণ্য আছে, কুপন দেওয়া হয়নি” আর “কার্টে পণ্য আছে, অবৈধ কুপন বাতিল হয়েছে” একই অবস্থা কি না, তা এভাবেই ঠিক করা যায়।
Compiler আর text-খোঁজার টুলে regex থেকে বানানো DFA প্রায়ই অপ্রয়োজনীয় state-এ ভরা থাকে, আর minimisation (পর্ব ১৯) ঠিক Nerode class-এ নামিয়ে মেমরি বাঁচায়। Machine learning-এর দিকে, Angluin-এর L* algorithm একটি অজানা যন্ত্রকে প্রশ্ন করে এই class-গুলো খুঁজে বের করে, আর পরের গবেষণায় network protocol-এর আচরণ থেকে model শেখায় এর রূপ ব্যবহৃত হয়েছে।
মূল উপলব্ধি: State মানে অতীতের সবচেয়ে ছোট সংক্ষিপ্তসার যা ভবিষ্যৎ ঠিক করে; Myhill–Nerode এই সংক্ষিপ্তসারকে গাণিতিকভাবে সংজ্ঞায়িত করে, আর testing, minimisation ও automaton শেখা তিনটিই এর ওপর দাঁড়িয়ে।
প্র ০৩সসীম সংখ্যক পরীক্ষা দিয়ে কি কখনো প্রমাণ করা যায় যে দুটি string একই class-এ? কালো বাক্স পরীক্ষার সীমা কোথায়?
সাধারণভাবে না। ≡L-এর সংজ্ঞায় “প্রতিটি z”, আর z অসীম সংখ্যক। দৈর্ঘ্য 8 পর্যন্ত কোনো z আলাদা না করলেও দৈর্ঘ্য 9-এর একটি z আলাদা করতে পারে। অংশ ৭-এর “শেষ থেকে ৫ম চিহ্ন” উদাহরণে এটি দেখা গেছে: k = 3 পর্যন্ত suffix দেখলে মাত্র ১৬টি দল, অথচ আসল class ৩২টি। কোনো language-কে শুধু একটি predicate হিসেবে পেলে, যেকোনো সসীম পরীক্ষার পর এমন একটি language বানানো যায় যা সব পরীক্ষিত string-এ মেলে কিন্তু একটি অপরীক্ষিত suffix-এ আলাদা।
কিন্তু একটি বাড়তি তথ্য থাকলে ছবি বদলে যায়: যন্ত্রটির state-সংখ্যার একটি উপরের সীমা। যদি জানা থাকে L-এর কোনো DFA-তে বড়জোর n-টি state, তাহলে দুটি আলাদা state-কে দৈর্ঘ্য বড়জোর n − 2-এর একটি string আলাদা করে। যুক্তিটি পর্ব ১৯-এর refinement-এর: প্রথমে state-গুলোকে “accepting / non-accepting” দুই দলে ভাগ করুন, তারপর প্রতি round-এ একটি চিহ্ন বেশি দেখে দল ভাঙুন। প্রতিটি কার্যকর round দলের সংখ্যা অন্তত একটি বাড়ায়, আর দল n-এর বেশি হতে পারে না, তাই n − 2 round-এর পর আর কিছু বদলায় না। এই ধরনের ফল Moore-এর ১৯৫৬ সালের কাজের সঙ্গে যুক্ত।
এর থেকে hardware ও software testing-এ “conformance testing”-এর একটি পুরো ধারা এসেছে: একটি বাস্তব যন্ত্র একটি নির্দিষ্ট নকশার সঙ্গে মেলে কি না, সসীম test দিয়ে যাচাই করা, যদি যন্ত্রের state-সংখ্যার সীমা জানা থাকে। এই ধারার পরিচিত পদ্ধতিগুলোর একটি সাধারণত Chow-এর ১৯৭৮ সালের W-method নামে উল্লেখ করা হয়; এর মূলে প্রতিটি state-জোড়ার বিচ্ছিন্নকারী suffix-এর একটি সেট।
বাজারঘরের দলের জন্য শিক্ষাটি সোজা। একটি regex বা validator-কে কয়েক হাজার random input দিয়ে পরীক্ষা করা খুব কাজের, ভুল ধরতে দারুণ, কিন্তু সঠিকতার প্রমাণ নয়। প্রমাণ আসে গঠন থেকে: দুটি DFA-র equivalence পরীক্ষা (পর্ব ২০), বা অংশ ২-এর মতো একটি যুক্তি। আর কোড যখন বলে “no separator up to length 8”, তখন সেটি একটি অনুমান, যা প্রমাণ বা Moore-সীমা দিয়ে পাকা করতে হয়।
মূল উপলব্ধি: সসীম পরীক্ষা আলাদা হওয়া প্রমাণ করতে পারে, সমান হওয়া নয়; যন্ত্রের আকারের একটি সীমা জানা থাকলে তবেই সসীম পরীক্ষা পূর্ণ সত্য বলতে পারে।
প্র ০৪DFA-র ক্ষেত্রে minimal যন্ত্র অনন্য, অথচ NFA-র ক্ষেত্রে নয়। Myhill–Nerode এই পার্থক্য কীভাবে ব্যাখ্যা করে?
DFA-তে একটি string পড়ার পর যন্ত্র ঠিক একটি state-এ থাকে। তাই প্রতিটি DFA Σ∗-এর একটি partition দেয় (≡M), আর অংশ ৩-এর প্রমাণ দেখিয়েছে সেই partition সবসময় ≡L-এর refinement. Minimal হলে partition দুটি সমান হতে বাধ্য, আর state ঠিক Nerode class. অর্থাৎ minimal DFA-র প্রতিটি state-এর একটি অর্থ আছে, যা language নিজেই ঠিক করে দেয়, নকশাকারী নন। তাই দুটি minimal DFA-র মধ্যে শুধু নামের পার্থক্য থাকতে পারে।
NFA-তে একটি string পড়ার পর যন্ত্র একসঙ্গে অনেক state-এ থাকতে পারে। NFA-র state আর কোনো partition দেয় না; একটি string একাধিক state-এর “দলে” পড়ে, আর একটি state বহু ভিন্ন ভবিষ্যতের string ধারণ করতে পারে। ফলে NFA-র state-এর কোনো language-নির্ধারিত অর্থ নেই, আর একই language-এর দুটি ভিন্ন গঠনের সবচেয়ে ছোট NFA থাকতে পারে। সবচেয়ে ছোট NFA খুঁজে বের করার সমস্যাটি PSPACE-complete বলে প্রমাণিত (সাধারণত Jiang আর Ravikumar-এর ১৯৯৩ সালের কাজ হিসেবে উল্লেখ করা হয়), যেখানে DFA minimisation দ্রুত (Hopcroft-এর algorithm O(n log n)-এর মতো সময়ে, পর্ব ১৯)।
নিম্নসীমার ক্ষেত্রেও পার্থক্য দেখা যায়। DFA-র জন্য fooling set নিখুঁত: সবচেয়ে বড় fooling set-এর আকার ঠিক minimal DFA-র state-সংখ্যা, কারণ প্রতিটি class থেকে একজন প্রতিনিধি নিলেই সেট হয়। NFA-র জন্য fooling set-এর একটি দুর্বল রূপ আছে (জোড়া (xi, yi) নিয়ে, যেখানে xiyi ∈ L কিন্তু ভিন্ন জোড়া মিশালে বাইরে), যা সাধারণত Glaister আর Shallit-এর ১৯৯৬ সালের কাজের সঙ্গে যুক্ত; কিন্তু এটি শুধু একটি সীমা দেয়, সবসময় সঠিক সংখ্যা নয়।
পর্ব ১০-এর Ln এই পার্থক্যের সবচেয়ে পরিষ্কার ছবি: NFA-তে n + 1টি state, অথচ Myhill–Nerode-এর 2nটি class দেখায় যে কোনো DFA এর কমে পারে না। Nondeterminism “অনুমান” করতে পারে কোথা থেকে শেষ n-টি চিহ্ন শুরু, তাই পুরো ইতিহাস মনে রাখতে হয় না; DFA পারে না।
মূল উপলব্ধি: DFA-র state একটি partition, আর minimal partition language নিজেই ঠিক করে, তাই minimal DFA অনন্য; NFA-র state partition নয়, তাই সেখানে অনন্যতা নেই আর minimisation কঠিন।
প্র ০৫বাজারঘরের একজন প্রকৌশলী বলছেন, “অর্ডার-বন্ধনী যাচাই regex দিয়ে করব, একটু বড় করে লিখলেই হবে।” Myhill–Nerode এই দাবি সম্পর্কে কী বলে, আর বাস্তবে কী করা উচিত?
বাজারঘরের order query language-এ শর্ত বন্ধনী দিয়ে গোছানো যায়, যেমন (পরিমাণ > 2 এবং (জেলা = ঢাকা অথবা জেলা = খুলনা)). বন্ধনী সুষম কি না, তা যাচাইয়ের language-এর জন্য অংশ ৬-এ অসীম fooling set দেখানো হয়েছে: (i-গুলো জোড়ায় জোড়ায় )i দিয়ে আলাদা। তাই কোনো formal regex, যত বড়ই হোক, সব ক্ষেত্রে সঠিক হতে পারে না। এটি “চেষ্টা করে দেখিনি” ধরনের কথা নয়, একটি প্রমাণিত অসম্ভবতা।
প্রকৌশলীর দাবিতে তবু একটি সত্য অংশ আছে। বন্ধনীর গভীরতা যদি একটি নির্দিষ্ট সংখ্যা, ধরুন ৩, পর্যন্ত সীমিত করা হয়, তাহলে language-টি সসীম তথ্যে ধরা যায়: “এখন গভীরতা 0, 1, 2 বা 3, নাকি ইতিমধ্যে ভুল”। Index তখন ৫, আর একটি regex বা DFA ঠিকই কাজ করে। তাই সঠিক প্রশ্ন হলো, ব্যবসার নিয়মে গভীরতার সীমা আছে কি না। সীমা থাকলে, সেটি স্পষ্টভাবে লিখে রাখা আর validator-কে সেই সীমায় পরীক্ষা করা; না থাকলে, regex নয়।
বাস্তব regex engine-এ (Python-এর কিছু library, PCRE) recursion বা backreference-এর মতো বৈশিষ্ট্য আছে, যা formal অর্থে regular নয় আর বন্ধনী মেলাতে পারে। কিন্তু তখন automaton-ভিত্তিক দ্রুততার নিশ্চয়তা চলে যায়, আর backtracking-এর ঝুঁকি আসে; এর বিস্তারিত পর্ব ২১-এ। বন্ধনীযুক্ত ভাষার স্বাভাবিক হাতিয়ার হলো context-free grammar আর parser (পর্ব ২৫ থেকে মডিউল ৭), যেখানে একটি stack অসীম তথ্যের প্রয়োজন মেটায়।
একটি ভালো দলীয় অভ্যাস হলো, নতুন validator লেখার আগে প্রশ্ন করা: “অক্ষর একটি একটি করে পড়তে গিয়ে কী মনে রাখতে হবে, আর তা কি সসীম?” উত্তর সসীম হলে একটি DFA বা regex যথেষ্ট, আর class-সংখ্যাই মেমরির মাপ বলে দেয়। উত্তর অসীম হলে প্রথম দিনেই parser-এর দিকে যাওয়া সময় বাঁচায়। Myhill–Nerode এই প্রশ্নটিকে আন্দাজ থেকে প্রমাণে তোলে।
মূল উপলব্ধি: অসীম fooling set মানে কোনো regex যথেষ্ট নয়, যত বড়ই হোক; সীমিত গভীরতা হলে সসীম class, তাই regex চলে, না হলে grammar আর parser.
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। Predicate বদলে nerode_classes.py ব্লকে বসিয়ে নিজের উত্তরও যাচাই করতে পারেন।
-
নকশা (class থেকে DFA): Σ = {a, b}-এর ওপর L = {w : w-এ aa substring আছে}. (ক) ≡L-এর class-গুলো বর্ণনা করুন আর প্রতি জোড়ার জন্য একটি বিচ্ছিন্নকারী suffix দিন। (খ) Class থেকে minimal DFA নকশা করুন।
(ক) তিনটি class: C0 = [ε] “aa নেই, আর শেষে a নেই” (ε, b, ab, bb, …); C1 = [a] “aa নেই, শেষে একটি a” (a, ba, aba, …); C2 = [aa] “aa আছে” (aa, aaa, aab, baa, …). বিচ্ছিন্নকারী: ε আর a-কে z = a (aa ∈ L, a ∉ L); ε আর aa-কে z = ε; a আর aa-কে z = ε. একই class-এর সমতা: C2-এর সবাই প্রতিটি z-এ L-এ; C0-এর x-এ শেষ চিহ্ন a নয় আর aa নেই, তাই xz-এ aa আছে ⇔ z-এ aa আছে; C1-এ xz-এ aa আছে ⇔ z a দিয়ে শুরু বা z-এ aa আছে।
(খ) শুরু [ε]. [ε]: a → [a], b → [ε]; [a]: a → [aa], b → [ε]; [aa]: a, b দুটিতেই → [aa]. F = {[aa]}. এটি ৩ state-এর DFA, আর [aa] একটি “গৃহীত ফাঁদ”। Scratch-এ class finder দৈর্ঘ্য 5 পর্যন্ত string আর 4 পর্যন্ত suffix নিয়ে ঠিক এই তিন দল দিয়েছে (প্রতিনিধি ε, a, aa).
-
প্রমাণ: Myhill–Nerode theorem ব্যবহার করে প্রমাণ করুন যে L = {ww : w ∈ {0, 1}∗} regular নয়।
- S = {0i1 : i ≥ 0} নিন; এটি অসীম। — প্রার্থী সেট
- i ≠ j নিন আর z = 0i1. তাহলে 0i1·z = 0i10i1 = ww, যেখানে w = 0i1, তাই ∈ L. — সরাসরি
- ধরুন 0j10i1 = uu কোনো u-র জন্য। string-টিতে ঠিক দুটি 1, তাই প্রতিটি অর্ধে একটি, আর দুটি অর্ধই 1 দিয়ে শেষ (শেষ চিহ্ন 1, আর প্রথম অর্ধের শেষে দ্বিতীয় 1-এর আগের অংশ)। অর্থাৎ u = 0t1, আর uu = 0t10t1, যার জন্য j = t = i লাগে। কিন্তু i ≠ j, বিরোধ। তাই 0j10i1 ∉ L. — contradiction
- তাই S-এর প্রতি জোড়া distinguishable, S অসীম fooling set, আর উপপাদ্য ৬.১ (খ) অনুযায়ী L regular নয়। ∎ — উপপাদ্য ৬.১
Scratch-এ i, j < 4-এর সব জোড়ায় দুটি দাবি (ধাপ ২ আর ৩) যাচাই করা হয়েছে, আর class finder দৈর্ঘ্য 6 পর্যন্ত string ও suffix-এ ১২৭টি দল পেয়েছে, যা দৈর্ঘ্য ≤ 6-এর মোট string-এর সংখ্যা: প্রতিটি string আলাদা class-এ।
-
প্রমাণের ভুল ধরুন: দাবি: “L = a∗b∗ regular নয়। প্রমাণ: S = {ai : i ≥ 0} নিন। i ≠ j হলে z = bi তাদের আলাদা করে, কারণ aibi-এ a আর b সমান সংখ্যক। S অসীম, তাই L non-regular. ∎” ভুল কোথায়? L-এর আসল index কত?
বিচ্ছিন্নকারী suffix-এর সংজ্ঞা হলো xz আর yz-এর ঠিক একটি L-এ। এখানে aibi আর ajbi দুটিই a∗b∗-এ আছে, কারণ L-এ a আর b-এর সংখ্যা সমান হওয়ার কোনো শর্ত নেই। “সমান সংখ্যক” কথাটি anbn-এর, এই L-এর নয়। তাই z = bi কিছু আলাদা করে না, আর প্রমাণ ভেঙে পড়ে। আসলে সব ai একই class-এ।
L = a∗b∗-এর index ৩: [ε] = a∗ (এখনো a বা b দুটিই আসতে পারে), [b] = a∗b+ (এখন শুধু b আসতে পারে), আর [ba] = “b-এর পরে a এসেছে” (আর কখনো গৃহীত হবে না)। বিচ্ছিন্নকারী: ε আর b-কে z = a (a ∈ L, ba ∉ L); দুটির কাউকে ba থেকে z = ε. Scratch-এর class finder এই তিন দলই দিয়েছে। শিক্ষা: প্রতিটি z-এ দুটি string বসিয়ে language-এর আসল সংজ্ঞায় পরীক্ষা করুন।
-
আউটপুট অনুমান: L = “binary মান ৪ দিয়ে বিভাজ্য” (val(ε) = 0). nerode_classes.py-এর
classes(L, "01", 6, k)k = 0, 1 আর 5-এ কয়টি দল দেবে, আর k = 5-এ দলগুলোর প্রথম সদস্য কী? কেন k = 0-এ কম?k = 0-এ শুধু z = ε পরীক্ষা হয়, তাই দল দুটি: L-এ আছে (ε, 0, 00, 100, …) আর নেই। k = 1-এ suffix ε, 0, 1. তখন 1 আর 10 আলাদা হয়: z = 0 দিলে 10 (মান 2) ∉ L কিন্তু 100 (মান 4) ∈ L. তাই ৩টি দল, আর k = 5-এও ৩টি, কারণ আসল index ৩ (অংশ ৫-এর টেবিল)। প্রথম সদস্য ε, 1, 10. Scratch-এ k = 0 থেকে 5-এর জন্য ফল এসেছে [2, 3, 3, 3, 3, 3] আর প্রতিনিধি '', '1', '10', অনুমানের সঙ্গে হুবহু।
এখানে minimal DFA-র state ৩টি, তাই Moore-সীমা অনুযায়ী দৈর্ঘ্য ≤ 3 − 2 = 1-এর suffix-ই সব class আলাদা করতে যথেষ্ট, আর k = 1-এই পূর্ণ সংখ্যা এসেছে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি regular language-এর ≡L class থেকে minimal DFA বানানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- ≡L-এর সব class খুঁজে প্রতিটির একজন প্রতিনিধি বাছাই করা
- প্রতিটি class-কে একটি state ধরা, আর [ε]-কে শুরুর state করা
- প্রতিটি class [x] আর চিহ্ন a-র জন্য তীর [x] → [xa] দেওয়া
- যাদের প্রতিনিধি L-এ আছে, সেই class-গুলোকে accepting করা
- Induction-এ δ̂([ε], w) = [w] দেখিয়ে L(M) = L নিশ্চিত করা
Σ = {a, b}-এর ওপর L = {w : w ab দিয়ে শেষ}. ≡L-এর index কত?
- ১
- ২
- ৩
- ৪
L = {anbn : n ≥ 0}. নিচের কোন suffix z, aaa আর aaaaa-কে আলাদা করে (অর্থাৎ ঠিক একটি জোড়া-ফল L-এ)?
- bbb
- bb
- ab
- ε
Myhill–Nerode theorem অনুযায়ী একটি language L regular হয় ঠিক তখন, যখন:
- L pumping lemma-র শর্ত পূরণ করে
- ≡L-এর index সসীম
- L-এ সসীম সংখ্যক string আছে
- ≡L-এর ঠিক একটি class আছে
যেকোনো language L আর x ≡L y হলে নিচের কোনটি সবসময় সত্য?
- প্রতিটি চিহ্ন c-র জন্য cx ≡L cy
- |x| = |y|
- x ∈ L আর y ∉ L হতে পারে
- প্রতিটি চিহ্ন c-র জন্য xc ≡L yc
একটি program দৈর্ঘ্য ≤ 6-এর string-কে দৈর্ঘ্য ≤ 5-এর সব suffix-এ পরীক্ষা করে একটি language-এর জন্য ৭টি আলাদা দল পেয়েছে। কোন সিদ্ধান্তটি নিরাপদ?
- ≡L-এর index ঠিক ৭
- ≡L-এর index অন্তত ৭
- L regular, আর minimal DFA-তে ৭টি state
- L regular নয়
L = {aibjck : i = 0 অথবা j = k}. এটি non-regular প্রমাণের সবচেয়ে উপযুক্ত পথ কোনটি?
- সরাসরি pumping lemma, s = abpcp নিয়ে
- কয়েকবার regex লেখার চেষ্টা করে ব্যর্থ হওয়া
- Myhill–Nerode, অসীম সেট {abj} আর suffix cj দিয়ে
- দৈর্ঘ্য 10 পর্যন্ত brute force চালানো
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- x ≡L y ⇔ প্রতিটি z-এ xz ∈ L ⇔ yz ∈ L. এটি একটি equivalence relation আর right-invariant (ডানে জুড়লে টিকে থাকে, বাঁয়ে নয়)।
- Myhill–Nerode: L regular ⇔ ≡L-এর index সসীম; প্রমাণ (১) DFA ⇒ (২) সসীম right-invariant E ⇒ (৩) সসীম ≡L ⇒ (১).
- Class থেকে DFA: শুরু [ε], δ([x], a) = [xa], F = {[x] : x ∈ L}. এটিই minimal DFA, আর state-এর নাম বদল ছাড়া অনন্য।
- Non-regular প্রমাণ: অসীম fooling set আর প্রতি জোড়ায় একটি z; anbn-এ {ai} আর bi. Pumping lemma যেখানে ব্যর্থ, সেখানেও এটি কাজ করে।
- Suffix পরীক্ষা দিয়ে class গোনা একটি নিম্নসীমা দেয়; DFA-র আকারের সীমা জানা থাকলে (দৈর্ঘ্য n − 2-এর suffix যথেষ্ট) তবেই সঠিক সংখ্যা।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ১৭ · Regular language-এর pumping lemma — non-regular প্রমাণফিরে দেখুনNon-regular প্রমাণের অন্য পথ, আর কেন সেটি শুধু একটি প্রয়োজনীয় শর্ত।
- পর্ব ১০ · NFA থেকে DFA — subset construction আর state বিস্ফোরণফিরে দেখুনLn-এর 2n নিম্নসীমা, যা এই পর্বের fooling set নীতির একটি প্রয়োগ।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ১৯ DFA minimization.
- পর্ব ০২ · প্রয়োজনীয় গণিত — set, relation, function, graph আর countabilityপটভূমিEquivalence relation, class আর partition, যার ওপর এই পর্ব দাঁড়িয়ে।
- পর্ব ০৮ · DFA নকশা — product construction, complement আর গণনার কৌশলপটভূমি“একই ভবিষ্যৎ মানে একই state” ধারণার প্রথম পরিচয় আর mod-4 DFA.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৪ — Finite automaton আর regular expression-এর পরিচয়পটভূমিPumping lemma আর Myhill–Nerode-এর একটি ছোট প্রথম পরিচয়।
- Software Testing · পর্ব ১০ — state-transition testingপাশের ট্র্যাকবিচ্ছিন্নকারী input-ক্রম কীভাবে test case হয়ে ওঠে।