लीनियर बाउंडेड ऑटोमेटन
कंप्यूटर विज्ञान में, लीनियर बाउंडेड ऑटोमेटन (प्लूरल लीनियर बाउंडेड ऑटोमेटा, संक्षिप्त एलबीए) ट्यूरिंग मशीन का प्रतिबंधित रूप है।
ऑपरेशन
लीनियर बाउंडेड ऑटोमेटन नॉन डीटरमिनिस्टिक ट्यूरिंग मशीन है जो निम्नलिखित तीन नियमों को पूर्ण करती है:
- इसके इनपुट अल्फाबेट में दो विशेष प्रतीक सम्मिलित हैं, जो बाएँ और दाएँ एंडमार्कर के रूप में कार्य करते हैं।
- इसके ट्रांज़िशन एंडमार्कर पर अन्य प्रतीकों को प्रिंट नहीं कर सकते हैं।
- इसके ट्रांज़िशन न तो बाएं एंडमार्कर के बाईं ओर जा सकते हैं और न ही दाएं एंडमार्कर के दाईं ओर।[1]: 225
दूसरे शब्दों में: गणना करने के लिए संभावित रूप से अनंत टेप होने के अतिरिक्त, गणना इनपुट वाले टेप के भाग और एंडमार्कर वाले दो टेप वर्गों तक ही सीमित है।
वैकल्पिक, कम प्रतिबंधात्मक परिभाषा इस प्रकार है:
- ट्यूरिंग मशीन के जैसे, एलबीए में सेल से बना टेप होता है जिसमें सीमित सेट अल्फाबेट (कंप्यूटर विज्ञान) के प्रतीक हो सकते हैं, हेड जो समय में टेप पर सेल से रीड या राइट लिख सकते है और स्थानांतरित किया जा सकता है, और सीमित संख्या में स्टेट है।
- एलबीए ट्यूरिंग मशीन से इस आशय में भिन्न होता है कि प्रारंभ में टेप को असीमित लंबाई वाला माना जाता है, किन्तु टेप का केवल सीमित सन्निहित भाग, जिसकी लंबाई प्रारंभिक इनपुट की लंबाई का लीनियर फंक्शन है, रीड/राइट हेड द्वारा एक्सेस किया जा सकता है; इसलिए इसका नाम लीनियर बाउंडेड ऑटोमेटन हुआ।[1]: 225
यह सीमा एलबीए को ट्यूरिंग मशीन की तुलना में वास्तविक संसार के कंप्यूटर का कुछ सीमा तक अधिक त्रुटिहीन मॉडल बनाती है, जिसकी परिभाषा असीमित टेप मानती है।
स्ट्रांग और वीकर परिभाषा संबंधित ऑटोमेटन वर्गों की समान कम्प्यूटेशनल क्षमताओं को उत्पन्न करती है,[1]: 225 उसी लॉजिक द्वारा जिसका उपयोग लीनियर स्पीडअप प्रमेय को सिद्ध करने के लिए किया जाता है।
एलबीए और कॉन्टेक्स्ट-सेंसिटिव लैंग्वेजेज
लीनियर बाउंडेड ऑटोमेटा कॉन्टेक्स्ट-सेंसिटिव लैंग्वेजेज के वर्ग के लिए एक्सपटर हैं।[1]: 225–226 ऐसी लैंग्वेजेज के लिए फॉर्मल ग्रामर पर लगाया गया मात्र प्रतिबंध यह है कि कोई भी उत्पादन किसी स्ट्रिंग को छोटी स्ट्रिंग में मैप नहीं करता है। इस प्रकार कॉन्टेक्स्ट-सेंसिटिव लैंग्वेज में किसी स्ट्रिंग की किसी भी व्युत्पत्ति में स्ट्रिंग से अधिक लंबा कोई भावनात्मक रूप नहीं हो सकता है। चूंकि लीनियर-बाउंड ऑटोमेटा और ऐसे ग्रामर के मध्य पत्राचार होता है, इसलिए ऑटोमेटन द्वारा स्ट्रिंग को पहचानने के लिए मूल स्ट्रिंग द्वारा प्रभुत्व किए गए टेप से अधिक टेप आवश्यक नहीं है।
इतिहास
1960 में, जॉन माइहिल ने ऑटोमेटन मॉडल प्रस्तुत किया जिसे आज डीटरमिनिस्टिक लीनियर बाउंडेड ऑटोमेटन के रूप में जाना जाता है।[2] 1963 में, पीटर लैंडवेबर ने सिद्ध किया कि डीटरमिनिस्टिक एलबीए द्वारा स्वीकृत लैंग्वेज कॉन्टेक्स्ट-सेंसिटिव हैं।[3] 1964 में, एस.वाई. कुरोदा ने (नॉनडेटर्मिनिस्टिक) लीनियर बाउंडेड ऑटोमेटा का अधिक सामान्य मॉडल प्रस्तुत किया, और यह दिखाने के लिए लैंडवेबर के प्रमाण को अनुकूलित किया कि नॉनडेटरमिनिस्टिक लीनियर बाउंडेड ऑटोमेटा द्वारा स्वीकार की जाने वाली लैंग्वेज वास्तव में कॉन्टेक्स्ट-सेंसिटिव लैंग्वेज हैं।[4][5]
एलबीए समस्याएं
अपने मौलिक पेपर में, कुरोदा ने दो शोध उद्देश भी बताईं, जो पश्चात में एलबीए समस्याओं के रूप में प्रसिद्ध हुईं: प्रथम एलबीए समस्या यह है कि क्या एलबीए द्वारा स्वीकृत लैंग्वेजेज का वर्ग डीटरमिनिस्टिक एलबीए द्वारा स्वीकृत लैंग्वेजेज के वर्ग के समान है। इस समस्या को कम्प्यूटेशनल कोम्प्लेक्सिटी थ्योरी की लैंग्वेज में संक्षेप में इस प्रकार व्यक्त किया जा सकता है:
एलबीए की दूसरी समस्या यह है कि क्या एलबीए द्वारा स्वीकृत लैंग्वेजेज का वर्ग पूरक के अंतर्गत विवृत है।
- दूसरी एलबीए समस्या: क्या NSPACE(O(n)) = NSPACE(O(n)) है?
जैसा कि कुरोदा ने पहले ही देखा है, दूसरी एलबीए समस्या का ऋणात्मक उत्तर पहली समस्या का ऋणात्मक उत्तर होगा। किन्तु दूसरी एलबीए समस्या का धनात्मक उत्तर है, जो कि समस्या उठाए जाने के 20 वर्ष पश्चात सिद्ध हुए इमरमैन-स्ज़ेलेपीसीसेनी प्रमेय द्वारा निहित है।[6][7] आज तक, पहली एलबीए समस्या अभी भी संवृत हुई है। सैविच का प्रमेय प्रारंभिक अंतर्दृष्टि प्रदान करता है, कि NSPACE(O(n)) ⊆ DSPACE(O(n2)) है।[8]
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 John E. Hopcroft; Jeffrey D. Ullman (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय. Addison-Wesley. ISBN 978-0-201-02988-8.
- ↑ John Myhill (June 1960). लीनियर बाउंडेड ऑटोमेटा (WADD Technical Note). Wright Patterson AFB, Wright Air Development Division, Ohio.
- ↑ P.S. Landweber (1963). "प्रकार 1 के वाक्यांश संरचना व्याकरण पर तीन प्रमेय". Information and Control. 6 (2): 131–136. doi:10.1016/s0019-9958(63)90169-4.
- ↑ Sige-Yuki Kuroda (Jun 1964). "भाषाओं की कक्षाएं और रैखिक-बद्ध ऑटोमेटा". Information and Control. 7 (2): 207–223. doi:10.1016/s0019-9958(64)90120-2.
- ↑ Willem J. M. Levelt (2008). औपचारिक भाषाओं और ऑटोमेटा के सिद्धांत का एक परिचय. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2.
- ↑ Immerman, Neil (1988), "Nondeterministic space is closed under complementation" (PDF), SIAM Journal on Computing, 17 (5): 935–938, doi:10.1137/0217058, MR 0961049
- ↑ Szelepcsényi, Róbert (1988), "The method of forcing for nondeterministic automata", Acta Informatica, 26 (3): 279–284, doi:10.1007/BF00299636, S2CID 10838178
- ↑ Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
बाहरी संबंध
- Linear Bounded Automata by Forbes D. Lewis
- Linear Bounded Automata slides, part of Context-sensitive Languages by Arthur C. Fleck
- Linear-Bounded Automata, part of Theory of Computation syllabus, by David Matuszek
