पॉवरसेट निर्माण: Difference between revisions

Revision as of 10:37, 2 August 2023

गणना और ऑटोमेटा सिद्धांत के सिद्धांत में, पॉवरसेट निर्माण या सबसेट निर्माण एक गैर-नियतात्मक परिमित ऑटोमेटन (एनएफए) को एक नियतात्मक परिमित ऑटोमेटन (डीएफए) में परिवर्तित करने के लिए एक मानक विधि है जो समान औपचारिक लैंग्वेज को पहचानता है। यह सैद्धांतिक रूप से महत्वपूर्ण है क्योंकि यह स्थापित करता है कि एनएफए, अपने अतिरिक्त लचीलेपन के अतिरिक्त किसी भी लैंग्वेज को पहचानने में असमर्थ हैं जिसे कुछ डीएफए द्वारा मान्यता नहीं दी जा सकती है। निर्माण में आसान एनएफए को अधिक कुशलतापूर्वक निष्पादन योग्य डीएफए में परिवर्तित करना व्यवहार में भी महत्वपूर्ण है। चूँकि यदि एनएफए में एन अवस्था हैं, तो परिणामी डीएफए में 2ⁿ अवस्था तक हो सकते हैं, जो कि एक तेजी से बड़ी संख्या है, जो कभी-कभी बड़े एनएफए के लिए निर्माण को अव्यवहारिक बना देता है।

निर्माण, जिसे कभी-कभी अन्य प्रकार के ऑटोमेटा के समान निर्माणों से अलग करने के लिए राबिन-स्कॉट पॉवरसेट निर्माण (या सबसेट निर्माण) कहा जाता है, पहली बार 1959 में माइकल ओ. राबिन और डाना स्कॉट द्वारा प्रकाशित किया गया था।^[1]

अंतर्ज्ञान

किसी दिए गए इनपुट स्ट्रिंग पर डीएफए के संचालन को अनुकरण करने के लिए, किसी को किसी भी समय एक ही स्थिति पर दृष्टि रखने की आवश्यकता होती है: वह स्थिति जहां ऑटोमेटन इनपुट के उपसर्ग को देखने के बाद पहुंचेगा। इसके विपरीत, एनएफए का अनुकरण करने के लिए, किसी को अवस्थाओ के एक सेट पर दृष्टि रखने की आवश्यकता होती है: ऑटोमेटन द्वारा बनाए गए गैर-नियतात्मक विकल्पों के अनुसार, सभी अवस्था जहां ऑटोमेटन इनपुट के समान उपसर्ग को देखने के बाद पहुंच सकता है। यदि, इनपुट के एक निश्चित उपसर्ग के बाद, अवस्थाओ के एक सेट S तक पहुंचा जा सकता है, तो अगले इनपुट प्रतीक x के बाद पहुंच योग्य अवस्थाओ का सेट $S$ और $x$ का एक नियतात्मक कार्य है। इसलिए, पहुंच योग्य एनएफए अवस्थाओ के सेट एनएफए सिमुलेशन में वही भूमिका निभाते हैं जैसे एकल डीएफए अवस्था डीएफए सिमुलेशन में निभाते हैं, और वास्तव में इस सिमुलेशन में दिखाई देने वाले एनएफए अवस्थाओ के सेट को डीएफए के अवस्थाओ के रूप में फिर से व्याख्या किया जा सकता है।^[2]

निर्माण

पावरसेट निर्माण सबसे सीधे एनएफए पर प्रयुक्त होता है जो इनपुट प्रतीकों (या: "ε-मूव्स") का उपभोग किए बिना अवस्था परिवर्तनों की अनुमति नहीं देता है। ऐसे ऑटोमेटन को 5-टुपल ( $(Q, Σ, T, q 0, F)$ के रूप में परिभाषित किया जा सकता है, जिसमें $Q$ अवस्थाओ का सेट है, $Σ$ इनपुट प्रतीकों का सेट है, $T$ संक्रमण फ़ंक्शन है (एक अवस्था का मानचित्रण और अवस्थाओ के एक सेट के लिए एक इनपुट प्रतीक), $q 0$ प्रारंभिक स्थिति है, और $F$ स्वीकार करने वाले अवस्थाओ का सेट है। संबंधित DFA में $Q$ के उपसमुच्चय के अनुरूप स्थितियाँ हैं। DFA की प्रारंभिक अवस्था ${q 0}$ है, प्रारंभिक अवस्थाओं का (एक-तत्व) सेट डीएफए का संक्रमण फ़ंक्शन एक अवस्था $S$ ( $Q$ के उपसमुच्चय का प्रतिनिधित्व करता है) और एक इनपुट प्रतीक $x$ को सेट $T (S, x) = \cup{T (q, x) | q \in S}$ पर मैप करता है।, सभी अवस्थाओ का सेट जो एस में एक अवस्था से $x$ -संक्रमण द्वारा पहुंचा जा सकता है। डीएफए का एक अवस्था $S$ एक स्वीकार्य अवस्था है यदि और केवल यदि $S$ का कम से कम एक सदस्य एनएफए की एक स्वीकार्य स्थिति है।^[2]^[3]

पॉवरसेट निर्माण के सबसे सरल संस्करण में, DFA के सभी अवस्था का सेट $Q$ का पॉवरसेट है, जो की $Q$ के सभी संभावित उपसमूहों का सेट चूँकि परिणामी DFA के कई अवस्था व्यर्थ हो सकते हैं क्योंकि वे पहुंच से बाहर हो सकते हैं आरंभिक अवस्था निर्माण का एक वैकल्पिक संस्करण केवल उन अवस्था का निर्माण करता है जो वास्तव में पहुंच योग्य हैं।^[4]

एनएफए ε-चालों के साथ

ε-मूव्स (जिसे ε-NFA भी कहा जाता है) वाले एनएफए के लिए, अवस्थाओ के ε-प्रतिवर्ती सकर्मक समापन की गणना करके इनसे निपटने के लिए निर्माण को संशोधित किया जाना चाहिए: केवल ε-मूव्स का उपयोग करके किसी दिए गए अवस्था से पहुंचने योग्य सभी अवस्थाओ का सेट वैन नोर्ड पावरसेट निर्माण में इस क्लोजर गणना को सम्मिलित करने के तीन संभावित विधियों को पहचानते हैं:^[5]

संपूर्ण ऑटोमेटन के ε-क्लोजर की गणना प्रीप्रोसेसिंग चरण के रूप में करें, जो ε-चालों के बिना समतुल्य एनएफए का उत्पादन करता है, फिर नियमित पावरसेट निर्माण प्रयुक्त करें। होपक्रॉफ्ट और उलमैन द्वारा चर्चा किए गए इस संस्करण को प्रयुक्त करना आसान है,^[6] किंतु बड़ी संख्या में ε-चाल वाले ऑटोमेटा के लिए अव्यावहारिक है, जैसा कि समान्यत: प्राकृतिक लैंग्वेज प्रसंस्करण अनुप्रयोग में होता है।^[5]
पावरसेट गणना के समय , प्रत्येक स्थिति $q$ के ε-क्लोजर $\{q'~|~q\to _{\varepsilon }^{*}q'\}$ की गणना करें जिसे एल्गोरिदम द्वारा माना जाता है (और परिणाम को कैश करें)।
पावरसेट गणना के समय , अवस्थाओ $Q'$ के प्रत्येक उपसमूह के ε-क्लोजर $\{q'~|~\exists q\in Q',q\to _{\varepsilon }^{*}q'\}$ की गणना करें जिसे एल्गोरिदम द्वारा माना जाता है, और इसके तत्वों को $Q'$ में जोड़ें।

