अनरिस्ट्रिक्टेड ग्रामर: Difference between revisions
From Vigyanwiki
(Created page with "ऑटोमेटा सिद्धांत में, अप्रतिबंधित व्याकरणों का वर्ग (जिसे सेमी-थ...") |
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>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> एक विशेष रूप से नामित प्रारंभ प्रतीक है।<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}} | * <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> | जैसा कि नाम से पता चलता है, अप्रतिबंधित व्याकरण के उत्पादन नियमों के प्रकारों पर कोई वास्तविक प्रतिबंध नहीं है।<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>\beta \to \gamma</math> में प्रस्तुतियों से <math>G</math>. | # गैर-नियतात्मक एल्गोरिदम एक उत्पादन चुनें <math>\beta \to \gamma</math> में प्रस्तुतियों से <math>G</math>. | ||
# | # यदि <math>\beta</math> दूसरे टेप पर किसी स्थान पर दिखाई देता है, तो उस बिंदु पर <math>\beta</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> को पुनरावर्ती रूप से गणना योग्य होना चाहिए। | ||
विपरीत निर्माण भी संभव है. कुछ ट्यूरिंग मशीन को देखते हुए, एक समतुल्य अप्रतिबंधित व्याकरण बनाना संभव है<ref name="Hopcroft.Ullman.1979"/>{{rp|222}} जो केवल | विपरीत निर्माण भी संभव है. कुछ ट्यूरिंग मशीन को देखते हुए, एक समतुल्य अप्रतिबंधित व्याकरण बनाना संभव है<ref name="Hopcroft.Ullman.1979"/>{{rp|222}} जो केवल बायीं ओर एक या अधिक गैर-टर्मिनल प्रतीकों वाली प्रस्तुतियों का उपयोग करता है। इसलिए, एक मनमाना अप्रतिबंधित व्याकरण को हमेशा ट्यूरिंग मशीन में परिवर्तित करके और फिर से बाद वाले फॉर्म का पालन करने के लिए समान रूप से परिवर्तित किया जा सकता है। कुछ लेखक {{cn|date=February 2017}} अप्रतिबंधित व्याकरण की परिभाषा के रूप में बाद वाले रूप का उपयोग करते हैं। | ||
== कम्प्यूटेशनल गुण == | == कम्प्यूटेशनल गुण == | ||
किसी दिए गए स्ट्रिंग | किसी दिए गए स्ट्रिंग को किसी अप्रतिबंधित व्याकरण द्वारा उत्पन्न किया जा सकता है या नहीं, इसकी निर्णय समस्या इस समस्या के बराबर है कि क्या इसे व्याकरण के समकक्ष ट्यूरिंग मशीन द्वारा स्वीकार किया जा सकता है। बाद वाली समस्या को हॉल्टिंग समस्या कहा जाता है और यह अनिर्णीत है। | ||
पुनरावर्ती रूप से गणना योग्य भाषाएं [[क्लेन स्टार]] | पुनरावर्ती रूप से गणना योग्य भाषाएं [[क्लेन स्टार]], कॉन्सटेनेशन, यूनियन और इंटरसेक्शन के तहत बंद हैं, लेकिन सेट अंतर के तहत नहीं, पुनरावर्ती रूप से गणना योग्य भाषा # क्लोजर गुण देखें। | ||
ट्यूरिंग मशीनों के लिए अप्रतिबंधित व्याकरणों की समानता एक सार्वभौमिक अप्रतिबंधित व्याकरण के अस्तित्व को दर्शाती है, एक व्याकरण जो भाषा का विवरण दिए जाने पर किसी भी अन्य अप्रतिबंधित व्याकरण की भाषा को स्वीकार करने में सक्षम है। इस कारण से, अप्रतिबंधित व्याकरण (जैसे | ट्यूरिंग मशीनों के लिए अप्रतिबंधित व्याकरणों की समानता एक सार्वभौमिक अप्रतिबंधित व्याकरण के अस्तित्व को दर्शाती है, एक व्याकरण जो भाषा का विवरण दिए जाने पर किसी भी अन्य अप्रतिबंधित व्याकरण की भाषा को स्वीकार करने में सक्षम है। इस कारण से, अप्रतिबंधित व्याकरण (जैसे थ्यू ([[प्रोग्रामिंग भाषा]])) के आधार पर एक प्रोग्रामिंग भाषा बनाना सैद्धांतिक रूप से संभव है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
Revision as of 19:51, 1 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.
