नियमित भाषाओं के लिए पंपिंग लेम्मा

औपचारिक भाषाओं के सिद्धांत में, नियमित भाषाओं के लिए पंपिंग लेम्मा (गणित) का उपयोग किया जाता है, जो सभी नियमित भाषाओं के आवश्यक गुणों का वर्णन करता है। इस प्रकार अनौपचारिक रूप से, यह कहा जाता है कि नियमित भाषा में सभी पर्याप्त लंबी स्ट्रिंग्स (कंप्यूटर विज्ञान) को पंप किया जा सकता है- अर्थात, स्ट्रिंग के मध्य भाग को स्वयं अपनी तरह से कई बार दोहराया जा सकता है- इस प्रकार की नई स्ट्रिंग्स का उत्पादन करने के लिए भी यह इस भाषा का विशेष भाग हैं।

विशेष रूप से, पंपिंग लेम्मा किसी भी नियमित भाषा के लिए यह उचित करती है, जिसमें $L$ को यहाँ पर स्थिरांक $p$ द्वारा स्थापित किया जाता है, जैसे कि कोई भी स्ट्रिंग $w$ में $L$ कम से कम लंबाई के साथ $p$ तीन सबस्ट्रिंग में विभाजित किया जा सकता है, जिसे $x$, $y$ और $z$ के लिए $w=xyz$, के साथ $y$ गैर-रिक्त होना आवश्यक होता हैं, जैसे कि स्ट्रिंग $xz,xyz,xyyz,xyyyz,...$ दोहराने के पश्चात बनाया गया हैं। इस कारण $y$ शून्य या अधिक बार $L$ का मान अभी भी उपस्थित हैं, इसके दोहराव होने के कारण इस प्रक्रिया को पंपिंग के रूप में जाना जाता है। इसके अतिरिक्त, पंपिंग लेम्मा इसकी लंबाई की गारंटी देता है, जिसके लिए $xy$ का अधिकतम मान $p$ होगा, इन विधियों पर उपयुक्त सीमा के लिए $w$ द्वारा विभाजित किया जाता है, इस प्रकार किसी परिमित भाषाएँ शून्य सत्य होने से पंपिंग लेम्मा को संतुष्ट करती हैं, इसके आधार पर $p$ के अधिकतम मान के लिए स्ट्रिंग की लंबाई $L$ के बराबर होती हैं।

पंपिंग लेम्मा प्रश्न में किसी विशिष्ट भाषा की नियमितता को अस्वीकार करने के लिए उपयोगी है। इसे पहली बार 1959 में माइकल ओ. राबिन और डाना स्कॉट द्वारा सिद्ध किया गया था, और कुछ समय बाद 1961 में येहोशुआ बार-हिलेल, मीका ए. पर्ल्स और शमीर को द्वारा संदर्भ-मुक्त भाषाओं के लिए उनके पंपिंग लेम्मा के सरलीकरण के रूप में फिर से खोजा गया था।

औपचारिक कथन

इस प्रकार $L$ को नियमित भाषा बनाने के लिए पुनः वहाँ पूर्णांक $p\geq 1$ को सम्मिलित किया जाता है, जिसके लिए यह केवल $L$ पर निर्भर करता है, इस प्रकार ऐसी हर स्ट्रिंग $w$ में $L$ कम से कम लंबाई का $p$ जहाँ $p$ पंपिंग लंबाई कहलाती है, जिसे $w=xyz$ के रूप में लिखा जा सकता है, अर्थात यहाँ पर $w$ को निम्नलिखित शर्तों को पूरा करते हुए तीन सबस्ट्रिंग्स में विभाजित किया जा सकता है:

• $|y|\geq 1$
• $|xy|\leq p$
• $(\forall n\geq 0)(xy^{n}z\in L)$

