এই পর্বে যা শিখবেন
- GNFA-র formal সংজ্ঞা, আর DFA থেকে GNFA বানানোর তিনটি ধাপ
- State elimination হাতে আর Python-এ করা, প্রতিটি অপসারণের পর regex দেখে
- Elimination-এর সঠিকতার প্রমাণের রূপরেখা, আর Kleene-এর উপপাদ্যের পূর্ণ চিত্র
- Arden-এর সূত্রের প্রমাণ, এর শর্ত ε ∉ L(A) কেন জরুরি, আর state-সমীকরণ সমাধান
- Elimination ক্রম কীভাবে regex-এর আকার বদলায়, আর পাওয়া regex brute force ও random testing দিয়ে যাচাই করা
১ · উল্টো দিকের প্রশ্ন — ছবি থেকে সূত্র
পর্ব ১৩-এ আপনি regular expression-এর formal সংজ্ঞা দেখেছেন: ∅, ε আর একক চিহ্ন থেকে শুরু করে union (∪), concatenation আর Kleene star (∗) দিয়ে গড়া সূত্র। পর্ব ১৪ দেখিয়েছে, যেকোনো regex থেকে একটি ε-NFA বানানো যায় (Thompson construction). এই পর্ব উল্টো দিকটি প্রমাণ করে: যেকোনো finite automaton থেকে একটি regex পাওয়া যায়, যার language ঠিক automaton-টির language. দুই দিক একসঙ্গে মিলে বলে, regex আর automaton একই জিনিসের দুটি ভাষা।
প্রশ্নটি বাস্তবেও ওঠে। ধরুন বাজারঘরের একজন প্রকৌশলী একটি validator-কে state diagram হিসেবে এঁকেছেন: কোন অবস্থায় কোন অক্ষর এলে কোথায় যেতে হবে। এখন আরেকটি টুলে ঠিক সেই নিয়ম বসাতে হবে, আর টুলটি শুধু regex নেয়। ছবিটি দেখে মাথা খাটিয়ে regex লিখলে ভুলের ঝুঁকি থাকে। দরকার একটি যান্ত্রিক পদ্ধতি, যা প্রতিবার সঠিক উত্তর দেবে, আর যার সঠিকতা প্রমাণ করা যায়।
ঢাকার একটি এলাকার রিকশার রুটের মানচিত্র ভাবুন। মোড়গুলো state, রাস্তাগুলো তীর। কেউ জানতে চাইলেন, “বাসস্ট্যান্ড থেকে বাজারে যাওয়ার সব পথ এক লাইনে লিখে দিন।” আপনি একটি একটি করে মাঝের মোড় মানচিত্র থেকে মুছে ফেলেন। কোনো মোড় মোছার আগে, সেই মোড় হয়ে যত পথ যেত, সেগুলো দুই পাশের মোড়ের মধ্যে সরাসরি একটি “লম্বা রাস্তা” হিসেবে লিখে রাখেন: “এখান থেকে ওই মোড়ে ঢুকে, সেখানে যতবার খুশি চক্কর দিয়ে, ওপাশে বেরিয়ে যান।” শেষে শুধু বাসস্ট্যান্ড আর বাজার বাকি থাকে, আর তাদের মাঝের একটি রাস্তার গায়ে লেখা থাকে সব পথের বর্ণনা। State elimination ঠিক এই কাজ।
এই পর্বে দুটি পদ্ধতি দেখবেন। প্রথমটি ছবির ওপর কাজ করে: GNFA আর state elimination, Sipser-এর বইয়ের ধাঁচে। দ্বিতীয়টি বীজগণিতের: প্রতিটি state-এর জন্য একটি language-সমীকরণ লিখে Arden-এর সূত্র দিয়ে একে একে সমাধান। দুটি পদ্ধতি একই উদাহরণে চালিয়ে দেখা যাবে, উত্তর এক।
এই পর্বের notation: DFA M = (Q, Σ, δ, q0, F), যেখানে δ : Q × Σ → Q total (পর্ব ০৭)। Regex-এ union লেখা হয় ∪ দিয়ে; অনেক বই “+” লেখে, আর বাস্তবের টুল (Python, JavaScript) লেখে “|”, তাই কোড ব্লকে “|” দেখবেন। অগ্রাধিকার: star সবচেয়ে আগে, তারপর concatenation, শেষে union. তাই 01∗0 মানে 0(1∗)0, আর ab ∪ c মানে (ab) ∪ c. L(R) হলো regex R-এর language. লেখার সুবিধায় কোড আর stepper-এ star-কে সাধারণ * বা ∗ হিসেবে লাইনের ওপরেই লেখা হয়েছে।
২ · GNFA — তীরের গায়ে পুরো regex
সাধারণ NFA-তে প্রতিটি তীরের গায়ে একটি চিহ্ন বা ε থাকে। State elimination-এর সময় তীরের লেবেল বড় হতে থাকে: “0” থেকে “01∗0”, তারপর আরও বড়। তাই এমন একটি যন্ত্র দরকার যার তীরের গায়ে যেকোনো regex বসতে পারে। তীর ধরে যাওয়ার সময় যন্ত্রটি একবারে একটি গোটা অংশ পড়ে, যে অংশটি সেই তীরের regex-এর language-এ আছে। এর নাম generalized NFA, সংক্ষেপে GNFA.
একটি GNFA হলো G = (Q, Σ, δ, qstart, qaccept), যেখানে Q সসীম state-সেট, Σ alphabet, আর ℛ দিয়ে Σ-এর ওপর সব regex-এর সেট বোঝালে
δ : (Q − {qaccept}) × (Q − {qstart}) → ℛ
অর্থাৎ শুরুর state-এ কোনো তীর ঢোকে না, accepting state থেকে কোনো তীর বের হয় না, qstart ≠ qaccept, আর বাকি প্রতিটি জোড়ার (নিজের কাছে ফেরাসহ) মধ্যে ঠিক একটি তীর আছে, যার লেবেল একটি regex. তীর “না থাকা” মানে লেবেল ∅.
গ্রহণ: G একটি string w গ্রহণ করে যদি w = w1w2⋯wk লেখা যায় (প্রতিটি wi ∈ Σ∗, ফাঁকাও হতে পারে) আর এমন state-ক্রম r0, r1, …, rk থাকে যাতে r0 = qstart, rk = qaccept, আর প্রতিটি i-তে wi ∈ L(δ(ri−1, ri)).
সংজ্ঞার প্রতিটি শর্তের একটি কারণ আছে। শুরুর state-এ কোনো তীর না ঢোকায় শুরুটিকে কখনো সরাতে হয় না, আর তার আশপাশে চক্কর তৈরি হয় না। একমাত্র accepting state থাকায় শেষে উত্তরটি একটি তীরে জমা হয়। আর “প্রতি জোড়ায় ঠিক একটি তীর” মানে একই দিকে দুটি সমান্তরাল তীর থাকলে তাদের লেবেল ∪ দিয়ে জুড়ে একটি করা হয়েছে।
DFA থেকে GNFA বানাতে তিনটি ধাপ লাগে:
- নতুন শুরু state s যোগ করুন, আর s থেকে পুরোনো শুরু q0-তে একটি ε-তীর দিন।
- নতুন accepting state t যোগ করুন, আর পুরোনো প্রতিটি accepting state থেকে t-তে ε-তীর দিন; পুরোনো state-গুলো আর accepting নয়।
- একই দুই state-এর মধ্যে একই দিকে একাধিক তীর থাকলে লেবেল ∪ দিয়ে জুড়ুন (যেমন “0, 1” হয়ে যায় 0 ∪ 1); যে জোড়ায় তীর নেই, সেখানে লেবেল ∅.
এই ধাপগুলো language বদলায় না। নতুন ε-তীর কোনো চিহ্ন পড়ে না, তাই s থেকে t-তে যাওয়ার প্রতিটি পথ পুরোনো DFA-র q0 থেকে একটি accepting state পর্যন্ত একটি পথের সঙ্গে হুবহু মেলে। একই কাজ NFA বা ε-NFA-তেও করা যায়: ε-তীরের লেবেল ε থাকবে, আর একই চিহ্নে একাধিক তীর থাকলে কোনো সমস্যা নেই। তাই পুরো পদ্ধতিটি যেকোনো finite automaton-এ কাজ করে, আগে DFA বানানোর দরকার নেই।
এই পর্বের চলমান উদাহরণ পর্ব ০৮-এর DIV3: Σ = {0, 1}-এর ওপর সেই string-গুলো, যাদের binary মান ৩ দিয়ে বিভাজ্য (val(ε) = 0 ধরে, তাই ε ∈ DIV3). DFA-র state q0, q1, q2 মানে এ পর্যন্ত পড়া মানের ৩ দিয়ে ভাগশেষ; শুরু আর accepting দুটিই q0. নিচের ছবিতে এর GNFA রূপ।
DIV3-এর DFA থেকে GNFA
নতুন শুরু s আর নতুন accepting t (দুই দাগের বৃত্ত)। q0 আর accepting নয়; তার বদলে q0 থেকে t-তে একটি ε-তীর। যে জোড়ায় তীর আঁকা নেই, তার লেবেল ∅.
৩ · State elimination — R1R2∗R3 ∪ R4
এবার মূল নিয়ম। s আর t ছাড়া যেকোনো একটি state বেছে নিন, নাম qrip (“rip” মানে ছিঁড়ে ফেলা)। এটি সরালে যে পথগুলো qrip হয়ে যেত, সেগুলো হারিয়ে যাবে, যদি না তাদের অন্য তীরে লিখে রাখা হয়। তাই qrip ছাড়া বাকি প্রতিটি জোড়া (qi, qj)-এর জন্য, যেখানে qi ≠ t আর qj ≠ s (qi = qj হতে পারে), চারটি লেবেল দেখুন:
তারপর নতুন GNFA-তে qi থেকে qj-এর লেবেল হবে
কথায়: qi থেকে qj-এ যাওয়ার দুই রকম উপায় ছিল। হয় qrip-এ ঢুকে (R1), সেখানে শূন্য বা বেশিবার চক্কর দিয়ে (R2∗), বেরিয়ে যাওয়া (R3); নয়তো সরাসরি তীর ধরে (R4). নতুন লেবেল দুটিকেই ধরে রাখে। নিচের ছবিতে নিয়মটি।
একটি state সরানোর নিয়ম
উপরে: qrip হয়ে যাওয়ার পথ (R1, চক্কর R2, R3) আর সরাসরি তীর R4. নিচে: qrip সরানোর পর একটিমাত্র তীর।
হাতে কাজ করার সময় কয়েকটি সরলীকরণ সবসময় খাটে, আর এগুলোই লেবেলকে ছোট রাখে: R∅ = ∅R = ∅, R ∪ ∅ = R, Rε = εR = R, আর ∅∗ = ε∗ = ε. বিশেষ করে R2 = ∅ হলে (qrip-এ চক্কর নেই) R2∗ = ε, তাই নতুন লেবেল R1R3 ∪ R4. এই identity-গুলোর প্রমাণ পর্ব ১৩-এ আছে।
পুরো algorithm-টি এক লাইনে: GNFA-তে k টি state থাকলে (s আর t সহ), k = 2 না হওয়া পর্যন্ত একটি করে qrip সরান; শেষে δ(s, t) হলো উত্তর। n-state DFA থেকে শুরু করলে k = n + 2, তাই ঠিক nবার অপসারণ। নিচের stepper-এ DIV3-এর GNFA থেকে q2, q1, q0 এই ক্রমে সরানো হলো।
1DFA → GNFA (s, t যোগ)2q2 বাছাই: কোন তীর যুক্ত?3q2 সরানো: জোড়া (q1, q1)4q1 সরানো: জোড়া (q0, q0)5q0 সরানো: জোড়া (s, t)6যাচাই
| qrip | |
| R1, R2 | |
| R3, R4 | |
| নতুন লেবেল | |
| বাকি state |
- GNFA বানানো। নতুন s থেকে q0-তে ε, q0 থেকে নতুন t-তে ε. DFA-র ছয়টি তীর আগের মতোই, প্রতিটির লেবেল একটি চিহ্ন। মোট ৫টি state আর ৮টি তীর; বাকি সব জোড়ার লেবেল ∅.
- q2 বাছাই। q2-তে ঢোকে শুধু q1 থেকে (লেবেল 0), q2-এর নিজের চক্কর 1, আর q2 থেকে বের হয় শুধু q1-এ (লেবেল 0). তাই যে জোড়ায় R1 আর R3 দুটিই ∅ নয়, সেটি একটিই: (q1, q1). বাকি সব তীর অপরিবর্তিত থাকবে।
- q2 সরানো। জোড়া (q1, q1): R1 = 0, R2 = 1, R3 = 0, আর R4 = ∅, কারণ আগে q1-এ কোনো চক্কর ছিল না। নতুন লেবেল 01∗0 ∪ ∅ = 01∗0. অর্থ: q1 থেকে q2 হয়ে যেকোনো সংখ্যক 1 পড়ে q1-এ ফেরা।
- q1 সরানো। q1-এ ঢোকে q0 থেকে (1), চক্কর 01∗0, বের হয় q0-তে (1). জোড়া (q0, q0)-এ আগে থেকেই চক্কর 0 ছিল, তাই R4 = 0. নতুন লেবেল 1(01∗0)∗1 ∪ 0. লক্ষ করুন, R2-এর ভেতরে ∪ নেই কিন্তু দৈর্ঘ্য একের বেশি, তাই star-এর আগে বন্ধনী লাগে।
- q0 সরানো। জোড়া (s, t): R1 = ε (s → q0), R2 = 1(01∗0)∗1 ∪ 0, R3 = ε (q0 → t), আর R4 = ∅. Rε = R নিয়মে লেবেল (1(01∗0)∗1 ∪ 0)∗. শুধু s আর t বাকি, তাই এটিই উত্তর।
- যাচাই। Union-এর ক্রম বদলালে এটি পরিচিত রূপ (0 ∪ 1(01∗0)∗1)∗. দৈর্ঘ্য 0 থেকে 10-এর সব 2047টি binary string-এ এর language আর DFA-র language মেলানো হয়েছে: একটিও অমিল নেই (নিচের Python ব্লকে নিজে চালিয়ে দেখুন)।
উত্তরটির একটি সুন্দর ব্যাখ্যাও আছে। q0 মানে “এ পর্যন্ত মান ৩-এর গুণিতক”। সেখান থেকে q0-তে ফেরার দুটি উপায়: একটি 0 পড়া (মান দ্বিগুণ হয়, গুণিতকই থাকে), অথবা 1 পড়ে q1-এ গিয়ে, q1 আর q2-এর মধ্যে 01∗0 ধরনের ঘোরাঘুরি করে, শেষে আরেকটি 1 পড়ে ফেরা। Regex-টি ঠিক “q0 থেকে q0-তে ফেরার সব উপায়, যতবার খুশি”।
৪ · কেন সঠিক — প্রমাণের রূপরেখা আর Kleene-এর উপপাদ্য
উদাহরণে কাজ করেছে, কিন্তু সব automaton-এ করবে কি? প্রমাণটি দুই স্তরে। প্রথম স্তর একটি lemma: একটি state সরালে GNFA-র language বদলায় না। দ্বিতীয় স্তর state-সংখ্যার ওপর induction.
G একটি GNFA, যাতে k ≥ 3টি state. qrip ∉ {qstart, qaccept} সরিয়ে নিয়ম অনুযায়ী লেবেল বদলে G′ পাওয়া গেলে L(G′) = L(G).
প্রমাণের রূপরেখা (Sipser-এর বইয়ের Claim 1.65-এর ধাঁচে):
- L(G) ⊆ L(G′): ধরুন G একটি state-ক্রম qstart, r1, …, qaccept ধরে w গ্রহণ করে। ক্রমে qrip না থাকলে প্রতিটি ধাপ G′-তেও বৈধ, কারণ নতুন লেবেলের ∪-এর একটি অংশ R4, অর্থাৎ পুরোনো লেবেল। — R4 ⊆ R1R2∗R3 ∪ R4
- ক্রমে qrip থাকলে, পরপর আসা qrip-গুলোর প্রতিটি সর্বোচ্চ খণ্ড নিন: qi, qrip, …, qrip, qj, যেখানে qi, qj ≠ qrip. এই খণ্ডে পড়া অংশটি একটি R1-অংশ, তারপর শূন্য বা বেশি R2-অংশ, তারপর একটি R3-অংশ। তাই এটি L(R1R2∗R3)-এ আছে, আর G′-তে qi → qj একটি ধাপেই পড়া যায়। — R2∗-এর সংজ্ঞা
- L(G′) ⊆ L(G): G′-এর গ্রহণকারী ক্রমের প্রতিটি ধাপ qi → qj একটি অংশ পড়ে, যা হয় L(R4)-এ (তখন G-তেও সরাসরি একই ধাপ), নয়তো L(R1R2∗R3)-এ (তখন G-তে qrip হয়ে কয়েকটি ধাপ)। ধাপগুলো জুড়ে G-এর একটি গ্রহণকারী ক্রম পাওয়া যায়। — ∪ আর concatenation-এর সংজ্ঞা
- দুই দিক মিলে L(G′) = L(G). ∎
প্রতিটি DFA, NFA বা ε-NFA M-এর জন্য একটি regex R আছে যাতে L(R) = L(M). State elimination সেটি যান্ত্রিকভাবে বের করে।
প্রমাণ (GNFA-র state-সংখ্যা k-এর ওপর induction; পদ্ধতিটি পর্ব ০৪-এর মতো):
- M থেকে অংশ ২-এর তিন ধাপে GNFA G বানান; L(G) = L(M). — ε-তীর কিছু পড়ে না, আর ∪-জোড়া সমান্তরাল তীরের সমান
- ভিত্তি, k = 2: শুধু qstart আর qaccept, মাঝে একটি তীর, লেবেল R. G-এর প্রতিটি গ্রহণকারী ক্রম ঠিক এক ধাপের, তাই L(G) = L(R). — GNFA-র গ্রহণের সংজ্ঞা
- ধাপ, k ≥ 3: একটি qrip সরিয়ে G′ পান; G′-এ k − 1টি state আর L(G′) = L(G). — Lemma ৪.১
- Induction hypothesis অনুযায়ী G′-এর থেকে state elimination যে regex দেয়, তার language L(G′). তাই G-এর থেকেও একই regex, যার language L(G) = L(M). ∎ — k − 1-এ দাবি সত্য ধরা
এখন সব মিলিয়ে কোর্সের প্রথম বড় সমতা পাওয়া গেল। এর তিনটি অংশ তিনটি পর্বে প্রমাণ হয়েছে বা হবে:
একটি language L ⊆ Σ∗-এর জন্য নিচের তিনটি কথা সমতুল্য:
(ক) কোনো DFA L চেনে; (খ) কোনো NFA (ε-move সহ বা ছাড়া) L চেনে; (গ) কোনো regex L বর্ণনা করে।
প্রমাণের মানচিত্র: (ক) ⇒ (খ) সরাসরি (প্রতিটি DFA একটি NFA); (খ) ⇒ (ক) subset construction (পর্ব ১০, ε-closure সহ পর্ব ১১); (গ) ⇒ (খ) Thompson construction (পর্ব ১৪); (ক) বা (খ) ⇒ (গ) state elimination (উপপাদ্য ৪.২)।
এই কারণেই “regular language” শব্দটির তিনটি সংজ্ঞা একই শ্রেণি দেয়। কোনো প্রশ্নে যে রূপটি সুবিধাজনক, সেটি ব্যবহার করা যায়: closure প্রমাণে প্রায়ই NFA (পর্ব ১৬), membership আর minimisation-এ DFA (পর্ব ১৯), আর বর্ণনা ও যোগাযোগে regex.
Stephen Kleene-এর প্রবন্ধ “Representation of Events in Nerve Nets and Finite Automata” ১৯৫৬ সালে Shannon আর McCarthy সম্পাদিত Automata Studies সংকলনে প্রকাশিত হয়; এর আগের একটি রূপ ১৯৫১ সালে RAND-এর একটি গবেষণা প্রতিবেদন হিসেবে ছিল বলে উল্লেখ পাওয়া যায়। Kleene-এর লক্ষ্য ছিল McCulloch–Pitts-এর (১৯৪৩) স্নায়ু-জালের মডেল কোন “ঘটনা” চিনতে পারে, তা বর্ণনা করা; সেখান থেকেই “regular event” আর star operation-এর ধারণা। Kleene-এর মূল প্রমাণ আর পরে McNaughton ও Yamada-র (১৯৬০) পদ্ধতি দুটিই সব পথকে মাঝের state-এর সংখ্যা ধরে ধাপে ধাপে গোনে (আরও গভীরে দেখুন)। ছবির ওপর state সরানোর পদ্ধতিটি সাধারণত Brzozowski আর McCluskey-র ১৯৬৩ সালের কাজের সঙ্গে যুক্ত করা হয়, আর GNFA দিয়ে এর পরিষ্কার উপস্থাপন Sipser-এর পাঠ্যবইয়ে জনপ্রিয় হয়েছে।
৫ · ব্রাউজারের Python-এ state elimination
নিচের ব্লকটি নিয়মগুলো সরাসরি কোডে লেখে। Regex এখানে সাধারণ string; ∅ বোঝাতে Python-এর None. union, cat আর star অংশ ৩-এর সরলীকরণগুলো প্রয়োগ করে, আর top_union দেখে কোথায় বন্ধনী লাগবে (বাইরের স্তরে ∪ থাকলে concatenation-এর আগে বন্ধনী)। gnfa অংশ ২-এর তিন ধাপ, আর eliminate প্রতিটি অপসারণের পর সব তীর ছাপে। এর পরের ব্লক এই function-গুলোই ব্যবহার করবে (data-shared), তাই আগে এটি চালান।
def top_union(r): # is there a ∪ outside every bracket?
depth = 0
for c in r:
depth += (c == "(") - (c == ")")
if c == "∪" and depth == 0: return True
return False
def union(a, b): # None stands for ∅
if a is None: return b
if b is None or a == b: return a
return a + "∪" + b
def cat(*rs):
if None in rs: return None # R∅ = ∅
s = "".join("(" + r + ")" if top_union(r) else r for r in rs if r != "ε")
return s or "ε" # Rε = R
def star(r):
if r is None or r == "ε": return "ε" # ∅* = ε* = ε
return (r if len(r) == 1 else "(" + r + ")") + "*"
def gnfa(dfa, start, finals): # new s and t, merge arrows
R = {("s", start): "ε", **{(f, "t"): "ε" for f in finals}}
for (q, a), p in dfa.items(): R[q, p] = union(R.get((q, p)), a)
return R
def eliminate(R, order, show=True):
live = {q for edge in R for q in edge}
for rip in order:
live.discard(rip)
R = {(i, j): x for i in live - {"t"} for j in live - {"s"}
if (x := union(cat(R.get((i, rip)), star(R.get((rip, rip))),
R.get((rip, j))), R.get((i, j)))) is not None}
if show: print("remove", rip, "|", " ".join(f"{i}→{j}: {x}" for (i, j), x in sorted(R.items())))
return R["s", "t"]
# DIV3: binary value divisible by 3 (state = remainder so far)
dfa = {("q0", "0"): "q0", ("q0", "1"): "q1", ("q1", "0"): "q2",
("q1", "1"): "q0", ("q2", "0"): "q1", ("q2", "1"): "q2"}
print("regex:", eliminate(gnfa(dfa, "q0", {"q0"}), ["q2", "q1", "q0"]))আসল আউটপুট (ব্রাউজারের Python):
remove q2 | q0→q0: 0 q0→q1: 1 q0→t: ε q1→q0: 1 q1→q1: 01*0 s→q0: ε
remove q1 | q0→q0: 1(01*0)*1∪0 q0→t: ε s→q0: ε
remove q0 | s→t: (1(01*0)*1∪0)*
regex: (1(01*0)*1∪0)*
প্রতিটি লাইন stepper-এর একটি ধাপ। q2 সরানোর পর শুধু q1→q1 তীরটি নতুন (01*0); বাকি পাঁচটি তীর আগের মতো, কারণ তাদের জোড়ার R1 বা R3 ছিল ∅. Dictionary comprehension-এর ভেতরের := (walrus) নতুন লেবেল হিসাব করে রাখে, আর লেবেল ∅ (None) হলে তীরটি বাদ দেয়, কারণ GNFA-তে ∅-তীর আঁকার দরকার নেই। এই কোড নিজে কোনো regex library ব্যবহার করে না; সব কাজ string জোড়া দিয়ে। Python-এর re শুধু পরের ব্লকে যাচাইয়ের জন্য আসবে।
৬ · Arden-এর সূত্র — বীজগণিতের পথ
দ্বিতীয় পদ্ধতিটি ছবি ছাড়াই চলে। DFA-র প্রতিটি state q-এর জন্য একটি অজানা language ধরুন:
অর্থাৎ q থেকে শুরু করলে যে string-গুলো গৃহীত হয় (δ̂ হলো পুরো string-এর transition; কিছু বইয়ে δ∗)। তাহলে L(M) = Xq0. একটি string w ∈ Xq হয় ঠিক দুইভাবে: w = ε আর q ∈ F; অথবা w = aw′, যেখানে a একটি চিহ্ন আর w′ ∈ Xδ(q, a). তাই প্রতিটি state-এর জন্য একটি language-সমীকরণ পাওয়া যায়:
এই সমীকরণগুলো সাধারণ বীজগণিতের মতো একে একে বসিয়ে সমাধান করা যায়, শুধু একটি বিশেষ নিয়ম লাগে: যখন একটি অজানা নিজের সমীকরণেই আসে, যেমন X = 0X ∪ 1. এর সমাধান দেয় Arden-এর সূত্র।
A আর B দুটি language (বা regex), আর ε ∉ A. তাহলে X = AX ∪ B সমীকরণের একমাত্র সমাধান X = A∗B.
(একই যুক্তিতে X = XA ∪ B-এর একমাত্র সমাধান X = BA∗; অনেক বই এই ডান-দিকের রূপে লেখে।)
প্রমাণ:
- A∗B একটি সমাধান: A(A∗B) ∪ B = (AA∗)B ∪ {ε}B. — concatenation associative, আর {ε}B = B
- = (AA∗ ∪ {ε})B = A∗B. — concatenation ∪-এর ওপর বণ্টিত হয়, আর A∗ = {ε} ∪ AA∗ (star-এর সংজ্ঞা)
- যেকোনো সমাধান X-এ A∗B আছে: k-এর ওপর induction-এ AkB ⊆ X. k = 0: B ⊆ AX ∪ B = X. k থেকে k + 1: Ak+1B = A(AkB) ⊆ AX ⊆ X. — X = AX ∪ B
- সব k-এর union নিয়ে A∗B = ⋃k AkB ⊆ X. — star-এর সংজ্ঞা
- X-এ A∗B-এর বাইরে কিছু নেই: ধরুন আছে; X − A∗B-এর সবচেয়ে ছোট দৈর্ঘ্যের একটি string w নিন। — contradiction-এর জন্য ধরে নেওয়া
- w ∈ X = AX ∪ B, আর w ∉ B (কারণ B ⊆ A∗B). তাই w = uv, যেখানে u ∈ A আর v ∈ X. — ∪-এর সংজ্ঞা
- ε ∉ A, তাই |u| ≥ 1, ফলে |v| < |w|. — এখানেই শর্তটি লাগে
- v ∈ X আর w-এর চেয়ে ছোট, তাই w-এর ন্যূনতমতা অনুযায়ী v ∈ A∗B. তাহলে w = uv ∈ AA∗B ⊆ A∗B, বিরোধ। তাই X = A∗B. ∎ — ধাপ ৫-এর অনুমান খণ্ডিত
শর্তটি বাদ দিলে কী হয়? A = {ε, a}, B = {b} নিন (Σ = {a, b})। A∗B = a∗b একটি সমাধান, ঠিকই। কিন্তু X = Σ∗-ও সমাধান: AΣ∗ ∪ {b} = Σ∗ ∪ aΣ∗ ∪ {b} = Σ∗. দুটি ভিন্ন সমাধান, তাই “একমাত্র” কথাটি মিথ্যা। ধাপ ৭-এ u = ε হলে v = w, আর ছোট string-এর যুক্তি ভেঙে পড়ে। DFA থেকে লেখা সমীকরণে A সবসময় একক চিহ্নের union (ε নেই), তাই সেখানে সূত্রটি নিরাপদ। ε-NFA থেকে সমীকরণ লিখলে আগে ε-তীর দূর করতে হয়।
এবার DIV3-এ পদ্ধতিটি চালানো যাক। DFA থেকে তিনটি সমীকরণ (q0 accepting, তাই প্রথমটিতে ε):
1তিনটি সমীকরণ লেখা2X2-এ Arden3X2 বসানো X1-এ4X1-এ Arden5X1 বসানো X0-এ6X0-এ Arden: উত্তর
| সমীকরণ | |
| A, B | |
| ফল | |
| ε ∉ A? |
- সমীকরণ। প্রতিটি state-এর জন্য একটি: q থেকে a পড়ে যেখানে যাওয়া যায়, সেই state-এর অজানা আর a জুড়ে। শুধু q0 accepting, তাই শুধু X0-এ “∪ ε”। লক্ষ্য X0 বের করা।
- X2-এ Arden. X2 = 1X2 ∪ 0X1 রূপটি X = AX ∪ B, যেখানে A = 1 আর B = 0X1. ε ∉ {1}, তাই একমাত্র সমাধান X2 = 1∗0X1. অর্থ: q2-তে যত খুশি 1 পড়ে, একটি 0 পড়ে q1-এ ফেরা।
- X1-এ বসানো। X1 = 1X0 ∪ 0X2 = 1X0 ∪ 0·1∗0X1. এখন X2 আর নেই; X1 নিজের ওপর আর X0-এর ওপর নির্ভর করে।
- X1-এ Arden. X1 = (01∗0)X1 ∪ 1X0. A = 01∗0, যার প্রতিটি string অন্তত দুই অক্ষরের, তাই ε ∉ A. সমাধান X1 = (01∗0)∗1X0. State elimination-এ q2 সরানোর পর q1-এর চক্করও ঠিক 01∗0 ছিল।
- X0-এ বসানো। X0 = 0X0 ∪ 1(01∗0)∗1X0 ∪ ε. Concatenation ∪-এর ওপর বণ্টিত হয় বলে X0-এর দুই পদ একসঙ্গে লেখা যায়: (0 ∪ 1(01∗0)∗1)X0 ∪ ε.
- শেষ ধাপ। A = 0 ∪ 1(01∗0)∗1, B = ε, আর ε ∉ A. তাই X0 = A∗ε = (0 ∪ 1(01∗0)∗1)∗, state elimination-এর উত্তরের সঙ্গে হুবহু এক (শুধু ∪-এর দুই পাশ অদলবদল)।
মিলটি কাকতালীয় নয়। সমীকরণ থেকে একটি অজানা মুছে ফেলা আর GNFA থেকে একটি state সরানো একই কাজ: X2-এ Arden প্রয়োগ মানে q2-এর চক্কর 1-কে star করা, আর X2 বসানো মানে q2 হয়ে যাওয়া পথগুলো সরাসরি তীরে লেখা। অজানা মোছার ক্রম তাই state সরানোর ক্রমের মতোই ফলের আকার বদলায়। পরীক্ষায় কোন পদ্ধতি লিখবেন, তা নির্ভর করে প্রশ্নের ওপর; উত্তর দুই পথেই একই language.
৭ · Elimination ক্রম আর regex-এর আকার
উপপাদ্য ৪.২ যেকোনো ক্রমে কাজ করে, কিন্তু সব ক্রম সমান নয়। DIV3-এ q2, q1, q0 ক্রমে ১৪ অক্ষরের regex এসেছে। উল্টো ক্রমে কী হয়, নিচের stepper দেখায়। কারণটি সহজ: q0 শুরু s আর শেষ t দুটির সঙ্গেই যুক্ত, তাই তাকে আগে সরালে s আর t-এর সঙ্গে নতুন অনেক তীর তৈরি হয়, আর প্রতিটি তীরের লেবেল পরের অপসারণে আবার ভেঙে বড় হয়।
1ক্রম ক: q2, q1, q02ক্রম খ: আগে q03ক্রম খ: তারপর q14ক্রম খ: শেষে q25ছয়টি ক্রমের হিসাব
| তীর (s, t সহ) | |
| তীরের সংখ্যা | |
| regex-এর দৈর্ঘ্য |
- ক্রম ক। অংশ ৩-এর ফল: q2 সরালে একটি তীর বদলায়, q1 সরালে একটি, q0 সরালে শেষ উত্তর। প্রতিবার শুধু একটি জোড়া প্রভাবিত, তাই regex মাত্র ১৪ অক্ষরের।
- ক্রম খ, q0 প্রথমে। q0-তে ঢোকে s (ε) আর q1 (1), চক্কর 0, বের হয় q1 (1) আর t (ε)-তে। তাই চারটি জোড়া বদলায়: s→q1 = 0∗1, s→t = 0∗, q1→q1 = 10∗1, q1→t = 10∗. q1-q2-এর তিনটি পুরোনো তীর মিলিয়ে মোট ৭টি তীর।
- ক্রম খ, তারপর q1. q1 এখন s, q2 আর t তিনটির সঙ্গে যুক্ত, আর তার নিজের চক্কর 10∗1. চারটি নতুন লেবেল আসে, যেমন q2→q2 = 0(10∗1)∗0 ∪ 1 আর s→t = 0∗1(10∗1)∗10∗ ∪ 0∗.
- ক্রম খ, শেষে q2. s→q2, q2-এর চক্কর আর q2→t তিনটি লম্বা লেবেল জোড়া লাগে, সঙ্গে পুরোনো s→t. ফল ৫৩ অক্ষরের regex. Brute force-এ দৈর্ঘ্য 10 পর্যন্ত সব string-এ এটিও DIV3-এর সঙ্গে হুবহু মেলে।
- ছয়টি ক্রম। তিনটি state সাজানোর ৬টি উপায়ে দৈর্ঘ্য ১৪ থেকে ৫৩, সবগুলোই সঠিক (নিচের ব্লকে নিজে চালিয়ে দেখুন)। শিক্ষা: যে state শুরু আর শেষের সঙ্গে বেশি যুক্ত বা যার তীর বেশি, তাকে শেষে সরানো সাধারণত ভালো।
নিচের ব্লক আগের ব্লকের function-গুলো ব্যবহার করে দুটি কাজ করে। প্রথমত, DIV3-এর ছয়টি ক্রম, প্রতিটির regex Python-এর re-তে অনুবাদ করে (∪ → |, ε → ফাঁকা) brute force-এ দৈর্ঘ্য 10 পর্যন্ত সব 2047টি string-এ DFA-র সঙ্গে মেলানো। দ্বিতীয়ত, “binary মান m দিয়ে বিভাজ্য” DFA-গুলোতে (m = 2 থেকে 8, mটি state) দুই ক্রমের regex-দৈর্ঘ্য।
import re
from itertools import permutations, product
def disagreements(rx, dfa, start, finals, sigma="01", n=10):
py = re.compile(rx.replace("∪", "|").replace("ε", "")) # only to check
def accepts(w):
q = start
for c in w: q = dfa[q, c]
return q in finals
words = ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
return sum(bool(py.fullmatch(w)) != accepts(w) for w in words), len(words)
print("DIV3, all six elimination orders:")
for order in permutations(["q0", "q1", "q2"]):
rx = eliminate(gnfa(dfa, "q0", {"q0"}), order, show=False)
bad, total = disagreements(rx, dfa, "q0", {"q0"})
print(" ", *order, f" length {len(rx):2} wrong on {bad} of {total}")
print("binary mod m: regex length, two orders")
for m in range(2, 9):
d = {(f"q{r}", b): f"q{(2 * r + int(b)) % m}" for r in range(m) for b in "01"}
S = [f"q{r}" for r in range(m)]
down = eliminate(gnfa(d, "q0", {"q0"}), S[::-1], show=False)
up = eliminate(gnfa(d, "q0", {"q0"}), S, show=False)
ok = disagreements(down, d, "q0", {"q0"}, n=8)[0] + disagreements(up, d, "q0", {"q0"}, n=8)[0] == 0
print(f" m={m} q{m-1}..q0: {len(down):4} q0..q{m-1}: {len(up):5} correct: {ok}")আসল আউটপুট (ব্রাউজারের Python):
DIV3, all six elimination orders:
q0 q1 q2 length 53 wrong on 0 of 2047
q0 q2 q1 length 21 wrong on 0 of 2047
q1 q0 q2 length 45 wrong on 0 of 2047
q1 q2 q0 length 19 wrong on 0 of 2047
q2 q0 q1 length 21 wrong on 0 of 2047
q2 q1 q0 length 14 wrong on 0 of 2047
binary mod m: regex length, two orders
m=2 q1..q0: 9 q0..q1: 18 correct: True
m=3 q2..q0: 14 q0..q2: 53 correct: True
m=4 q3..q0: 27 q0..q3: 98 correct: True
m=5 q4..q0: 46 q0..q4: 255 correct: True
m=6 q5..q0: 63 q0..q5: 338 correct: True
m=7 q6..q0: 167 q0..q6: 1039 correct: True
m=8 q7..q0: 239 q0..q7: 1416 correct: True
ছয়টি ক্রমের দৈর্ঘ্য stepper-এর সংখ্যার সঙ্গে মেলে, আর প্রতিটিতে ভুল শূন্য: language একই, শুধু লেখা আলাদা। m বাড়লে পার্থক্য আরও স্পষ্ট: m = 7-এ একটি ক্রমে ১৬৭ অক্ষর, অন্যটিতে ১০৩৯, প্রায় ছয়গুণ। “correct: True” মানে দুই regex-ই দৈর্ঘ্য 8 পর্যন্ত সব 511টি string-এ DFA-র সঙ্গে একমত। এখানে re ব্যবহার হয়েছে শুধু স্বাধীন যাচাইয়ের জন্য; regex বানানোর কাজটি আগের ব্লকের নিজের কোড করেছে। একটি সতর্কতা: brute force দৈর্ঘ্য 10 পর্যন্ত মেলায়, সব দৈর্ঘ্যে নয়। সব দৈর্ঘ্যে নিশ্চিত হতে হলে উপপাদ্য ৪.২-এর প্রমাণ, বা পর্ব ২০-এর equivalence algorithm লাগে।
কত বড় হতে পারে? একটি অপসারণে নতুন লেবেল R1R2∗R3 ∪ R4-এ পুরোনো চারটি লেবেল জোড়া লাগে, তাই সবচেয়ে লম্বা লেবেলের দৈর্ঘ্য প্রতি অপসারণে বড়জোর প্রায় চারগুণ হয়। n-টি অপসারণের পর তাই উপরের সীমা মোটামুটি 4n-এর মাপের। এটি শুধু পদ্ধতির দুর্বলতা নয়। Ehrenfeucht আর Zeiger-এর ১৯৭৬ সালের কাজে এমন n-state DFA-র উদাহরণ আছে (বড় alphabet-এর ওপর), যাদের সমতুল্য প্রতিটি regex-এর দৈর্ঘ্য n-এর ঘাতের হারে বাড়ে; পরে Gruber আর Holzer (২০০৮ সালের দিকে) দেখান, ছোট alphabet-এও এমন ঘাতের নিম্নসীমা থাকে। অর্থাৎ পর্ব ১৪-এর দিকে (regex → NFA) আকার বাড়ে রৈখিক হারে, কিন্তু এই দিকে (automaton → regex) সবচেয়ে খারাপ ক্ষেত্রে ঘাতের হারে, আর সেটি এড়ানো যায় না।
বাস্তবে তাই ক্রম বাছার জন্য heuristic (অভিজ্ঞতাভিত্তিক নিয়ম) ব্যবহার হয়: যে state-এর ঢোকা আর বের হওয়া তীর সবচেয়ে কম, তাকে আগে সরানো। কারণ ঢোকা তীর × বের হওয়া তীর যতগুলো, ঠিক ততগুলো জোড়ার লেবেল বদলায়। পরের অংশে দেখবেন, একটি পরিচিত library ঠিক এই ধরনের নিয়ম ব্যবহার করে।
আরও গভীরে: Kleene-এর মূল পদ্ধতি state elimination নয়, বরং dynamic programming: Rij(k) = “i থেকে j-এর সব পথ, যাদের মাঝের state-গুলো শুধু প্রথম k-টি থেকে”, আর Rij(k) = Rik(k−1)(Rkk(k−1))∗Rkj(k−1) ∪ Rij(k−1); এর গঠন DSA কোর্সের পর্ব ৪৪-এর Floyd–Warshall algorithm-এর মতোই, শুধু (min, +)-এর জায়গায় (∪, concatenation, star). এই মিল থেকে “Kleene algebra” নামের বীজগণিত এসেছে, যা regex, shortest path আর transitive closure একই কাঠামোয় দেখে। একটি regex-এ star-এর সর্বোচ্চ nesting গভীরতার নাম star height; একটি regular language-এর ন্যূনতম star height গণনা করা যায় (Hashiguchi, ১৯৮৮), কিন্তু complement-ও ব্যবহার করতে দিলে (generalized star height) star height 1-এর বেশি লাগে এমন কোনো language আদৌ আছে কি না, সেটি এখনো খোলা প্রশ্ন।
৮ · সত্যিকারের run — automata-lib আর random testing
নিজের কোডের ফল একটি স্বাধীন library-তে মেলানো দরকার। automata-lib (MIT licence) Python-এর একটি automata library, যার GNFA class ঠিক এই পর্বের state elimination চালায়: GNFA.from_dfa(dfa).to_regex(). Library-র কোডে কোনো network বা usage-reporting অংশ নেই (scratch-এ খুঁজে দেখা হয়েছে)। নিচের script ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে চালানো হয়েছে: automata-lib 9.2.0, Python 3.12. তিনটি DFA: DIV3; “01 আর 10 substring সমান সংখ্যকবার”, যা শুনতে গোনার মতো কিন্তু আসলে regular; আর বাজারঘরের অর্ডার কোড BG-dddd, alphabet {B, G, -, d}-এর ওপর (d মানে যেকোনো অঙ্ক)। প্রতিটি regex থেকে library-ই আবার NFA বানিয়ে মূল DFA-র সঙ্গে language-সমতা পরীক্ষা করে, আর আলাদাভাবে Python-এর re দিয়ে brute force.
import re
from itertools import product
from importlib.metadata import version
from automata.fa.dfa import DFA
from automata.fa.gnfa import GNFA
from automata.fa.nfa import NFA
print("automata-lib", version("automata-lib"))
def check(name, dfa, sigma, n=10):
rx = GNFA.from_dfa(dfa).to_regex() # state elimination
back = DFA.from_nfa(NFA.from_regex(rx, input_symbols=dfa.input_symbols))
py = re.compile(rx) # same syntax: | * ? ( )
words = ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
bad = sum(bool(py.fullmatch(w)) != dfa.accepts_input(w) for w in words)
print(f"{name}: {len(dfa.states)} states, regex length {len(rx)}")
print(" regex:", rx)
print(" same language (library):", back == dfa,
f"| brute force up to {n}: {len(words)} strings, {bad} disagreements")
mod3 = DFA(states={"q0", "q1", "q2"}, input_symbols={"0", "1"},
transitions={"q0": {"0": "q0", "1": "q1"}, "q1": {"0": "q2", "1": "q0"},
"q2": {"0": "q1", "1": "q2"}},
initial_state="q0", final_states={"q0"})
check("mod-3", mod3, "01")
# equal numbers of 01 and 10 substrings
eq = DFA(states={"s", "a0", "b0", "a1", "b1"}, input_symbols={"0", "1"},
transitions={"s": {"0": "a0", "1": "a1"}, "a0": {"0": "a0", "1": "b0"},
"b0": {"0": "a0", "1": "b0"}, "a1": {"0": "b1", "1": "a1"},
"b1": {"0": "b1", "1": "a1"}},
initial_state="s", final_states={"s", "a0", "a1"})
check("01 = 10", eq, "01")
# bazarghar order code BG-dddd over {B, G, -, d}, partial DFA
t = {"q0": {"B": "q1"}, "q1": {"G": "q2"}, "q2": {"-": "q3"}, "q3": {"d": "q4"},
"q4": {"d": "q5"}, "q5": {"d": "q6"}, "q6": {"d": "q7"}, "q7": {}}
code = DFA(states=set(t), input_symbols={"B", "G", "-", "d"}, transitions=t,
initial_state="q0", final_states={"q7"}, allow_partial=True)
check("order code", code, "BG-d", n=7)সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12):
~/bazarghar-toc$ uv run python to_regex.py
automata-lib 9.2.0
mod-3: 3 states, regex length 21
regex: (10(00|1)*01|(11|0))*
same language (library): True | brute force up to 10: 2047 strings, 0 disagreements
01 = 10: 5 states, regex length 24
regex: 1(00*1|1)*|(0(11*0|0)*)?
same language (library): True | brute force up to 10: 2047 strings, 0 disagreements
order code: 8 states, regex length 7
regex: BG-dddd
same language (library): True | brute force up to 7: 21845 strings, 0 disagreements
DIV3-এর জন্য library দিয়েছে (10(00 ∪ 1)∗01 ∪ 11 ∪ 0)∗, যা আমাদের ক্রম “q1, q2, q0”-এর ফলের সঙ্গে হুবহু এক (আমাদের হিসাবে ১৯ অক্ষর; library-র বাড়তি বন্ধনীসহ ২১)। কারণ library-র কোড প্রতিবার সবচেয়ে কম তীরে যুক্ত state সরায়, আর শুরুতে q1 আর q2 সমান, নামের ক্রমে q1 আগে আসে। অর্থাৎ এই heuristic-এ সবচেয়ে ছোট ১৪ অক্ষরের উত্তর আসেনি, কিন্তু ৫৩-এর বিপদও এড়ানো গেছে। দ্বিতীয় DFA-র regex পড়লে language-টির আসল রূপ চোখে পড়ে: 1 দিয়ে শুরু হলে 1 দিয়ে শেষ, 0 দিয়ে শুরু হলে 0 দিয়ে শেষ, অথবা ফাঁকা string (শেষের ? মানে “থাকতেও পারে, না-ও পারে”, অর্থাৎ ∪ ε)। প্রতিবার 01 থেকে 10-এ বা উল্টো দিকে যেতে হলে একটি সীমানা পার হতে হয়, তাই “প্রথম আর শেষ চিহ্ন সমান” আর “01 ও 10 সমান সংখ্যক” একই কথা। অর্ডার কোডের DFA partial (dead state নেই), আর regex হুবহু BG-dddd. তিন ক্ষেত্রেই library-র সমতা পরীক্ষা আর brute force দুটিই একমত।
Brute force ছোট দৈর্ঘ্যে সব string দেখে। লম্বা string-এ কী হয়? নিচের JavaScript ব্লক ব্রাউজারের নিজস্ব RegExp engine-এ, স্থির seed-এর ছদ্ম-দৈব (Park–Miller সূত্র) দৈর্ঘ্য 30 পর্যন্ত ২০,০০০ string নিয়ে প্রতিটি regex-কে language-এর সংজ্ঞার সঙ্গে মেলায়। চতুর্থ সারিতে একটি “AI-এর অনুমান”: DIV3-এর জন্য (0 ∪ 11)∗, যা দেখতে বিশ্বাসযোগ্য। Regex-এ “ends ab” হলো অনুশীলন ৪-এর উত্তর।
// Random testing: regexes from state elimination vs. the definitions.
let x = 2026; // fixed seed (Park–Miller)
const rnd = () => (x = (x * 48271) % 2147483647);
const word = (sigma, maxLen) => {
let w = "";
for (let n = rnd() % (maxLen + 1); n > 0; n--) w += sigma[rnd() % sigma.length];
return w;
};
const pairs = (w, p) => [...w.slice(1)].filter((c, i) => w[i] + c === p).length;
const tests = [ // name, regex (| for ∪), definition, alphabet
["DIV3", /^(?:1(?:01*0)*1|0)*$/, w => w === "" || BigInt("0b" + w) % 3n === 0n, "01"],
["01 = 10", /^(?:1(?:00*1|1)*|(?:0(?:11*0|0)*)?)$/, w => pairs(w, "01") === pairs(w, "10"), "01"],
["ends ab", /^(?:a(?:ba|a)*bb|b)*a(?:ba|a)*b$/, w => w.endsWith("ab"), "ab"],
["AI guess", /^(?:0|11)*$/, w => w === "" || BigInt("0b" + w) % 3n === 0n, "01"],
];
const t0 = performance.now();
for (const [name, rx, def, sigma] of tests) {
let bad = 0, first = null, yes = 0;
for (let k = 0; k < 20000; k++) {
const w = word(sigma, 30);
if (def(w)) yes++;
if (rx.test(w) !== def(w)) { bad++; if (first === null || w.length < first.length) first = w; }
}
console.log(name.padEnd(9), "in language:", yes, " wrong:", bad,
first === null ? "" : " shortest counterexample: " + first);
}
console.log("20000 random strings each, under 1 s:", performance.now() - t0 < 1000);আসল আউটপুট (ব্রাউজারের JavaScript):
DIV3 in language: 7364 wrong: 0
01 = 10 in language: 10663 wrong: 0
ends ab in language: 4672 wrong: 0
AI guess in language: 7229 wrong: 4703 shortest counterexample: 1001
20000 random strings each, under 1 s: true
প্রথম তিনটি regex ২০,০০০ লম্বা দৈব string-এ একবারও ভুল করেনি। “in language” সংখ্যাটি দেখায়, পরীক্ষায় দুই রকম string-ই যথেষ্ট ছিল: DIV3-এ প্রায় এক-তৃতীয়াংশের বেশি (ফাঁকা আর শুধু 0-এর string-ও গুণিতক), 01 = 10-এ প্রায় অর্ধেক। “AI guess” ৪৭০৩ বার ভুল, আর পাওয়া সবচেয়ে ছোট পাল্টা-উদাহরণ 1001: binary মান 9, ৩ দিয়ে বিভাজ্য, কিন্তু (0 ∪ 11)∗ এটি মেলায় না, কারণ মাঝের 00-কে 11-এর জোড়ায় ভাগ করা যায় না। (0 ∪ 11)∗-এর প্রতিটি string DIV3-এ আছে, কিন্তু উল্টোটি সত্য নয়। এখানে JavaScript-এ BigInt লাগে, কারণ ৩০ অঙ্কের binary মান সাধারণ number-এ নিখুঁত থাকে না। শেষ লাইনে সময়ের পরীক্ষা true এসেছে: সব কাজ এক সেকেন্ডের কম সময়ে।
একটি সূক্ষ্ম কথা: এই পর্বের regex formal regex, শুধু ∅, ε, চিহ্ন, ∪, concatenation আর star. বাস্তব engine-এর (?:…), ^, $ বা ? শুধু লেখার সুবিধা। কিন্তু backreference, lookaround-এর মতো কিছু বৈশিষ্ট্য গণিতের অর্থে regular নয়, আর সেগুলোর জন্য এই পর্বের উল্টো রূপান্তর খাটে না। Formal আর বাস্তব regex-এর পার্থক্য, আর backtracking engine-এর ঝুঁকি (ReDoS) পর্ব ২১-এর বিষয়। Python আর JavaScript-এ regex লেখার হাতে-কলমে চর্চা আছে Python প্রোগ্রামিং কোর্সের পর্ব ৩০ আর JavaScript কোর্সের পর্ব ৩০-এ।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- একটি DFA-কে state elimination দিয়ে regex-এ রূপান্তর করুন। s আর t যোগ, প্রতিটি অপসারণে R1R2∗R3 ∪ R4, প্রতিটি ধাপে বদলানো তীরগুলো লিখে দেখানো।
- Arden-এর সূত্র বলুন আর প্রমাণ করুন। ε ∉ L(A) হলে X = AX ∪ B-এর একমাত্র সমাধান A∗B; ε ∈ L(A) হলে সমাধান অনন্য নয়।
- Arden দিয়ে DFA-র regex বের করুন। প্রতিটি state-এর সমীকরণ লিখে, একটি একটি অজানা মুছে, শেষে শুরুর state-এর অজানা।
- Kleene-এর উপপাদ্য কী বলে? DFA, NFA আর regex ঠিক একই language-শ্রেণি, regular language, বর্ণনা করে।
- Elimination-এর ক্রম কি উত্তর বদলায়? লেখা বদলায়, language নয়; আর লেখার দৈর্ঘ্য অনেক বদলাতে পারে।
৯ · AI-এর যুগে automaton থেকে regex
AI assistant-কে একটি DFA দিয়ে regex চাইলে সে প্রায়ই দেখতে সুন্দর, ছোট একটি regex দেয়। সমস্যা হলো, ছোট আর সুন্দর হওয়া মানে সঠিক হওয়া নয়। এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| পদ্ধতি না চালিয়ে “অনুমান” করা regex, যেমন DIV3-এর জন্য (0 ∪ 11)∗ | Random আর brute-force পরীক্ষা: 1001-এর মতো পাল্টা-উদাহরণ সঙ্গে সঙ্গে আসে |
| ε ভুলে যাওয়া: শুরুর state accepting হলেও regex ফাঁকা string মেলায় না | ε, একক চিহ্ন আর দৈর্ঘ্য ২-এর সব string আগে হাতে দেখা |
| R2∗ বাদ দেওয়া বা R4 (পুরোনো সরাসরি তীর) ভুলে যাওয়া | প্রতিটি অপসারণে চারটি লেবেল আলাদা করে লেখা, তারপর সূত্রে বসানো |
| বন্ধনী ভুল জায়গায়, যেমন 1(01∗0)∗1 ∪ 0-কে 1(01∗0)∗(1 ∪ 0) লেখা | অগ্রাধিকার (star > concatenation > union) মনে রেখে, কোডে চালিয়ে দেখা |
| ε ∈ L(A) হলেও Arden-এর সূত্রে “একমাত্র সমাধান” দাবি | A-তে ফাঁকা string আছে কি না সবসময় আগে দেখা |
| “এটিই সবচেয়ে ছোট regex” বা “regex সবসময় DFA-র মাপের” ধরনের দাবি | অংশ ৭-এর সংখ্যা মনে রাখা: ক্রম বদলালে ১৪ থেকে ৫৩; সবচেয়ে খারাপে ঘাতের হার |
| বানানো রেফারেন্স বা ভুল সাল (যেমন Kleene-এর উপপাদ্যকে ১৯৭০-এর দশকে বসানো) | Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখা |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু উত্তর নয়, প্রতিটি ধাপ আর একটি স্বাধীন যাচাইয়ের কোড চাওয়া, তারপর সেটি নিজে চালানো।
(নিজে যাচাই করুন: DFA-টি “ab দিয়ে শেষ” language চেনে। সঠিক ধাপে উত্তর (a(ba ∪ a)∗bb ∪ b)∗a(ba ∪ a)∗b, আর ছোট রূপ (a ∪ b)∗ab. অনুশীলন ৪-এ পুরো হিসাব আছে, আর উপরের JavaScript ব্লক প্রথম রূপটিকে ২০,০০০ string-এ পরীক্ষা করেছে।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Kleene-এর উপপাদ্য শুধু একটি সুন্দর গাণিতিক ফল, নাকি এর বাস্তব গুরুত্বও আছে? “বর্ণনা” আর “যন্ত্র” একই হওয়ার মানে কী?
Kleene-এর ১৯৫৬ সালের প্রবন্ধের প্রশ্ন ছিল জীববিজ্ঞান-ঘেঁষা: McCulloch আর Pitts-এর ১৯৪৩ সালের স্নায়ু-জালের মডেল কোন ধরনের “ঘটনা” চিনতে পারে? Kleene দেখালেন, উত্তরটি একটি সরল সূত্র-ভাষা দিয়ে লেখা যায়, যেখানে আছে বিকল্প (union), পরপর ঘটা (concatenation) আর বারবার ঘটা (star). এভাবে একটি যন্ত্রের আচরণের প্রশ্ন একটি ভাষার প্রশ্নে বদলে গেল।
বাস্তবে এর মানে হলো, দুই রকম মানুষ দুই রকম ভাষায় কথা বলেও একই জিনিস বোঝাতে পারেন। একজন নিয়ম লেখেন regex-এ, কারণ সেটি ছোট আর পড়া সহজ: বাজারঘরের অর্ডার কোড BG-dddd. আরেকজন সেটি চালান automaton হিসেবে, কারণ সেটি দ্রুত আর মেমরি নির্দিষ্ট: প্রতিটি অক্ষরে একটি টেবিল-দেখা। পর্ব ১৪-এর Thompson construction আর এই পর্বের state elimination এই দুই ভাষার মধ্যে নিশ্চিত অনুবাদক। Lexer generator (পর্ব ২২) ঠিক এই সেতুর ওপর দাঁড়িয়ে: প্রকৌশলী token-এর নিয়ম regex-এ লেখেন, টুল সেটি DFA বানিয়ে কোড তৈরি করে।
উল্টো দিকটিও কাজে লাগে। একটি state machine-কে regex-এ লিখলে কখনো তার গঠন চোখে পড়ে, যেমন “01 আর 10 সমান সংখ্যক” language-এর regex দেখে বোঝা গেল আসল শর্তটি “প্রথম আর শেষ চিহ্ন সমান”। আবার প্রমাণের ক্ষেত্রেও সমতাটি শক্তিশালী: কোনো language regular প্রমাণ করতে regex, NFA বা DFA, যেটি সহজ সেটি বানালেই চলে; আর non-regular প্রমাণ করতে (পর্ব ১৭–১৮) যেকোনো একটি মডেলের সীমা দেখালেই তিনটির সীমা দেখানো হয়।
ইতিহাসের দিক থেকে উপপাদ্যটি নাম আর ধারণার উৎসও: “regular” শব্দটি Kleene-এর “regular event” থেকে, আর star operation-কে আজও তাঁর নামে Kleene star বলা হয়। পরবর্তী গবেষকরা (McNaughton–Yamada ১৯৬০, Brzozowski ১৯৬০-এর দশক) রূপান্তরগুলোকে আরও যান্ত্রিক algorithm-এ রূপ দেন, যা পরে compiler আর text-খোঁজার টুলে ব্যবহার হয়।
মূল উপলব্ধি: Kleene-এর উপপাদ্য একটি অনুবাদের নিশ্চয়তা: বর্ণনার ভাষা (regex) আর চালানোর যন্ত্র (automaton) একই শ্রেণির language ধরে। এই সেতুর ওপরই lexer, validator আর text-খোঁজার টুল দাঁড়িয়ে।
প্র ০২Regex থেকে NFA বানাতে আকার বাড়ে রৈখিক হারে, অথচ automaton থেকে regex বানাতে ঘাতের হারে বাড়তে পারে। এই অসমতার কারণ কী?
Thompson construction-এ (পর্ব ১৪) regex-এর প্রতিটি অংশের জন্য কয়েকটি নতুন state আর ε-তীর যোগ হয়; কোনো অংশ কপি হয় না। তাই NFA-র আকার regex-এর দৈর্ঘ্যের অনুপাতে। কারণটি গঠনের: regex একটি গাছ, আর গাছের প্রতিটি node একবারই যন্ত্রে বসে। Automaton কিন্তু গাছ নয়, একটি সাধারণ graph, যেখানে চক্রের ভেতর চক্র আর একই state-এ বহু পথ এসে মেলে।
State elimination-এ একটি state সরালে প্রতিটি জোড়ার নতুন লেবেলে R1, R2, R3 কপি হয়। একই R2 বহু জোড়ার লেবেলে একসঙ্গে বসে, আর পরের অপসারণে সেই কপিগুলো আবার কপি হয়। অংশ ৭-এ দেখেছেন, mod-7 DFA-তে খারাপ ক্রমে এক হাজারের বেশি অক্ষর। Regex-এ কোনো “নাম দিয়ে আবার ব্যবহার” ব্যবস্থা নেই: একটি উপ-অংশ দুই জায়গায় লাগলে দুবার লিখতে হয়। Graph-এ সেটি একটি state দিয়ে ভাগ করে নেওয়া যায়।
এটি শুধু পদ্ধতির দোষ নয়, বরং অনিবার্য। Ehrenfeucht আর Zeiger ১৯৭৬ সালে এমন DFA-র পরিবার দেখান, যেখানে প্রতিটি সমতুল্য regex ঘাতের হারে বড়; তাঁদের উদাহরণে alphabet বড় ছিল। Gruber আর Holzer প্রায় ২০০৮ সালে দেখান, ছোট alphabet-এও এমন সীমা থাকে, আর তাঁরা regex-এর আকারকে graph-এর একটি গঠনগত মাপের (cycle rank-এর মতো) সঙ্গে যুক্ত করেন। অর্থাৎ যে automaton-এর graph বেশি “জট পাকানো”, তার regex অনিবার্যভাবে লম্বা।
বাস্তবের শিক্ষা: automaton থেকে বানানো regex প্রায়ই মানুষের পড়ার যোগ্য থাকে না। তাই যন্ত্রে বানানো regex সাধারণত যন্ত্রের মধ্যেই ব্যবহার হয়, যেমন যাচাই বা প্রমাণে। মানুষের জন্য regex লেখার সময় আগে language-টি বুঝে হাতে ছোট regex লেখা, তারপর brute force বা পর্ব ২০-এর equivalence পরীক্ষা দিয়ে মূল automaton-এর সঙ্গে মেলানো ভালো, যেমন “ab দিয়ে শেষ”-এর ক্ষেত্রে (a ∪ b)∗ab.
মূল উপলব্ধি: Regex একটি গাছ, automaton একটি graph. গাছ থেকে graph বানানো সস্তা, কিন্তু জট-পাকানো graph-কে গাছে খুলতে গেলে কপি করতে হয়, আর সবচেয়ে খারাপ ক্ষেত্রে সেই কপির খরচ ঘাতের হারে, যা কোনো চালাক পদ্ধতিও এড়াতে পারে না।
প্র ০৩Arden-এর সূত্র, state elimination আর Kleene-এর Rij(k) পদ্ধতি কি আসলে তিনটি আলাদা জিনিস? এদের সঙ্গে shortest path algorithm-এর মিল কোথায়?
তিনটি পদ্ধতির ভেতরের ধাপ একই: “একটি মধ্যবর্তী বিন্দু বাদ দিয়ে, তার হয়ে যাওয়া সব পথ সরাসরি লেখা”। State elimination সেটি ছবিতে করে; Arden-এর সূত্রে একটি অজানা মুছে ফেলা সেটি সমীকরণে করে; আর Kleene-এর মূল প্রমাণ (পরে McNaughton আর Yamada ১৯৬০ সালে যার একটি algorithm-রূপ দেন) সেটি একটি টেবিলে করে: Rij(k) হলো i থেকে j-এর সেই সব পথ, যাদের মাঝের state শুধু 1 থেকে k-এর মধ্যে। k বাড়ানো মানে একটি নতুন মধ্যবর্তী state “অনুমতি দেওয়া”, আর সূত্রটি হুবহু R1R2∗R3 ∪ R4.
এবার DSA কোর্সের Floyd–Warshall algorithm মনে করুন: dij(k) = min(dij(k−1), dik(k−1) + dkj(k−1)). কাঠামো একই, শুধু operation আলাদা। ∪-এর জায়গায় min, concatenation-এর জায়গায় যোগ, আর star-এর জায়গায় “চক্রে ঘুরে লাভ নেই”, অর্থাৎ ঋণাত্মক চক্র না থাকলে 0. Transitive closure-এর Warshall algorithm-এ আবার ∪-এর জায়গায় OR আর concatenation-এর জায়গায় AND. এই সাধারণ কাঠামোর নাম হয়েছে Kleene algebra বা closed semiring; একই algorithm তিন রকম প্রশ্নের উত্তর দেয়, শুধু “যোগ” আর “গুণ” বদলে।
বীজগণিতের দিক থেকে regex-এর সমতা নিয়ে গভীর কাজ আছে। Regex-এর সব সত্য identity কোন অল্প কয়েকটি স্বতঃসিদ্ধ থেকে প্রমাণ করা যায়, এই প্রশ্নে Dexter Kozen ১৯৯০-এর দশকের শুরুতে Kleene algebra-র একটি সম্পূর্ণ স্বতঃসিদ্ধ-ব্যবস্থা দেন বলে পরিচিত; সেখানে Arden-ধরনের একটি নিয়ম (“X ⊇ AX ∪ B হলে X ⊇ A∗B”) একটি স্বতঃসিদ্ধ হিসেবেই আসে। প্রোগ্রাম যাচাইয়ের কিছু গবেষণায় এই বীজগণিত ব্যবহার হয়।
পরীক্ষার দিক থেকে কোনটি বেছে নেবেন? ছোট DFA-তে state elimination সবচেয়ে দ্রুত আর কম ভুলপ্রবণ, কারণ প্রতিটি ধাপ চোখে দেখা যায়। Arden-এর পদ্ধতি তখন ভালো, যখন প্রশ্নেই সমীকরণ দেওয়া থাকে বা উত্তর লিখে যুক্তি দেখাতে হয়। আর Rij(k) টেবিল কোডে লেখার জন্য সহজ, কিন্তু হাতে করলে অনেক বেশি ঘর ভরতে হয় (n2টি জোড়া, n + 1টি স্তর)।
মূল উপলব্ধি: তিনটি পদ্ধতি একই ধারণার তিনটি পোশাক: মধ্যবর্তী বিন্দু বাদ দিয়ে পথ জোড়া। একই কাঠামো shortest path আর transitive closure-এও কাজ করে, শুধু operation বদলে।
প্র ০৪State elimination একটি সঠিক regex দেয়, কিন্তু সবচেয়ে ছোটটি নয়। সবচেয়ে ছোট সমতুল্য regex খুঁজে বের করা কি সহজ? না হলে বাস্তবে কী করা হয়?
DFA-র ক্ষেত্রে সবচেয়ে ছোট রূপ খোঁজা সহজ আর অনন্য: minimisation দ্রুত চলে, আর minimal DFA নাম বদল ছাড়া একটিই (পর্ব ১৮–১৯)। Regex-এর ক্ষেত্রে ছবিটি একেবারে আলাদা। একই language-এর বহু সমান-দৈর্ঘ্যের সবচেয়ে ছোট regex থাকতে পারে, যেমন DIV3-এর (0 ∪ 1(01∗0)∗1)∗ আর ∪-এর দুই পাশ অদলবদল করা রূপ। আর খোঁজার খরচও বিশাল।
কারণটি equivalence-এর কঠিনতায়। দুটি regex একই language বর্ণনা করে কি না, সেটি যাচাই করা PSPACE-complete বলে প্রমাণিত; ফলটি সাধারণত Meyer আর Stockmeyer-এর ১৯৭০-এর দশকের শুরুর কাজের সঙ্গে যুক্ত। “সবচেয়ে ছোট সমতুল্য regex” খুঁজতে অন্তত এমন প্রশ্নের উত্তর জানতে হয় (“এই ছোট regex কি মূলটির সমান?”), তাই সাধারণভাবে এটিও অন্তত ততটা কঠিন। PSPACE-complete মানে polynomial সময়ের কোনো algorithm জানা নেই, আর থাকলে P = PSPACE হতো, যা বেশিরভাগ বিশেষজ্ঞ অসম্ভব মনে করেন, যদিও সেটি প্রমাণিত নয় (পর্ব ৬৫)।
বাস্তবে তাই তিনটি কৌশল একসঙ্গে চলে। প্রথমত, ভালো elimination ক্রম (কম তীরে যুক্ত state আগে), যা অংশ ৭-এ দৈর্ঘ্য ৫৩ থেকে ১৪-এ নামিয়েছে। দ্বিতীয়ত, প্রতিটি ধাপে সরলীকরণের identity: R ∪ R = R, (R∗)∗ = R∗, ε ∪ RR∗ = R∗, আর সমান অংশগুলো বাইরে আনা (পর্ব ১৩)। তৃতীয়ত, শুরুতেই DFA-টিকে minimise করা (পর্ব ১৯), কারণ কম state মানে কম অপসারণ আর কম কপি।
বাজারঘরের দলের জন্য ব্যবহারিক নিয়মটি সরল। Validator-এর regex মানুষ পড়বে আর বদলাবে, তাই সেটি হাতে লিখুন, ছোট আর অর্থপূর্ণ করে। তারপর automaton-টিকে “সত্যের উৎস” ধরে state elimination বা equivalence পরীক্ষা দিয়ে নিশ্চিত হোন যে দুটি একই language. অর্থাৎ যন্ত্র দিয়ে যাচাই, মানুষ দিয়ে লেখা।
মূল উপলব্ধি: সঠিক regex পাওয়া সহজ (state elimination), সবচেয়ে ছোটটি পাওয়া সাধারণভাবে কঠিন (equivalence PSPACE-complete). তাই বাস্তবে heuristic ক্রম, সরলীকরণ আর আগে DFA minimisation, আর মানুষের লেখা regex-কে যন্ত্র দিয়ে যাচাই।
প্র ০৫“01 আর 10 substring সমান সংখ্যকবার” language regular, অথচ “0 আর 1 সমান সংখ্যকবার” regular নয়। দুটিই তো গোনার শর্ত। পার্থক্য কোথায়, আর automaton থেকে regex বানানো এখানে কী শেখায়?
প্রথম দেখায় দুটি শর্তই একই রকম: দুটি জিনিস গুনে তুলনা। “0 আর 1 সমান সংখ্যক” language-এ যন্ত্রকে পার্থক্যটি মনে রাখতে হয়, যা যেকোনো বড় হতে পারে: 0n পড়ার পর n-টি সম্ভাব্য অবস্থা আলাদা রাখতে হয়। সসীম state দিয়ে সেটি অসম্ভব; প্রমাণ পর্ব ১৭-এর pumping lemma বা পর্ব ১৮-এর Myhill–Nerode দিয়ে। এটি regular নয়, কিন্তু context-free (পর্ব ২৫)।
“01 আর 10 সমান সংখ্যক” language-এ কিন্তু একটি গোপন গঠন আছে। একটি binary string-কে একই চিহ্নের খণ্ডে ভাগ করুন: যেমন 0011101 = 00 | 111 | 0 | 1. প্রতিটি সীমানায় হয় 01, নয় 10 থাকে, আর সীমানাগুলো পালাক্রমে আসে: 0-খণ্ড থেকে 1-খণ্ডে গেলে 01, তারপর 1 থেকে 0-তে গেলে 10. তাই দুই সংখ্যার পার্থক্য সবসময় 0 বা 1, আর পার্থক্য 0 মানে ঠিক “প্রথম খণ্ড আর শেষ খণ্ড একই চিহ্নের”। যন্ত্রকে মনে রাখতে হয় শুধু প্রথম চিহ্ন আর শেষ চিহ্ন: ৫টি state যথেষ্ট।
এখানেই automaton থেকে regex বানানোর একটি শিক্ষামূলক ব্যবহার। ৫-state DFA-টি বানানো হয়তো একটু চিন্তার কাজ, কিন্তু automata-lib-এর state elimination যে regex দিয়েছে, 1(00∗1 ∪ 1)∗ ∪ (0(11∗0 ∪ 0)∗)? (শেষের ? মানে ∪ ε), সেটি পড়লেই গঠন স্পষ্ট: 1 দিয়ে শুরু হলে 1 দিয়ে শেষ, 0 দিয়ে শুরু হলে 0 দিয়ে শেষ, অথবা ফাঁকা। Regex-টি language-এর একটি “ব্যাখ্যা” হয়ে উঠেছে। আর brute force (2047টি string) আর ২০,০০০ দৈব string-এর পরীক্ষা দুটিই দেখিয়েছে যে ব্যাখ্যাটি সংজ্ঞার সঙ্গে মেলে।
বৃহত্তর শিক্ষা হলো, “গোনার মতো শোনায়” দেখে non-regular ধরে নেওয়া একটি সাধারণ ভুল, আর AI assistant-ও প্রায়ই এই ভুল করে। একটি language regular কি না, তার উত্তর আসে প্রমাণ থেকে: হয় একটি যন্ত্র বা regex বানিয়ে যাচাই করা, নয়তো একটি non-regularity প্রমাণ। প্রথম চিহ্ন আর শেষ চিহ্ন মনে রাখার মতো সসীম তথ্যই কখনো যথেষ্ট হয়।
মূল উপলব্ধি: Regularity নির্ভর করে যন্ত্রকে কত তথ্য মনে রাখতে হয় তার ওপর, শর্তটি শুনতে কেমন তার ওপর নয়। Automaton থেকে regex বানানো কখনো একটি language-এর লুকানো সরল গঠন বের করে আনে।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। DFA বদলে state_elim.py ব্লকে বসিয়ে নিজের উত্তরও যাচাই করতে পারেন।
-
নকশা ও রূপান্তর: Σ = {0, 1}-এর ওপর L = {w : w-এ 01 substring যতবার, 10 substring ঠিক ততবার}. (ক) L-এর জন্য একটি DFA নকশা করুন। (খ) ছোট উদাহরণে দেখান, L = “ফাঁকা, অথবা প্রথম আর শেষ চিহ্ন সমান”। (গ) DFA থেকে একটি regex লিখুন।
(ক) পাঁচটি state: s (শুরু, কিছু পড়া হয়নি), a0 (প্রথম 0, শেষ 0), b0 (প্রথম 0, শেষ 1), a1 (প্রথম 1, শেষ 1), b1 (প্রথম 1, শেষ 0). s থেকে 0-তে a0, 1-এ a1. a0 আর b0-এর মধ্যে: 0 পড়লে a0, 1 পড়লে b0. a1 আর b1-এর মধ্যে: 1 পড়লে a1, 0 পড়লে b1. Accepting: s, a0, a1. এটি অংশ ৮-এর automata-lib run-এর DFA.
(খ) 0110: 01 একবার, 10 একবার, সমান; প্রথম আর শেষ দুটিই 0. 011: 01 একবার, 10 শূন্যবার, অসমান; প্রথম 0, শেষ 1. যুক্তি: একই চিহ্নের খণ্ডের সীমানায় 01 আর 10 পালাক্রমে আসে, তাই দুই সংখ্যা সমান ⇔ প্রথম আর শেষ খণ্ড একই চিহ্নের (ভাবনার প্রশ্ন ০৫)। Scratch-এ দৈর্ঘ্য 12 পর্যন্ত সব string-এ এই দুই সংজ্ঞা মেলানো হয়েছে।
(গ) হাতে সহজ রূপ: ε ∪ 0 ∪ 1 ∪ 0(0 ∪ 1)∗0 ∪ 1(0 ∪ 1)∗1. State elimination-এ automata-lib দিয়েছে 1(00∗1 ∪ 1)∗ ∪ (0(11∗0 ∪ 0)∗)?, যেখানে ? মানে ∪ ε. দুটি regex ভিন্ন দেখালেও একই language; দৈর্ঘ্য 10 পর্যন্ত brute force-এ দুটিই DFA-র সঙ্গে মিলেছে।
-
প্রমাণের ভুল ধরুন: Σ = {a, b}. দাবি: “X = (a ∪ ε)X ∪ b সমীকরণের একমাত্র সমাধান X = (a ∪ ε)∗b = a∗b.” যুক্তি: “Arden-এর সূত্রে A = a ∪ ε আর B = b, তাই X = A∗B. ∎” ভুল কোথায়? একটি দ্বিতীয় সমাধান দিন।
Arden-এর সূত্রের শর্ত ε ∉ L(A), কিন্তু এখানে A = a ∪ ε, তাই ε ∈ L(A). শর্ত ভাঙলে A∗B তবু একটি সমাধান থাকে (প্রমাণের ধাপ ১–২ শর্ত ছাড়াই খাটে), কিন্তু “একমাত্র” দাবিটি (ধাপ ৫–৮) ভেঙে পড়ে: ধাপ ৭-এ u = ε নেওয়া যায়, তখন v = w আর ছোট string-এর যুক্তি কাজ করে না।
দ্বিতীয় সমাধান X = Σ∗: (a ∪ ε)Σ∗ ∪ {b} = aΣ∗ ∪ Σ∗ ∪ {b} = Σ∗. আরও সাধারণভাবে, যে X-এ b আছে আর যার প্রতিটি string-এর বাঁয়ে a জুড়লে ফল আবার X-এই থাকে, সেটিই সমাধান, যেমন a∗b ∪ a∗bb. Scratch-এ দৈর্ঘ্য 8 পর্যন্ত string নিয়ে তিনটি সমাধানই (a∗b, a∗b ∪ a∗bb আর Σ∗) সমীকরণের দুই পাশে বসিয়ে যাচাই করা হয়েছে।
-
হিসাব (Arden): Σ = {0, 1}-এর ওপর “1-এর সংখ্যা বিজোড়” DFA: x0 (শুরু) 0-তে x0, 1-এ x1; x1 (accepting) 0-তে x1, 1-এ x0. সমীকরণ লিখে Arden-এর সূত্রে L-এর regex বের করুন। তারপর অনুমান করুন: এই regex 0110-কে মেলাবে কি? 0100?
সমীকরণ: X0 = 0X0 ∪ 1X1, আর X1 = 0X1 ∪ 1X0 ∪ ε. X1-এ Arden (A = 0, B = 1X0 ∪ ε): X1 = 0∗(1X0 ∪ ε) = 0∗1X0 ∪ 0∗. X0-এ বসিয়ে: X0 = 0X0 ∪ 10∗1X0 ∪ 10∗ = (0 ∪ 10∗1)X0 ∪ 10∗. আবার Arden (A = 0 ∪ 10∗1, যাতে ε নেই): X0 = (0 ∪ 10∗1)∗10∗.
0110-এ 1 দুটি (জোড়), তাই মেলাবে না; 0100-এ 1 একটি, তাই মেলাবে: 0 (প্রথম অংশ থেকে), তারপর 1, তারপর 00 (শেষের 0∗)। Scratch-এ এই regex দৈর্ঘ্য 10 পর্যন্ত সব 2047টি string-এ DFA-র সঙ্গে মিলেছে।
-
Trace (state elimination): Σ = {a, b}-এর DFA: q0 (শুরু) a-তে q1, b-তে q0; q1 a-তে q1, b-তে q2; q2 (accepting) a-তে q1, b-তে q0. GNFA বানিয়ে q2, q1, q0 ক্রমে state সরান; প্রতিটি অপসারণের পর বদলানো তীরগুলো লিখুন। শেষ regex কী, আর এটি কি (a ∪ b)∗ab-এর সমতুল্য?
- GNFA: s→q0: ε, q2→t: ε, আর DFA-র ছয়টি তীর। — অংশ ২-এর তিন ধাপ
- q2 সরানো: ঢোকে q1 থেকে (b), চক্কর নেই (R2 = ∅, তাই R2∗ = ε), বের হয় q1 (a), q0 (b) আর t (ε)-তে। নতুন: q1→q1 = ba ∪ a, q1→q0 = bb, q1→t = b. — R1R3 ∪ R4
- q1 সরানো: ঢোকে q0 থেকে (a), চক্কর ba ∪ a, বের হয় q0 (bb) আর t (b)-তে। নতুন: q0→q0 = a(ba ∪ a)∗bb ∪ b, q0→t = a(ba ∪ a)∗b. — বাইরের স্তরে ∪ আছে বলে চক্করের চারপাশে বন্ধনী
- q0 সরানো: s→t = (a(ba ∪ a)∗bb ∪ b)∗a(ba ∪ a)∗b. ∎ — R1 = ε, R4 = ∅
হ্যাঁ, সমতুল্য: DFA-টি ঠিক “ab দিয়ে শেষ” string চেনে (q1 মানে শেষ চিহ্ন a, q2 মানে শেষ দুটি ab). Scratch-এ state_elim.py-এর কোডে এই ক্রমে হুবহু একই regex এসেছে, আর এটি এবং (a ∪ b)∗ab দুটিই দৈর্ঘ্য 10 পর্যন্ত সব 2047টি string-এ DFA-র সঙ্গে মিলেছে। অন্য ক্রমে (q1, q2, q0) পাওয়া যায় (aa∗b(aa∗b)∗b ∪ b)∗aa∗b(aa∗b)∗, আরও লম্বা। কোনো ক্রমই সরাসরি ছোট রূপটি দেয় না; সেটি পেতে হাতে চিন্তা লাগে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি DFA থেকে state elimination দিয়ে regex বের করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- নতুন শুরু state s যোগ করে s থেকে পুরোনো শুরুতে ε-তীর দেওয়া
- নতুন accepting state t যোগ করে প্রতিটি পুরোনো accepting state থেকে t-তে ε-তীর দেওয়া
- একই দিকের সমান্তরাল তীরের লেবেল ∪ দিয়ে জোড়া, তীর না থাকলে লেবেল ∅ ধরা
- একটি qrip বেছে প্রতিটি জোড়ার লেবেল R1R2∗R3 ∪ R4 দিয়ে বদলানো আর qrip মুছে ফেলা
- শুধু s আর t বাকি থাকলে s থেকে t তীরের লেবেলটি উত্তর হিসেবে নেওয়া
একটি GNFA-তে qi → qrip লেবেল a, qrip-এর নিজের চক্কর b, qrip → qj লেবেল c, আর qi → qj লেবেল d. qrip সরালে qi → qj-এর নতুন লেবেল কী?
- abc ∪ d
- ab∗c
- ab∗c ∪ d
- (abc)∗ ∪ d
Sipser-ধরনের GNFA-র সংজ্ঞায় নিচের কোনটি শর্ত নয়?
- শুরুর state-এ কোনো তীর ঢোকে না
- প্রতিটি তীরের লেবেল একটি একক চিহ্ন বা ε
- ঠিক একটি accepting state, যা থেকে কোনো তীর বের হয় না
- শুরু আর accepting state ভিন্ন
Σ = {0, 1}-এর ওপর X = 0X ∪ 1 সমীকরণের একমাত্র সমাধান কী?
- 0∗1
- 10∗
- (0 ∪ 1)∗
- 0∗
Arden-এর সূত্রে X = AX ∪ B-এর সমাধান “একমাত্র” হওয়ার জন্য কোন শর্ত লাগে?
- B ≠ ∅
- A একটি সসীম language
- A ∩ B = ∅
- ε ∉ A
একটি language-এর জন্য DFA, NFA আর regex-এর মধ্যে সম্পর্ক নিয়ে Kleene-এর উপপাদ্য (state elimination আর Thompson construction মিলিয়ে) কী বলে?
- NFA DFA-র চেয়ে বেশি language চেনে, আর regex দুটির চেয়ে কম
- একটি language DFA-র language ⇔ NFA-র language ⇔ কোনো regex-এর language
- শুধু কিছু regex-এর language DFA দিয়ে চেনা যায়
- তিনটির সমতা একটি অপ্রমাণিত অনুমান
একই DFA-তে দুটি ভিন্ন ক্রমে state elimination চালালে ফল সম্পর্কে কোনটি সত্য?
- সবসময় হুবহু একই regex আসে
- কিছু ক্রমে ভুল language আসতে পারে
- Regex ভিন্ন হতে পারে, কিন্তু language একই, আর দৈর্ঘ্য অনেক আলাদা হতে পারে
- সঠিক ক্রমে সবসময় সবচেয়ে ছোট সম্ভাব্য regex আসে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- GNFA: তীরের গায়ে regex, শুরুতে কোনো তীর ঢোকে না, একমাত্র accepting state থেকে কোনো তীর বের হয় না। DFA থেকে বানাতে নতুন s আর t, আর সমান্তরাল তীর ∪ দিয়ে জোড়া।
- State elimination: qrip সরালে নতুন লেবেল R1R2∗R3 ∪ R4; শুধু s আর t বাকি থাকলে s → t-এর লেবেলই উত্তর। প্রতিটি অপসারণ language রাখে।
- Arden-এর সূত্র: ε ∉ L(A) হলে X = AX ∪ B-এর একমাত্র সমাধান A∗B; DFA-র state-সমীকরণ একে একে সমাধান করলে state elimination-এর মতোই উত্তর।
- Kleene-এর উপপাদ্য (১৯৫৬): DFA = NFA = regex, তিনটিই ঠিক regular language বর্ণনা করে।
- Elimination ক্রম regex-এর দৈর্ঘ্য বদলায় (DIV3-এ ১৪ থেকে ৫৩), আর সবচেয়ে খারাপ ক্ষেত্রে regex ঘাতের হারে বড় হওয়া অনিবার্য; ফল সবসময় brute force বা equivalence পরীক্ষায় যাচাই করুন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ১০ · NFA থেকে DFA — subset construction আর state বিস্ফোরণফিরে দেখুনKleene-এর উপপাদ্যের আরেকটি অংশ: NFA থেকে DFA, আর উল্টো দিকের আকার-বিস্ফোরণের সঙ্গে তুলনা।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ১৬ regular language-এর closure property.
- পর্ব ০৮ · DFA নকশা — product construction, complement আর গণনার কৌশলপটভূমিDIV3 আর mod-m DFA-র নকশা, যেগুলো এই পর্বে regex-এ রূপান্তর হয়েছে।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৪ — Finite automaton আর regular expression-এর পরিচয়পটভূমিFinite automaton, regex আর Kleene-এর উপপাদ্যের একটি ছোট প্রথম পরিচয়।
- DSA · পর্ব ৪৪ — Bellman-Ford আর Floyd-Warshallপাশের ট্র্যাকKleene-এর Rij(k) পদ্ধতির সঙ্গে একই কাঠামোর shortest path algorithm.
- Python প্রোগ্রামিং · পর্ব ৩০ — regular expressionহাতে-কলমেPython-এর re module; formal regex থেকে বাস্তব regex-এ যাওয়ার সেতু।