Pumping lemma for context-free languages
कंप्यूटर विज्ञान में, विशेष रूप से औपचारिक भाषा सिद्धांत में, संदर्भ-मुक्त भाषाओं के लिए पंपिंग लेम्मा, जिसे बार-हिलेल लेम्मा के रूप में भी जाना जाता है, एक ऐसा लेम्मा है जो सभी संदर्भ-मुक्त भाषाओं द्वारा साझा गुण देता है और नियमित भाषाओं के लिए पंपिंग लेम्मा को सामान्य करता है। पंपिंग लेम्मा का उपयोग इस विरोधाभास से प्रमाण बनाने के लिए किया जा सकता है कि एक विशिष्ट भाषा संदर्भ-मुक्त नहीं है। इसके विपरीत, पंपिंग लेम्मा यह गारंटी देने के लिए पर्याप्त नहीं है कि एक भाषा संदर्भ-मुक्त है; अन्य आवश्यक शर्तें हैं, जैसे कि ओग्डेन का लेम्मा, या इंटरचेंज लेम्मा। औपचारिक कथन यदि कोई भाषा संदर्भ-मुक्त है, तो कुछ पूर्णांक (जिसे "पंपिंग लेंथ" कहा जाता है) इस तरह मौजूद होता है कि उसमें प्रत्येक स्ट्रिंग की लंबाई या अधिक प्रतीक होते हैं (यानी। के साथ) को सबस्ट्रिंग के साथ लिखा जा सकता है और, जैसे कि सभी के लिए 1., 2., और 3. नीचे पंपिंग लेम्मा की एक औपचारिक अभिव्यक्ति दी गई है। अनौपचारिक कथन और व्याख्या संदर्भ-मुक्त भाषाओं के लिए पंपिंग लेम्मा (जिसे इस लेख के बाकी हिस्सों के लिए सिर्फ "पंपिंग लेम्मा" कहा जाता है) एक ऐसे गुण का वर्णन करता है जो सभी संदर्भ-मुक्त भाषाओं के पास होने की गारंटी है। गुण भाषा में सभी तारों का एक गुण है जो कम से कम लंबाई के हैं, जहां एक स्थिरांक है-जिसे पंपिंग लंबाई कहा जाता है-जो संदर्भ-मुक्त भाषाओं के बीच भिन्न होता है। मान लीजिए कि लंबाई की एक स्ट्रिंग है जो कम से कम भाषा में है। पंपिंग लेम्मा में कहा गया है कि इसे पांच सबस्ट्रिंग में विभाजित किया जा सकता है, जहां गैर-खाली है और इसकी लंबाई अधिक से अधिक है, जैसे कि दोहराने और समान संख्या में () एक स्ट्रिंग का उत्पादन करता है जो अभी भी भाषा में है। यह अक्सर शून्य बार दोहराने के लिए उपयोगी होता है, जो स्ट्रिंग को हटा देता है। और की अतिरिक्त प्रतियों के साथ "पम्पिंग अप" करने की यह प्रक्रिया ही पम्पिंग लेम्मा को इसका नाम देती है। परिमित भाषाएँ (जो नियमित हैं और इसलिए संदर्भ-मुक्त हैं) प्लस वन में अधिकतम स्ट्रिंग लंबाई के बराबर होने के कारण पंपिंग लेम्मा का तुच्छ रूप से पालन करती हैं। चूंकि इस लंबाई के कोई तार नहीं हैं, इसलिए पंपिंग लेम्मा का उल्लंघन नहीं होता है। लेम्मा का उपयोग पंपिंग लेम्मा का उपयोग अक्सर यह साबित करने के लिए किया जाता है कि दी गई भाषा गैर-संदर्भ-मुक्त है, यह दर्शाते हुए कि मनमाने ढंग से लंबे तार हैं जिन्हें बाहर से तार बनाए बिना "पंप" नहीं किया जा सकता है। उदाहरण के लिए, यदि अनंत है लेकिन इसमें (अनंत) अंकगणितीय प्रगति नहीं है, तो संदर्भ-मुक्त नहीं है। विशेष रूप से, न तो अभाज्य संख्याएँ और न ही वर्ग संख्याएँ संदर्भ-मुक्त हैं। उदाहरण के लिए, विरोधाभास द्वारा प्रमाण में पंपिंग लेम्मा का उपयोग करके भाषा को गैर-संदर्भ-मुक्त दिखाया जा सकता है। सबसे पहले, मान लीजिए कि यह संदर्भ मुक्त है। पंपिंग लेम्मा द्वारा, एक पूर्णांक मौजूद होता है जो भाषा की पंपिंग लंबाई है। स्ट्रिंग पर विचार करें। पंपिंग लेम्मा हमें बताता है कि इसे इस रूप में लिखा जा सकता है, जहां, और सबस्ट्रिंग हैं, जैसे कि, और प्रत्येक पूर्णांक के लिए। के चयन और इस तथ्य से, यह आसानी से देखा जा सकता है कि सबस्ट्रिंग में दो से अधिक अलग-अलग प्रतीक नहीं हो सकते हैं। अर्थात्, हमारे पास पाँच संभावनाओं में से एक हैः कुछ के लिए। किसी के लिए और किसी के लिए। किसी के लिए और किसी के साथ। कुछ लोगों के लिए। प्रत्येक मामले के लिए, यह आसानी से सत्यापित किया जाता है कि किसी के लिए प्रत्येक अक्षर की समान संख्या नहीं है। इस प्रकार, इसका कोई रूप नहीं है। यह परिभाषा के विपरीत है। इसलिए, हमारी प्रारंभिक धारणा जो संदर्भ मुक्त है, गलत होनी चाहिए। जबकि पंपिंग लेम्मा अक्सर यह साबित करने के लिए एक उपयोगी उपकरण है कि दी गई भाषा संदर्भ-मुक्त नहीं है, यह संदर्भ-मुक्त भाषाओं का पूर्ण लक्षण वर्णन नहीं देता है। यदि कोई भाषा पंपिंग लेम्मा द्वारा दी गई शर्त को पूरा नहीं करती है, तो हमने स्थापित किया है कि यह संदर्भ-मुक्त नहीं है। दूसरी ओर, ऐसी भाषाएँ हैं जो संदर्भ-मुक्त नहीं हैं, लेकिन फिर भी पंपिंग लेम्मा द्वारा दी गई शर्त को पूरा करती हैं, उदाहरण के लिए जैसे। जे ≤ 1 में केवल बी शामिल हैं, क्योंकि केवल ए शामिल हैं; दोनों ही मामलों में सभी पंप किए गए तार अभी भी एल में हैं। पंपिंग लेम्मा के अग्रदूत का उपयोग 1960 में शाइनबर्ग द्वारा यह साबित करने के लिए किया गया था कि यह संदर्भ-मुक्त नहीं है। संदर्भ-धारा 1.4: अनियमित भाषाएँ, पृ. 77-83 में पुनर्मुद्रित। धारा 2.3: गैर-संदर्भ-मुक्त भाषाएँ, पृ. 115-119। औपचारिक भाषाएँ लेम्मास