एकाधिक प्रारंभिक अवस्थाएँ

यदि एनएफए को कई प्रारंभिक स्थितियों की अनुमति देने के लिए परिभाषित किया गया है,^[7] संबंधित डीएफए की प्रारंभिक अवस्था एनएफए की सभी प्रारंभिक अवस्थाओं का समुच्चय है, या (यदि एनएफए में ε-चालें भी हैं) ε-चालों द्वारा प्रारंभिक अवस्थाओं तक पहुंचने योग्य सभी अवस्थाओं का समुच्चय है।

उदाहरण

नीचे दिए गए एनएफए में चार अवस्था हैं; अवस्था 1 प्रारंभिक है, और अवस्था 3 और 4 स्वीकार कर रहे हैं। इसकी वर्णमाला में दो प्रतीक 0 और 1 सम्मिलित हैं, और इसमें ε-चालें हैं।

इस एनएफए से निर्मित डीएफए की प्रारंभिक स्थिति उन सभी एनएफए अवस्थाओ का सेट है जो ε-चालों द्वारा अवस्था 1 से पहुंच योग्य हैं; अर्थात्, यह समुच्चय {1,2,3} है। इनपुट प्रतीक 0 द्वारा {1,2,3} से संक्रमण को या तो अवस्था 1 से अवस्था 2 तक तीर का अनुसरण करना चाहिए, या अवस्था 3 से अवस्था 4 तक तीर का पालन करना चाहिए। इसके अतिरिक्त, इसे न तो अवस्था 2 और न ही अवस्था 4 में आउटगोइंग ε-चालें हैं। इसलिए, $T$ ({1,2,3},0) = {2,4}, और इसी तर्क से एनएफए से निर्मित पूर्ण डीएफए नीचे दिखाया गया है।

जैसा कि इस उदाहरण में देखा जा सकता है, डीएफए की आरंभिक स्थिति से पांच अवस्थाओ तक पहुंचा जा सकता है; एनएफए अवस्थाओ के सेट के पावरसेट में शेष 11 सेट पहुंच योग्य नहीं हैं।

कॉम्प्लेक्सिटी

5 अवस्थाओ वाला एनएफए (बाएं) जिसके डीएफए (दाएं) के लिए 16 अवस्थाओ की आवश्यकता है।^[4]

क्योंकि DFA अवस्थाओ में NFA अवस्थाओ का समूह सम्मिलित होता है, एक $n$ -अवस्था NFA को अधिकतम $2 n$ अवस्थाओ वाले DFA में परिवर्तित किया जा सकता है।^[2] प्रत्येक $n$ के लिए, $n$ -स्टेट एनएफए उपस्थित हैं, जैसे कि अवस्थाओ का प्रत्येक उपसमूह प्रारंभिक उपसमुच्चय से पहुंच योग्य है, ताकि परिवर्तित डीएफए में बिल्कुल $2 n$ अवस्था हों, जो Θ $2 n$ सबसे व्यर्थ स्थिति समय सम्मिश्रता देता है।^[8]^[9] लगभग इतने अवस्थाओ की आवश्यकता वाला एक सरल उदाहरण वर्णमाला {0,1} पर स्ट्रिंग की लैंग्वेज है जिसमें कम से कम $n$ वर्ण हैं, जिनमें से अंतिम से $n$ वाँ 1 है। इसे $(n + 1)$ द्वारा दर्शाया जा सकता है -एनएफए बताएं, किंतु इसके लिए $2 n$ की आवश्यकता है डीएफए $n =4$ के लिए इनपुट सीएफ चित्र के प्रत्येक $n$ -वर्ण प्रत्यय के लिए एक बताता है।

अनुप्रयोग

डीएफए न्यूनीकरण के लिए ब्रज़ोज़ोस्की का एल्गोरिदम पावरसेट निर्माण का दो बार उपयोग करता है। यह अपने सभी तीरों को विपरीत कर और प्रारंभिक और स्वीकार करने वाले अवस्थाओ की भूमिकाओं का आदान-प्रदान करके, रिवर्स लैंग्वेज के लिए इनपुट डीएफए को एनएफए में परिवर्तित करता है, पावरसेट निर्माण का उपयोग करके एनएफए को वापस डीएफए में परिवर्तित करता है, और फिर इसकी प्रक्रिया को दोहराता है। कुछ अन्य ज्ञात डीएफए न्यूनीकरण एल्गोरिदम के विपरीत, इसकी सबसे व्यर्थ स्थिति की सम्मिश्रता घातीय है, किंतु कई उदाहरणों में यह अपनी सबसे व्यर्थ स्थिति की सम्मिश्रता की तुलना में अधिक तेज़ी से प्रदर्शन करती है।^[10]

