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

Revision as of 21:42, 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$ भाग ए, ए $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

.^[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 19: / Line 19: @@
   | publisher=Addison Wesley
 }} 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 28: / 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 भागों में विभाजित किया जा सकता है।
@@ Line 44: / Line 42: @@
 \end{array}
 </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> भाग ए, ए <math>y</math> भाग बीसी और ए <math>z</math> भाग डी.
 एक अतिरिक्त टिप्पणी के रूप में, यह जाँचने की समस्या कि क्या किसी दिए गए स्ट्रिंग को किसी दिए गए [[गैर-नियतात्मक परिमित ऑटोमेटन]] द्वारा किसी भी राज्य में बार-बार आए बिना स्वीकार किया जा सकता है, [[एनपी कठिन]] है।
 == नियमित भाषाओं के लिए पंपिंग लेम्मा का सामान्य संस्करण ==
-यदि कोई भाषा <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>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 से अलग किया गया है, तो स्ट्रिंग में अन्य दो वर्णों में से एक को पंप करें, जो डुप्लिकेट वाले सबस्ट्रिंग को प्रभावित नहीं करेगा।
+* यदि डुप्लिकेट वर्णों को 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> माईहिल-नेरोड प्रमेय द्वारा नियमित नहीं है।
-माईहिल-नेरोड प्रमेय एक परीक्षण प्रदान करता है जो नियमित भाषाओं की सटीक विशेषता बताता है। यह साबित करने की सामान्य विधि कि कोई भाषा नियमित है, या तो एक परिमित राज्य मशीन या भाषा के लिए एक [[नियमित अभिव्यक्ति]] का निर्माण करना है।
+माईहिल-नेरोड प्रमेय परीक्षण प्रदान करता है जो नियमित भाषाओं की सटीक विशेषता बताता है। यह साबित करने की सामान्य विधि कि कोई भाषा नियमित है, या तो परिमित राज्य मशीन या भाषा के लिए [[नियमित अभिव्यक्ति]] का निर्माण करना है।
 == यह भी देखें ==
@@ Line 94: / Line 90: @@
 == टिप्पणियाँ ==
 <references/>
 == संदर्भ ==
@@ Line 101: / Line 96: @@
 * {{cite book | first1=John E. | last1=Hopcroft | author1-link=John Hopcroft | first2=Jeffrey D. | last2=Ullman | author2-link=Jeffrey Ullman | title=Introduction to Automata Theory, Languages, and Computation | publisher=Addison-Wesley Publishing | location=Reading, Massachusetts | year=1979 | isbn=978-0-201-02988-8 | zbl=0426.68001 | title-link=Introduction to Automata Theory, Languages, and Computation }} ''(See chapter 3.)''
 * {{cite book|author1=Bakhadyr Khoussainov|author2=Anil Nerode|authorlink2=Anil Nerode|title=Automata Theory and its Applications|url=https://books.google.com/books?id=wR_oBwAAQBAJ|date=6 December 2012|publisher=Springer Science & Business Media|isbn=978-1-4612-0171-7}}
-{{Formal languages and grammars |state=collapsed}}
 [[Category: औपचारिक भाषाएँ]] [[Category: लेम्मास]] [[Category: स्वचालित रूप से समाप्त हो गया]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 21:42, 25 July 2023

Contents

औपचारिक कथन

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

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 21:42, 25 July 2023

औपचारिक कथन

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

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories