अनरिस्ट्रिक्टेड ग्रामर: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[ऑटोमेटा सिद्धांत]] में | [[ऑटोमेटा सिद्धांत]] में '''अनरिस्ट्रिक्टेड ग्रामर''' क्लास (जिसे सेमी-थ्यू, टाइप-0 या फ्रेज संरचना ग्रामर भी कहा जाता है) [[चॉम्स्की पदानुक्रम|चॉम्स्की हायरार्की]] में ग्रामर की सबसे सामान्य क्लास है। अनरिस्ट्रिक्टेड ग्रामर के निर्माण पर कोई प्रतिबंध नहीं लगाया गया है क्योकि अनरिस्ट्रिक्टेड ग्रामर की प्रत्येक बायी क्लास गैर-रिक्त होती है।<ref name="Hopcroft.Ullman.1979"/>{{rp|220}} सामान्यतः यह ग्रामर क्लास अपेक्षाकृत रूप से [[पुनरावर्ती रूप से गणना योग्य भाषा|रिकर्सिवली एनयूमेरबल भाषाएँ]] उत्पन्न कर सकती है। | ||
== औपचारिक परिभाषा == | == औपचारिक परिभाषा == | ||
अनरिस्ट्रिक्टेड ग्रामर एक [[औपचारिक व्याकरण|औपचारिक ग्रामर]] <math display="inline">G = (N, T, P, S)</math> है, जहां | |||
* <math>N</math> [[नॉनटर्मिनल प्रतीक]] का एक सीमित | * <math>N</math> [[नॉनटर्मिनल प्रतीक]] का एक सीमित समूह है। | ||
* <math>T</math>, <math>N</math> और <math>T</math> | * <math>T</math>, <math>N</math> और <math>T</math> डिसजोईन्ट के साथ [[टर्मिनल प्रतीक|टर्मिनल]] प्रतीकों का एक सीमित समूह है।<ref group="note">Actually, <math>T\cap N=\emptyset</math> is not strictly necessary since unrestricted grammars make no real distinction between the two. The designation exists purely so that one knows when to stop generating [[Formal grammar#sentential-form|sentential forms]] of the grammar; more precisely, the language <math>L(G)</math> recognized by <math>G</math> is restricted to strings of terminal symbols.</ref> | ||
* <math>P</math> | * <math>P</math> बीटा के [[उत्पादन (कंप्यूटर विज्ञान)|कंप्यूटर]] उत्पादन नियमों का एक सीमित समूह <math>\alpha \to \beta</math> है। <math>\alpha</math> और <math>\beta</math>, <math>N \cup T</math> में प्रतीकों की स्ट्रिंग हैं, जहां <math>\alpha</math> रिक्त स्ट्रिंग नहीं है। | ||
* <math>S \in N</math> एक विशेष रूप से नामित | * <math>S \in N</math> एक विशेष रूप से नामित प्रारम्भिक प्रतीक है।<ref name="Hopcroft.Ullman.1979">{{cite book |last1=Hopcroft |first1=John |authorlink=John Hopcroft |last2=Ullman |first2=Jeffrey D. |authorlink2=Jeffrey Ullman |year=1979 |title=[[Introduction to Automata Theory, Languages, and Computation]] |publisher=Addison-Wesley |edition=1st | isbn=0-201-44124-1}}</ref>{{rp|220}} | ||
जैसा कि नाम से पता चलता है | जैसा कि नाम से पता चलता है कि अनरिस्ट्रिक्टेड ग्रामर के उत्पादन नियमों के प्रकारों पर कोई वास्तविक प्रतिबंध नहीं होता है।<ref group="note">While Hopcroft and Ullman (1979) do not mention the cardinalities of <math>N</math>, <math>T</math>, <math>P</math> explicitly, the proof of their Theorem 9.3 (construction of an equivalent Turing machine from a given unrestricted grammar, p.221, cf. Section [[#Equivalence to Turing machines]]) tacitly requires finiteness of <math>P</math> and finite lengths of all strings in rules of <math>P</math>. Any member of <math>N</math> or <math>T</math> that does not occur in <math>P</math> can be omitted without affecting the generated language.</ref> | ||
== ट्यूरिंग मशीनों के समतुल्य == | == ट्यूरिंग मशीनों के समतुल्य == | ||
अनरिस्ट्रिक्टेड ग्रामर [[पुनरावर्ती रूप से गणना योग्य भाषा|रिकर्सिवली एनयूमेरबल भाषाओं]] की विशेषता बताती है। यह कहने के लिए सामान्य है कि प्रत्येक अनरिस्ट्रिक्टेड ग्रामर <math>G</math> के लिए कुछ [[ट्यूरिंग मशीन]] सम्मिलित हैं जो इसके विपरीत <math>L(G)</math> को पहचानने में सक्षम है। अनरिस्ट्रिक्टेड ग्रामर को देखते हुए, ऐसी ट्यूरिंग मशीन दो-टेप [[गैर-नियतात्मक ट्यूरिंग मशीन|डेटर्मिनिस्टिक ट्यूरिंग मशीन]] के रूप में बनाने के लिए अपेक्षाकृत सरल है।<ref name="Hopcroft.Ullman.1979"/>{{rp|221}} पहले टेप में परीक्षण के लिए इनपुट शब्द <math>w</math> होता है, और दूसरे टेप का उपयोग मशीन द्वारा <math>G</math> से सिन्टेक्स को उत्पन्न करने के लिए किया जाता है। जिससे ट्यूरिंग मशीन प्रायः निम्नलिखित कार्य करती है: | |||
# दूसरे टेप के बाईं ओर से प्रारंभ करें और बार-बार दाईं ओर जाने का चयन करें या टेप पर वर्तमान स्थिति का चयन करें। | # दूसरे टेप के बाईं ओर से प्रारंभ करें और बार-बार दाईं ओर जाने का चयन करें या टेप पर वर्तमान स्थिति का चयन करें। | ||
# | # <math>G</math> प्रस्तुतियों में से [[Index.php?title=डेटर्मिनिस्टिक एल्गोरिदम|डेटर्मिनिस्टिक एल्गोरिदम]] <math>\beta \to \gamma</math> को चुनें। | ||
# यदि <math>\beta</math> दूसरे टेप पर किसी स्थान पर दिखाई देता है, तो उस बिंदु पर <math>\beta</math> को | # यदि <math>\beta</math> दूसरे टेप पर किसी स्थान पर दिखाई देता है, तो उस बिंदु पर <math>\beta</math> को <math>\gamma</math> से परिवर्तित करें, संभवतः <math>\beta</math> और <math>\gamma</math> की सापेक्ष लंबाई के आधार पर टेप पर प्रतीकों को बाएं या दाएं स्थानांतरित करें। उदाहरण के लिए यदि <math>\beta</math>, <math>\gamma</math> से लंबा है, तो टेप को स्थानांतरित करें। | ||
# टेप 2 पर परिणामी | # टेप 2 पर परिणामी सिन्टेक्स की तुलना टेप 1 पर टेक्स्ट से करें। यदि वे समान हैं, तो ट्यूरिंग मशीन टेक्स्ट को स्वीकृत कर लेती है। यदि वे ऐसा नहीं करती है, तो ट्यूरिंग मशीन टेप 1 पर वापस चली जाती है। | ||
यह देखना आसान है कि यह ट्यूरिंग मशीन अंतिम | यह देखना आसान है कि यह ट्यूरिंग मशीन अंतिम टेप को अपेक्षाकृत रूप से कई बार कार्यान्वित करने के बाद अपने दूसरे टेप पर <math>G</math> के सभी और केवल टेक्स्ट रूपों को उत्पन्न उत्पन्न करती है। इस प्रकार भाषा <math>L(G)</math> को रिकर्सिवली एनयूमेरबल भाषा के रूप मे माना जा सकता है। | ||
विपरीत निर्माण भी संभव है | इसके विपरीत निर्माण भी संभव है यदि कुछ ट्यूरिंग मशीन को देखते हुए, एक समतुल्य अनरिस्ट्रिक्टेड ग्रामर बनाना संभव है जो केवल बायीं ओर एक या एक से अधिक गैर-टर्मिनल प्रतीकों वाली प्रस्तुतियों का उपयोग करता है।<ref name="Hopcroft.Ullman.1979"/>{{rp|222}} इसलिए एक अपेक्षाकृत अनरिस्ट्रिक्टेड ग्रामर को सदैव ट्यूरिंग मशीन में परिवर्तित करके और फिर से बाद वाले फॉर्म का उपयोग करने के लिए समान रूप से परिवर्तित किया जा सकता है। कुछ लेखक {{cn|date=February 2017}} अनरिस्ट्रिक्टेड ग्रामर की परिभाषा के रूप में भी इसका उपयोग करते हैं। | ||
== कम्प्यूटेशनल | == कम्प्यूटेशनल विशेषताएँ == | ||
किसी | किसी दी गई स्ट्रिंग को किसी अनरिस्ट्रिक्टेड ग्रामर द्वारा उत्पन्न किया जा सकता है या नहीं उत्पन्न किया जा सकता है। इसकी निर्णय समस्या इस समस्या के बराबर है कि क्या इसे ग्रामर के समकक्ष ट्यूरिंग मशीन द्वारा स्वीकृत किया जा सकता है। बाद वाली समस्या को हॉल्टिंग समस्या कहा जाता है और सामान्यतः यह अनडिसाइडेबल है। | ||
रिकर्सिवली एनयूमेरबल भाषाएं [[क्लेन स्टार]], कॉन्सटेनेशन, यूनियन और इंटरसेक्शन के अंतर्गत क्लोजर हैं। जिसके लिए रिकर्सिवली एनयूमेरबल भाषा क्लोजर गुण देखें। | |||
ट्यूरिंग मशीनों के लिए | ट्यूरिंग मशीनों के लिए अनरिस्ट्रिक्टेड ग्रामर की समानता एक सार्वभौमिक अनरिस्ट्रिक्टेड ग्रामर के अस्तित्व को दर्शाती है। एक ग्रामर भाषा का विवरण दिए जाने पर अन्य अनरिस्ट्रिक्टेड ग्रामर भाषा विवरण को स्वीकृत करने में सक्षम होती है। इस कारण से अनरिस्ट्रिक्टेड ग्रामर जैसे थ्यू ([[प्रोग्रामिंग भाषा]]) के आधार पर एक प्रोग्रामिंग भाषा बनाना सैद्धांतिक रूप से संभव है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[लैम्ब्डा कैलकुलस]] | * [[लैम्ब्डा कैलकुलस]] | ||
* [[सेमी-थू प्रणाली]] - टर्मिनल और नॉनटर्मिनल प्रतीकों में अंतर नहीं करता है | * [[सेमी-थू प्रणाली|सेमी-थू सिस्टम]] - टर्मिनल और नॉनटर्मिनल प्रतीकों में अंतर नहीं करता है और रिक्त बाएं क्लास को स्वीकृत करता है। | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
Revision as of 11:42, 2 August 2023
ऑटोमेटा सिद्धांत में अनरिस्ट्रिक्टेड ग्रामर क्लास (जिसे सेमी-थ्यू, टाइप-0 या फ्रेज संरचना ग्रामर भी कहा जाता है) चॉम्स्की हायरार्की में ग्रामर की सबसे सामान्य क्लास है। अनरिस्ट्रिक्टेड ग्रामर के निर्माण पर कोई प्रतिबंध नहीं लगाया गया है क्योकि अनरिस्ट्रिक्टेड ग्रामर की प्रत्येक बायी क्लास गैर-रिक्त होती है।[1]: 220 सामान्यतः यह ग्रामर क्लास अपेक्षाकृत रूप से रिकर्सिवली एनयूमेरबल भाषाएँ उत्पन्न कर सकती है।
औपचारिक परिभाषा
अनरिस्ट्रिक्टेड ग्रामर एक औपचारिक ग्रामर है, जहां
- नॉनटर्मिनल प्रतीक का एक सीमित समूह है।
- , और डिसजोईन्ट के साथ टर्मिनल प्रतीकों का एक सीमित समूह है।[note 1]
- बीटा के कंप्यूटर उत्पादन नियमों का एक सीमित समूह है। और , में प्रतीकों की स्ट्रिंग हैं, जहां रिक्त स्ट्रिंग नहीं है।
- एक विशेष रूप से नामित प्रारम्भिक प्रतीक है।[1]: 220
जैसा कि नाम से पता चलता है कि अनरिस्ट्रिक्टेड ग्रामर के उत्पादन नियमों के प्रकारों पर कोई वास्तविक प्रतिबंध नहीं होता है।[note 2]
ट्यूरिंग मशीनों के समतुल्य
अनरिस्ट्रिक्टेड ग्रामर रिकर्सिवली एनयूमेरबल भाषाओं की विशेषता बताती है। यह कहने के लिए सामान्य है कि प्रत्येक अनरिस्ट्रिक्टेड ग्रामर के लिए कुछ ट्यूरिंग मशीन सम्मिलित हैं जो इसके विपरीत को पहचानने में सक्षम है। अनरिस्ट्रिक्टेड ग्रामर को देखते हुए, ऐसी ट्यूरिंग मशीन दो-टेप डेटर्मिनिस्टिक ट्यूरिंग मशीन के रूप में बनाने के लिए अपेक्षाकृत सरल है।[1]: 221 पहले टेप में परीक्षण के लिए इनपुट शब्द होता है, और दूसरे टेप का उपयोग मशीन द्वारा से सिन्टेक्स को उत्पन्न करने के लिए किया जाता है। जिससे ट्यूरिंग मशीन प्रायः निम्नलिखित कार्य करती है:
- दूसरे टेप के बाईं ओर से प्रारंभ करें और बार-बार दाईं ओर जाने का चयन करें या टेप पर वर्तमान स्थिति का चयन करें।
- प्रस्तुतियों में से डेटर्मिनिस्टिक एल्गोरिदम को चुनें।
- यदि दूसरे टेप पर किसी स्थान पर दिखाई देता है, तो उस बिंदु पर को से परिवर्तित करें, संभवतः और की सापेक्ष लंबाई के आधार पर टेप पर प्रतीकों को बाएं या दाएं स्थानांतरित करें। उदाहरण के लिए यदि , से लंबा है, तो टेप को स्थानांतरित करें।
- टेप 2 पर परिणामी सिन्टेक्स की तुलना टेप 1 पर टेक्स्ट से करें। यदि वे समान हैं, तो ट्यूरिंग मशीन टेक्स्ट को स्वीकृत कर लेती है। यदि वे ऐसा नहीं करती है, तो ट्यूरिंग मशीन टेप 1 पर वापस चली जाती है।
यह देखना आसान है कि यह ट्यूरिंग मशीन अंतिम टेप को अपेक्षाकृत रूप से कई बार कार्यान्वित करने के बाद अपने दूसरे टेप पर के सभी और केवल टेक्स्ट रूपों को उत्पन्न उत्पन्न करती है। इस प्रकार भाषा को रिकर्सिवली एनयूमेरबल भाषा के रूप मे माना जा सकता है।
इसके विपरीत निर्माण भी संभव है यदि कुछ ट्यूरिंग मशीन को देखते हुए, एक समतुल्य अनरिस्ट्रिक्टेड ग्रामर बनाना संभव है जो केवल बायीं ओर एक या एक से अधिक गैर-टर्मिनल प्रतीकों वाली प्रस्तुतियों का उपयोग करता है।[1]: 222 इसलिए एक अपेक्षाकृत अनरिस्ट्रिक्टेड ग्रामर को सदैव ट्यूरिंग मशीन में परिवर्तित करके और फिर से बाद वाले फॉर्म का उपयोग करने के लिए समान रूप से परिवर्तित किया जा सकता है। कुछ लेखक[citation needed] अनरिस्ट्रिक्टेड ग्रामर की परिभाषा के रूप में भी इसका उपयोग करते हैं।
कम्प्यूटेशनल विशेषताएँ
किसी दी गई स्ट्रिंग को किसी अनरिस्ट्रिक्टेड ग्रामर द्वारा उत्पन्न किया जा सकता है या नहीं उत्पन्न किया जा सकता है। इसकी निर्णय समस्या इस समस्या के बराबर है कि क्या इसे ग्रामर के समकक्ष ट्यूरिंग मशीन द्वारा स्वीकृत किया जा सकता है। बाद वाली समस्या को हॉल्टिंग समस्या कहा जाता है और सामान्यतः यह अनडिसाइडेबल है।
रिकर्सिवली एनयूमेरबल भाषाएं क्लेन स्टार, कॉन्सटेनेशन, यूनियन और इंटरसेक्शन के अंतर्गत क्लोजर हैं। जिसके लिए रिकर्सिवली एनयूमेरबल भाषा क्लोजर गुण देखें।
ट्यूरिंग मशीनों के लिए अनरिस्ट्रिक्टेड ग्रामर की समानता एक सार्वभौमिक अनरिस्ट्रिक्टेड ग्रामर के अस्तित्व को दर्शाती है। एक ग्रामर भाषा का विवरण दिए जाने पर अन्य अनरिस्ट्रिक्टेड ग्रामर भाषा विवरण को स्वीकृत करने में सक्षम होती है। इस कारण से अनरिस्ट्रिक्टेड ग्रामर जैसे थ्यू (प्रोग्रामिंग भाषा) के आधार पर एक प्रोग्रामिंग भाषा बनाना सैद्धांतिक रूप से संभव है।
यह भी देखें
- लैम्ब्डा कैलकुलस
- सेमी-थू सिस्टम - टर्मिनल और नॉनटर्मिनल प्रतीकों में अंतर नहीं करता है और रिक्त बाएं क्लास को स्वीकृत करता है।
टिप्पणियाँ
- ↑ Actually, is not strictly necessary since unrestricted grammars make no real distinction between the two. The designation exists purely so that one knows when to stop generating sentential forms of the grammar; more precisely, the language recognized by is restricted to strings of terminal symbols.
- ↑ While Hopcroft and Ullman (1979) do not mention the cardinalities of , , explicitly, the proof of their Theorem 9.3 (construction of an equivalent Turing machine from a given unrestricted grammar, p.221, cf. Section #Equivalence to Turing machines) tacitly requires finiteness of and finite lengths of all strings in rules of . Any member of or that does not occur in can be omitted without affecting the generated language.
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 Hopcroft, John; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-44124-1.
