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

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


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


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


# दूसरे टेप के बाईं ओर से प्रारंभ करें और बार-बार दाईं ओर जाने का चयन करें या टेप पर वर्तमान स्थिति का चयन करें।
# दूसरे टेप के बाईं ओर से प्रारंभ करें और बार-बार दाईं ओर जाने का चयन करें या टेप पर वर्तमान स्थिति का चयन करें।
# गैर-नियतात्मक एल्गोरिदम एक उत्पादन चुनें <math>\beta \to \gamma</math> में प्रस्तुतियों से <math>G</math>.
# <math>G</math> प्रस्तुतियों में से [[Index.php?title=डेटर्मिनिस्टिक एल्गोरिदम|डेटर्मिनिस्टिक एल्गोरिदम]] <math>\beta \to \gamma</math> को चुनें।
# अगर <math>\beta</math> दूसरे टेप पर किसी स्थान पर दिखाई देता है, बदलें <math>\beta</math> द्वारा <math>\gamma</math> उस बिंदु पर, संभवतः टेप पर प्रतीकों को सापेक्ष लंबाई के आधार पर बाएँ या दाएँ स्थानांतरित करना <math>\beta</math> और <math>\gamma</math> (उदा. यदि <math>\beta</math> से अधिक लम्बा है <math>\gamma</math>, टेप प्रतीकों को बाईं ओर शिफ्ट करें)।
# यदि <math>\beta</math> दूसरे टेप पर किसी स्थान पर दिखाई देता है, तो उस बिंदु पर <math>\beta</math> को <math>\gamma</math> से परिवर्तित करें, संभवतः <math>\beta</math> और <math>\gamma</math> की सापेक्ष लंबाई के आधार पर टेप पर प्रतीकों को बाएं या दाएं स्थानांतरित करें। उदाहरण के लिए यदि <math>\beta</math>, <math>\gamma</math> से लंबा है, तो टेप को स्थानांतरित करें।
# टेप 2 पर परिणामी वाक्यात्मक रूप की तुलना टेप 1 पर शब्द से करें। यदि वे मेल खाते हैं, तो ट्यूरिंग मशीन शब्द को स्वीकार कर लेती है। यदि वे ऐसा नहीं करते हैं, तो ट्यूरिंग मशीन चरण 1 पर वापस चली जाएगी।
# टेप 2 पर परिणामी सिन्टेक्स की तुलना टेप 1 पर टेक्स्ट से करें। यदि वे समान हैं, तो ट्यूरिंग मशीन टेक्स्ट को स्वीकृत कर लेती है। यदि वे ऐसा नहीं करती है, तो ट्यूरिंग मशीन टेप 1 पर वापस चली जाती है।


यह देखना आसान है कि यह ट्यूरिंग मशीन सभी और केवल भावनात्मक रूपों को उत्पन्न करेगी <math>G</math> अंतिम चरण के बाद इसके दूसरे टेप पर मनमाने ढंग से कई बार क्रियान्वित किया जाता है, इस प्रकार भाषा <math>L(G)</math> पुनरावर्ती रूप से गणना योग्य होना चाहिए।
यह देखना आसान है कि यह ट्यूरिंग मशीन अंतिम टेप को अपेक्षाकृत रूप से कई बार कार्यान्वित करने के बाद अपने दूसरे टेप पर <math>G</math> के सभी और केवल टेक्स्ट रूपों को उत्पन्न उत्पन्न करती है। इस प्रकार भाषा <math>L(G)</math> को रिकर्सिवली एनयूमेरबल भाषा के रूप मे माना जा सकता है।


विपरीत निर्माण भी संभव है. कुछ ट्यूरिंग मशीन को देखते हुए, एक समतुल्य अप्रतिबंधित व्याकरण बनाना संभव है<ref name="Hopcroft.Ullman.1979"/>{{rp|222}} जो केवल उन प्रस्तुतियों का उपयोग करता है जिनके बाईं ओर एक या अधिक गैर-टर्मिनल प्रतीक होते हैं। इसलिए, एक मनमाना अप्रतिबंधित व्याकरण को हमेशा ट्यूरिंग मशीन में परिवर्तित करके और फिर से बाद वाले फॉर्म का पालन करने के लिए समान रूप से परिवर्तित किया जा सकता है। कुछ लेखक{{cn|date=February 2017}} अप्रतिबंधित व्याकरण की परिभाषा के रूप में बाद वाले फॉर्म का उपयोग करें।
इसके विपरीत निर्माण भी संभव है यदि कुछ ट्यूरिंग मशीन को देखते हुए, एक समतुल्य अनरिस्ट्रिक्टेड ग्रामर बनाना संभव है जो केवल बायीं ओर एक या एक से अधिक गैर-टर्मिनल प्रतीकों वाली प्रस्तुतियों का उपयोग करता है।<ref name="Hopcroft.Ullman.1979"/>{{rp|222}} इसलिए एक अपेक्षाकृत अनरिस्ट्रिक्टेड ग्रामर को सदैव ट्यूरिंग मशीन में परिवर्तित करके और फिर से बाद वाले फॉर्म का उपयोग करने के लिए समान रूप से परिवर्तित किया जा सकता है। कुछ लेखक {{cn|date=February 2017}} अनरिस्ट्रिक्टेड ग्रामर की परिभाषा के रूप में भी इसका उपयोग करते हैं।


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


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


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


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


==यह भी देखें==
==यह भी देखें==
* [[लैम्ब्डा कैलकुलस]]
* [[लैम्ब्डा कैलकुलस]]
* [[सेमी-थू प्रणाली]] - टर्मिनल और नॉनटर्मिनल प्रतीकों में अंतर नहीं करता है, खाली बाएं हाथ को स्वीकार करता है
* [[सेमी-थू प्रणाली|सेमी-थू सिस्टम]] - टर्मिनल और नॉनटर्मिनल प्रतीकों में अंतर नहीं करता है और रिक्त बाएं क्लास को स्वीकृत करता है।


==टिप्पणियाँ==
==टिप्पणियाँ==
{{reflist|group=note}}
{{reflist|group=note}}
==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}


{{Formal languages and grammars}}
{{Formal languages and grammars}}
[[Category: औपचारिक भाषाएँ]]


[[Category: Machine Translated Page]]
[[Category:All articles with unsourced statements]]
[[Category:Articles with unsourced statements from February 2017]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:औपचारिक भाषाएँ]]

Latest revision as of 15:27, 30 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अनरिस्ट्रिक्टेड_ग्रामर&oldid=254639’