लीनियर बाउंडेड ऑटोमेटन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 23: | Line 23: | ||
1960 में, [[जॉन माइहिल]] ने ऑटोमेटन मॉडल प्रस्तुत किया जिसे आज डीटरमिनिस्टिक लीनियर बाउंडेड ऑटोमेटन के रूप में जाना जाता है।<ref>{{cite report | author=John Myhill | authorlink=John Myhill | title=लीनियर बाउंडेड ऑटोमेटा| institution=Wright Patterson AFB, Wright Air Development Division, Ohio | type=WADD Technical Note | number=60–165 | date=June 1960 }}</ref>1963 में, [[पीटर लैंडवेबर]] ने सिद्ध किया कि डीटरमिनिस्टिक एलबीए द्वारा स्वीकृत लैंग्वेज कॉन्टेक्स्ट-सेंसिटिव हैं।<ref>{{cite journal | author=P.S. Landweber | title=प्रकार 1 के वाक्यांश संरचना व्याकरण पर तीन प्रमेय| journal=[[Information and Control]] | volume=6 | number=2 | pages=131–136 | year=1963 | doi=10.1016/s0019-9958(63)90169-4| doi-access=free }}</ref>1964 में, एस.वाई. कुरोदा ने (नॉनडेटर्मिनिस्टिक) लीनियर बाउंडेड ऑटोमेटा का अधिक सामान्य मॉडल प्रस्तुत किया, और यह दिखाने के लिए लैंडवेबर के प्रमाण को अनुकूलित किया कि नॉनडेटरमिनिस्टिक लीनियर बाउंडेड ऑटोमेटा द्वारा स्वीकार की जाने वाली लैंग्वेज वास्तव में कॉन्टेक्स्ट-सेंसिटिव लैंग्वेज हैं।<ref>{{cite journal | author=Sige-Yuki Kuroda | authorlink=Sige-Yuki Kuroda |title=भाषाओं की कक्षाएं और रैखिक-बद्ध ऑटोमेटा| journal=Information and Control | volume=7 | number=2 | pages=207–223 | date=Jun 1964 | doi=10.1016/s0019-9958(64)90120-2| doi-access=free }}</ref><ref>{{cite book|author=Willem J. M. Levelt| authorlink=Willem Levelt| title=औपचारिक भाषाओं और ऑटोमेटा के सिद्धांत का एक परिचय|url=https://books.google.com/books?id=tFvtwGYNe7kC&pg=PA126|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2|pages=126–127}}</ref> | 1960 में, [[जॉन माइहिल]] ने ऑटोमेटन मॉडल प्रस्तुत किया जिसे आज डीटरमिनिस्टिक लीनियर बाउंडेड ऑटोमेटन के रूप में जाना जाता है।<ref>{{cite report | author=John Myhill | authorlink=John Myhill | title=लीनियर बाउंडेड ऑटोमेटा| institution=Wright Patterson AFB, Wright Air Development Division, Ohio | type=WADD Technical Note | number=60–165 | date=June 1960 }}</ref>1963 में, [[पीटर लैंडवेबर]] ने सिद्ध किया कि डीटरमिनिस्टिक एलबीए द्वारा स्वीकृत लैंग्वेज कॉन्टेक्स्ट-सेंसिटिव हैं।<ref>{{cite journal | author=P.S. Landweber | title=प्रकार 1 के वाक्यांश संरचना व्याकरण पर तीन प्रमेय| journal=[[Information and Control]] | volume=6 | number=2 | pages=131–136 | year=1963 | doi=10.1016/s0019-9958(63)90169-4| doi-access=free }}</ref>1964 में, एस.वाई. कुरोदा ने (नॉनडेटर्मिनिस्टिक) लीनियर बाउंडेड ऑटोमेटा का अधिक सामान्य मॉडल प्रस्तुत किया, और यह दिखाने के लिए लैंडवेबर के प्रमाण को अनुकूलित किया कि नॉनडेटरमिनिस्टिक लीनियर बाउंडेड ऑटोमेटा द्वारा स्वीकार की जाने वाली लैंग्वेज वास्तव में कॉन्टेक्स्ट-सेंसिटिव लैंग्वेज हैं।<ref>{{cite journal | author=Sige-Yuki Kuroda | authorlink=Sige-Yuki Kuroda |title=भाषाओं की कक्षाएं और रैखिक-बद्ध ऑटोमेटा| journal=Information and Control | volume=7 | number=2 | pages=207–223 | date=Jun 1964 | doi=10.1016/s0019-9958(64)90120-2| doi-access=free }}</ref><ref>{{cite book|author=Willem J. M. Levelt| authorlink=Willem Levelt| title=औपचारिक भाषाओं और ऑटोमेटा के सिद्धांत का एक परिचय|url=https://books.google.com/books?id=tFvtwGYNe7kC&pg=PA126|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2|pages=126–127}}</ref> | ||
== एलबीए | == एलबीए प्रॉब्लम्स == | ||
अपने मौलिक पेपर में, कुरोदा ने दो | अपने मौलिक पेपर में, कुरोदा ने दो रिसर्च उद्देश भी बताएं, जो पश्चात में एलबीए समस्याओं के रूप में प्रसिद्ध हुईं: प्रथम एलबीए प्रॉब्लम यह है कि क्या एलबीए द्वारा स्वीकृत लैंग्वेजेस का वर्ग डीटरमिनिस्टिक एलबीए द्वारा स्वीकृत लैंग्वेजेस के वर्ग के समान है। इस प्रॉब्लम को [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कोम्प्लेक्सिटी थ्योरी]] की लैंग्वेज में संक्षेप में इस प्रकार व्यक्त किया जा सकता है: | ||
:प्रथम एलबीए | :प्रथम एलबीए प्रॉब्लम: क्या [[एनएसपीएसीई|NSPACE]](O(n)) = [[डीएसपीएसीई|DSPACE]](O(n)) है? | ||
एलबीए की दूसरी | एलबीए की दूसरी प्रॉब्लम यह है कि क्या एलबीए द्वारा स्वीकृत लैंग्वेजेज का वर्ग पूरक के अंतर्गत क्लोज्ड है। | ||
:दूसरी एलबीए | :दूसरी एलबीए प्रॉब्लम: क्या NSPACE(O(n)) = NSPACE(O(n)) है? | ||
जैसा कि कुरोदा ने पहले ही देखा है, दूसरी एलबीए | जैसा कि कुरोदा ने पहले ही देखा है, दूसरी एलबीए प्रॉब्लम का पॉजिटिव आंसर प्रथम प्रॉब्लम का पॉजिटिव आंसर होगा। किन्तु दूसरी एलबीए प्रॉब्लम का नेगेटिव आंसर है, जो कि प्रॉब्लम उठाए जाने के 20 वर्ष पश्चात सिद्ध हुए इमरमैन-स्ज़ेलेपीसीसेनी प्रमेय द्वारा निहित है।<ref>{{citation | last = Immerman | first = Neil | authorlink = Neil Immerman | doi = 10.1137/0217058 | issue = 5 | journal = [[SIAM Journal on Computing]] | mr = 961049 | pages = 935–938 | title = Nondeterministic space is closed under complementation | url = http://www.cs.umass.edu/~immerman/pub/space.pdf | volume = 17 | year = 1988}}</ref><ref>{{citation | last = Szelepcsényi | first = Róbert | author-link = Róbert Szelepcsényi | journal = [[Acta Informatica]] | pages = 279–284 | title = The method of forcing for nondeterministic automata | volume = 26 | issue = 3 | year = 1988| doi = 10.1007/BF00299636 | s2cid = 10838178 }}</ref> प्रथम एलबीए प्रॉब्लम अभी भी ओपन है। सैविच का प्रमेय प्रारंभिक इनसाइट प्रदान करता है, कि NSPACE(O(''n'')) ⊆ DSPACE(O(''n''<sup>2</sup>)) है।<ref>{{cite book |last1= Arora |first1= Sanjeev |authorlink = Sanjeev Arora|last2= Barak |first2= Boaz |author2link = Boaz Barak|url= http://www.cs.princeton.edu/theory/complexity/ |title= Complexity Theory: A Modern Approach |publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 }}</ref> | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 19:27, 7 September 2023
कंप्यूटर विज्ञान में, लीनियर बाउंडेड ऑटोमेटन (प्लूरल लीनियर बाउंडेड ऑटोमेटा, संक्षिप्त एलबीए) ट्यूरिंग मशीन का प्रतिबंधित रूप है।
ऑपरेशन
लीनियर बाउंडेड ऑटोमेटन नॉन डीटरमिनिस्टिक ट्यूरिंग मशीन है जो निम्नलिखित तीन नियमों को पूर्ण करती है:
- इसके इनपुट अल्फाबेट में दो विशेष प्रतीक सम्मिलित हैं, जो बाएँ और दाएँ एंडमार्कर के रूप में कार्य करते हैं।
- इसके ट्रांज़िशन एंडमार्कर पर अन्य प्रतीकों को प्रिंट नहीं कर सकते हैं।
- इसके ट्रांज़िशन न तो बाएं एंडमार्कर के बाईं ओर जा सकते हैं और न ही दाएं एंडमार्कर के दाईं ओर जा सकते हैं।[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