सफरा का निर्माण, जो $n$ अवस्थाओ के साथ एक गैर-नियतात्मक बुची ऑटोमेटन को एक नियतात्मक मुलर ऑटोमेटन में या 2^{O(n log n)} अवस्थाओ के साथ एक नियतात्मक राबिन ऑटोमेटन में परिवर्तित करता है, अपनी मशीनरी के भाग के रूप में पावरसेट निर्माण का उपयोग करता है।^[11]

संदर्भ

↑ Rabin, M. O.; Scott, D. (1959). "परिमित ऑटोमेटा और उनकी निर्णय समस्याएं". IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114. ISSN 0018-8646.
↑ ^2.0 ^2.1 ^2.2 Sipser, Michael (1997). "Theorem 1.19". संगणना के सिद्धांत का परिचय. pp. 55–56. ISBN 0-534-94728-X.
↑ Hopcroft, John E.; Ullman, Jeffrey D. (1979). "The equivalence of DFA's and NFA's". Introduction to Automata Theory, Languages, and Computation. Reading Massachusetts: Addison-Wesley. pp. 22–23. ISBN 0-201-02988-X.
↑ ^4.0 ^4.1 Schneider, Klaus (2004). Verification of reactive systems: formal methods and algorithms. Springer. pp. 210–212. ISBN 978-3-540-00296-3.
↑ ^5.0 ^5.1 Van Noord, Gertjan (2000). "एप्सिलॉन का उपचार उपसमुच्चय निर्माण में चलता है". Computational Linguistics. 26 (1): 61–76. arXiv:cmp-lg/9804003. doi:10.1162/089120100561638. S2CID 5622079.
↑ Hopcroft & Ullman (1979), pp. 26–27.
↑ Rothe, Jörg (2006). Complexity Theory and Cryptology: An Introduction to Cryptocomplexity. Texts in Theoretical Computer Science. Springer. pp. 21–22. ISBN 9783540285205..
↑ Lupanov, Oleg B. (1963). "A comparison of two types of finite sources". Problemy Kibernetiki. 9: 321–326.
↑ Moore, Frank R. (1971). "On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata". IEEE Transactions on Computers. C-20 (10): 1211–1214. doi:10.1109/T-C.1971.223108. S2CID 206618275..
↑ Brzozowski, J. A. (1963). "Canonical regular expressions and minimal state graphs for definite events". Proc. Sympos. Math. Theory of Automata (New York, 1962). Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y. pp. 529–561. MR 0175719.
↑ Safra, S. (1988). "On the complexity of ω-automata". Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS '88). Washington, DC, USA: IEEE Computer Society. pp. 319–327. doi:10.1109/SFCS.1988.21948..

अग्रिम पठन

Anderson, James Andrew (2006). Automata theory with modern applications. Cambridge University Press. pp. 43–49. ISBN 978-0-521-84887-9.

[1] Rabin, M. O.; Scott, D. (1959). "परिमित ऑटोमेटा और उनकी निर्णय समस्याएं". IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114. ISSN 0018-8646.

[sipser-2] 2.0 ^2.1 ^2.2 Sipser, Michael (1997). "Theorem 1.19". संगणना के सिद्धांत का परिचय. pp. 55–56. ISBN 0-534-94728-X.

[hu-3] Hopcroft, John E.; Ullman, Jeffrey D. (1979). "The equivalence of DFA's and NFA's". Introduction to Automata Theory, Languages, and Computation. Reading Massachusetts: Addison-Wesley. pp. 22–23. ISBN 0-201-02988-X.

[schneider-4] 4.0 ^4.1 Schneider, Klaus (2004). Verification of reactive systems: formal methods and algorithms. Springer. pp. 210–212. ISBN 978-3-540-00296-3.

[vannoord-5] 5.0 ^5.1 Van Noord, Gertjan (2000). "एप्सिलॉन का उपचार उपसमुच्चय निर्माण में चलता है". Computational Linguistics. 26 (1): 61–76. arXiv:cmp-lg/9804003. doi:10.1162/089120100561638. S2CID 5622079.

[6] Hopcroft & Ullman (1979), pp. 26–27.

[7] Rothe, Jörg (2006). Complexity Theory and Cryptology: An Introduction to Cryptocomplexity. Texts in Theoretical Computer Science. Springer. pp. 21–22. ISBN 9783540285205..

[8] Lupanov, Oleg B. (1963). "A comparison of two types of finite sources". Problemy Kibernetiki. 9: 321–326.

[moore71-9] Moore, Frank R. (1971). "On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata". IEEE Transactions on Computers. C-20 (10): 1211–1214. doi:10.1109/T-C.1971.223108. S2CID 206618275..

[10] Brzozowski, J. A. (1963). "Canonical regular expressions and minimal state graphs for definite events". Proc. Sympos. Math. Theory of Automata (New York, 1962). Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y. pp. 529–561. MR 0175719.

[11] Safra, S. (1988). "On the complexity of ω-automata". Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS '88). Washington, DC, USA: IEEE Computer Society. pp. 319–327. doi:10.1109/SFCS.1988.21948..

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
 {{Short description|Method for making finite automata deterministic}}
