Pumping lemmas और nonmembership proofs
लक्ष्य और quantifier game
Pumping की necessary properties से nonregular या non-context-free होना सिद्ध करें। Pumping length assumed language का है; convenient split देखकर बाद में नहीं चुनते। दोनों lemmas one-way necessary conditions हैं। एक string का pump होना, या lemma की पूरी condition स्थापित करना भी, अपने आप class membership का proof नहीं है।
1. Regular pumping lemma
यदि L regular है तो कोई p≥1 है जिससे हर w∈L, |w|≥p के लिए w=xyz का split मिलता है, जहाँ |xy|≤p, |y|≥1 और हर integer i≥0 पर xy^i z∈L। क्रम है ∃p, ∀long w, ∃valid split, ∀i। DFA path के पहले p+1 states में repeated state से loop y मिलता है; उसे हटाने पर i=0 और दोहराने पर बड़े i मिलते हैं।
Nonregularity के लिए hypothetical p मानें, उसके आधार पर w चुनें, फिर हर valid split को किसी i से हराएँ; i split पर निर्भर हो सकता है। Opponent के लिए y आप नहीं चुन सकते। एक खराब split पर्याप्त नहीं, क्योंकि lemma केवल एक अच्छे split का वादा करता है।
हल: L={a^n b^n:n≥0} में w=a^p b^p लें। हर valid split में y=a^k, 1≤k≤p है क्योंकि |xy|≤p। i=0 पर xz=a^(p−k)b^p में counts unequal हैं, इसलिए L के बाहर। हर split fail है, इसलिए regularity assumption गलत। w=ε चुनना गलत होता, क्योंकि lemma length कम-से-कम p की strings पर condition देता है।
दूसरा proof: L={a^(n²):n≥0} में w=a^(p²) लें। हर valid y की length k है, 1≤k≤p। i=2 पर length p²+k। चूँकि p²<p²+k≤p²+p<(p+1)², यह square नहीं है। इसलिए L nonregular है। Inequality हर k को संभालती है, किसी चुने split को ही नहीं।
2. Context-free pumping lemma
यदि L CFL है तो कोई p≥1 है जिससे हर w∈L, |w|≥p का split uvxyz मिलता है, जहाँ |vxy|≤p, |vy|≥1 और हर integer i≥0 पर uv^i x y^i z∈L। v तथा y एक ही i से साथ pump होते हैं। एक empty हो सकता है, दोनों नहीं। Bounded window vxy है, पूरा prefix uvxy नहीं। लंबे parse-tree path पर repeated variable nested derivations दोहराने देता है, जिससे दो pumped pieces मिलते हैं।
Non-CFL proof के लिए हर hypothetical p पर long word चुनें, हर allowed five-part split देखें और कोई exponent देकर result को L से बाहर करें। Regular lemma fail होने से केवल nonregularity सिद्ध होती है; PDA फिर भी language पहचान सकता है।
3. तीन equal blocks का पूरा proof
L={a^n b^n c^n:n≥0} में w=a^p b^p c^p लें। Length अधिकतम p का window vxy एक a और एक c दोनों नहीं रख सकता: इनके बीच सभी p b तथा दोनों ओर एक-एक symbol होने से length कम-से-कम p+2 होगी। इसलिए v और y मिलकर अधिकतम दो adjacent blocks के symbols रखते हैं।
i=0 लेकर v,y delete करें। |vy|≥1 से कम-से-कम एक symbol हटेगा। Window एक पूरा symbol type छोड़ता है, इसलिए उस type की count p रहेगी; कोई दूसरी count p से कम होगी। Deletion से abc* order बचता है, लेकिन तीन counts equal नहीं रह सकते। इसलिए हर valid split पर uxz∉L, जो CFL lemma का contradiction है। यह proof एक block के भीतर window, boundary-crossing window और empty v या y, सभी संभालता है; दोनों को nonempty नहीं मानता।
4. Closure के साथ pumping
K={w over {a,b,c}: #a(w)=#b(w)=#c(w)} को regular abc* से intersect करें। Result ठीक ऊपर की three-block non-CFL है। यदि K CFL होता तो regular intersection closure से result भी CFL होता। Contradiction से K non-CFL है। Regular filter proof सरल करता है और contradiction की दिशा बनाए रखता है।
Checklist
Assumed class बताएँ; quantifiers लिखें; लंबा w∈L चुनें; split arbitrary रखें; length restrictions मानें; i बताएँ; pumped result L से बाहर सिद्ध करें। Proof attempt fail होने को membership का proof न मानें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Regular pumping contradiction में valid split को कैसे संभालना है?
A. एक convenient split चुनें B. हर valid split की failure दिखाएँ C. |xy|≤p अनदेखा करें D. y के बाद p चुनें
उत्तर: B
A: Lemma दूसरा split ले सकता है।
B: हर possible promised split हराना होगा।
C: यह restriction y की जगह तय करती है।
D: Pumping length पहले आता है।
P02. a^p b^p में regular pumping से y क्या होगा?
A. a^k, जहाँ 1≤k≤p B. b^k, जहाँ k≥1 C. ε D. a/b boundary जरूर पार करने वाली string
उत्तर: A
A: पहले p positions केवल a हैं।
B: Bound b तक जाने नहीं देता।
C: Empty y मना है।
D: Window a block के भीतर खत्म है।
P03. CFL pumping lemma में क्या जरूरी है?
A. v और y दोनों nonempty हों B. केवल v pump हो C. |vxy|≤p और |vy|≥1 D. |uvxy|≤p
उत्तर: C
A: v,y में एक empty हो सकता है।
B: दोनों एक exponent से pump होते हैं।
C: यही window तथा nonemptiness constraints हैं।
D: Bounded window में u नहीं है।
P04. a^p b^p c^p का length-p window a और c दोनों क्यों नहीं रख सकता?
A. a और c समान symbols हैं B. कम-से-कम p+2 positions चाहिए C. Word में b नहीं है D. Pumping length शून्य होना चाहिए
उत्तर: B
A: दोनों अलग symbols हैं।
B: चुने a और c के बीच सभी p b हैं।
C: ठीक p b हैं।
D: p कम-से-कम एक है।
P05. Language nonregular होने का proof क्या सिद्ध करता है?
A. वह context-free नहीं B. वह undecidable है C. कोई finite automaton उसे recognize नहीं करता D. कोई PDA उसे recognize नहीं करता
उत्तर: C
A: कुछ nonregular languages CFL हैं।
B: a^n b^n decidable है।
C: Regular language की definition से यही मिलता है।
D: PDA a^n b^n पहचानता है।
P06. Square-length proof में 1≤k≤p पर p²+k square क्यों नहीं?
A. वह हमेशा odd है B. वह p² और (p+1)² के बीच strictly है C. सभी बड़े numbers nonsquare हैं D. Pumping alphabet बदलता है
उत्तर: B
A: Parity बदल सकती है।
B: Consecutive squares के बीच square नहीं है।
C: Arbitrarily large squares होते हैं।
D: Alphabet unary ही रहता है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Theory of Computation syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन