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

From Vigyanwiki
 
(7 intermediate revisions by 2 users not shown)
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>
 
 
==संदर्भ==
<references/>
<references/>


Line 49: Line 46:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 22:29, 2 February 2024

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

ऑपरेशन

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

  • इसके इनपुट अल्फाबेट में दो विशेष प्रतीक सम्मिलित हैं, जो बाएँ और दाएँ एंडमार्कर के फॉर्म में कार्य करते हैं।
  • इसके ट्रांज़िशन एंडमार्कर पर अन्य प्रतीकों को प्रिंट नहीं कर सकते हैं।
  • इसके ट्रांज़िशन न तो बाएं एंडमार्कर के बाईं ओर जा सकते हैं और न ही दाएं एंडमार्कर के दाईं ओर जा सकते हैं।[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=281419’