$y$ वह सबस्ट्रिंग है, जिसे कितनी भी बार पंप किया जा सकता है, इस प्रकार इसे यहाँ से हटाया या दोहराया जा सकता है, और परिणामी स्ट्रिंग सदैव $L$ के अंदर रहती है, इस प्रकार समीकरण (1) का अर्थ है कि लूप $y$ पंप किए जाने के लिए कम से कम लंबाई होनी चाहिए, इसी प्रकार समीकरण (2) का अर्थ है कि लूप पहले के भीतर होना चाहिए, यहाँ पर $p$ पात्र के लिए $|x|$ का मान कम होना चाहिए, तथा $p$ ((1) और (2) का निष्कर्ष के बाद इसे पुनः इसके अतिरिक्त $x$ और $z$ के लिए किसी भी प्रकार का प्रतिबंध नहीं रखते है।

सरल शब्दों में, किसी भी नियमित भाषा के लिए $L$, कोई भी पर्याप्त लंबी स्ट्रिंग $w$ (में $L$) को 3 भागों में विभाजित किया जा सकता है। अर्थात $w=xyz$ , जैसे कि सभी स्ट्रिंग $xy^{n}z$ के लिए $n\geq 0$ में भी $L$ हैं,

इस प्रकार नीचे पम्पिंग लेम्मा की औपचारिक अभिव्यक्ति है।

${\begin{array}{l}(\forall L\subseteq \Sigma ^{*})\\\quad ({\mbox{regular}}(L)\Rightarrow \\\quad ((\exists p\geq 1)((\forall w\in L)((|w|\geq p)\Rightarrow \\\quad ((\exists x,y,z\in \Sigma ^{*})(w=xyz\land (|y|\geq 1\land |xy|\leq p\land (\forall n\geq 0)(xy^{n}z\in L))))))))\end{array}}$

लेम्मा का उपयोग

पंपिंग लेम्मा का उपयोग अधिकांशतः यह प्रमाणित करने के लिए किया जाता है कि विशेष भाषा गैर-नियमित है: इसके विरोधाभास के प्रमाण में भाषा में स्ट्रिंग को आवश्यक के अनुसार विशेषतः इस लंबाई के अनुसार प्रदर्शित किया जा सकता हैं जिसमें यह सम्मिलित रहता है, जिसमें पंपिंग लेम्मा में उल्लिखित गुणोंका अभाव है।

उदाहरण के लिए, भाषा $L=\{a^{n}b^{n}:n\geq 0\}$ वर्णमाला के ऊपर $\Sigma =\{a,b\}$ निम्नानुसार गैर-नियमित दिखाया जा सकता है:

इसके आधार पर $w,x,y,z,p$, और $n$ जैसा कि नियमित भाषाओं के लिए पंपिंग लेम्मा में उपयोग किया जाता है, यहाँ पर ऊपर औपचारिक विवरण दिया गया हैं। इस प्रकार मान लीजिए कि $p$ कोई स्थिरांक है, जिसके लिए लेम्मा की आवश्यकता के अनुसार इसे सम्मिलित किया जाता है। इसके अनुसार $w$ में $L$ को $w=a^{p}b^{p}$ द्वारा दिया जाता हैं, जो कि इससे स्ट्रिंग $p$ तक लंबी है, इस प्रकार पंपिंग लेम्मा द्वारा अपघटन होने के अतिरिक्त इसका उपस्थित आवश्यक होना चाहिए, जिसके लिए $w=xyz$ के साथ $|xy|\leq p$ और $|y|\geq 1$ का मान प्राप्त होता हैं।

$xy^{i}z$ में $L$ को इसके प्रत्येक मान के लिए $i\geq 0$ के लिए $|xy|\leq p$, समीकरण के आधार पर डोर $y$ तक केवल इस उदाहरण के लिए उपस्थित किया जाता हैं, इस प्रकार $a$ के अतिरिक्त, $|y|\geq 1$, के मान के लिए इसमें उचित पत्र के आधार पर इसका कम से कम उदाहरण उपस्थिति होता है, यहाँ पर $a$ का मान चूंकि $xy^{2}z$ के पत्र पर और भी उदाहरण हैं, इसके लिए $a$ पत्र की तुलना में $b$ के कुछ उदाहरणों के बाद इसे $a$ मान के लिए इसे $b$ के मान के लिए इसका कोई भी मान नहीं जोड़ा गया था। इसलिए, $xy^{2}z$ इसमें उपस्थिति नहीं है, इस कारण $L$ जो पम्पिंग लेम्मा का खंडन करता है। इसलिए $L$ को यहाँ पर नियमित रूप से उपयोग नहीं किया जा सकता हैं।

इस बात का प्रमाण हैं कि डाइक भाषा या संतुलित अर्थात, उचित रूप से नेस्टेड ​​कोष्ठकों की भाषा नियमित नहीं है, यह इसी प्रकार उसी विचार का अनुसरण करती है। इस कारण यहाँ पर दिया गया $p$ का मान संतुलित कोष्ठकों की श्रृंखला को निरूपित करता है, जो इससे अधिक मान के लिए प्रारंभ होता है, यहाँ पर $p$ कोष्ठक को बाएँ ओर जिससे कि $y$ को पूर्ण रूप से बाएँ कोष्ठक से युक्त किया जाता हैं। इसे दोहराते हुए $y$, स्ट्रिंग का उत्पादन किया जा सकता है, जिसमें बाएँ और दाएँ कोष्ठकों की समान संख्या नहीं है, और इसलिए उन्हें संतुलित नहीं किया जा सकता है।

पंपिंग लेम्मा का प्रमाण

प्रमाण विचार: जब भी पर्याप्त लंबी स्ट्रिंग (औपचारिक भाषाएं) xyz को परिमित ऑटोमेटन#गणितीय मॉडल द्वारा पहचाना जाता है, तो यह किसी स्थिति तक पहुंच गया होगा ($q_{s}=q_{t}$) दो बार। इसलिए, मध्य भाग को दोहराने (पम्पिंग) के बाद $y$ मनमाने ढंग से अधिकांशतः (xyyz, xyyyz, ...) स्ट्रिंग अभी भी पहचानी जाएगी।

प्रत्येक नियमित भाषा के लिए परिमित स्थिति के लिए ऑटोमेटन के लिए एफएसए होता है जो भाषा को स्वीकार करता है। ऐसे एफएसए में स्थितिों की संख्या की गणना की जाती है और उस गणना का उपयोग पंपिंग लंबाई $p$ के रूप में किया जाता है, इसमें कम से कम लंबाई की स्ट्रिंग के लिए $p$, के आधार पर $q_{0}$ के आरंभिक अवस्था के रूप में निरूपित किया जाता हैं। इस प्रकार $q_{1},...,q_{p}$ के लिए इसके अगले मान के क्रम $p$ को स्ट्रिंग द्वारा उत्सर्जित होने पर इस स्थिति को प्राप्त करता है। क्योंकि एफएसए के पास $p$ स्थितियाँ ही है, इस प्रकार इसके इस क्रम के भीतर $p+1$ के लिए इन स्थितियों का मान प्राप्त किया गया हैं, इस प्रकार यहां पर कम से कम इस स्थिति के लिए इसे अवश्य ही दोहराया जाना चाहिए। इसे $q_{s}$ द्वारा लिखा जाता हैं, ऐसी स्थिति के लिए परिवर्तन जो मशीन को इस स्थिति की पहली मुठभेड़ से लेते हैं, जिसके लिए $q_{s}$ स्थिति का दूसरी स्थिति के लिए $q_{s}$ को इस प्रकार की स्ट्रिंग से संयोजित करते हैं, इस स्ट्रिंग को $y$ लेम्मा कहा जाता है, और चूंकि मशीन बिना किसी स्ट्रिंग से मेल खाएगी, इसलिए $y$ भाग या इस स्ट्रिंग के साथ $y$ को कितनी भी बार दोहराए जाने पर, लेम्मा की शर्तें संतुष्ट हो जाती हैं।

उदाहरण के लिए, निम्न प्रतिबिंब एफएसए दिखाती है।

एफएसए स्ट्रिंग एबीसीडी को अधिकृत करता है। चूंकि इस स्ट्रिंग की लंबाई कम से कम इन स्थितियों की संख्या के आधार पर जितनी ज्यादा होती है, जिसका मान सामान्यतः चार रहता है, पिजनहोल सिद्धांत इंगित करता है कि प्रारंभ स्थिति और अगले चार विज़िट किए गए स्थितिों के बीच कम से कम दोहराया स्थिति होना चाहिए। इस उदाहरण में, केवल $q_{1}$ बार-बार दोहराई जाने वाली स्थिति है, चूंकि सबस्ट्रिंग बीसी मशीन को उन बदलावों के माध्यम से ले जाती है, जो $q_{1}$ स्थिति में प्रारंभ होते हैं, और $q_{1}$ स्थिति पर समाप्त होता है, इस कारण उस भाग को दोहराया जा सकता है और एफएसए स्ट्रिंग देते हुए अभी भी स्वीकार करेगा, जैसे abcbcd को वैकल्पिक रूप से बीसी के उचित भाग के लिए हटाया जा सकता है, और इस प्रकार एफएसए अभी भी स्ट्रिंग विज्ञापन देना स्वीकार करेगा। इसके आधार पर पंपिंग लेम्मा के संदर्भ में, स्ट्रिंग एबीसीडी को में तोड़ दिया गया है, जिसके लिए $x$ भाग a, a $y$ भाग bc और a $z$ भाग d द्वारा निरूपित करते हैं।

इसके अतिरिक्त टिप्पणी के रूप में यह जाँचने की समस्या कि क्या किसी दिए गए स्ट्रिंग को किसी दिए गए गैर-नियतात्मक परिमित ऑटोमेटन द्वारा किसी भी स्थिति में बार-बार आए बिना स्वीकार किया जा सकता है, यहाँ पर एनपी कठिन है।

नियमित भाषाओं के लिए पंपिंग लेम्मा का सामान्य संस्करण

यदि कोई भाषा $L$ पूर्ण रूप से नियमित है, तो $p\geq 1$ संख्या यहाँ पर सम्मिलित रहती है, यहाँ पर पंपिंग लंबाई इस प्रकार हैं कि हर स्ट्रिंग का मान $uwv$ में $L$ साथ $|w|\geq p$ फॉर्म में लिखा जा सकता है। इस प्रकार उक्त समीकरण प्राप्त होता हैं-

$uwv=uxyzv$

स्ट्रिंग के साथ $x$, $y$ और $z$ का मान इस प्रकार हैं कि $|xy|\leq p$, $|y|\geq 1$ और

$uxy^{i}zv$ में है $L$ प्रत्येक पूर्णांक के लिए $i\geq 0$ मान प्राप्त होता हैं।

इसके लिए औपचारिक कथन मानक संस्करण दोनों के साथ विशेष स्थिति का अनुसरण करता है, जिसके लिए $u$ और $v$ रिक्त स्ट्रिंग को प्रकट करते हैं।

चूँकि सामान्य संस्करण भाषा पर इसकी अधिक आवश्यकताएँ होती है, इसका उपयोग कई और भाषाओं की गैर-नियमितता को प्रमाणित करने के लिए किया जा सकता है।

लेम्मा का व्युत्क्रम असत्य मान

जबकि पंपिंग लेम्मा में कहा गया है कि सभी नियमित भाषाएँ ऊपर वर्णित शर्तों को पूरा करती हैं, इस कथन का विपरीत मान असत्य होता है, जिसके कारण इस भाषा के अनुसार जो इन शर्तों को पूरा करती है वह अभी भी गैर-नियमित हो सकती है। दूसरे शब्दों में, पंपिंग लेम्मा का मूल और सामान्य संस्करण दोनों ही किसी भाषा के नियमित होने के लिए आवश्यक और पर्याप्त स्थिति देते हैं।

उदाहरण के लिए, निम्नलिखित भाषा पर विचार करें:

${\begin{matrix}L&=&\{uvwxy:u,y\in \{0,1,2,3\}^{*};v,w,x\in \{0,1,2,3\}\land (v=w\lor v=x\lor x=w)\}\\&&\cup \ \{w:w\in \{0,1,2,3\}^{*}\land {\text{precisely }}{\tfrac {1}{7}}{\text{ of the characters in }}w{\text{ are 3's}}\}\end{matrix}}$.

दूसरे शब्दों में, $L$ इसमें वर्णमाला के सभी स्ट्रिंग $\{0,1,2,3\}$ उपस्थित हैं, जिसके लिए डुप्लिकेट वर्ण सहित लंबाई 3 की सबस्ट्रिंग के साथ ही इस वर्णमाला की सभी स्ट्रिंग्स जहां स्ट्रिंग के वर्णों का 1/7 भाग 3 है। यह भाषा नियमित नहीं है लेकिन फिर भी $p=5$ के लिए इसका उपयोग किया जा सकता है, इस प्रकार यहाँ पर मान लीजिए कि कुछ स्ट्रिंग एस की लंबाई कम से कम 5 है। चूंकि इस उचित वर्णमाला में केवल चार अक्षर हैं, स्ट्रिंग में पहले पांच अक्षरों में से कम से कम दो डुप्लिकेट होने चाहिए। वे अधिकतम तीन वर्णों द्वारा अलग किए गए हैं।

• यदि डुप्लिकेट वर्णों को 0 वर्णों या 1 से अलग किया गया है, तो स्ट्रिंग में अन्य दो वर्णों में से को पंप करें, जो डुप्लिकेट वाले सबस्ट्रिंग को प्रभावित नहीं करेगा।
• यदि डुप्लिकेट वर्णों को 2 या 3 वर्णों से अलग किया गया है, तो उन्हें अलग करने वाले 2 वर्णों को पंप करते हैं। इस प्रकार नीचे या ऊपर पंप करने के कारण इसके आकार 3 की सबस्ट्रिंग का निर्माण होता है, जिसमें 2 डुप्लिकेट वर्ण होते हैं।
• जिसकी दूसरी शर्त $L$ निश्चित करता है कि $L$ नियमित नहीं है: इस प्रकार स्ट्रिंग $(013)^{3m}(012)^{i}$ पर विचार करें, यहाँ पर यह स्ट्रिंग $L$ के अंदर है, जो बिल्कुल $i=4m$ होने पर और इसी प्रकार $L$ माईहिल-नेरोड प्रमेय द्वारा नियमित नहीं है।

माईहिल-नेरोड प्रमेय परीक्षण प्रदान करता है जो नियमित भाषाओं की सटीक विशेषता को बताता है। यह प्रमाणित करने की सामान्य विधि कि कोई भाषा नियमित है, या तो परिमित स्थिति मशीन या भाषा के लिए नियमित अभिव्यक्ति का निर्माण करना है।

यह भी देखें

• ओग्डेन की लेम्मा
• संदर्भ-मुक्त भाषाओं के लिए लेम्मा में अधिकता करना
• नियमित ट्री भाषाओं के लिए पंपिंग लेम्मा

संदर्भ

• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 978-1-58488-255-8. Zbl 1086.68074.
• Sipser, Michael (1997). "1.4: Nonregular Languages". Introduction to the Theory of Computation. PWS Publishing. pp. 77–83. ISBN 978-0-534-94728-6. Zbl 1169.68300.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001. (See chapter 3.)
• Bakhadyr Khoussainov; Anil Nerode (6 December 2012). Automata Theory and its Applications. Springer Science & Business Media. ISBN 978-1-4612-0171-7.