Regular Expressions ও Pumping Lemma — ক্ষমতা আর তার সীমা

Thompson’s construction — regex থেকে NFA, structural induction দিয়ে

মূল কৌশল: regex-এর সংজ্ঞার প্রতিটা case-এর জন্য একটা fixed NFA fragment টেমপ্লেট, ঠিক একটা start state আর একটা accept state-সহ। জটিল regex-এর fragment ছোট fragment জোড়া দিয়ে বানানো হয় — mathematics/induction-এর structural induction ঠিক এই প্যাটার্নে কোড হয়ে ওঠে।

Base: ε              Base: a                Base: ∅
  ┌──ε──┐              ┌──a──┐                (কোনো accept-যোগ্য
 →○      ●→            →○     ●→               path নেই — একটা
  └─────┘              └─────┘                 বিচ্ছিন্ন state)

Union (R1|R2):                Concat (R1R2):
      ┌─ε→[ R1 ]─ε─┐            →[ R1 ]──ε──[ R2 ]→
   →○─┤             ├●→          (R1-র accept = R2-র start,
      └─ε→[ R2 ]─ε─┘             ε দিয়ে জোড়া)

Star (R1*):
        ┌────────ε────────┐
        ↓                 │
   →○───ε──→[ R1 ]──ε──→──┴──●→
    │                          ↑
    └─────────ε────────────────┘

প্রতিটা fragment-এর ভেতরের state-গুলো fragment-এর বাইরে থেকে অদৃশ্য — শুধু একটা start আর একটা accept বাইরে জোড়া লাগানোর জন্য উন্মুক্ত। এটাই compositionality — বড় regex-এর NFA বানাতে পুরো global structure নতুন করে ভাবতে হয় না, শুধু sub-regex-এর fragment জোড়া লাগালেই হয়।

সম্পূর্ণ worked example — a(b|c)*

compilers/lexical-analysis-এ আমরা এই ধরনের NFA “থেকে এসেছে” বলে ধরে নিয়েছিলাম — এবার হাতে বানাই।

ধাপ ১ — a: টেমপ্লেট থেকে সরাসরি: s0 --a--> s1।

ধাপ ২ — b, c: s2 --b--> s3 এবং s4 --c--> s5।

ধাপ ৩ — (b|c): Union টেমপ্লেট প্রয়োগ, নতুন u_start, u_accept:

u_start --ε--> s2 --b--> s3 --ε--> u_accept
u_start --ε--> s4 --c--> s5 --ε--> u_accept

ধাপ ৪ — (b|c)*: Star টেমপ্লেট প্রয়োগ, নতুন st_start, st_accept:

st_start --ε--> u_start   (fragment-এ ঢোকা)
u_accept --ε--> st_start  (আবার লুপ)
st_start --ε--> st_accept (শূন্যবার — সরাসরি স্কিপ)
u_accept --ε--> st_accept (এক বা একাধিকবার পরে বেরোনো)

ধাপ ৫ — a(b|c)*: Concat টেমপ্লেট প্রয়োগ — s1 (আগের a-র accept) থেকে st_start-এ ε দিয়ে জোড়া:

s0 --a--> s1 --ε--> st_start --ε--> u_start --b--> s3 --ε--> u_accept
                        ↑                                        │
                        └───────────────ε───────────────────────┘
                     (loop) ... এবং u_start --ε--> s4 --c--> s5 --ε--> u_accept
st_start --ε--> st_accept (final)

এই পুরো NFA-টা এখন গত লেসনের subset construction-এ সরাসরি feed করা যায় — একটা DFA বেরিয়ে আসবে যেটা a(b|c)* চেনে O(1)/character-এ। এটাই সম্পূর্ণ pipeline: regex (মানুষ লেখে) → NFA (Thompson’s, যান্ত্রিক) → DFA (subset construction, যান্ত্রিক) → minimized DFA (partition refinement, যান্ত্রিক)। প্রতিটা তীর একটা প্রমাণিত, deterministic algorithm — মানুষের হাতে শুধু প্রথম ধাপ।

