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

Revision as of 23:55, 25 July 2023

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

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

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

औपचारिक कथन

इस प्रकार $L$ को नियमित भाषा बनाने के लिए पुनः वहाँ पूर्णांक $p\geq 1$ को सम्मिलित किया जाता है, जिसके लिए यह केवल $L$ पर निर्भर करता है, इस प्रकार ऐसी हर स्ट्रिंग $w$ में $L$ कम से कम लंबाई का $p$ जहाँ $p$ पंपिंग लंबाई कहलाती है,^[4] जिसे $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

मान प्राप्त होता हैं।^[5]

इसके लिए औपचारिक कथन मानक संस्करण दोनों के साथ विशेष स्थिति का अनुसरण करता है, जिसके लिए $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$ माईहिल-नेरोड प्रमेय द्वारा नियमित नहीं है।

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

यह भी देखें

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

↑ Rabin, Michael; Scott, Dana (Apr 1959). "परिमित ऑटोमेटा और उनकी निर्णय समस्याएं" (PDF). IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114. Archived from the original on December 14, 2010.{{cite journal}}: CS1 maint: unfit URL (link) Here: Lemma 8, p.119
↑ Bar-Hillel, Y.; Perles, M.; Shamir, E. (1961), "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14 (2): 143–172
↑ John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation. Addison Wesley. Here: Sect.4.6, p.166
↑ Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). शब्दों पर संयोजकता. क्रिस्टोफ़ेल शब्द और शब्दों में दोहराव. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. p. 86. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
↑ Savitch, Walter (1982). सार मशीनें और व्याकरण. p. 49. ISBN 978-0-316-77161-0.

संदर्भ

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.

[1] Rabin, Michael; Scott, Dana (Apr 1959). "परिमित ऑटोमेटा और उनकी निर्णय समस्याएं" (PDF). IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114. Archived from the original on December 14, 2010.{{cite journal}}: CS1 maint: unfit URL (link) Here: Lemma 8, p.119

[2] Bar-Hillel, Y.; Perles, M.; Shamir, E. (1961), "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14 (2): 143–172

[3] John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation. Addison Wesley. Here: Sect.4.6, p.166

[BLRS86-4] Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). शब्दों पर संयोजकता. क्रिस्टोफ़ेल शब्द और शब्दों में दोहराव. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. p. 86. ISBN 978-0-8218-4480-9. Zbl 1161.68043.

[5] Savitch, Walter (1982). सार मशीनें और व्याकरण. p. 49. ISBN 978-0-316-77161-0.

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
 {{Short description|Type of pumping lemma}}
