पॉवरसेट निर्माण
गणना और ऑटोमेटा सिद्धांत के सिद्धांत में, पॉवरसेट निर्माण या सबसेट निर्माण एक गैर-नियतात्मक फिनिट ऑटोमेटन (एनएफए) को एक नियतात्मक फिनिट ऑटोमेटन (डीएफए) में परिवर्तित करने के लिए एक मानक विधि है जो समान औपचारिक लैंग्वेज को पहचानता है। यह सैद्धांतिक रूप से महत्वपूर्ण है क्योंकि यह स्थापित करता है कि एनएफए, अपने अतिरिक्त लचीलेपन के अतिरिक्त किसी भी लैंग्वेज को पहचानने में असमर्थ हैं जिसे कुछ डीएफए द्वारा मान्यता नहीं दी जा सकती है। निर्माण में आसान एनएफए को अधिक कुशलतापूर्वक निष्पादन योग्य डीएफए में परिवर्तित करना व्यवहार में भी महत्वपूर्ण है। चूँकि यदि एनएफए में n अवस्था हैं, तो परिणामी डीएफए में 2n अवस्था तक हो सकते हैं, जो कि एक तेजी से बड़ी संख्या है, जो कभी-कभी बड़े एनएफए के लिए निर्माण को अव्यवहारिक बना देता है।
निर्माण, जिसे कभी-कभी अन्य प्रकार के ऑटोमेटा के समान निर्माणों से अलग करने के लिए राबिन-स्कॉट पॉवरसेट निर्माण (या सबसेट निर्माण) कहा जाता है, पहली बार 1959 में माइकल ओ. राबिन और डाना स्कॉट द्वारा प्रकाशित किया गया था।[1]
इनट्यूशन
किसी दिए गए इनपुट स्ट्रिंग पर डीएफए के संचालन को अनुकरण करने के लिए, किसी को किसी भी समय एक ही स्थिति पर दृष्टि रखने की आवश्यकता होती है: वह स्थिति जहां ऑटोमेटन इनपुट के उपसर्ग को देखने के बाद पहुंचेगा। इसके विपरीत, एनएफए का अनुकरण करने के लिए, किसी को अवस्थाओ के एक सेट पर दृष्टि रखने की आवश्यकता होती है: ऑटोमेटन द्वारा बनाए गए गैर-नियतात्मक विकल्पों के अनुसार, सभी अवस्था जहां ऑटोमेटन इनपुट के समान उपसर्ग को देखने के बाद पहुंच सकता है। यदि, इनपुट के एक निश्चित उपसर्ग के बाद, अवस्थाओ के एक सेट S तक पहुंचा जा सकता है, तो अगले इनपुट प्रतीक x के बाद पहुंच योग्य अवस्थाओ का सेट S और x का एक नियतात्मक कार्य है। इसलिए, पहुंच योग्य एनएफए अवस्थाओ के सेट एनएफए सिमुलेशन में वही भूमिका निभाते हैं जैसे एकल डीएफए अवस्था डीएफए सिमुलेशन में निभाते हैं, और वास्तव में इस सिमुलेशन में दिखाई देने वाले एनएफए अवस्थाओ के सेट को डीएफए के अवस्थाओ के रूप में फिर से व्याख्या किया जा सकता है।[2]
निर्माण
पावरसेट निर्माण सबसे सीधे एनएफए पर प्रयुक्त होता है जो इनपुट प्रतीकों (या: "ε-मूव्स") का उपभोग किए बिना अवस्था परिवर्तनों की अनुमति नहीं देता है। ऐसे ऑटोमेटन को 5-टुपल ((Q, Σ, T, q0, F) के रूप में परिभाषित किया जा सकता है, जिसमें Q अवस्थाओ का सेट है, Σ इनपुट प्रतीकों का सेट है, T संक्रमण फ़ंक्शन है (एक अवस्था का मानचित्रण और अवस्थाओ के एक सेट के लिए एक इनपुट प्रतीक), q0 प्रारंभिक स्थिति है, और F स्वीकार करने वाले अवस्थाओ का सेट है। संबंधित डीएफए में Q के उपसमुच्चय के अनुरूप स्थितियाँ हैं। डीएफए की प्रारंभिक अवस्था {q0}है, प्रारंभिक अवस्थाओं का (एक-कंपोनेंट) सेट डीएफए का संक्रमण फ़ंक्शन एक अवस्था S (Q के उपसमुच्चय का प्रतिनिधित्व करता है) और एक इनपुट प्रतीक x को सेट T(S,x) = ∪{T(q,x) | q ∈ S} पर मैप करता है।, सभी अवस्थाओ का सेट जो एस में एक अवस्था से x-संक्रमण द्वारा पहुंचा जा सकता है। डीएफए का एक अवस्था S एक स्वीकार्य अवस्था है यदि और केवल यदि S का कम से कम एक सदस्य एनएफए की एक स्वीकार्य स्थिति है।[3][4]
पॉवरसेट निर्माण के सबसे सरल संस्करण में, डीएफए के सभी अवस्था का सेट Q का पॉवरसेट है, जो की Q के सभी संभावित उपसमूहों का सेट चूँकि परिणामी डीएफए के कई अवस्था व्यर्थ हो सकते हैं क्योंकि वे पहुंच से बाहर हो सकते हैं आरंभिक अवस्था निर्माण का एक वैकल्पिक संस्करण केवल उन अवस्था का निर्माण करता है जो वास्तव में पहुंच योग्य हैं।[5]
एनएफए ε-चालों के साथ
ε-मूव्स (जिसे ε-एनएफए भी कहा जाता है) वाले एनएफए के लिए, अवस्थाओ के ε- प्रतिवर्ती सकर्मक समापन की गणना करके इनसे निपटने के लिए निर्माण को संशोधित किया जाना चाहिए: केवल ε-मूव्स का उपयोग करके किसी दिए गए अवस्था से पहुंचने योग्य सभी अवस्थाओ का सेट वैन नोर्ड पावरसेट निर्माण में इस क्लोजर गणना को सम्मिलित करने के तीन संभावित विधियों को पहचानते हैं:[6]
- संपूर्ण ऑटोमेटन के ε-क्लोजर की गणना प्रीप्रोसेसिंग चरण के रूप में करें, जो ε-चालों के बिना समतुल्य एनएफए का उत्पादन करता है, फिर नियमित पावरसेट निर्माण प्रयुक्त करें। होपक्रॉफ्ट और उलमैन द्वारा चर्चा किए गए इस संस्करण को प्रयुक्त करना आसान है,[7] किंतु बड़ी संख्या में ε-चाल वाले ऑटोमेटा के लिए अव्यावहारिक है, जैसा कि समान्यत: प्राकृतिक लैंग्वेज प्रसंस्करण अनुप्रयोग में होता है।[6]
- पावरसेट गणना के समय , प्रत्येक स्थिति q के ε-क्लोजर की गणना करें जिसे एल्गोरिदम द्वारा माना जाता है (और परिणाम को कैश करें)।
- पावरसेट गणना के समय , अवस्थाओ Q' के प्रत्येक उपसमूह के ε-क्लोजर की गणना करें जिसे एल्गोरिदम द्वारा माना जाता है, और इसके कंपोनेंटों को Q' में जोड़ें।
एकाधिक प्रारंभिक अवस्थाएँ
यदि एनएफए को कई प्रारंभिक स्थितियों की अनुमति देने के लिए परिभाषित किया गया है,[8] संबंधित डीएफए की प्रारंभिक अवस्था एनएफए की सभी प्रारंभिक अवस्थाओं का समुच्चय है, या (यदि एनएफए में ε-चालें भी हैं) ε-चालों द्वारा प्रारंभिक अवस्थाओं तक पहुंचने योग्य सभी अवस्थाओं का समुच्चय है।
उदाहरण
नीचे दिए गए एनएफए में चार अवस्था हैं; अवस्था 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 सेट पहुंच योग्य नहीं हैं।
कॉम्प्लेक्सिटी
क्योंकि डीएफए अवस्थाओ में एनएफए अवस्थाओ का समूह सम्मिलित होता है, एक n-अवस्था एनएफए को अधिकतम 2n अवस्थाओ वाले डीएफए में परिवर्तित किया जा सकता है।[2] प्रत्येक n के लिए, n-स्टेट एनएफए उपस्थित हैं, जैसे कि अवस्थाओ का प्रत्येक उपसमूह प्रारंभिक उपसमुच्चय से पहुंच योग्य है, ताकि परिवर्तित डीएफए में बिल्कुल 2n अवस्था हों, जो Θ 2n सबसे व्यर्थ स्थिति समय सम्मिश्रता देता है।[9][10] लगभग इतने अवस्थाओ की आवश्यकता वाला एक सरल उदाहरण वर्णमाला {0,1} पर स्ट्रिंग की लैंग्वेज है जिसमें कम से कम n वर्ण हैं, जिनमें से अंतिम से nवाँ 1 है। इसे (n + 1) द्वारा दर्शाया जा सकता है -एनएफए बताएं, किंतु इसके लिए 2n की आवश्यकता है डीएफए n=4 के लिए इनपुट सीएफ चित्र के प्रत्येक n-वर्ण प्रत्यय के लिए एक बताता है।
अनुप्रयोग
डीएफए न्यूनीकरण के लिए ब्रज़ोज़ोस्की का एल्गोरिदम पावरसेट निर्माण का दो बार उपयोग करता है। यह अपने सभी तीरों को विपरीत कर और प्रारंभिक और स्वीकार करने वाले अवस्थाओ की भूमिकाओं का आदान-प्रदान करके, रिवर्स लैंग्वेज के लिए इनपुट डीएफए को एनएफए में परिवर्तित करता है, पावरसेट निर्माण का उपयोग करके एनएफए को वापस डीएफए में परिवर्तित करता है, और फिर इसकी प्रक्रिया को दोहराता है। कुछ अन्य ज्ञात डीएफए न्यूनीकरण एल्गोरिदम के विपरीत, इसकी सबसे व्यर्थ स्थिति की सम्मिश्रता घातीय है, किंतु कई उदाहरणों में यह अपनी सबसे व्यर्थ स्थिति की सम्मिश्रता की तुलना में अधिक तेज़ी से प्रदर्शन करती है।
सफरा का निर्माण, जो एन स्तर के साथ एक गैर-नियतात्मक बुची ऑटोमेटन को एक नियतात्मक मुलर ऑटोमेटन में या 2O(n log n) स्तर के साथ एक नियतात्मक राबिन ऑटोमेटन में परिवर्तित करता है, अपनी मशीनरी के भाग के रूप में पावरसेट निर्माण का उपयोग करता है
संदर्भ
- ↑ 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 Sipser, Michael (1997). "Theorem 1.19". संगणना के सिद्धांत का परिचय. pp. 55–56. ISBN 0-534-94728-X.
- ↑ 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.
- ↑ 5.0 5.1 Schneider, Klaus (2004). Verification of reactive systems: formal methods and algorithms. Springer. pp. 210–212. ISBN 978-3-540-00296-3.
- ↑ 6.0 6.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..
अग्रिम पठन
- Anderson, James Andrew (2006). Automata theory with modern applications. Cambridge University Press. pp. 43–49. ISBN 978-0-521-84887-9.
