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

Latest revision as of 15:27, 30 August 2023

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

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

अनरिस्ट्रिक्टेड ग्रामर एक औपचारिक ग्रामर ${\textstyle G=(N,T,P,S)}$ है, जहां

$N$ गैर-टर्मिनल प्रतीक का एक सीमित समूह है।
$T$ , $N$ और $T$ डिसजोईन्ट के साथ टर्मिनल प्रतीकों का एक सीमित समूह है।^{[note 1]}
$P$ बीटा के कंप्यूटर उत्पादन नियमों का एक सीमित समूह $\alpha \to \beta$ है। $\alpha$ और $\beta$ , $N\cup T$ में प्रतीकों की स्ट्रिंग हैं, जहां $\alpha$ रिक्त स्ट्रिंग नहीं है।

$S\in N$ एक विशेष रूप से नामित प्रारम्भिक प्रतीक है।^[1]^: 220

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

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

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

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

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

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

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

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

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

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

यह भी देखें

लैम्ब्डा कैलकुलस
सेमी-थू सिस्टम - टर्मिनल और नॉनटर्मिनल प्रतीकों में अंतर नहीं करता है और रिक्त बाएं क्लास को स्वीकृत करता है।

↑ Actually, $T\cap N=\emptyset$ 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 $L(G)$ recognized by $G$ is restricted to strings of terminal symbols.
↑ While Hopcroft and Ullman (1979) do not mention the cardinalities of $N$ , $T$ , $P$ 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 $P$ and finite lengths of all strings in rules of $P$ . Any member of $N$ or $T$ that does not occur in $P$ 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.

[2] Actually, $T\cap N=\emptyset$ 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 $L(G)$ recognized by $G$ is restricted to strings of terminal symbols.

[3] While Hopcroft and Ullman (1979) do not mention the cardinalities of $N$ , $T$ , $P$ 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 $P$ and finite lengths of all strings in rules of $P$ . Any member of $N$ or $T$ that does not occur in $P$ can be omitted without affecting the generated language.

[Hopcroft.Ullman.1979-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.

[1]

[note 1]

[note 2]

@@ Line 1: / Line 1: @@
-[[ऑटोमेटा सिद्धांत]] में '''अनरिस्ट्रिक्टेड ग्रामर''' क्लास (जिसे सेमी-थ्यू, टाइप-0 या फ्रेज संरचना ग्रामर भी कहा जाता है) [[चॉम्स्की पदानुक्रम|चॉम्स्की हायरार्की]] में ग्रामर की यह सबसे सामान्य क्लास है। अनरिस्ट्रिक्टेड ग्रामर के निर्माण पर कोई प्रतिबंध नहीं लगाया गया है क्योकि अनरिस्ट्रिक्टेड ग्रामर की प्रत्येक बायी क्लास गैर-रिक्त होती है।<ref name="Hopcroft.Ullman.1979"/>{{rp|220}} सामान्यतः यह ग्रामर क्लास अपेक्षाकृत रूप से [[पुनरावर्ती रूप से गणना योग्य भाषा|रिकर्सिवली एनयूमेरबल भाषाएँ]] उत्पन्न कर सकती है।
+[[ऑटोमेटा सिद्धांत]] में '''अनरिस्ट्रिक्टेड ग्रामर''' क्लास (जिसे सेमी-थ्यू, टाइप-0 या फ्रेज स्ट्रक्चर ग्रामर भी कहा जाता है) [[चॉम्स्की पदानुक्रम|चॉम्स्की हायरार्की]] में ग्रामर की यह सबसे सामान्य क्लास है। अनरिस्ट्रिक्टेड ग्रामर के निर्माण पर कोई प्रतिबंध नहीं लगाया गया है क्योकि अनरिस्ट्रिक्टेड ग्रामर की प्रत्येक बायी क्लास गैर-रिक्त होती है।<ref name="Hopcroft.Ullman.1979"/>{{rp|220}} सामान्यतः यह ग्रामर क्लास अपेक्षाकृत रूप से [[पुनरावर्ती रूप से गणना योग्य भाषा|रिकर्सिवली एनयूमेरबल भाषाएँ]] उत्पन्न कर सकती है।
 == औपचारिक परिभाषा ==
@@ Line 43: / Line 43: @@
 {{Formal languages and grammars}}
-[[Category: औपचारिक भाषाएँ]]
+[[Category:All articles with unsourced statements]]
+[[Category:Articles with unsourced statements from February 2017]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 25/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:औपचारिक भाषाएँ]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 15:27, 30 August 2023

Contents

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 15:27, 30 August 2023

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories