अनरिस्ट्रिक्टेड ग्रामर: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
[[ऑटोमेटा सिद्धांत]] में '''अनरिस्ट्रिक्टेड ग्रामर''' क्लास (जिसे सेमी-थ्यू, टाइप-0 या फ्रेज संरचना ग्रामर भी कहा जाता है) [[चॉम्स्की पदानुक्रम|चॉम्स्की हायरार्की]] में ग्रामर की सबसे सामान्य क्लास है। अनरिस्ट्रिक्टेड ग्रामर के निर्माण पर कोई प्रतिबंध नहीं लगाया गया है क्योकि अनरिस्ट्रिक्टेड ग्रामर की प्रत्येक बायी क्लास गैर-रिक्त होती है।<ref name="Hopcroft.Ullman.1979"/>{{rp|220}} सामान्यतः यह ग्रामर क्लास अपेक्षाकृत रूप से [[पुनरावर्ती रूप से गणना योग्य भाषा|रिकर्सिवली एनयूमेरबल भाषाएँ]] उत्पन्न कर सकती है।
[[ऑटोमेटा सिद्धांत]] में '''अनरिस्ट्रिक्टेड ग्रामर''' क्लास (जिसे सेमी-थ्यू, टाइप-0 या फ्रेज संरचना ग्रामर भी कहा जाता है) [[चॉम्स्की पदानुक्रम|चॉम्स्की हायरार्की]] में ग्रामर की यह सबसे सामान्य क्लास है। अनरिस्ट्रिक्टेड ग्रामर के निर्माण पर कोई प्रतिबंध नहीं लगाया गया है क्योकि अनरिस्ट्रिक्टेड ग्रामर की प्रत्येक बायी क्लास गैर-रिक्त होती है।<ref name="Hopcroft.Ullman.1979"/>{{rp|220}} सामान्यतः यह ग्रामर क्लास अपेक्षाकृत रूप से [[पुनरावर्ती रूप से गणना योग्य भाषा|रिकर्सिवली एनयूमेरबल भाषाएँ]] उत्पन्न कर सकती है।


== औपचारिक परिभाषा ==
== औपचारिक परिभाषा ==
Line 5: Line 5:
अनरिस्ट्रिक्टेड ग्रामर एक [[औपचारिक व्याकरण|औपचारिक ग्रामर]] <math display="inline">G = (N, T, P, S)</math> है, जहां
अनरिस्ट्रिक्टेड ग्रामर एक [[औपचारिक व्याकरण|औपचारिक ग्रामर]] <math display="inline">G = (N, T, P, S)</math> है, जहां


* <math>N</math> [[नॉनटर्मिनल प्रतीक]] का एक सीमित समूह है।
* <math>N</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>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>\alpha \to \beta</math> है। <math>\alpha</math> और <math>\beta</math>, <math>N \cup T</math> में प्रतीकों की स्ट्रिंग हैं, जहां <math>\alpha</math> रिक्त स्ट्रिंग नहीं है।
* <math>P</math> बीटा के [[उत्पादन (कंप्यूटर विज्ञान)|कंप्यूटर]] उत्पादन नियमों का एक सीमित समूह <math>\alpha \to \beta</math> है। <math>\alpha</math> और <math>\beta</math>, <math>N \cup T</math> में प्रतीकों की स्ट्रिंग हैं, जहां <math>\alpha</math> रिक्त स्ट्रिंग नहीं है।
Line 14: Line 14:
== ट्यूरिंग मशीनों के समतुल्य ==
== ट्यूरिंग मशीनों के समतुल्य ==


अनरिस्ट्रिक्टेड ग्रामर [[पुनरावर्ती रूप से गणना योग्य भाषा|रिकर्सिवली एनयूमेरबल भाषाओं]] की विशेषता बताती है। यह कहने के लिए सामान्य है कि प्रत्येक अनरिस्ट्रिक्टेड ग्रामर <math>G</math> के लिए कुछ [[ट्यूरिंग मशीन]] सम्मिलित हैं जो इसके विपरीत <math>L(G)</math> को पहचानने में सक्षम है। अनरिस्ट्रिक्टेड ग्रामर को देखते हुए, ऐसी ट्यूरिंग मशीन दो-टेप [[गैर-नियतात्मक ट्यूरिंग मशीन|डेटर्मिनिस्टिक ट्यूरिंग मशीन]] के रूप में बनाने के लिए अपेक्षाकृत सरल है।<ref name="Hopcroft.Ullman.1979"/>{{rp|221}} पहले टेप में परीक्षण के लिए इनपुट शब्द <math>w</math> होता है, और दूसरे टेप का उपयोग मशीन द्वारा <math>G</math> से सिन्टेक्स को उत्पन्न करने के लिए किया जाता है। जिससे ट्यूरिंग मशीन प्रायः निम्नलिखित कार्य करती है:
अनरिस्ट्रिक्टेड ग्रामर [[पुनरावर्ती रूप से गणना योग्य भाषा|रिकर्सिवली एनयूमेरबल भाषाओं]] की विशेषता बताती है। यह कहने के लिए सामान्य है कि प्रत्येक अनरिस्ट्रिक्टेड ग्रामर <math>G</math> के लिए कुछ [[ट्यूरिंग मशीन|ट्यूरिंग मशीने]] सम्मिलित हैं जो इसके विपरीत <math>L(G)</math> को पहचानने में सक्षम हैं। अनरिस्ट्रिक्टेड ग्रामर को देखते हुए, ऐसी ट्यूरिंग मशीन दो-टेप [[गैर-नियतात्मक ट्यूरिंग मशीन|डेटर्मिनिस्टिक ट्यूरिंग मशीन]] के रूप में बनाने के लिए अपेक्षाकृत सरल है।<ref name="Hopcroft.Ullman.1979"/>{{rp|221}} पहले टेप में परीक्षण के लिए इनपुट शब्द <math>w</math> होता है और दूसरे टेप का उपयोग मशीन द्वारा <math>G</math> से सिन्टेक्स को उत्पन्न करने के लिए किया जाता है। जिससे ट्यूरिंग मशीन प्रायः निम्नलिखित कार्य करती है:


# दूसरे टेप के बाईं ओर से प्रारंभ करें और बार-बार दाईं ओर जाने का चयन करें या टेप पर वर्तमान स्थिति का चयन करें।
# दूसरे टेप के बाईं ओर से प्रारंभ करें और बार-बार दाईं ओर जाने का चयन करें या टेप पर वर्तमान स्थिति का चयन करें।
Line 27: Line 27:
== कम्प्यूटेशनल विशेषताएँ ==
== कम्प्यूटेशनल विशेषताएँ ==


किसी दी गई स्ट्रिंग को किसी अनरिस्ट्रिक्टेड ग्रामर द्वारा उत्पन्न किया जा सकता है या नहीं उत्पन्न किया जा सकता है। इसकी निर्णय समस्या इस समस्या के बराबर है कि क्या इसे ग्रामर के समकक्ष ट्यूरिंग मशीन द्वारा स्वीकृत किया जा सकता है। बाद वाली समस्या को हॉल्टिंग समस्या कहा जाता है और सामान्यतः यह अनडिसाइडेबल है।
किसी दी गई स्ट्रिंग को किसी अनरिस्ट्रिक्टेड ग्रामर द्वारा उत्पन्न किया जा सकता है या नहीं उत्पन्न किया जा सकता है। इसकी निर्णय समस्या इस समस्या के बराबर है कि क्या इसे ग्रामर के समकक्ष ट्यूरिंग मशीन द्वारा स्वीकृत किया जा सकता है। बाद वाली समस्या को हॉल्टिंग समस्या कहा जाता है और सामान्यतः यह अनडिसाइडेबल (अनिर्णनीय) है।


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


ट्यूरिंग मशीनों के लिए अनरिस्ट्रिक्टेड ग्रामर की समानता एक सार्वभौमिक अनरिस्ट्रिक्टेड ग्रामर के अस्तित्व को दर्शाती है। एक ग्रामर भाषा का विवरण दिए जाने पर अन्य अनरिस्ट्रिक्टेड ग्रामर भाषा विवरण को स्वीकृत करने में सक्षम होती है। इस कारण से अनरिस्ट्रिक्टेड ग्रामर जैसे थ्यू ([[प्रोग्रामिंग भाषा]]) के आधार पर एक प्रोग्रामिंग भाषा बनाना सैद्धांतिक रूप से संभव है।
ट्यूरिंग मशीनों के लिए अनरिस्ट्रिक्टेड ग्रामर की समानता एक सार्वभौमिक अनरिस्ट्रिक्टेड ग्रामर के अस्तित्व को दर्शाती है। एक ग्रामर भाषा का विवरण दिए जाने पर अन्य अनरिस्ट्रिक्टेड ग्रामर भाषाएं विवरण को स्वीकृत करने में सक्षम होती हैं। इस कारण से अनरिस्ट्रिक्टेड ग्रामर जैसे थ्यू ([[प्रोग्रामिंग भाषा]]) के आधार पर एक प्रोग्रामिंग भाषा बनाना सैद्धांतिक रूप से संभव है।


==यह भी देखें==
==यह भी देखें==
Line 39: Line 39:
==टिप्पणियाँ==
==टिप्पणियाँ==
{{reflist|group=note}}
{{reflist|group=note}}
==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}

Revision as of 11:48, 2 August 2023

ऑटोमेटा सिद्धांत में अनरिस्ट्रिक्टेड ग्रामर क्लास (जिसे सेमी-थ्यू, टाइप-0 या फ्रेज संरचना ग्रामर भी कहा जाता है) चॉम्स्की हायरार्की में ग्रामर की यह सबसे सामान्य क्लास है। अनरिस्ट्रिक्टेड ग्रामर के निर्माण पर कोई प्रतिबंध नहीं लगाया गया है क्योकि अनरिस्ट्रिक्टेड ग्रामर की प्रत्येक बायी क्लास गैर-रिक्त होती है।[1]: 220  सामान्यतः यह ग्रामर क्लास अपेक्षाकृत रूप से रिकर्सिवली एनयूमेरबल भाषाएँ उत्पन्न कर सकती है।

औपचारिक परिभाषा

अनरिस्ट्रिक्टेड ग्रामर एक औपचारिक ग्रामर है, जहां

  • गैर-टर्मिनल प्रतीक का एक सीमित समूह है।
  • , और डिसजोईन्ट के साथ टर्मिनल प्रतीकों का एक सीमित समूह है।[note 1]
  • बीटा के कंप्यूटर उत्पादन नियमों का एक सीमित समूह है। और , में प्रतीकों की स्ट्रिंग हैं, जहां रिक्त स्ट्रिंग नहीं है।
  • एक विशेष रूप से नामित प्रारम्भिक प्रतीक है।[1]: 220 

जैसा कि नाम से पता चलता है कि अनरिस्ट्रिक्टेड ग्रामर के उत्पादन नियमों के प्रकारों पर कोई वास्तविक प्रतिबंध नहीं होता है।[note 2]

ट्यूरिंग मशीनों के समतुल्य

