Pumping Lemma
পাম্পিং লেমা
প্রতিটা যথেষ্ট লম্বা regular (বা context-free) স্ট্রিং-এর একটা অংশ বারবার পুনরাবৃত্তি (pump) করা যায় আর তবু ভাষায় থাকে — এই necessary condition ভঙ্গ দেখিয়েই কোনো ভাষা non-regular/non-CF প্রমাণ করা হয়।
also: Pumping Theorem
Regular ভাষার জন্য: L regular হলে একটা p আছে এমন যে
L-এর প্রতিটা s (|s| ≥ p) s = xyz আকারে ভাগ হয়, |xy| ≤ p,
|y| ≥ 1, আর সব i ≥ 0-এর জন্য xyⁱz ∈ L। প্রমাণের উৎস:
pigeonhole নীতি — p-state DFA-তে p-এর বেশি character পড়লে
কোনো state পুনরাবৃত্ত হবেই, সেই লুপ-অংশটাই y।
Context-free ভাষার জন্য: সংস্করণ একটু জটিল — s = uvwxy,
|vwx| ≤ p, |vx| ≥ 1, সব i-তে uvⁱwxⁱy ∈ L (দুইটা অংশ
একসাথে pump হয়, parse tree-র recursive structure থেকে)।
Classic প্রয়োগ: {0ⁿ1ⁿ} non-regular (pigeonhole — লুপ শুধু
0-ব্লকে পড়ে, pump করলে সংখ্যা অসমান হয়ে যায়); {aⁿbⁿcⁿ}
non-context-free (কোনো ≤p window একসাথে তিনটা ব্লক ছুঁতে পারে না)।
সতর্কতা: এটা শুধু একমুখী প্রমাণের টুল — pumping lemma পাস করা মানে ভাষাটা regular/CF, এমন প্রমাণ না (inherently non-regular কিছু ভাষা এটা পাস করে); ব্যর্থ হলেই কেবল non-membership নিশ্চিত।