लीनियर बाउंडेड ऑटोमेटन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में, लीनियर बाउंडेड ऑटोमेटन (बहुवचन लीनियर बाउंडेड ऑटोमेटा, संक्षिप्त एलबीए) [[ट्यूरिंग मशीन]] का प्रतिबंधित रूप है।
[[कंप्यूटर विज्ञान]] में, '''लीनियर बाउंडेड ऑटोमेटन''' (प्लूरल लीनियर बाउंडेड ऑटोमेटा, संक्षिप्त एलबीए) [[ट्यूरिंग मशीन]] का प्रतिबंधित रूप है।


== ऑपरेशन ==
== ऑपरेशन ==
लीनियर बाउंडेड ऑटोमेटन [[गैर-नियतात्मक ट्यूरिंग मशीन]] है जो निम्नलिखित तीन शर्तों को पूरा करती है:
लीनियर बाउंडेड ऑटोमेटन [[गैर-नियतात्मक ट्यूरिंग मशीन|नॉन डीटरमिनिस्टिक ट्यूरिंग मशीन]] है जो निम्नलिखित तीन नियमों को पूर्ण करती है:


* इसके इनपुट वर्णमाला में दो विशेष प्रतीक शामिल हैं, जो बाएँ और दाएँ एंडमार्कर के रूप में कार्य करते हैं।
* इसके इनपुट अल्फाबेट में दो विशेष प्रतीक सम्मिलित हैं, जो बाएँ और दाएँ एंडमार्कर के रूप में कार्य करते हैं।
* इसके ट्रांज़िशन एंडमार्कर पर अन्य प्रतीकों को प्रिंट नहीं कर सकते हैं।
* इसके ट्रांज़िशन एंडमार्कर पर अन्य प्रतीकों को प्रिंट नहीं कर सकते हैं।
* इसके संक्रमण न तो बाएं एंडमार्कर के बाईं ओर जा सकते हैं और न ही दाएं एंडमार्कर के दाईं ओर।<ref name="Hopcroft.Ullman.1979">{{cite book| author1=John E. Hopcroft| author2=Jeffrey D. Ullman| author1link=John E. Hopcroft| author2link=Jeffrey D. Ullman| title=ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय| year=1979| publisher=Addison-Wesley| isbn=978-0-201-02988-8| url-access=registration| url=https://archive.org/details/introductiontoau00hopc}}</ref>{{rp|225}}
* इसके ट्रांज़िशन न तो बाएं एंडमार्कर के बाईं ओर जा सकते हैं और न ही दाएं एंडमार्कर के दाईं ओर।<ref name="Hopcroft.Ullman.1979">{{cite book| author1=John E. Hopcroft| author2=Jeffrey D. Ullman| author1link=John E. Hopcroft| author2link=Jeffrey D. Ullman| title=ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय| year=1979| publisher=Addison-Wesley| isbn=978-0-201-02988-8| url-access=registration| url=https://archive.org/details/introductiontoau00hopc}}</ref>{{rp|225}}
दूसरे शब्दों में:
दूसरे शब्दों में: गणना करने के लिए संभावित रूप से अनंत टेप होने के अतिरिक्त, गणना इनपुट वाले टेप के भाग और एंडमार्कर वाले दो टेप वर्गों तक ही सीमित है।
गणना करने के लिए संभावित रूप से अनंत टेप होने के बजाय, गणना इनपुट वाले टेप के हिस्से और एंडमार्कर वाले दो टेप वर्गों तक ही सीमित है।


वैकल्पिक, कम प्रतिबंधात्मक परिभाषा इस प्रकार है:
वैकल्पिक, कम प्रतिबंधात्मक परिभाषा इस प्रकार है:
* ट्यूरिंग मशीन की तरह, एलबीए में कोशिकाओं से बना टेप होता है जिसमें सीमित सेट [[वर्णमाला (कंप्यूटर विज्ञान)]] के प्रतीक हो सकते हैं, हेड जो समय में टेप पर सेल से पढ़ या लिख ​​सकता है और स्थानांतरित किया जा सकता है, और राज्यों की  सीमित संख्या।
* ट्यूरिंग मशीन के जैसे, एलबीए में सेल से बना टेप होता है जिसमें सीमित सेट [[वर्णमाला (कंप्यूटर विज्ञान)|अल्फाबेट (कंप्यूटर विज्ञान)]] के प्रतीक हो सकते हैं, हेड जो समय में टेप पर सेल से रीड या राइट लिख ​​सकते है और स्थानांतरित किया जा सकता है, और सीमित संख्या में स्टेट है।
* एलबीए ट्यूरिंग मशीन से इस मायने में भिन्न होता है कि शुरुआत में टेप को असीमित लंबाई वाला माना जाता है, लेकिन टेप का केवल सीमित सन्निहित भाग, जिसकी लंबाई प्रारंभिक इनपुट की लंबाई का रैखिक कार्य है, को रीड/राइट हेड द्वारा ्सेस किया जा सकता है; इसलिए इसका नाम लीनियर बाउंडेड ऑटोमेटन पड़ा।<ref name="Hopcroft.Ullman.1979"/>{{rp|225}}
* एलबीए ट्यूरिंग मशीन से इस आशय में भिन्न होता है कि प्रारंभ में टेप को असीमित लंबाई वाला माना जाता है, किन्तु टेप का केवल सीमित सन्निहित भाग, जिसकी लंबाई प्रारंभिक इनपुट की लंबाई का लीनियर फंक्शन है, रीड/राइट हेड द्वारा एक्सेस किया जा सकता है; इसलिए इसका नाम लीनियर बाउंडेड ऑटोमेटन हुआ।<ref name="Hopcroft.Ullman.1979"/>{{rp|225}}


यह सीमा एलबीए को ट्यूरिंग मशीन की तुलना में वास्तविक दुनिया के [[कंप्यूटर]] का कुछ हद तक अधिक सटीक मॉडल बनाती है, जिसकी परिभाषा असीमित टेप मानती है।
यह सीमा एलबीए को ट्यूरिंग मशीन की तुलना में वास्तविक संसार के [[कंप्यूटर]] का कुछ सीमा तक अधिक त्रुटिहीन मॉडल बनाती है, जिसकी परिभाषा असीमित टेप मानती है।


मजबूत और कमजोर परिभाषा संबंधित ऑटोमेटन वर्गों की समान कम्प्यूटेशनल क्षमताओं को जन्म देती है,<ref name="Hopcroft.Ullman.1979"/>{{rp|225}} उसी तर्क द्वारा जिसका उपयोग रैखिक गति प्रमेय को सिद्ध करने के लिए किया जाता है।
स्ट्रांग और वीकर परिभाषा संबंधित ऑटोमेटन वर्गों की समान कम्प्यूटेशनल क्षमताओं को उत्पन्न करती है,<ref name="Hopcroft.Ullman.1979"/>{{rp|225}} उसी लॉजिक द्वारा जिसका उपयोग लीनियर स्पीडअप प्रमेय को सिद्ध करने के लिए किया जाता है।


==एलबीए और [[संदर्भ-संवेदनशील भाषा]]एँ==
==एलबीए और [[संदर्भ-संवेदनशील भाषा|कॉन्टेक्स्ट-सेंसिटिव लैंग्वेजेज]]==
रैखिक बाउंडेड ऑटोमेटा संदर्भ-संवेदनशील भाषाओं के वर्ग के लिए [[स्वीकर्ता (परिमित-राज्य मशीन)]] हैं।<ref name="Hopcroft.Ullman.1979"/>{{rp|225-226}} ऐसी भाषाओं के लिए Formal_grammar पर लगाया गया मात्र प्रतिबंध यह है कि कोई भी उत्पादन किसी स्ट्रिंग को छोटी स्ट्रिंग में मैप नहीं करता है। इस प्रकार संदर्भ-संवेदनशील भाषा में किसी स्ट्रिंग की किसी भी व्युत्पत्ति में स्ट्रिंग से अधिक लंबा कोई भावनात्मक रूप नहीं हो सकता है। चूंकि रैखिक-बद्ध ऑटोमेटा और ऐसे व्याकरणों के बीच -से- पत्राचार होता है, इसलिए ऑटोमेटन द्वारा स्ट्रिंग को पहचानने के लिए मूल स्ट्रिंग द्वारा कब्जा किए गए टेप से अधिक टेप आवश्यक नहीं है।
लीनियर बाउंडेड ऑटोमेटा कॉन्टेक्स्ट-सेंसिटिव लैंग्वेजेज के वर्ग के लिए [[स्वीकर्ता (परिमित-राज्य मशीन)|एक्सपटर]] हैं।<ref name="Hopcroft.Ullman.1979"/>{{rp|225-226}} ऐसी लैंग्वेजेज के लिए फॉर्मल ग्रामर पर लगाया गया मात्र प्रतिबंध यह है कि कोई भी उत्पादन किसी स्ट्रिंग को छोटी स्ट्रिंग में मैप नहीं करता है। इस प्रकार कॉन्टेक्स्ट-सेंसिटिव लैंग्वेज में किसी स्ट्रिंग की किसी भी व्युत्पत्ति में स्ट्रिंग से अधिक लंबा कोई भावनात्मक रूप नहीं हो सकता है। चूंकि लीनियर-बाउंड ऑटोमेटा और ऐसे ग्रामर के मध्य पत्राचार होता है, इसलिए ऑटोमेटन द्वारा स्ट्रिंग को पहचानने के लिए मूल स्ट्रिंग द्वारा प्रभुत्व किए गए टेप से अधिक टेप आवश्यक नहीं है।


==इतिहास==
==इतिहास==
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>
जैसा कि कुरोदा ने पहले ही देखा है, दूसरी एलबीए समस्या का ऋणात्मक उत्तर पहली समस्या का ऋणात्मक उत्तर होगा। किन्तु दूसरी एलबीए समस्या का धनात्मक उत्तर है, जो कि समस्या उठाए जाने के 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 11:39, 6 August 2023

कंप्यूटर विज्ञान में, लीनियर बाउंडेड ऑटोमेटन (प्लूरल लीनियर बाउंडेड ऑटोमेटा, संक्षिप्त एलबीए) ट्यूरिंग मशीन का प्रतिबंधित रूप है।

ऑपरेशन

लीनियर बाउंडेड ऑटोमेटन नॉन डीटरमिनिस्टिक ट्यूरिंग मशीन है जो निम्नलिखित तीन नियमों को पूर्ण करती है:

  • इसके इनपुट अल्फाबेट में दो विशेष प्रतीक सम्मिलित हैं, जो बाएँ और दाएँ एंडमार्कर के रूप में कार्य करते हैं।
  • इसके ट्रांज़िशन एंडमार्कर पर अन्य प्रतीकों को प्रिंट नहीं कर सकते हैं।
  • इसके ट्रांज़िशन न तो बाएं एंडमार्कर के बाईं ओर जा सकते हैं और न ही दाएं एंडमार्कर के दाईं ओर।[1]: 225 

दूसरे शब्दों में: गणना करने के लिए संभावित रूप से अनंत टेप होने के अतिरिक्त, गणना इनपुट वाले टेप के भाग और एंडमार्कर वाले दो टेप वर्गों तक ही सीमित है।

वैकल्पिक, कम प्रतिबंधात्मक परिभाषा इस प्रकार है:

  • ट्यूरिंग मशीन के जैसे, एलबीए में सेल से बना टेप होता है जिसमें सीमित सेट अल्फाबेट (कंप्यूटर विज्ञान) के प्रतीक हो सकते हैं, हेड जो समय में टेप पर सेल से रीड या राइट लिख ​​सकते है और स्थानांतरित किया जा सकता है, और सीमित संख्या में स्टेट है।
  • एलबीए ट्यूरिंग मशीन से इस आशय में भिन्न होता है कि प्रारंभ में टेप को असीमित लंबाई वाला माना जाता है, किन्तु टेप का केवल सीमित सन्निहित भाग, जिसकी लंबाई प्रारंभिक इनपुट की लंबाई का लीनियर फंक्शन है, रीड/राइट हेड द्वारा एक्सेस किया जा सकता है; इसलिए इसका नाम लीनियर बाउंडेड ऑटोमेटन हुआ।[1]: 225 

यह सीमा एलबीए को ट्यूरिंग मशीन की तुलना में वास्तविक संसार के कंप्यूटर का कुछ सीमा तक अधिक त्रुटिहीन मॉडल बनाती है, जिसकी परिभाषा असीमित टेप मानती है।

स्ट्रांग और वीकर परिभाषा संबंधित ऑटोमेटन वर्गों की समान कम्प्यूटेशनल क्षमताओं को उत्पन्न करती है,[1]: 225  उसी लॉजिक द्वारा जिसका उपयोग लीनियर स्पीडअप प्रमेय को सिद्ध करने के लिए किया जाता है।

एलबीए और कॉन्टेक्स्ट-सेंसिटिव लैंग्वेजेज

लीनियर बाउंडेड ऑटोमेटा कॉन्टेक्स्ट-सेंसिटिव लैंग्वेजेज के वर्ग के लिए एक्सपटर हैं।[1]: 225–226  ऐसी लैंग्वेजेज के लिए फॉर्मल ग्रामर पर लगाया गया मात्र प्रतिबंध यह है कि कोई भी उत्पादन किसी स्ट्रिंग को छोटी स्ट्रिंग में मैप नहीं करता है। इस प्रकार कॉन्टेक्स्ट-सेंसिटिव लैंग्वेज में किसी स्ट्रिंग की किसी भी व्युत्पत्ति में स्ट्रिंग से अधिक लंबा कोई भावनात्मक रूप नहीं हो सकता है। चूंकि लीनियर-बाउंड ऑटोमेटा और ऐसे ग्रामर के मध्य पत्राचार होता है, इसलिए ऑटोमेटन द्वारा स्ट्रिंग को पहचानने के लिए मूल स्ट्रिंग द्वारा प्रभुत्व किए गए टेप से अधिक टेप आवश्यक नहीं है।

इतिहास

1960 में, जॉन माइहिल ने ऑटोमेटन मॉडल प्रस्तुत किया जिसे आज डीटरमिनिस्टिक लीनियर बाउंडेड ऑटोमेटन के रूप में जाना जाता है।[2] 1963 में, पीटर लैंडवेबर ने सिद्ध किया कि डीटरमिनिस्टिक एलबीए द्वारा स्वीकृत लैंग्वेज कॉन्टेक्स्ट-सेंसिटिव हैं।[3] 1964 में, एस.वाई. कुरोदा ने (नॉनडेटर्मिनिस्टिक) लीनियर बाउंडेड ऑटोमेटा का अधिक सामान्य मॉडल प्रस्तुत किया, और यह दिखाने के लिए लैंडवेबर के प्रमाण को अनुकूलित किया कि नॉनडेटरमिनिस्टिक लीनियर बाउंडेड ऑटोमेटा द्वारा स्वीकार की जाने वाली लैंग्वेज वास्तव में कॉन्टेक्स्ट-सेंसिटिव लैंग्वेज हैं।[4][5]

एलबीए समस्याएं

अपने मौलिक पेपर में, कुरोदा ने दो शोध उद्देश भी बताईं, जो पश्चात में एलबीए समस्याओं के रूप में प्रसिद्ध हुईं: प्रथम एलबीए समस्या यह है कि क्या एलबीए द्वारा स्वीकृत लैंग्वेजेज का वर्ग डीटरमिनिस्टिक एलबीए द्वारा स्वीकृत लैंग्वेजेज के वर्ग के समान है। इस समस्या को कम्प्यूटेशनल कोम्प्लेक्सिटी थ्योरी की लैंग्वेज में संक्षेप में इस प्रकार व्यक्त किया जा सकता है:

प्रथम एलबीए समस्या: क्या NSPACE(O(n)) = DSPACE(O(n)) है?

एलबीए की दूसरी समस्या यह है कि क्या एलबीए द्वारा स्वीकृत लैंग्वेजेज का वर्ग पूरक के अंतर्गत विवृत है।

दूसरी एलबीए समस्या: क्या NSPACE(O(n)) = NSPACE(O(n)) है?

जैसा कि कुरोदा ने पहले ही देखा है, दूसरी एलबीए समस्या का ऋणात्मक उत्तर पहली समस्या का ऋणात्मक उत्तर होगा। किन्तु दूसरी एलबीए समस्या का धनात्मक उत्तर है, जो कि समस्या उठाए जाने के 20 वर्ष पश्चात सिद्ध हुए इमरमैन-स्ज़ेलेपीसीसेनी प्रमेय द्वारा निहित है।[6][7] आज तक, पहली एलबीए समस्या अभी भी संवृत हुई है। सैविच का प्रमेय प्रारंभिक अंतर्दृष्टि प्रदान करता है, कि NSPACE(O(n)) ⊆ DSPACE(O(n2)) है।[8]

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 John E. Hopcroft; Jeffrey D. Ullman (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय. Addison-Wesley. ISBN 978-0-201-02988-8.
  2. ↑ John Myhill (June 1960). लीनियर बाउंडेड ऑटोमेटा (WADD Technical Note). Wright Patterson AFB, Wright Air Development Division, Ohio.
  3. ↑ P.S. Landweber (1963). "प्रकार 1 के वाक्यांश संरचना व्याकरण पर तीन प्रमेय". Information and Control. 6 (2): 131–136. doi:10.1016/s0019-9958(63)90169-4.
  4. ↑ Sige-Yuki Kuroda (Jun 1964). "भाषाओं की कक्षाएं और रैखिक-बद्ध ऑटोमेटा". Information and Control. 7 (2): 207–223. doi:10.1016/s0019-9958(64)90120-2.
  5. ↑ Willem J. M. Levelt (2008). औपचारिक भाषाओं और ऑटोमेटा के सिद्धांत का एक परिचय. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2.
  6. ↑ Immerman, Neil (1988), "Nondeterministic space is closed under complementation" (PDF), SIAM Journal on Computing, 17 (5): 935–938, doi:10.1137/0217058, MR 0961049
  7. ↑ Szelepcsényi, Róbert (1988), "The method of forcing for nondeterministic automata", Acta Informatica, 26 (3): 279–284, doi:10.1007/BF00299636, S2CID 10838178
  8. ↑ Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लीनियर_बाउंडेड_ऑटोमेटन&oldid=281413’