-गणना और [[ऑटोमेटा सिद्धांत]] के सिद्धांत में, पॉवरसेट निर्माण या सबसेट निर्माण एक [[गैर-[[नियतात्मक परिमित ऑटोमेटन]]]] (एनएफए) को एक नियतात्मक परिमित ऑटोमेटन (डीएफए) में परिवर्तित करने के लिए एक मानक विधि है जो समान [[औपचारिक भाषा]] को पहचानता है। यह सैद्धांतिक रूप से महत्वपूर्ण है क्योंकि यह स्थापित करता है कि एनएफए, अपने अतिरिक्त लचीलेपन के बावजूद, किसी भी भाषा को पहचानने में असमर्थ हैं जिसे कुछ डीएफए द्वारा मान्यता नहीं दी जा सकती है। निर्माण में आसान एनएफए को अधिक कुशलतापूर्वक निष्पादन योग्य डीएफए में परिवर्तित करना व्यवहार में भी महत्वपूर्ण है। हालाँकि, यदि एनएफए में ''एन'' राज्य हैं, तो परिणामी डीएफए में 2 तक हो सकते हैं<sup>n</sup> बताता है, एक तेजी से बड़ी संख्या, जो कभी-कभी बड़े एनएफए के लिए निर्माण को अव्यवहारिक बना देती है।
-निर्माण, जिसे कभी-कभी अन्य प्रकार के ऑटोमेटा के समान निर्माणों से अलग करने के लिए 'राबिन-स्कॉट पावरसेट निर्माण' (या सबसेट निर्माण) कहा जाता है, पहली बार 1959 में माइकल ओ. राबिन और [[दाना स्कॉट]] द्वारा प्रकाशित किया गया था।<ref>{{cite journal |last1=Rabin |first1=M. O. |authorlink1=Michael O. Rabin |last2=Scott |first2=D. |authorlink2=Dana Scott |date=1959 |title=परिमित ऑटोमेटा और उनकी निर्णय समस्याएं|journal=IBM Journal of Research and Development |issn=0018-8646 |doi=10.1147/rd.32.0114 |volume=3 |issue=2 |pages=114–125}}</ref>
+गणना और ऑटोमेटा सिद्धांत के सिद्धांत में, '''पॉवरसेट निर्माण''' या सबसेट निर्माण एक गैर-नियतात्मक परिमित ऑटोमेटन (एनएफए) को एक नियतात्मक परिमित ऑटोमेटन (डीएफए) में परिवर्तित करने के लिए एक मानक विधि है जो समान औपचारिक लैंग्वेज को पहचानता है। यह सैद्धांतिक रूप से महत्वपूर्ण है क्योंकि यह स्थापित करता है कि एनएफए, अपने अतिरिक्त लचीलेपन के अतिरिक्त किसी भी लैंग्वेज को पहचानने में असमर्थ हैं जिसे कुछ डीएफए द्वारा मान्यता नहीं दी जा सकती है। निर्माण में आसान एनएफए को अधिक कुशलतापूर्वक निष्पादन योग्य डीएफए में परिवर्तित करना व्यवहार में भी महत्वपूर्ण है। चूँकि यदि एनएफए में एन अवस्था हैं, तो परिणामी डीएफए में 2<sup>''n''</sup> अवस्था तक हो सकते हैं, जो कि एक तेजी से बड़ी संख्या है, जो कभी-कभी बड़े एनएफए के लिए निर्माण को अव्यवहारिक बना देता है।
+निर्माण, जिसे कभी-कभी अन्य प्रकार के ऑटोमेटा के समान निर्माणों से अलग करने के लिए राबिन-स्कॉट पॉवरसेट निर्माण (या सबसेट निर्माण) कहा जाता है, पहली बार 1959 में माइकल ओ. राबिन और डाना स्कॉट द्वारा प्रकाशित किया गया था।<ref>{{cite journal |last1=Rabin |first1=M. O. |authorlink1=Michael O. Rabin |last2=Scott |first2=D. |authorlink2=Dana Scott |date=1959 |title=परिमित ऑटोमेटा और उनकी निर्णय समस्याएं|journal=IBM Journal of Research and Development |issn=0018-8646 |doi=10.1147/rd.32.0114 |volume=3 |issue=2 |pages=114–125}}</ref>
 ==अंतर्ज्ञान==