Backtracking regex engine — সম্পূর্ণ ভিন্ন একটা কৌশল

এখন প্রশ্ন — Python-এর re, PCRE, JavaScript regex কি এই pipeline অনুসরণ করে? না। এরা ব্যবহার করে backtracking — একটা সম্পূর্ণ ভিন্ন algorithm পরিবার, যেটা regex-কে recursive search হিসেবে ট্রিট করে।

Backtracking matcher regex-কে বাম থেকে ডানে চেষ্টা করে; |-এ প্রথম বিকল্প নেয়, *-এ যতদূর সম্ভব greedily নেয়। যদি পরে ব্যর্থ হয়, backtrack করে — আগের সিদ্ধান্ত পাল্টে অন্য বিকল্প চেষ্টা করে। এটাই *-এর প্রতিটা সম্ভাব্য বিভাজন exhaustively চেষ্টা করতে পারে যদি প্রথম কয়েকটা চেষ্টা ব্যর্থ হয়।

কেন এই ডিজাইন? কারণ backtracking engine সহজেই এমন feature সমর্থন করে যা automaton-ভিত্তিক পদ্ধতিতে অসম্ভব — backreference (\1), lookahead/lookbehind। এই feature-গুলো regular ভাষার সংজ্ঞার বাইরে (লেসন ১-এর misconception অংশ মনে করুন) — তাই কোনো DFA/NFA এগুলো represent করতেই পারে না। Backtracking-ই একমাত্র স্বাভাবিক উপায় এগুলো implement করার।

মূল্য: সেই নমনীয়তার বিনিময়ে backtracking engine-এর worst-case সময় exponential, DFA simulation-এর গ্যারান্টিড O(n)-এর বিপরীতে।

Catastrophic backtracking — কীভাবে exponential হয়

Classic উদাহরণ: pattern (a+)+b — string "aaaaaaaaaaaaaaaaaaaa" (কোনো ট্রেইলিং b নেই, তাই ব্যর্থ হতেই হবে)-এর বিরুদ্ধে চালান।

কেন এত ধীর? (a+)+ -এর ভেতরের a+ আর বাইরের + — দুইটাই “এক বা একাধিকবার” বোঝায়, তাই n টা a-কে groups-এ ভাগ করার সম্ভাব্য উপায় সূচকীয়ভাবে বেশি (2^(n-1)-এর কাছাকাছি — এটা composition-এর সংখ্যা, mathematics-এর combinatorics লেসনের “compositions of n” গণনার ঠিক প্রয়োগ)। শেষে b না পেয়ে matcher ব্যর্থ হয়, কিন্তু ব্যর্থ হওয়ার আগে প্রতিটা সম্ভাব্য বিভাজন চেষ্টা করে ফেলে।

এটাই ReDoS (Regular Expression Denial of Service) — যদি কোনো attacker আপনার input validation regex-এ এমন একটা pattern খুঁজে পায় যা catastrophic backtracking-এর শিকার, তাহলে মাত্র কয়েকশ character-এর একটা string পাঠিয়েই আপনার সার্ভারের একটা CPU core সেকেন্ডের বদলে ঘণ্টার পর ঘণ্টা ব্যস্ত রাখতে পারে — Cloudflare-এর গল্পটা ঠিক এভাবেই ঘটেছিল।

Pumping Lemma — regular ভাষার একটা কাঠামোগত সীমাবদ্ধতা

গত লেসনে আমরা দেখেছি DFA-র state সংখ্যা সসীম। এই সসীমতাই একটা গভীর পরিণতি টেনে আনে, যেটা এখন আমরা কঠোরভাবে বিবৃত করব।

সহজ যুক্তি (pigeonhole): একটা p-state DFA-তে যদি একটা string s accept হয় যার দৈর্ঘ্য |s| ≥ p, তাহলে s পড়ার সময় DFA কমপক্ষে p+1 টা state visit করে (শুরুর state + প্রতিটা character পড়ার পরের state)। কিন্তু DFA-তে মাত্র p টা state আছে — তাই pigeonhole নীতি অনুযায়ী (mathematics/relations-এর pigeonhole, লেসন ১-এও উল্লেখ করা হয়েছিল) কোনো state অন্তত দুইবার visit হবেই, প্রথম p character পড়ার মধ্যে।