अनरिस्ट्रिक्टेड ग्रामर रिकर्सिवली एनयूमेरबल भाषाओं की विशेषता बताती है। यह कहने के लिए सामान्य है कि प्रत्येक अनरिस्ट्रिक्टेड ग्रामर के लिए कुछ ट्यूरिंग मशीने सम्मिलित हैं जो इसके विपरीत को पहचानने में सक्षम हैं। अनरिस्ट्रिक्टेड ग्रामर को देखते हुए, ऐसी ट्यूरिंग मशीन दो-टेप डेटर्मिनिस्टिक ट्यूरिंग मशीन के रूप में बनाने के लिए अपेक्षाकृत सरल है।[1]: 221  पहले टेप में परीक्षण के लिए इनपुट शब्द होता है और दूसरे टेप का उपयोग मशीन द्वारा से सिन्टेक्स को उत्पन्न करने के लिए किया जाता है। जिससे ट्यूरिंग मशीन प्रायः निम्नलिखित कार्य करती है:

  1. दूसरे टेप के बाईं ओर से प्रारंभ करें और बार-बार दाईं ओर जाने का चयन करें या टेप पर वर्तमान स्थिति का चयन करें।
  2. प्रस्तुतियों में से डेटर्मिनिस्टिक एल्गोरिदम को चुनें।
  3. यदि दूसरे टेप पर किसी स्थान पर दिखाई देता है, तो उस बिंदु पर को से परिवर्तित करें, संभवतः और की सापेक्ष लंबाई के आधार पर टेप पर प्रतीकों को बाएं या दाएं स्थानांतरित करें। उदाहरण के लिए यदि , से लंबा है, तो टेप को स्थानांतरित करें।
  4. टेप 2 पर परिणामी सिन्टेक्स की तुलना टेप 1 पर टेक्स्ट से करें। यदि वे समान हैं, तो ट्यूरिंग मशीन टेक्स्ट को स्वीकृत कर लेती है। यदि वे ऐसा नहीं करती है, तो ट्यूरिंग मशीन टेप 1 पर वापस चली जाती है।

यह देखना आसान है कि यह ट्यूरिंग मशीन अंतिम टेप को अपेक्षाकृत रूप से कई बार कार्यान्वित करने के बाद अपने दूसरे टेप पर के सभी और केवल टेक्स्ट रूपों को उत्पन्न उत्पन्न करती है। इस प्रकार भाषा को रिकर्सिवली एनयूमेरबल भाषा के रूप मे माना जा सकता है।

इसके विपरीत निर्माण भी संभव है यदि कुछ ट्यूरिंग मशीन को देखते हुए, एक समतुल्य अनरिस्ट्रिक्टेड ग्रामर बनाना संभव है जो केवल बायीं ओर एक या एक से अधिक गैर-टर्मिनल प्रतीकों वाली प्रस्तुतियों का उपयोग करता है।[1]: 222  इसलिए एक अपेक्षाकृत अनरिस्ट्रिक्टेड ग्रामर को सदैव ट्यूरिंग मशीन में परिवर्तित करके और फिर से बाद वाले फॉर्म का उपयोग करने के लिए समान रूप से परिवर्तित किया जा सकता है। कुछ लेखक[citation needed] अनरिस्ट्रिक्टेड ग्रामर की परिभाषा के रूप में भी इसका उपयोग करते हैं।

कम्प्यूटेशनल विशेषताएँ

किसी दी गई स्ट्रिंग को किसी अनरिस्ट्रिक्टेड ग्रामर द्वारा उत्पन्न किया जा सकता है या नहीं उत्पन्न किया जा सकता है। इसकी निर्णय समस्या इस समस्या के बराबर है कि क्या इसे ग्रामर के समकक्ष ट्यूरिंग मशीन द्वारा स्वीकृत किया जा सकता है। बाद वाली समस्या को हॉल्टिंग समस्या कहा जाता है और सामान्यतः यह अनडिसाइडेबल (अनिर्णनीय) है।

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

ट्यूरिंग मशीनों के लिए अनरिस्ट्रिक्टेड ग्रामर की समानता एक सार्वभौमिक अनरिस्ट्रिक्टेड ग्रामर के अस्तित्व को दर्शाती है। एक ग्रामर भाषा का विवरण दिए जाने पर अन्य अनरिस्ट्रिक्टेड ग्रामर भाषाएं विवरण को स्वीकृत करने में सक्षम होती हैं। इस कारण से अनरिस्ट्रिक्टेड ग्रामर जैसे थ्यू (प्रोग्रामिंग भाषा) के आधार पर एक प्रोग्रामिंग भाषा बनाना सैद्धांतिक रूप से संभव है।

यह भी देखें

टिप्पणियाँ

  1. 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.
  2. 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. 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.