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

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

विशेष रूप से, पंपिंग लेम्मा किसी भी नियमित भाषा के लिए ऐसा कहती है $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$ भाग ए, ए $y$ भाग बीसी और ए $z$ भाग डी.

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

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

यदि कोई भाषा $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.