लीनियर बाउंडेड ऑटोमेटन
कंप्यूटर विज्ञान में, लीनियर बाउंडेड ऑटोमेटन (प्लूरल लीनियर बाउंडेड ऑटोमेटा, संक्षिप्त एलबीए) ट्यूरिंग मशीन का प्रतिबंधित फॉर्म है।
ऑपरेशन
लीनियर बाउंडेड ऑटोमेटन नॉन डीटरमिनिस्टिक ट्यूरिंग मशीन है जो निम्नलिखित तीन नियमों को पूर्ण करती है:
- इसके इनपुट अल्फाबेट में दो विशेष प्रतीक सम्मिलित हैं, जो बाएँ और दाएँ एंडमार्कर के फॉर्म में कार्य करते हैं।
- इसके ट्रांज़िशन एंडमार्कर पर अन्य प्रतीकों को प्रिंट नहीं कर सकते हैं।
- इसके ट्रांज़िशन न तो बाएं एंडमार्कर के बाईं ओर जा सकते हैं और न ही दाएं एंडमार्कर के दाईं ओर जा सकते हैं।[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