-किसी दिए गए इनपुट स्ट्रिंग पर डीएफए के संचालन को अनुकरण करने के लिए, किसी को किसी भी समय एक ही स्थिति पर नज़र रखने की आवश्यकता होती है: वह स्थिति जहां ऑटोमेटन इनपुट के सबस्ट्रिंग # उपसर्ग को देखने के बाद पहुंचेगा। इसके विपरीत, एनएफए का अनुकरण करने के लिए, किसी को राज्यों के एक सेट पर नज़र रखने की आवश्यकता होती है: ऑटोमेटन द्वारा बनाए गए गैर-नियतात्मक विकल्पों के अनुसार, सभी राज्य जहां ऑटोमेटन इनपुट के समान उपसर्ग को देखने के बाद पहुंच सकता है। यदि, इनपुट के एक निश्चित उपसर्ग के बाद, एक सेट {{mvar|S}} राज्यों तक पहुंचा जा सकता है, फिर अगले इनपुट प्रतीक के बाद {{mvar|x}} पहुंच योग्य राज्यों का सेट एक नियतात्मक कार्य है {{mvar|S}} और {{mvar|x}}. इसलिए, पहुंच योग्य एनएफए राज्यों के सेट एनएफए सिमुलेशन में वही भूमिका निभाते हैं जैसे एकल डीएफए राज्य डीएफए सिमुलेशन में निभाते हैं, और वास्तव में इस सिमुलेशन में दिखाई देने वाले एनएफए राज्यों के सेट को डीएफए के राज्यों के रूप में फिर से व्याख्या किया जा सकता है।<ref name="sipser">{{cite book |last=Sipser |first=Michael |authorlink=Michael Sipser |title=संगणना के सिद्धांत का परिचय|year=1997 |isbn=0-534-94728-X |contribution=Theorem 1.19 |pages=[https://archive.org/details/introductiontoth00sips/page/55 55–56] |url-access=registration |url=https://archive.org/details/introductiontoth00sips/page/55 }}</ref>
+किसी दिए गए इनपुट स्ट्रिंग पर डीएफए के संचालन को अनुकरण करने के लिए, किसी को किसी भी समय एक ही स्थिति पर दृष्टि रखने की आवश्यकता होती है: वह स्थिति जहां ऑटोमेटन इनपुट के उपसर्ग को देखने के बाद पहुंचेगा। इसके विपरीत, एनएफए का अनुकरण करने के लिए, किसी को अवस्थाओ के एक सेट पर दृष्टि रखने की आवश्यकता होती है: ऑटोमेटन द्वारा बनाए गए गैर-नियतात्मक विकल्पों के अनुसार, सभी अवस्था जहां ऑटोमेटन इनपुट के समान उपसर्ग को देखने के बाद पहुंच सकता है। यदि, इनपुट के एक निश्चित उपसर्ग के बाद, अवस्थाओ के एक सेट S तक पहुंचा जा सकता है, तो अगले इनपुट प्रतीक x के बाद पहुंच योग्य अवस्थाओ का सेट  {{mvar|S}} और {{mvar|x}} का एक नियतात्मक कार्य है। इसलिए, पहुंच योग्य एनएफए अवस्थाओ के सेट एनएफए सिमुलेशन में वही भूमिका निभाते हैं जैसे एकल डीएफए अवस्था डीएफए सिमुलेशन में निभाते हैं, और वास्तव में इस सिमुलेशन में दिखाई देने वाले एनएफए अवस्थाओ के सेट को डीएफए के अवस्थाओ के रूप में फिर से व्याख्या किया जा सकता है।<ref name="sipser">{{cite book |last=Sipser |first=Michael |authorlink=Michael Sipser |title=संगणना के सिद्धांत का परिचय|year=1997 |isbn=0-534-94728-X |contribution=Theorem 1.19 |pages=[https://archive.org/details/introductiontoth00sips/page/55 55–56] |url-access=registration |url=https://archive.org/details/introductiontoth00sips/page/55 }}</ref>
+==निर्माण==
+पावरसेट निर्माण सबसे सीधे एनएफए पर प्रयुक्त  होता है जो इनपुट प्रतीकों (या: "ε-मूव्स") का उपभोग किए बिना अवस्था परिवर्तनों की अनुमति नहीं देता है। ऐसे ऑटोमेटन को 5-टुपल ({{math|(''Q'', Σ, ''T'', ''q''<sub>0</sub>, ''F'')}} के रूप में परिभाषित किया जा सकता है, जिसमें {{mvar|Q}}अवस्थाओ का सेट है, {{math|Σ}} इनपुट प्रतीकों का सेट है, {{mvar|T}} संक्रमण फ़ंक्शन है (एक अवस्था का मानचित्रण और अवस्थाओ के एक सेट के लिए एक इनपुट प्रतीक), {{math|''q''<sub>0</sub>}} प्रारंभिक स्थिति है, और {{mvar|F}} स्वीकार करने वाले अवस्थाओ का सेट है। संबंधित DFA में {{mvar|Q}} के उपसमुच्चय के अनुरूप स्थितियाँ हैं। DFA की प्रारंभिक अवस्था{{math|{{mset|''q''<sub>0</sub>}}}}है, प्रारंभिक अवस्थाओं का (एक-तत्व) सेट डीएफए का संक्रमण फ़ंक्शन एक अवस्था {{mvar|S}} ({{mvar|Q}} के उपसमुच्चय का प्रतिनिधित्व करता है) और एक इनपुट प्रतीक {{mvar|x}} को सेट {{math|1=''T''(''S'',''x'') = &cup;{{mset|''T''(''q'',''x'') {{pipe}} ''q'' ∈ ''S''}}}} पर मैप करता है।, सभी अवस्थाओ का सेट जो एस में एक अवस्था से {{mvar|x}}-संक्रमण द्वारा पहुंचा जा सकता है। डीएफए का एक अवस्था {{mvar|S}} एक स्वीकार्य अवस्था है यदि और केवल यदि {{mvar|S}} का कम से कम एक सदस्य  एनएफए की एक स्वीकार्य स्थिति है।<ref name="sipser"/><ref name="hu">{{cite book |last1=Hopcroft |first1=John E. |authorlink1=John Hopcroft |last2=Ullman |first2=Jeffrey D. |authorlink2=Jeffrey Ullman |date=1979 |title=[[Introduction to Automata Theory, Languages, and Computation]] |publisher=Addison-Wesley |location=Reading Massachusetts |isbn=0-201-02988-X |contribution=The equivalence of DFA's and NFA's |pages=[https://archive.org/details/introductiontoau00hopc/page/22 22–23] }}</ref>
-==निर्माण==
+पॉवरसेट निर्माण के सबसे सरल संस्करण में, DFA के सभी अवस्था  का सेट {{mvar|Q}} का पॉवरसेट है, जो की {{mvar|Q}} के सभी संभावित उपसमूहों का सेट चूँकि परिणामी DFA के कई अवस्था व्यर्थ हो सकते हैं क्योंकि वे पहुंच से बाहर हो सकते हैं आरंभिक अवस्था निर्माण का एक वैकल्पिक संस्करण केवल उन अवस्था का निर्माण करता है जो वास्तव में पहुंच योग्य हैं।<ref name="schneider">{{cite book |last=Schneider |first=Klaus |date=2004 |title=Verification of reactive systems: formal methods and algorithms |publisher=Springer |isbn=978-3-540-00296-3 |pages=210–212 |url=https://books.google.com/books?id=Z92bL1VrD_sC&pg=PA210}}</ref>
-पावरसेट निर्माण सबसे सीधे एनएफए पर लागू होता है जो इनपुट प्रतीकों (उर्फ: ε-मूव्स) का उपभोग किए बिना राज्य परिवर्तनों की अनुमति नहीं देता है। ऐसे ऑटोमेटन को टुपल|5-[[ टपल ]] के रूप में परिभाषित किया जा सकता है {{math|(''Q'', Σ, ''T'', ''q''<sub>0</sub>, ''F'')}}, जिसमें {{mvar|Q}} राज्यों का समूह है, {{math|Σ}} इनपुट प्रतीकों का सेट है, {{mvar|T}} संक्रमण फ़ंक्शन है (एक राज्य और एक इनपुट प्रतीक को राज्यों के समूह में मैप करना), {{math|''q''<sub>0</sub>}} प्रारंभिक अवस्था है, और {{mvar|F}} स्वीकार करने वाले राज्यों का समूह है। संगत DFA में उपसमुच्चय के अनुरूप स्थितियाँ होती हैं {{mvar|Q}}. DFA की प्रारंभिक अवस्था है {{math|{{mset|''q''<sub>0</sub>}}}}, प्रारंभिक अवस्थाओं का (एक-तत्व) सेट। डीएफए का संक्रमण कार्य किसी राज्य का मानचित्रण करता है {{mvar|S}} (के एक उपसमुच्चय का प्रतिनिधित्व करना {{mvar|Q}}) और एक इनपुट प्रतीक {{mvar|x}} सेट पर {{math|1=''T''(''S'',''x'') = &cup;{{mset|''T''(''q'',''x'') {{pipe}} ''q'' ∈ ''S''}}}}, सभी राज्यों का समूह जिन तक a द्वारा पहुंचा जा सकता है {{mvar|x}}-एक राज्य से संक्रमण {{mvar|S}}.
-एक राज्य {{mvar|S}} डीएफए एक स्वीकार्य राज्य है यदि और केवल तभी जब इसका कम से कम एक सदस्य हो {{mvar|S}} एनएफए की एक स्वीकार्य स्थिति है।<ref name="sipser"/><ref name="hu">{{cite book |last1=Hopcroft |first1=John E. |authorlink1=John Hopcroft |last2=Ullman |first2=Jeffrey D. |authorlink2=Jeffrey Ullman |date=1979 |title=[[Introduction to Automata Theory, Languages, and Computation]] |publisher=Addison-Wesley |location=Reading Massachusetts |isbn=0-201-02988-X |contribution=The equivalence of DFA's and NFA's |pages=[https://archive.org/details/introductiontoau00hopc/page/22 22–23] }}</ref>
-पावरसेट निर्माण के सबसे सरल संस्करण में, डीएफए के सभी राज्यों का सेट [[ सत्ता स्थापित ]] है {{mvar|Q}}, के सभी संभावित उपसमुच्चय का समुच्चय {{mvar|Q}}. हालाँकि, परिणामी DFA की कई स्थितियाँ बेकार हो सकती हैं क्योंकि वे प्रारंभिक अवस्था से अप्राप्य हो सकती हैं। निर्माण का एक वैकल्पिक संस्करण केवल उन राज्यों का निर्माण करता है जो वास्तव में पहुंच योग्य हैं।<ref name="schneider">{{cite book |last=Schneider |first=Klaus |date=2004 |title=Verification of reactive systems: formal methods and algorithms |publisher=Springer |isbn=978-3-540-00296-3 |pages=210–212 |url=https://books.google.com/books?id=Z92bL1VrD_sC&pg=PA210}}</ref>
 ===एनएफए ε-चालों के साथ===
-ε-मूव्स (जिसे ε-NFA भी कहा जाता है) वाले एनएफए के लिए, राज्यों के ε-[[ प्रतिवर्ती सकर्मक समापन ]] की गणना करके इनसे निपटने के लिए निर्माण को संशोधित किया जाना चाहिए: केवल ε-मूव्स का उपयोग करके किसी दिए गए राज्य से पहुंचने योग्य सभी राज्यों का सेट। वैन नोर्ड पावरसेट निर्माण में इस क्लोजर गणना को शामिल करने के तीन संभावित तरीकों को पहचानते हैं:<ref name="vannoord">{{cite journal |last=Van Noord |first=Gertjan |title=एप्सिलॉन का उपचार उपसमुच्चय निर्माण में चलता है|journal=Computational Linguistics |volume=26 |issue=1 |year=2000 |pages=61–76 |url=http://www.mitpressjournals.org/doi/pdfplus/10.1162/089120100561638 |doi=10.1162/089120100561638|arxiv=cmp-lg/9804003 |s2cid=5622079 }}</ref>
+ε-मूव्स (जिसे ε-NFA भी कहा जाता है) वाले एनएफए के लिए, अवस्थाओ के ε-[[ प्रतिवर्ती सकर्मक समापन ]] की गणना करके इनसे निपटने के लिए निर्माण को संशोधित किया जाना चाहिए: केवल ε-मूव्स का उपयोग करके किसी दिए गए अवस्था से पहुंचने योग्य सभी अवस्थाओ का सेट वैन नोर्ड पावरसेट निर्माण में इस क्लोजर गणना को सम्मिलित करने के तीन संभावित विधियों को पहचानते हैं:<ref name="vannoord">{{cite journal |last=Van Noord |first=Gertjan |title=एप्सिलॉन का उपचार उपसमुच्चय निर्माण में चलता है|journal=Computational Linguistics |volume=26 |issue=1 |year=2000 |pages=61–76 |url=http://www.mitpressjournals.org/doi/pdfplus/10.1162/089120100561638 |doi=10.1162/089120100561638|arxiv=cmp-lg/9804003 |s2cid=5622079 }}</ref>
-# प्रीप्रोसेसिंग चरण के रूप में संपूर्ण ऑटोमेटन के ε-क्लोजर की गणना करें, ε-चालों के बिना समतुल्य एनएफए का उत्पादन करें, फिर नियमित पावरसेट निर्माण लागू करें। इस संस्करण पर हॉपक्रॉफ्ट और उल्मैन ने भी चर्चा की,<ref>{{harvtxt|Hopcroft|Ullman|1979}}, pp.&nbsp;26–27.</ref> लागू करना आसान है, लेकिन बड़ी संख्या में ε-मूव्स वाले ऑटोमेटा के लिए अव्यावहारिक है, जैसा कि आमतौर पर [[प्राकृतिक भाषा प्रसंस्करण]] अनुप्रयोग में होता है।{{r|vannoord}}
+#संपूर्ण ऑटोमेटन के ε-क्लोजर की गणना प्रीप्रोसेसिंग चरण के रूप में करें, जो ε-चालों के बिना समतुल्य एनएफए का उत्पादन करता है, फिर नियमित पावरसेट निर्माण प्रयुक्त  करें। होपक्रॉफ्ट और उलमैन द्वारा चर्चा किए गए इस संस्करण को प्रयुक्त  करना आसान है,<ref>{{harvtxt|Hopcroft|Ullman|1979}}, pp.&nbsp;26–27.</ref> किंतु बड़ी संख्या में ε-चाल वाले ऑटोमेटा के लिए अव्यावहारिक है, जैसा कि समान्यत: प्राकृतिक लैंग्वेज प्रसंस्करण अनुप्रयोग में होता है।{{r|vannoord}}
-# पावरसेट गणना के दौरान, ε-क्लोजर की गणना करें <math>\{q' ~|~ q \to^{*}_\varepsilon q' \}</math> प्रत्येक राज्य का {{mvar|q}} जिसे एल्गोरिथम द्वारा माना जाता है (और परिणाम को कैश करें)।
+#पावरसेट गणना के समय , प्रत्येक स्थिति {{mvar|q}} के ε-क्लोजर <math>\{q' ~|~ q \to^{*}_\varepsilon q' \}</math> की गणना करें जिसे एल्गोरिदम द्वारा माना जाता है (और परिणाम को कैश करें)।
-# पावरसेट गणना के दौरान, ε-क्लोजर की गणना करें <math>\{q' ~|~ \exists q \in Q', q \to^{*}_\varepsilon q' \}</math> राज्यों के प्रत्येक उपसमूह का {{mvar|Q'}} जिसे एल्गोरिथम द्वारा माना जाता है, और इसके तत्वों को इसमें जोड़ा जाता है {{mvar|Q'}}.
+#पावरसेट गणना के समय , अवस्थाओ {{mvar|Q'}} के प्रत्येक उपसमूह के ε-क्लोजर <math>\{q' ~|~ \exists q \in Q', q \to^{*}_\varepsilon q' \}</math> की गणना करें जिसे एल्गोरिदम द्वारा माना जाता है, और इसके तत्वों को {{mvar|Q'}} में जोड़ें।
 ===एकाधिक प्रारंभिक अवस्थाएँ===
@@ Line 25: / Line 25: @@
 ==उदाहरण==
-नीचे दिए गए एनएफए में चार राज्य हैं; अवस्था 1 प्रारंभिक है, और अवस्था 3 और 4 स्वीकार कर रहे हैं। इसकी वर्णमाला में दो प्रतीक 0 और 1 शामिल हैं, और इसमें ε-चालें हैं।
+नीचे दिए गए एनएफए में चार अवस्था हैं; अवस्था 1 प्रारंभिक है, और अवस्था 3 और 4 स्वीकार कर रहे हैं। इसकी वर्णमाला में दो प्रतीक 0 और 1 सम्मिलित हैं, और इसमें ε-चालें हैं।
-  [[File:NFA-powerset-construction-example.svg|frameकम|केंद्र|सीधा=1.5]]इस एनएफए से निर्मित डीएफए की प्रारंभिक स्थिति उन सभी एनएफए राज्यों का सेट है जो ε-चालों द्वारा राज्य 1 से पहुंच योग्य हैं; अर्थात्, यह समुच्चय {1,2,3} है।
+  [[File:NFA-powerset-construction-example.svg|frameकम|केंद्र|सीधा=1.5]]
-इनपुट प्रतीक 0 द्वारा {1,2,3} से संक्रमण को या तो राज्य 1 से राज्य 2 तक तीर का अनुसरण करना चाहिए, या राज्य 3 से राज्य 4 तक तीर का पालन करना चाहिए। इसके अतिरिक्त, न तो राज्य 2 और न ही राज्य 4 में आउटगोइंग ε-चालें हैं। इसलिए, {{mvar|T}}({1,2,3},0) = {2,4}, और इसी तर्क से एनएफए से निर्मित पूर्ण डीएफए नीचे दिखाया गया है।
+इस एनएफए से निर्मित डीएफए की प्रारंभिक स्थिति उन सभी एनएफए अवस्थाओ का सेट है जो ε-चालों द्वारा अवस्था 1 से पहुंच योग्य हैं; अर्थात्, यह समुच्चय {1,2,3} है। इनपुट प्रतीक 0 द्वारा {1,2,3} से संक्रमण को या तो अवस्था 1 से अवस्था 2 तक तीर का अनुसरण करना चाहिए, या अवस्था 3 से अवस्था 4 तक तीर का पालन करना चाहिए। इसके अतिरिक्त, इसे न तो अवस्था 2 और न ही अवस्था 4 में आउटगोइंग ε-चालें हैं। इसलिए, {{mvar|T}}({1,2,3},0) = {2,4}, और इसी तर्क से एनएफए से निर्मित पूर्ण डीएफए नीचे दिखाया गया है।
-[[File:DFA-powerset-construction-example.svg|frameकम|केंद्र|सीधा=1.5]]जैसा कि इस उदाहरण में देखा जा सकता है, डीएफए की आरंभिक स्थिति से पांच राज्यों तक पहुंचा जा सकता है; एनएफए राज्यों के सेट के पावरसेट में शेष 11 सेट पहुंच योग्य नहीं हैं।
+[[File:DFA-powerset-construction-example.svg|frameकम|केंद्र|सीधा=1.5]]
+जैसा कि इस उदाहरण में देखा जा सकता है, डीएफए की आरंभिक स्थिति से पांच अवस्थाओ तक पहुंचा जा सकता है; एनएफए अवस्थाओ के सेट के पावरसेट में शेष 11 सेट पहुंच योग्य नहीं हैं।
-==जटिलता==
+==कॉम्प्लेक्सिटी ==
-{{main article|State complexity}}
+{{main article|स्टेट कॉम्प्लेक्सिटी }}
-[[File:NFA_and_blown-up_equivalent_DFA_01.svg|thumb|upright=1.8|5 राज्यों वाला एनएफए (बाएं) जिसके डीएफए (दाएं) के लिए 16 राज्यों की आवश्यकता है।<ref name="schneider"/>]]क्योंकि DFA राज्यों में NFA राज्यों के सेट शामिल होते हैं, a {{mvar|n}}-स्टेट एनएफए को अधिक से अधिक डीएफए में परिवर्तित किया जा सकता है {{math|2<sup>''n''</sup>}} बताता है.<ref name="sipser"/>हरएक के लिए {{mvar|n}}, वहां है {{mvar|n}}-एनएफए को ऐसे बताएं कि राज्यों का प्रत्येक उपसमूह प्रारंभिक उपसमूह से पहुंच योग्य हो, ताकि परिवर्तित डीएफए बिल्कुल सही हो {{math|2<sup>''n''</sup>}} बताता है, Θ({{math|2<sup>''n''</sup>}}) [[सबसे खराब स्थिति जटिलता]]|सबसे खराब स्थिति समय जटिलता।<ref>{{cite journal
+[[File:NFA_and_blown-up_equivalent_DFA_01.svg|thumb|upright=1.8|5 अवस्थाओ वाला एनएफए (बाएं) जिसके डीएफए (दाएं) के लिए 16 अवस्थाओ की आवश्यकता है।<ref name="schneider" />]]क्योंकि DFA अवस्थाओ में NFA अवस्थाओ का समूह सम्मिलित होता है, एक {{mvar|n}}-अवस्था NFA को अधिकतम {{math|2<sup>''n''</sup>}} अवस्थाओ वाले DFA में परिवर्तित किया जा सकता है।<ref name="sipser" /> प्रत्येक {{mvar|n}} के लिए, {{mvar|n}}-स्टेट एनएफए उपस्थित हैं, जैसे कि अवस्थाओ का प्रत्येक उपसमूह प्रारंभिक उपसमुच्चय से पहुंच योग्य है, ताकि परिवर्तित डीएफए में बिल्कुल {{math|2<sup>''n''</sup>}} अवस्था हों, जो Θ {{math|2<sup>''n''</sup>}} सबसे व्यर्थ स्थिति समय सम्मिश्रता देता है।<ref>{{cite journal
 | last       = Lupanov
 | first      = Oleg B.
@@ Line 50: / Line 53: @@
   | volume = C-20
   | year = 1971| s2cid = 206618275
-  }}.</ref> लगभग इतने राज्यों की आवश्यकता वाला एक सरल उदाहरण वर्णमाला {0,1} पर स्ट्रिंग की भाषा है जिसमें कम से कम हैं {{mvar|n}} अक्षर, द {{mvar|n}}जिनमें से अंतिम से वां 1 है। इसे a द्वारा दर्शाया जा सकता है {{math|(''n'' + 1)}}-एनएफए बताएं, लेकिन इसकी आवश्यकता है {{math|2<sup>''n''</sup>}} डीएफए बताता है, प्रत्येक के लिए एक {{mvar|n}}-इनपुट का वर्ण प्रत्यय; सी एफ के लिए चित्र {{math|''n''<nowiki>=</nowiki>4}}.<ref name="schneider"/>
+  }}.</ref> लगभग इतने अवस्थाओ की आवश्यकता वाला एक सरल उदाहरण वर्णमाला {0,1} पर स्ट्रिंग की लैंग्वेज है जिसमें कम से कम {{mvar|n}} वर्ण हैं, जिनमें से अंतिम से {{mvar|n}}वाँ 1 है। इसे {{math|(''n'' + 1)}} द्वारा दर्शाया जा सकता है -एनएफए बताएं, किंतु इसके लिए {{math|2<sup>''n''</sup>}} की आवश्यकता है डीएफए {{math|''n''<nowiki>=</nowiki>4}} के लिए इनपुट सीएफ चित्र के प्रत्येक {{mvar|n}}-वर्ण प्रत्यय के लिए एक बताता है।
 ==अनुप्रयोग==
-डीएफए न्यूनीकरण#ब्रज़ोज़ोव्स्की का एल्गोरिदम|डीएफए न्यूनतमकरण के लिए ब्रज़ोज़ोव्स्की का एल्गोरिदम पावरसेट निर्माण का दो बार उपयोग करता है। यह अपने सभी तीरों को उलट कर और प्रारंभिक और स्वीकार करने वाले राज्यों की भूमिकाओं का आदान-प्रदान करके, रिवर्स भाषा के लिए इनपुट डीएफए को एनएफए में परिवर्तित करता है, पावरसेट निर्माण का उपयोग करके एनएफए को वापस डीएफए में परिवर्तित करता है, और फिर इसकी प्रक्रिया को दोहराता है। कुछ अन्य ज्ञात डीएफए न्यूनीकरण एल्गोरिदम के विपरीत, इसकी सबसे खराब स्थिति की जटिलता घातीय है, लेकिन कई उदाहरणों में यह अपनी सबसे खराब स्थिति की जटिलता की तुलना में अधिक तेजी से प्रदर्शन करती है।<ref>{{cite conference
+डीएफए न्यूनीकरण के लिए ब्रज़ोज़ोस्की का एल्गोरिदम पावरसेट निर्माण का दो बार उपयोग करता है। यह अपने सभी तीरों को विपरीत कर और प्रारंभिक और स्वीकार करने वाले अवस्थाओ की भूमिकाओं का आदान-प्रदान करके, रिवर्स लैंग्वेज के लिए इनपुट डीएफए को एनएफए में परिवर्तित करता है, पावरसेट निर्माण का उपयोग करके एनएफए को वापस डीएफए में परिवर्तित करता है, और फिर इसकी प्रक्रिया को दोहराता है। कुछ अन्य ज्ञात डीएफए न्यूनीकरण एल्गोरिदम के विपरीत, इसकी सबसे व्यर्थ स्थिति की सम्मिश्रता घातीय है, किंतु कई उदाहरणों में यह अपनी सबसे व्यर्थ स्थिति की सम्मिश्रता की तुलना में अधिक तेज़ी से प्रदर्शन करती है।<ref>{{cite conference
   | last = Brzozowski | first = J. A.
   | authorlink=Janusz Brzozowski (computer scientist)
@@ Line 63: / Line 64: @@
   | title = Proc. Sympos. Math. Theory of Automata (New York, 1962)
   | year = 1963}}</ref>
-सफरा का निर्माण, जो एक गैर-नियतात्मक बुची ऑटोमेटन को परिवर्तित करता है {{mvar|n}} एक नियतात्मक [[मुलर ऑटोमेटन]] में या 2 के साथ एक नियतात्मक ω-ऑटोमेटन में बताता है<sup>हे({{mvar|n}} लकड़ी का लट्ठा {{mvar|n}})</sup> बताता है, पावरसेट निर्माण को अपनी मशीनरी के हिस्से के रूप में उपयोग करता है।<ref>{{cite conference
+सफरा का निर्माण, जो {{mvar|n}} अवस्थाओ के साथ एक गैर-नियतात्मक बुची ऑटोमेटन को एक नियतात्मक मुलर ऑटोमेटन में या  2<sup>O(n log n)</sup> अवस्थाओ के साथ एक नियतात्मक राबिन ऑटोमेटन में परिवर्तित करता है, अपनी मशीनरी के भाग के रूप में पावरसेट निर्माण का उपयोग करता है।<ref>{{cite conference
   | last = Safra | first = S. | authorlink = Shmuel Safra
   | contribution = On the complexity of ω-automata

Anonymous

Search

पॉवरसेट निर्माण: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:37, 2 August 2023

Contents

अंतर्ज्ञान

निर्माण

एनएफए ε-चालों के साथ

एकाधिक प्रारंभिक अवस्थाएँ

उदाहरण

कॉम्प्लेक्सिटी

अनुप्रयोग

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

पॉवरसेट निर्माण: Difference between revisions

Revision as of 10:37, 2 August 2023

अंतर्ज्ञान

निर्माण

एनएफए ε-चालों के साथ

एकाधिक प्रारंभिक अवस्थाएँ

उदाहरण

कॉम्प्लेक्सिटी

अनुप्रयोग

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Hidden categories