সেই পুনরাবৃত্ত state-এর মাঝের অংশটা একটা loop — DFA-তে সেই loop-টা শূন্যবার, একবার, দুইবার, যতবার খুশি ঘোরা যায় আর প্রতিবারই বাকি string-এর সাথে মিলিয়ে string-টা এখনও accept হবে। এই “যতবার খুশি ঘোরানো”-ই pumping।

আনুষ্ঠানিক বিবৃতি

যদি L একটা regular ভাষা হয়, তাহলে একটা সংখ্যা p ≥ 1 (pumping length) আছে এমন যে: L-এর যেকোনো string s-এর জন্য যেখানে |s| ≥ p, s-কে তিন ভাগে ভাগ করা যায় s = xyz যেখানে:

1. |xy| ≤ p
2. |y| ≥ 1 (y খালি না)
3. প্রতিটা i ≥ 0-এর জন্য, xyⁱz ∈ L

p = সমতুল্য DFA-র state সংখ্যা (বা তার চেয়ে কম যেকোনো বৈধ bound)। xy -র দৈর্ঘ্য p-এর মধ্যে সীমাবদ্ধ রাখার শর্তটাই নিশ্চিত করে যে y লুপ-অংশটা string-এর প্রথম p character-এর ভেতরেই পড়বে — এটাই pigeonhole argument-এর সরাসরি ফলাফল।

সম্পূর্ণ প্রমাণ — {0ⁿ1ⁿ : n ≥ 0} regular না

এই module-এর প্রথম লেসন থেকেই এই দাবিটা ঝুলে আছে — এবার প্রমাণ।

দাবি: L = {0ⁿ1ⁿ : n ≥ 0} regular না।

প্রমাণ (contradiction দিয়ে, pumping lemma প্রয়োগ করে)।

ধরি L regular। তাহলে pumping lemma অনুযায়ী একটা p আছে যেমন বর্ণিত উপরে।

আমরা বাছি: s = 0ᵖ1ᵖ। লক্ষ্য করুন s ∈ L (n = p নিয়ে) এবং |s| = 2p ≥ p — শর্ত পূরণ।

প্রতিপক্ষ যেকোনো বিভাজন s = xyz বাছুক, শর্ত মেনে (|xy| ≤ p, |y| ≥ 1)। যেহেতু s-এর প্রথম p character সবগুলোই 0 (কারণ s = 0ᵖ1ᵖ), আর |xy| ≤ p, তাই xy সম্পূর্ণভাবে সেই প্রথম p-টা 0-এর মধ্যে পড়ে। অতএব x আর y দুটোই শুধু 0 দিয়ে গঠিত — y = 0ᵏ কোনো k ≥ 1-এর জন্য (|y| ≥ 1 শর্ত থেকে k ≥ 1)।

আমরা বাছি i = 2 (pump up):

$xy^2z = 0^{\,p-k}\underbrace{0^k \cdot 0^k}_{y \text{ দুইবার}}0^{\text{(z-এর 0 অংশ, যদি থাকে)}}1^p$

সরল করে — মোট 0-র সংখ্যা p + k (মূল p-এর সাথে অতিরিক্ত k যোগ হলো, 1-র সংখ্যা অপরিবর্তিত p)। যেহেতু k ≥ 1:

$xy^2z = 0^{\,p+k}1^p, \qquad p + k \neq p$

0-র সংখ্যা 1-র সংখ্যার সমান না, তাই xy²z ∉ L।

এটা pumping lemma-র ৩ নম্বর শর্তের সরাসরি বিরোধিতা — যেটা দাবি করেছিল সব i ≥ 0-এর জন্য xyⁱz ∈ L, কিন্তু আমরা একটা i (= 2) দেখিয়েছি যেখানে সেটা মিথ্যা। Contradiction।

অতএব আমাদের অনুমান (“L regular”) মিথ্যা। ∎