-[[औपचारिक भाषा]]ओं के सिद्धांत में, [[नियमित भाषा]]ओं के लिए पंपिंग लेम्मा [[लेम्मा (गणित)]] है जो सभी नियमित भाषाओं की आवश्यक संपत्ति का वर्णन करता है। अनौपचारिक रूप से, यह कहता है कि नियमित भाषा में सभी पर्याप्त लंबी [[स्ट्रिंग (कंप्यूटर विज्ञान)]] को ''पंप'' किया जा सकता है - अर्थात, स्ट्रिंग के मध्य भाग को मनमाने ढंग से कई बार दोहराया जा सकता है - नई स्ट्रिंग का उत्पादन करने के लिए भी। भाषा का हिस्सा.
+[[औपचारिक भाषा|औपचारिक भाषाओं]] के सिद्धांत में, '''[[नियमित भाषा|नियमित भाषाओं]] के लिए पंपिंग [[लेम्मा (गणित)|लेम्मा]]''' [[लेम्मा (गणित)|(गणित)]] का उपयोग किया जाता है, जो सभी नियमित भाषाओं की आवश्यक संपत्ति का वर्णन करता है। इस प्रकार अनौपचारिक रूप से, यह कहा जाता है कि नियमित भाषा में सभी पर्याप्त लंबी [[स्ट्रिंग (कंप्यूटर विज्ञान)]] को ''पंप'' किया जा सकता है- अर्थात, स्ट्रिंग के मध्य भाग को स्वयं अपनी तरह से कई बार दोहराया जा सकता है- इस प्रकार की नई स्ट्रिंग्स का उत्पादन करने के लिए भी यह भाषा का हिस्सा हैं।
-विशेष रूप से, पंपिंग लेम्मा किसी भी नियमित भाषा के लिए ऐसा कहती है <math>L</math> वहाँ स्थिरांक मौजूद है <math>p</math> जैसे कि कोई भी स्ट्रिंग <math>w</math> में <math>L</math> कम से कम लंबाई के साथ <math>p</math> तीन सबस्ट्रिंग में विभाजित किया जा सकता है <math>x</math>, <math>y</math> और <math>z</math> ({{nowrap begin}}<math>w = xyz</math>{{nowrap end}}, साथ <math>y</math> गैर-रिक्त होना), जैसे कि तार <math>xz, xyz, xyyz, xyyyz, ...</math> दोहराकर बनाया गया <math>y</math> शून्य या अधिक बार अभी भी हैं <math>L</math>. दोहराव की इस प्रक्रिया को पंपिंग के रूप में जाना जाता है। इसके अलावा, पंपिंग लेम्मा इसकी लंबाई की गारंटी देता है <math>xy</math> अधिकतम होगा <math>p</math>, तरीकों पर सीमा लगाना <math>w</math> विभाजित हो सकता है. परिमित भाषाएँ शून्य सत्य होने से पंपिंग लेम्मा को संतुष्ट करती हैं <math>p</math> अधिकतम स्ट्रिंग लंबाई के बराबर <math>L</math> मैं भी सहमत हूं।
+विशेष रूप से, पंपिंग लेम्मा किसी भी नियमित भाषा के लिए ऐसा कहती है, जिसमे <math>L</math> को यहाँ पर स्थिरांक <math>p</math> द्वारा स्थापित किया जाता है, जैसे कि कोई भी स्ट्रिंग <math>w</math> में <math>L</math> कम से कम लंबाई के साथ <math>p</math> तीन सबस्ट्रिंग में विभाजित किया जा सकता है, जिसे <math>x</math>, <math>y</math> और <math>z</math> के लिए {{nowrap begin}}<math>w = xyz</math>{{nowrap end}}, के साथ <math>y</math> गैर-रिक्त होना आवश्यक होता हैं, जैसे कि स्ट्रिंग <math>xz, xyz, xyyz, xyyyz, ...</math> दोहराकर बनाया गया हैं। इस कारण <math>y</math> शून्य या अधिक बार <math>L</math> का मान अभी भी उपस्थित हैं, इसके दोहराव होने के कारण इस प्रक्रिया को पंपिंग के रूप में जाना जाता है। इसके अतिरिक्त, पंपिंग लेम्मा इसकी लंबाई की गारंटी देता है, जिसके लिए <math>xy</math> का अधिकतम मान <math>p</math> होगा, इन विधियों पर उपयुक्त सीमा के लिए <math>w</math> को विभाजित किया जाता है, इस प्रकार किसी परिमित भाषाएँ शून्य सत्य होने से पंपिंग लेम्मा को संतुष्ट करती हैं, इसके आधार पर <math>p</math> के अधिकतम मान के लिए स्ट्रिंग की लंबाई <math>L</math> के बराबर होती हैं।
-पंपिंग लेम्मा प्रश्न में किसी विशिष्ट भाषा की नियमितता को अस्वीकार करने के लिए उपयोगी है। इसे पहली बार 1959 में माइकल ओ. राबिन और [[दाना स्कॉट]] द्वारा सिद्ध किया गया था,<ref>{{cite journal|last1=Rabin |first1=Michael |authorlink1=Michael O. Rabin|last2=Scott |first2=Dana |authorlink2=Dana Scott  |date=Apr 1959 |title=परिमित ऑटोमेटा और उनकी निर्णय समस्याएं|journal=IBM Journal of Research and Development |volume=3 |issue=2 |pages=114–125 |url=http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf |doi=10.1147/rd.32.0114 |url-status=unfit |archiveurl=https://web.archive.org/web/20101214122150/http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf |archivedate=December 14, 2010 }} Here: Lemma 8, p.119</ref> और कुछ ही समय बाद 1961 में [[येहोशुआ बार-हिलेल]], मीका ए. पर्ल्स और [[ शमीर को |शमीर को]] द्वारा संदर्भ-मुक्त भाषाओं के लिए उनके पंपिंग लेम्मा के सरलीकरण के रूप में फिर से खोजा गया।<ref>{{citation
+पंपिंग लेम्मा प्रश्न में किसी विशिष्ट भाषा की नियमितता को अस्वीकार करने के लिए उपयोगी है। इसे पहली बार 1959 में माइकल ओ. राबिन और [[दाना स्कॉट]] द्वारा सिद्ध किया गया था,<ref>{{cite journal|last1=Rabin |first1=Michael |authorlink1=Michael O. Rabin|last2=Scott |first2=Dana |authorlink2=Dana Scott  |date=Apr 1959 |title=परिमित ऑटोमेटा और उनकी निर्णय समस्याएं|journal=IBM Journal of Research and Development |volume=3 |issue=2 |pages=114–125 |url=http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf |doi=10.1147/rd.32.0114 |url-status=unfit |archiveurl=https://web.archive.org/web/20101214122150/http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf |archivedate=December 14, 2010 }} Here: Lemma 8, p.119</ref> और कुछ ही समय बाद 1961 में [[येहोशुआ बार-हिलेल]], मीका ए. पर्ल्स और [[ शमीर को |शमीर को]] द्वारा संदर्भ-मुक्त भाषाओं के लिए उनके पंपिंग लेम्मा के सरलीकरण के रूप में फिर से खोजा गया था।<ref>{{citation
   | last1 = Bar-Hillel | first1 = Y. | author1-link = Yehoshua Bar-Hillel
   | last2 = Perles | first2 = M.
@@ Line 20: / Line 20: @@
 }} Here: Sect.4.6, p.166</ref>
 == औपचारिक कथन ==
-होने देना <math>L</math> नियमित भाषा बनें. फिर वहाँ पूर्णांक मौजूद है <math>p \geq 1</math> केवल पर निर्भर करता है <math>L</math> ऐसे कि हर तार <math>w</math> में <math>L</math> कम से कम लंबाई का <math>p</math> (<math>p</math> पंपिंग लंबाई कहलाती है)<ref name=BLRS86>{{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=शब्दों पर संयोजकता. क्रिस्टोफ़ेल शब्द और शब्दों में दोहराव| series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | zbl=1161.68043 | page=86}}</ref> के रूप में लिखा जा सकता है <math>w = xyz</math> (अर्थात।, <math>w</math> निम्नलिखित शर्तों को पूरा करते हुए तीन उपस्ट्रिंग्स में विभाजित किया जा सकता है:
+इस प्रकार <math>L</math> को नियमित भाषा बनाने के लिए पुनः वहाँ पूर्णांक <math>p \geq 1</math> को सम्मिलित किया जाता है, जिसके लिए यह केवल <math>L</math> पर निर्भर करता है, इस प्रकार ऐसी हर स्ट्रिंग <math>w</math> में <math>L</math> कम से कम लंबाई का <math>p</math> जहाँ <math>p</math> पंपिंग लंबाई कहलाती है,<ref name=BLRS86>{{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=शब्दों पर संयोजकता. क्रिस्टोफ़ेल शब्द और शब्दों में दोहराव| series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | zbl=1161.68043 | page=86}}</ref> जिसे <math>w = xyz</math> के रूप में लिखा जा सकता है, अर्थात यहाँ पर ।, <math>w</math> निम्नलिखित शर्तों को पूरा करते हुए तीन उपस्ट्रिंग्स में विभाजित किया जा सकता है:
 * <math> |y| \geq 1 </math>
@@ Line 26: / Line 26: @@
 * <math> (\forall n \geq 0) ( xy^nz \in L )</math>
-<math>y</math> वह सबस्ट्रिंग है जिसे कितनी भी बार पंप किया जा सकता है (हटाया या दोहराया जा सकता है, और परिणामी स्ट्रिंग हमेशा अंदर रहती है) <math>L</math>). (1) का अर्थ है लूप <math>y</math> पंप किए जाने के लिए कम से कम लंबाई होनी चाहिए; (2) का अर्थ है कि लूप पहले के भीतर होना चाहिए <math>p</math> पात्र। <math>|x|</math> से छोटा होना चाहिए <math>p</math> ((1) और (2) का निष्कर्ष), लेकिन इसके अलावा, कोई प्रतिबंध नहीं है <math>x</math> और <math>z</math>.
+<math>y</math> वह सबस्ट्रिंग है, जिसे कितनी भी बार पंप किया जा सकता है, इस प्रकार इसे यहाँ से हटाया या दोहराया जा सकता है, और परिणामी स्ट्रिंग सदैव <math>L</math> के अंदर रहती है, इस प्रकार समीकरण (1) का अर्थ है कि लूप <math>y</math> पंप किए जाने के लिए कम से कम लंबाई होनी चाहिए, इसी प्रकार समीकरण (2) का अर्थ है कि लूप पहले के भीतर होना चाहिए, यहाँ पर  <math>p</math> पात्र के लिए <math>|x|</math> का मान कम होना चाहिए, तथा <math>p</math> ((1) और (2) का निष्कर्ष के बाद इसे पुनः इसके अतिरिक्त <math>x</math> और <math>z</math> के लिए किसी भी प्रकार का प्रतिबंध नहीं रखते है।
-सरल शब्दों में, किसी भी नियमित भाषा के लिए <math>L</math>, कोई भी पर्याप्त लंबी स्ट्रिंग <math>w</math> (में <math>L</math>) को 3 भागों में विभाजित किया जा सकता है।
+सरल शब्दों में, किसी भी नियमित भाषा के लिए <math>L</math>, कोई भी पर्याप्त लंबी स्ट्रिंग <math>w</math> (में <math>L</math>) को 3 भागों में विभाजित किया जा सकता है। अर्थात। <math>w = xyz</math> , जैसे कि सभी स्ट्रिंग <math>xy^nz</math> के लिए <math>n \geq 0</math> में भी <math>L</math> हैं,
-अर्थात। <math>w = xyz</math> , जैसे कि सभी तार <math>xy^nz</math> के लिए <math>n \geq 0</math> में भी हैं <math>L</math>.
-नीचे पम्पिंग लेम्मा की औपचारिक अभिव्यक्ति है।
+इस प्रकार नीचे पम्पिंग लेम्मा की औपचारिक अभिव्यक्ति है।
 <math>
@@ Line 43: / Line 42: @@
 </math>
 == लेम्मा का उपयोग ==
-पंपिंग लेम्मा का उपयोग अक्सर यह साबित करने के लिए किया जाता है कि विशेष भाषा गैर-नियमित है: विरोधाभास के प्रमाण में भाषा में स्ट्रिंग (आवश्यक लंबाई की) प्रदर्शित करना शामिल हो सकता है जिसमें पंपिंग लेम्मा में उल्लिखित संपत्ति का अभाव है।
+पंपिंग लेम्मा का उपयोग अधिकांशतः यह प्रमाणित करने के लिए किया जाता है कि विशेष भाषा गैर-नियमित है: इसके विरोधाभास के प्रमाण में भाषा में स्ट्रिंग को आवश्यक के अनुसार विशेषतः इस लंबाई के अनुसार प्रदर्शित किया जा सकता हैं जिसमें यह सम्मिलित रहता है, जिसमें पंपिंग लेम्मा में उल्लिखित संपत्ति का अभाव है।
 उदाहरण के लिए, भाषा <math>L = \{a^n b^n : n \geq 0\}</math> वर्णमाला के ऊपर <math>\Sigma = \{a, b\}</math> निम्नानुसार गैर-नियमित दिखाया जा सकता है:
-होने देना <math>w, x, y, z, p</math>, और <math>n</math> जैसा कि नियमित भाषाओं के लिए पंपिंग लेम्मा में उपयोग किया जाता है#ऊपर औपचारिक विवरण। मान लीजिए कि कोई स्थिरांक है <math>p</math> लेम्मा की आवश्यकता के अनुसार मौजूद है। होने देना <math>w</math> में <math>L</math> द्वारा दिया जाए <math>w = a^p b^p</math>, जो कि इससे स्ट्रिंग लंबी है <math>p</math>. पंपिंग लेम्मा द्वारा, अपघटन मौजूद होना चाहिए <math>w = xyz</math> साथ <math>|xy| \leq p</math> और <math>|y| \geq 1</math> ऐसा है कि
+इसके आधार पर <math>w, x, y, z, p</math>, और <math>n</math> जैसा कि नियमित भाषाओं के लिए पंपिंग लेम्मा में उपयोग किया जाता है, यहाँ पर ऊपर औपचारिक विवरण दिया गया हैं। इस प्रकार मान लीजिए कि <math>p</math> कोई स्थिरांक है, जिसके लिए लेम्मा की आवश्यकता के अनुसार इसे सम्मिलित किया जाता है। इसके अनुसार <math>w</math> में <math>L</math> को <math>w = a^p b^p</math> द्वारा दिया जाता हैं, जो कि इससे स्ट्रिंग <math>p</math> तक लंबी है, इस प्रकार पंपिंग लेम्मा द्वारा, अपघटन उपस्थित होना चाहिए, जिसके लिए <math>w = xyz</math> के साथ <math>|xy| \leq p</math> और <math>|y| \geq 1</math> का मान प्राप्त होता हैं।
-  <math>xy^iz</math> में <math>L</math> हरएक के लिए <math>i \geq 0</math>. तब से <math>|xy| \leq p</math>, डोर <math>y</math> केवल के उदाहरण शामिल हैं <math>a</math>. इसके अलावा, क्योंकि <math>|y| \geq 1</math>, इसमें पत्र का कम से कम उदाहरण शामिल है <math>a</math>. हालाँकि, <math>xy^2z</math> पत्र के और भी उदाहरण हैं <math>a</math> पत्र की तुलना में <math>b</math>, के कुछ उदाहरणों के बाद से <math>a</math> लेकिन कोई नहीं <math>b</math> जोड़ा गया था। इसलिए, <math>xy^2z</math> इसमें नहीं है <math>L</math> जो पम्पिंग लेम्मा का खंडन करता है। इसलिए, <math>L</math> नियमित नहीं हो सकता.
+  <math>xy^iz</math> में <math>L</math> को इसके प्रत्येक मान के लिए <math>i \geq 0</math> के लिए <math>|xy| \leq p</math>, समीकरण के आधार पर डोर <math>y</math> तक केवल इस उदाहरण के लिए उपस्थित किया जाता हैं, इस प्रकार <math>a</math> के अतिरिक्त, <math>|y| \geq 1</math>, के मान के लिए इसमें उचित पत्र के आधार पर इसका कम से कम उदाहरण उपस्थिति होता है, यहाँ पर <math>a</math> का मान चूंकि <math>xy^2z</math> के पत्र पर और भी उदाहरण हैं, इसके लिए <math>a</math> पत्र की तुलना में <math>b</math> के कुछ उदाहरणों के बाद इसे <math>a</math> मान के लिए इसे <math>b</math> के मान के लिए इसका कोई भी मान नहीं जोड़ा गया था। इसलिए, <math>xy^2z</math> इसमें उपस्थिति नहीं है, इस कारण <math>L</math> जो पम्पिंग लेम्मा का खंडन करता है। इसलिए <math>L</math> को यहाँ पर नियमित रूप से उपयोग नहीं किया जा सकता हैं।
-इस बात का प्रमाण कि डाइक भाषा|संतुलित (अर्थात, उचित रूप से नेस्टेड) कोष्ठकों की भाषा नियमित नहीं है, उसी विचार का अनुसरण करती है। दिया गया <math>p</math>, संतुलित कोष्ठकों की श्रृंखला है जो से अधिक से शुरू होती है <math>p</math> कोष्ठक बाएँ, ताकि <math>y</math> पूरी तरह से बाएँ कोष्ठक से युक्त होगा। दोहराते हुए <math>y</math>, स्ट्रिंग का उत्पादन किया जा सकता है जिसमें बाएँ और दाएँ कोष्ठकों की समान संख्या नहीं है, और इसलिए उन्हें संतुलित नहीं किया जा सकता है।
+इस बात का प्रमाण हैं कि डाइक भाषा या संतुलित अर्थात, उचित रूप से नेस्टेड कोष्ठकों की भाषा नियमित नहीं है, यह इसी प्रकार उसी विचार का अनुसरण करती है। इस कारण यहाँ पर दिया गया <math>p</math> का मान संतुलित कोष्ठकों की श्रृंखला को निरूपित करता है, जो इससे अधिक मान के लिए प्रारंभ होता है, यहाँ पर <math>p</math> कोष्ठक को बाएँ ओर जिससे कि <math>y</math> को पूर्ण रूप से बाएँ कोष्ठक से युक्त किया जाता हैं। इसे दोहराते हुए <math>y</math>, स्ट्रिंग का उत्पादन किया जा सकता है, जिसमें बाएँ और दाएँ कोष्ठकों की समान संख्या नहीं है, और इसलिए उन्हें संतुलित नहीं किया जा सकता है।
 == पंपिंग लेम्मा का प्रमाण ==
-[[File:Pumping-Lemma_xyz_svg.svg|thumb|400px|प्रमाण विचार: जब भी पर्याप्त लंबी स्ट्रिंग (औपचारिक भाषाएं) xyz को परिमित ऑटोमेटन#गणितीय मॉडल द्वारा पहचाना जाता है, तो यह किसी स्थिति तक पहुंच गया होगा (<math>q_s = q_t</math>) दो बार। इसलिए, मध्य भाग को दोहराने (पम्पिंग) के बाद <math>y</math> मनमाने ढंग से अक्सर (xyyz, xyyyz, ...) स्ट्रिंग अभी भी पहचानी जाएगी।]]प्रत्येक नियमित भाषा के लिए परिमित राज्य ऑटोमेटन (एफएसए) होता है जो भाषा को स्वीकार करता है। ऐसे एफएसए में राज्यों की संख्या की गणना की जाती है और उस गणना का उपयोग पंपिंग लंबाई के रूप में किया जाता है <math>p</math>. कम से कम लंबाई की स्ट्रिंग के लिए <math>p</math>, होने देना <math>q_0</math> आरंभ अवस्था बनें और जाने दें <math>q_1, ..., q_p</math> अगले का क्रम हो <math>p</math> स्ट्रिंग उत्सर्जित होने पर राज्यों का दौरा किया जाता है। क्योंकि एफएसए के पास ही है <math>p</math> राज्यों, के इस क्रम के भीतर <math>p+1</math> जिन राज्यों का दौरा किया गया वहां कम से कम राज्य अवश्य दोहराया जाना चाहिए। लिखना <math>q_s</math> ऐसे राज्य के लिए. परिवर्तन जो मशीन को राज्य की पहली मुठभेड़ से लेते हैं <math>q_s</math> राज्य की दूसरी मुठभेड़ के लिए <math>q_s</math> कुछ स्ट्रिंग का मिलान करें. इस स्ट्रिंग को कहा जाता है <math>y</math> लेम्मा में, और चूंकि मशीन बिना किसी स्ट्रिंग से मेल खाएगी <math>y</math> भाग, या स्ट्रिंग के साथ <math>y</math> कितनी भी बार दोहराए जाने पर, लेम्मा की शर्तें संतुष्ट हो जाती हैं।
+[[File:Pumping-Lemma_xyz_svg.svg|thumb|400px|प्रमाण विचार: जब भी पर्याप्त लंबी स्ट्रिंग (औपचारिक भाषाएं) xyz को परिमित ऑटोमेटन#गणितीय मॉडल द्वारा पहचाना जाता है, तो यह किसी स्थिति तक पहुंच गया होगा (<math>q_s = q_t</math>) दो बार। इसलिए, मध्य भाग को दोहराने (पम्पिंग) के बाद <math>y</math> मनमाने ढंग से अधिकांशतः (xyyz, xyyyz, ...) स्ट्रिंग अभी भी पहचानी जाएगी।]]प्रत्येक नियमित भाषा के लिए परिमित स्थिति के लिए ऑटोमेटन के लिए एफएसए होता है जो भाषा को स्वीकार करता है। ऐसे एफएसए में स्थितिों की संख्या की गणना की जाती है और उस गणना का उपयोग पंपिंग लंबाई  <math>p</math> के रूप में किया जाता है, इसमें कम से कम लंबाई की स्ट्रिंग के लिए <math>p</math>,  के आधार पर  <math>q_0</math> के आरंभिक अवस्था के रूप में निरूपित किया जाता हैं। इस प्रकार <math>q_1, ..., q_p</math> के लिए इसके अगले मान के क्रम  <math>p</math> को स्ट्रिंग द्वारा उत्सर्जित होने पर इस स्थिति को प्राप्त करता है। क्योंकि एफएसए के पास <math>p</math> स्थितियाँ ही है, इस प्रकार इसके इस क्रम के भीतर <math>p+1</math> के लिए इन स्थितियों का मान प्राप्त किया गया हैं, इस प्रकार यहां पर कम से कम इस स्थिति के लिए इसे अवश्य ही दोहराया जाना चाहिए। इसे <math>q_s</math> द्वारा लिखा जाता हैं, ऐसी स्थिति के लिए परिवर्तन जो मशीन को इस स्थिति की पहली मुठभेड़ से लेते हैं, जिसके लिए <math>q_s</math> स्थिति की दूसरी मुठभेड़ के लिए <math>q_s</math> को इस प्रकार की स्ट्रिंग से संयोजित करते हैं, इस स्ट्रिंग को <math>y</math> लेम्मा कहा जाता है, और चूंकि मशीन बिना किसी स्ट्रिंग से मेल खाएगी, इसलिए <math>y</math> भाग या इस स्ट्रिंग के साथ <math>y</math> को कितनी भी बार दोहराए जाने पर, लेम्मा की शर्तें संतुष्ट हो जाती हैं।
-उदाहरण के लिए, निम्न छवि एफएसए दिखाती है।
+उदाहरण के लिए, निम्न प्रतिबिंब एफएसए दिखाती है।
-[[File:An automat accepting the language a(bc)*d.svg]]एफएसए स्ट्रिंग स्वीकार करता है: एबीसीडी। चूंकि इस स्ट्रिंग की लंबाई कम से कम राज्यों की संख्या जितनी बड़ी है, जो कि चार है, पिजनहोल सिद्धांत इंगित करता है कि प्रारंभ राज्य और अगले चार विज़िट किए गए राज्यों के बीच कम से कम दोहराया राज्य होना चाहिए। इस उदाहरण में, केवल <math>q_1</math> बार-बार दोहराई जाने वाली स्थिति है. चूंकि सबस्ट्रिंग बीसी मशीन को उन बदलावों के माध्यम से ले जाती है जो राज्य में शुरू होते हैं <math>q_1</math> और राज्य पर समाप्त होता है <math>q_1</math>, उस हिस्से को दोहराया जा सकता है और एफएसए स्ट्रिंग देते हुए अभी भी स्वीकार करेगा {{not a typo|'''abcbcd'''}}. वैकल्पिक रूप से, बीसी भाग को हटाया जा सकता है और एफएसए अभी भी स्ट्रिंग विज्ञापन देना स्वीकार करेगा। पंपिंग लेम्मा के संदर्भ में, स्ट्रिंग एबीसीडी को में तोड़ दिया गया है <math>x</math> भाग ए, ए <math>y</math> भाग बीसी और ए <math>z</math> भाग डी.
+[[File:An automat accepting the language a(bc)*d.svg]]एफएसए स्ट्रिंग एबीसीडी को स्वीकार करता है। चूंकि इस स्ट्रिंग की लंबाई कम से कम इन स्थितियों की संख्या के आधार पर जितनी ज्यादा होती है, जिसका मान सामान्यतः चार रहता है, पिजनहोल सिद्धांत इंगित करता है कि प्रारंभ स्थिति और अगले चार विज़िट किए गए स्थितिों के बीच कम से कम दोहराया स्थिति होना चाहिए। इस उदाहरण में, केवल <math>q_1</math> बार-बार दोहराई जाने वाली स्थिति है, चूंकि सबस्ट्रिंग बीसी मशीन को उन बदलावों के माध्यम से ले जाती है, जो  <math>q_1</math> स्थिति में प्रारंभ होते हैं, और <math>q_1</math> स्थिति पर समाप्त होता है, इस कारण उस भाग को दोहराया जा सकता है और एफएसए स्ट्रिंग देते हुए अभी भी स्वीकार करेगा {{not a typo|'''abcbcd'''}}. वैकल्पिक रूप से, बीसी भाग को हटाया जा सकता है, और इस प्रकार एफएसए अभी भी स्ट्रिंग विज्ञापन देना स्वीकार करेगा। इसके आधार पर पंपिंग लेम्मा के संदर्भ में, स्ट्रिंग एबीसीडी को में तोड़ दिया गया है, जिसके लिए <math>x</math> भाग a, a <math>y</math> भाग bc और a <math>z</math> भाग d द्वारा निरूपित करते हैं।
-एक अतिरिक्त टिप्पणी के रूप में, यह जाँचने की समस्या कि क्या किसी दिए गए स्ट्रिंग को किसी दिए गए [[गैर-नियतात्मक परिमित ऑटोमेटन]] द्वारा किसी भी राज्य में बार-बार आए बिना स्वीकार किया जा सकता है, [[एनपी कठिन]] है।
+इसके अतिरिक्त टिप्पणी के रूप में यह जाँचने की समस्या कि क्या किसी दिए गए स्ट्रिंग को किसी दिए गए [[गैर-नियतात्मक परिमित ऑटोमेटन]] द्वारा किसी भी स्थिति में बार-बार आए बिना स्वीकार किया जा सकता है, यहाँ पर [[एनपी कठिन]] है।
 == नियमित भाषाओं के लिए पंपिंग लेम्मा का सामान्य संस्करण ==
-यदि कोई भाषा <math>L</math> नियमित है, तो संख्या मौजूद है <math>p \geq 1</math> (पंपिंग लंबाई) ऐसी कि हर तार <math>uwv</math> में <math>L</math> साथ <math>|w| \ge p</math> फॉर्म में लिखा जा सकता है
+यदि कोई भाषा <math>L</math> पूर्ण रूप से नियमित है, तो <math>p \geq 1</math> संख्या यहाँ पर सम्मिलित रहती है, यहाँ पर पंपिंग लंबाई इस प्रकार हैं कि हर स्ट्रिंग का मान <math>uwv</math> में <math>L</math> साथ <math>|w| \ge p</math> फॉर्म में लिखा जा सकता है। इस प्रकार उक्त समीकरण प्राप्त होता हैं-
 :<math>uwv = uxyzv</math>
-तार के साथ <math>x</math>, <math>y</math> और <math>z</math> ऐसा है कि <math>|xy| \le p</math>, <math>|y| \ge 1</math> और
+स्ट्रिंग के साथ <math>x</math>, <math>y</math> और <math>z</math> का मान इस प्रकार हैं कि <math>|xy| \le p</math>, <math>|y| \ge 1</math> और
-:<math>uxy^izv</math> में है <math>L</math> प्रत्येक पूर्णांक के लिए <math>i \geq 0</math>.<ref>{{cite book |last1=Savitch |first1=Walter |year=1982 |title=सार मशीनें और व्याकरण|isbn=978-0-316-77161-0 |page=[https://archive.org/details/abstractmachines0000savi/page/49 49] |url=https://archive.org/details/abstractmachines0000savi/page/49 }}</ref>
+:<math>uxy^izv</math> में है <math>L</math> प्रत्येक पूर्णांक के लिए <math>i \geq 0</math> मान प्राप्त होता हैं।<ref>{{cite book |last1=Savitch |first1=Walter |year=1982 |title=सार मशीनें और व्याकरण|isbn=978-0-316-77161-0 |page=[https://archive.org/details/abstractmachines0000savi/page/49 49] |url=https://archive.org/details/abstractmachines0000savi/page/49 }}</ref>
-इससे, #औपचारिक कथन मानक संस्करण दोनों के साथ विशेष मामले का अनुसरण करता है <math>u</math> और <math>v</math> खाली स्ट्रिंग होना.
+इसके लिए औपचारिक कथन मानक संस्करण दोनों के साथ विशेष स्थिति का अनुसरण करता है, जिसके लिए <math>u</math> और <math>v</math> रिक्त स्ट्रिंग को प्रकट करते हैं।
-चूँकि सामान्य संस्करण भाषा पर कड़ी आवश्यकताएँ लगाता है, इसका उपयोग कई और भाषाओं की गैर-नियमितता को साबित करने के लिए किया जा सकता है।
+चूँकि सामान्य संस्करण भाषा पर इसकी अधिक आवश्यकताएँ होती है, इसका उपयोग कई और भाषाओं की गैर-नियमितता को प्रमाणित करने के लिए किया जा सकता है।
 == लेम्मा का व्युत्क्रम सत्य नहीं ==
-जबकि पंपिंग लेम्मा में कहा गया है कि सभी नियमित भाषाएँ ऊपर वर्णित शर्तों को पूरा करती हैं, इस कथन का विपरीत सत्य नहीं है: भाषा जो इन शर्तों को पूरा करती है वह अभी भी गैर-नियमित हो सकती है। दूसरे शब्दों में, पंपिंग लेम्मा का मूल और सामान्य संस्करण दोनों ही किसी भाषा के नियमित होने के लिए आवश्यक और पर्याप्त स्थिति देते हैं।
+जबकि पंपिंग लेम्मा में कहा गया है कि सभी नियमित भाषाएँ ऊपर वर्णित शर्तों को पूरा करती हैं, इस कथन का विपरीत सत्य नहीं है, इस प्रकार इस भाषा के अनुसार जो इन शर्तों को पूरा करती है वह अभी भी गैर-नियमित हो सकती है। दूसरे शब्दों में, पंपिंग लेम्मा का मूल और सामान्य संस्करण दोनों ही किसी भाषा के नियमित होने के लिए आवश्यक और पर्याप्त स्थिति देते हैं।
 उदाहरण के लिए, निम्नलिखित भाषा पर विचार करें:
 :<math>\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}</math>.
-दूसरे शब्दों में, <math>L</math> इसमें वर्णमाला के सभी तार शामिल हैं <math>\{0,1,2,3\}</math> डुप्लिकेट वर्ण सहित लंबाई 3 की सबस्ट्रिंग के साथ, साथ ही इस वर्णमाला की सभी स्ट्रिंग्स जहां स्ट्रिंग के वर्णों का 1/7 भाग 3 है। यह भाषा नियमित नहीं है लेकिन फिर भी इसका उपयोग किया जा सकता है <math>p = 5</math>. मान लीजिए कि कुछ स्ट्रिंग एस की लंबाई कम से कम 5 है। फिर, चूंकि वर्णमाला में केवल चार अक्षर हैं, स्ट्रिंग में पहले पांच अक्षरों में से कम से कम दो डुप्लिकेट होने चाहिए। वे अधिकतम तीन वर्णों द्वारा अलग किए गए हैं।
+दूसरे शब्दों में, <math>L</math> इसमें वर्णमाला के सभी स्ट्रिंग <math>\{0,1,2,3\}</math> उपस्थित हैं, जिसके लिए डुप्लिकेट वर्ण सहित लंबाई 3 की सबस्ट्रिंग के साथ, साथ ही इस वर्णमाला की सभी स्ट्रिंग्स जहां स्ट्रिंग के वर्णों का 1/7 भाग 3 है। यह भाषा नियमित नहीं है लेकिन फिर भी <math>p = 5</math> के लिए इसका उपयोग किया जा सकता है, इस प्रकार यहाँ पर मान लीजिए कि कुछ स्ट्रिंग एस की लंबाई कम से कम 5 है। चूंकि इस उचित वर्णमाला में केवल चार अक्षर हैं, स्ट्रिंग में पहले पांच अक्षरों में से कम से कम दो डुप्लिकेट होने चाहिए। वे अधिकतम तीन वर्णों द्वारा अलग किए गए हैं।
 * यदि डुप्लिकेट वर्णों को 0 वर्णों या 1 से अलग किया गया है, तो स्ट्रिंग में अन्य दो वर्णों में से को पंप करें, जो डुप्लिकेट वाले सबस्ट्रिंग को प्रभावित नहीं करेगा।
-* यदि डुप्लिकेट वर्णों को 2 या 3 वर्णों से अलग किया गया है, तो उन्हें अलग करने वाले 2 वर्णों को पंप करें। नीचे या ऊपर पंप करने से आकार 3 की सबस्ट्रिंग का निर्माण होता है जिसमें 2 डुप्लिकेट वर्ण होते हैं।
+* यदि डुप्लिकेट वर्णों को 2 या 3 वर्णों से अलग किया गया है, तो उन्हें अलग करने वाले 2 वर्णों को पंप करें। नीचे या ऊपर पंप करने से आकार 3 की सबस्ट्रिंग का निर्माण होता है, जिसमें 2 डुप्लिकेट वर्ण होते हैं।
-*की दूसरी शर्त <math>L</math> निश्चित करता है की <math>L</math> नियमित नहीं है: स्ट्रिंग पर विचार करें <math>(013)^{3m}(012)^i</math>. यह स्ट्रिंग अंदर है <math>L</math> बिल्कुल कब <math>i=4m</math> और इस तरह <math>L</math> माईहिल-नेरोड प्रमेय द्वारा नियमित नहीं है।
+*जिसकी दूसरी शर्त <math>L</math> निश्चित करता है कि <math>L</math> नियमित नहीं है: इस प्रकार स्ट्रिंग <math>(013)^{3m}(012)^i</math> पर विचार करें, यहाँ पर यह स्ट्रिंग <math>L</math> के अंदर है, जो बिल्कुल <math>i=4m</math> होने पर और इसी प्रकार <math>L</math> माईहिल-नेरोड प्रमेय द्वारा नियमित नहीं है।
-माईहिल-नेरोड प्रमेय परीक्षण प्रदान करता है जो नियमित भाषाओं की सटीक विशेषता बताता है। यह साबित करने की सामान्य विधि कि कोई भाषा नियमित है, या तो परिमित राज्य मशीन या भाषा के लिए [[नियमित अभिव्यक्ति]] का निर्माण करना है।
+माईहिल-नेरोड प्रमेय परीक्षण प्रदान करता है जो नियमित भाषाओं की सटीक विशेषता बताता है। यह प्रमाणित करने की सामान्य विधि कि कोई भाषा नियमित है, या तो परिमित स्थिति मशीन या भाषा के लिए [[नियमित अभिव्यक्ति]] का निर्माण करना है।
 == यह भी देखें ==
 * ओग्डेन की लेम्मा
-* संदर्भ-मुक्त भाषाओं के लिए लेम्मा को बढ़ावा देना
+* संदर्भ-मुक्त भाषाओं के लिए लेम्मा में अधिकता करना
-* नियमित वृक्ष भाषाओं के लिए पंपिंग लेम्मा
+* नियमित ट्री भाषाओं के लिए पंपिंग लेम्मा
 == टिप्पणियाँ ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 23:55, 25 July 2023

Contents

औपचारिक कथन

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

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

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

लेम्मा का व्युत्क्रम सत्य नहीं

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 23:55, 25 July 2023

औपचारिक कथन

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

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

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

लेम्मा का व्युत्क्रम सत्य नहीं

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories