लीनियर बाउंडेड ऑटोमेटन
कंप्यूटर विज्ञान में, लीनियर बाउंडेड ऑटोमेटन (बहुवचन लीनियर बाउंडेड ऑटोमेटा, संक्षिप्त एलबीए) ट्यूरिंग मशीन का प्रतिबंधित रूप है।
ऑपरेशन
लीनियर बाउंडेड ऑटोमेटन गैर-नियतात्मक ट्यूरिंग मशीन है जो निम्नलिखित तीन शर्तों को पूरा करती है:
- इसके इनपुट वर्णमाला में दो विशेष प्रतीक शामिल हैं, जो बाएँ और दाएँ एंडमार्कर के रूप में कार्य करते हैं।
- इसके ट्रांज़िशन एंडमार्कर पर अन्य प्रतीकों को प्रिंट नहीं कर सकते हैं।
- इसके संक्रमण न तो बाएं एंडमार्कर के बाईं ओर जा सकते हैं और न ही दाएं एंडमार्कर के दाईं ओर।[1]: 225
दूसरे शब्दों में: गणना करने के लिए संभावित रूप से अनंत टेप होने के बजाय, गणना इनपुट वाले टेप के हिस्से और एंडमार्कर वाले दो टेप वर्गों तक ही सीमित है।
वैकल्पिक, कम प्रतिबंधात्मक परिभाषा इस प्रकार है:
- ट्यूरिंग मशीन की तरह, एलबीए में कोशिकाओं से बना टेप होता है जिसमें सीमित सेट वर्णमाला (कंप्यूटर विज्ञान) के प्रतीक हो सकते हैं, हेड जो समय में टेप पर सेल से पढ़ या लिख सकता है और स्थानांतरित किया जा सकता है, और राज्यों की सीमित संख्या।
- एलबीए ट्यूरिंग मशीन से इस मायने में भिन्न होता है कि शुरुआत में टेप को असीमित लंबाई वाला माना जाता है, लेकिन टेप का केवल सीमित सन्निहित भाग, जिसकी लंबाई प्रारंभिक इनपुट की लंबाई का रैखिक कार्य है, को रीड/राइट हेड द्वारा ्सेस किया जा सकता है; इसलिए इसका नाम लीनियर बाउंडेड ऑटोमेटन पड़ा।[1]: 225
यह सीमा एलबीए को ट्यूरिंग मशीन की तुलना में वास्तविक दुनिया के कंप्यूटर का कुछ हद तक अधिक सटीक मॉडल बनाती है, जिसकी परिभाषा असीमित टेप मानती है।
मजबूत और कमजोर परिभाषा संबंधित ऑटोमेटन वर्गों की समान कम्प्यूटेशनल क्षमताओं को जन्म देती है,[1]: 225 उसी तर्क द्वारा जिसका उपयोग रैखिक गति प्रमेय को सिद्ध करने के लिए किया जाता है।
एलबीए और संदर्भ-संवेदनशील भाषाएँ
रैखिक बाउंडेड ऑटोमेटा संदर्भ-संवेदनशील भाषाओं के वर्ग के लिए स्वीकर्ता (परिमित-राज्य मशीन) हैं।[1]: 225–226 ऐसी भाषाओं के लिए Formal_grammar पर लगाया गया मात्र प्रतिबंध यह है कि कोई भी उत्पादन किसी स्ट्रिंग को छोटी स्ट्रिंग में मैप नहीं करता है। इस प्रकार संदर्भ-संवेदनशील भाषा में किसी स्ट्रिंग की किसी भी व्युत्पत्ति में स्ट्रिंग से अधिक लंबा कोई भावनात्मक रूप नहीं हो सकता है। चूंकि रैखिक-बद्ध ऑटोमेटा और ऐसे व्याकरणों के बीच -से- पत्राचार होता है, इसलिए ऑटोमेटन द्वारा स्ट्रिंग को पहचानने के लिए मूल स्ट्रिंग द्वारा कब्जा किए गए टेप से अधिक टेप आवश्यक नहीं है।
इतिहास
1960 में, जॉन माइहिल ने ऑटोमेटन मॉडल पेश किया जिसे आज नियतात्मक रैखिक बाउंडेड ऑटोमेटन के रूप में जाना जाता है।[2] 1963 में, पीटर लैंडवेबर ने साबित किया कि नियतात्मक एलबीए द्वारा स्वीकृत भाषाएँ संदर्भ-संवेदनशील हैं।[3] 1964 में, एस.वाई. कुरोदा ने (नॉनडेटर्मिनिस्टिक) लीनियर बाउंडेड ऑटोमेटा का अधिक सामान्य मॉडल पेश किया, और यह दिखाने के लिए लैंडवेबर के प्रमाण को अनुकूलित किया कि नॉनडेटरमिनिस्टिक लीनियर बाउंडेड ऑटोमेटा द्वारा स्वीकार की जाने वाली भाषाएं वास्तव में संदर्भ-संवेदनशील भाषाएं हैं।[4][5]
एलबीए समस्याएं
अपने मौलिक पेपर में, कुरोदा ने दो शोध चुनौतियां भी बताईं, जो बाद में एलबीए समस्याओं के रूप में प्रसिद्ध हुईं: पहली एलबीए समस्या यह है कि क्या एलबीए द्वारा स्वीकृत भाषाओं का वर्ग नियतात्मक एलबीए द्वारा स्वीकृत भाषाओं के वर्ग के बराबर है। इस समस्या को कम्प्यूटेशनल जटिलता सिद्धांत की भाषा में संक्षेप में इस प्रकार व्यक्त किया जा सकता है:
- पहली एलबीए समस्या: क्या एनएसपीएसीई(ओ(एन)) = डीएसपीएसीई(ओ(एन)) है?
एलबीए की दूसरी समस्या यह है कि क्या एलबीए द्वारा स्वीकृत भाषाओं का वर्ग पूरक के अंतर्गत बंद है।
- दूसरी एलबीए समस्या: क्या एनएसपीएसीई(ओ(एन)) = सह-एनएसपीएसीई(ओ(एन)) है?
जैसा कि कुरोदा ने पहले ही देखा है, दूसरी एलबीए समस्या का नकारात्मक उत्तर पहली समस्या का नकारात्मक उत्तर होगा। लेकिन दूसरी एलबीए समस्या का सकारात्मक उत्तर है, जो कि समस्या उठाए जाने के 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
