रिकर्सिवली एन्युमरेबल लैंग्वेज: Difference between revisions
From Vigyanwiki
m (Abhishek moved page पुनरावर्ती गणना लैंग्वेज to रिकर्सिवली एन्युमरेबल लैंग्वेज without leaving a redirect) |
|||
| Line 1: | Line 1: | ||
{{short description|Formal language}} | {{short description|Formal language}} | ||
गणित, [[तर्क]] और [[कंप्यूटर विज्ञान]] में, एक [[औपचारिक भाषा]] को '''रिकर्सिवली एन्युमरेबल लैंग्वेज''' ( | गणित, [[तर्क]] और [[कंप्यूटर विज्ञान]] में, एक [[औपचारिक भाषा|फॉर्मल लैंग्वेज]] को '''रिकर्सिवली एन्युमरेबल लैंग्वेज''' (पार्शियली डिसाइडेबल, सेमीडिसाइडेबल, ट्यूरिंग-अक्सेप्टबल या ट्यूरिंग-रेकॉग्निजबल) कहा जाता है यदि यह लैंग्वेज के [[वर्णमाला (कंप्यूटर विज्ञान)|एल्फाबेट (कंप्यूटर विज्ञान)]] के सभी संभावित शब्दों के [[सेट (गणित)]] में रिकर्सिवली एन्युमरेबल सेट है अर्थात्, यदि कोई [[ट्यूरिंग मशीन]] उपस्थित है जो लैंग्वेज के सभी वैलिड स्ट्रिंग की गणना करेगी। | ||
फॉर्मल लैंग्वेज के [[चॉम्स्की पदानुक्रम|चॉम्स्की हायरार्की]] में रिकर्सिवली एन्युमरेबल लैंग्वेज को टाइप-0 लैंग्वेज के रूप में जाना जाता है। सभी [[नियमित भाषा|रेगुलर लैंग्वेज]], [[संदर्भ-मुक्त व्याकरण|कॉन्टेक्स्ट-फ्री]], [[संदर्भ-संवेदनशील भाषा|कॉन्टेक्स्ट-सेंसिटिव]] और [[पुनरावर्ती भाषा|रिकर्सिव]] लैंग्वेज रिकर्सिवली एन्युमरेबल हैं। | |||
सभी रिकर्सिवली एन्युमरेबल लैंग्वेज के वर्ग को [[आरई (जटिलता)]] कहा जाता है। | सभी रिकर्सिवली एन्युमरेबल लैंग्वेज के वर्ग को [[आरई (जटिलता)]] कहा जाता है। | ||
| Line 10: | Line 10: | ||
# एक रिकर्सिवली एन्युमरेबल लैंग्वेज जो वर्णमाला पर सभी संभावित शब्दों के [[सबसेट|सेट]](गणित) में एक रिकर्सिवली एन्युमरेबल उपसमुच्चय है। | # एक रिकर्सिवली एन्युमरेबल लैंग्वेज जो वर्णमाला पर सभी संभावित शब्दों के [[सबसेट|सेट]](गणित) में एक रिकर्सिवली एन्युमरेबल उपसमुच्चय है। | ||
# रिकर्सिवली एन्युमरेबल लैंग्वेज एक | # रिकर्सिवली एन्युमरेबल लैंग्वेज एक फॉर्मल लैंग्वेज है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) उपस्थित है जो लैंग्वेज के सभी वैलिड स्ट्रिंग की गणना करेगी। ध्यान दें कि यदि लैंग्वेज अपरिमित है तो दी गई गणना एल्गोरिदम का चयन किया जा सकता है जिससे यह पुनरावर्तन से बच सके क्योंकि हम परीक्षण कर सकते हैं कि संख्या n के लिए निर्मित स्ट्रिंग "पहले से ही" उस संख्या के लिए निर्मित है जो n से कम है। यदि यह पहले से ही निर्मित है तो इसके स्थान पर इनपुट n+1 के लिए आउटपुट का उपयोग करें (रिकर्सिवली) किंतु पुनः परीक्षण करें कि क्या यह "नया" है। | ||
# रिकर्सिवली एन्युमरेबल लैंग्वेज एक | # रिकर्सिवली एन्युमरेबल लैंग्वेज एक फॉर्मल लैंग्वेज है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) उपस्थित है जो इनपुट के रूप में लैंग्वेज में किसी भी स्ट्रिंग के साथ प्रस्तुत होने पर रुक जाएगी तथा स्वीकार कर लेगी, किंतु लैंग्वेज में एक स्ट्रिंग के साथ नहीं प्रस्तुत होने पर या तो रुक सकती है और अस्वीकार कर सकती है या सदैव के लिए लूप कर सकती है। इसकी तुलना रिकर्सिव लैंग्वेज से करें जिनके लिए आवश्यक है कि ट्यूरिंग मशीन सभी स्थितियों में रुक जाए। | ||
सभी नियमित भाषा, [[संदर्भ-मुक्त व्याकरण| | सभी [[नियमित भाषा|रेगुलर लैंग्वेज]], [[संदर्भ-मुक्त व्याकरण|कॉन्टेक्स्ट-फ्री]], [[संदर्भ-संवेदनशील भाषा|कॉन्टेक्स्ट-सेंसिटिव]] और रिकर्सिव लैंग्वेज रिकर्सिवली एन्युमरेबल हैं। | ||
पोस्ट के प्रमेय से पता चलता है कि | पोस्ट के प्रमेय से पता चलता है कि '''RE''' अपने [[पूरक (जटिलता)|कम्प्लीमेंट]] co-RE, के साथ [[अंकगणितीय पदानुक्रम|अंकगणितीय]] [[चॉम्स्की पदानुक्रम|हायरार्की]] के प्रथम स्तर के अनुरूप है। | ||
==उदाहरण== | ==उदाहरण== | ||
| Line 27: | Line 27: | ||
==संवृत्त गुण== | ==संवृत्त गुण== | ||
रिकर्सिवली एन्युमरेबल लैंग्वेज(आरईएल) निम्नलिखित परिचालनों के अंतर्गत संवृत्त हैं। अर्थात्, यदि L और P दो रिकर्सिवली एन्युमरेबल लैंग्वेज हैं तो निम्नलिखित | रिकर्सिवली एन्युमरेबल लैंग्वेज(आरईएल) निम्नलिखित परिचालनों के अंतर्गत संवृत्त हैं। अर्थात्, यदि L और P दो रिकर्सिवली एन्युमरेबल लैंग्वेज हैं तो निम्नलिखित लैंग्वेज भी रिकर्सिवली एन्युमरेबल हैं: | ||
* L का द क्लीन स्टार <math>L^*</math> | * L का द क्लीन स्टार <math>L^*</math> | ||
| Line 34: | Line 34: | ||
* [[प्रतिच्छेदन (सेट सिद्धांत)|प्रतिच्छेदन(सेट सिद्धांत)]] <math>L \cap P</math>. | * [[प्रतिच्छेदन (सेट सिद्धांत)|प्रतिच्छेदन(सेट सिद्धांत)]] <math>L \cap P</math>. | ||
रिकर्सिवली एन्युमरेबल लैंग्वेज सेट अंतर या पूरकता के अंतर्गत संवृत्त नहीं होती हैं। यदि <math>P</math> रिकर्सिव है तो सेट अंतर <math>L - P</math> रिकर्सिवली एन्युमरेबल है। यदि <math>L</math> रिकर्सिवली एन्युमरेबल है, तो <math>L</math> का पूरक रिकर्सिवली एन्युमरेबल है यदि और केवल यदि <math>L</math> भी रिकर्सिव है। | रिकर्सिवली एन्युमरेबल लैंग्वेज सेट अंतर या पूरकता (कम्प्लीमेंटशन)के अंतर्गत संवृत्त नहीं होती हैं। यदि <math>P</math> रिकर्सिव है तो सेट अंतर <math>L - P</math> रिकर्सिवली एन्युमरेबल है। यदि <math>L</math> रिकर्सिवली एन्युमरेबल है, तो <math>L</math> का पूरक (कम्प्लीमेंट) रिकर्सिवली एन्युमरेबल है यदि और केवल यदि <math>L</math> भी रिकर्सिव है। | ||
== यह भी देखें == | == यह भी देखें == | ||
* | *कंप्यूटेबली एन्युमरेबल सेट | ||
*रिकर्शन | *रिकर्शन | ||
Revision as of 22:03, 23 July 2023
गणित, तर्क और कंप्यूटर विज्ञान में, एक फॉर्मल लैंग्वेज को रिकर्सिवली एन्युमरेबल लैंग्वेज (पार्शियली डिसाइडेबल, सेमीडिसाइडेबल, ट्यूरिंग-अक्सेप्टबल या ट्यूरिंग-रेकॉग्निजबल) कहा जाता है यदि यह लैंग्वेज के एल्फाबेट (कंप्यूटर विज्ञान) के सभी संभावित शब्दों के सेट (गणित) में रिकर्सिवली एन्युमरेबल सेट है अर्थात्, यदि कोई ट्यूरिंग मशीन उपस्थित है जो लैंग्वेज के सभी वैलिड स्ट्रिंग की गणना करेगी।
फॉर्मल लैंग्वेज के चॉम्स्की हायरार्की में रिकर्सिवली एन्युमरेबल लैंग्वेज को टाइप-0 लैंग्वेज के रूप में जाना जाता है। सभी रेगुलर लैंग्वेज, कॉन्टेक्स्ट-फ्री, कॉन्टेक्स्ट-सेंसिटिव और रिकर्सिव लैंग्वेज रिकर्सिवली एन्युमरेबल हैं।
सभी रिकर्सिवली एन्युमरेबल लैंग्वेज के वर्ग को आरई (जटिलता) कहा जाता है।
परिभाषाएँ
रिकर्सिवली एन्युमरेबल लैंग्वेज की तीन समकक्ष परिभाषाएँ हैं:
- एक रिकर्सिवली एन्युमरेबल लैंग्वेज जो वर्णमाला पर सभी संभावित शब्दों के सेट(गणित) में एक रिकर्सिवली एन्युमरेबल उपसमुच्चय है।
- रिकर्सिवली एन्युमरेबल लैंग्वेज एक फॉर्मल लैंग्वेज है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) उपस्थित है जो लैंग्वेज के सभी वैलिड स्ट्रिंग की गणना करेगी। ध्यान दें कि यदि लैंग्वेज अपरिमित है तो दी गई गणना एल्गोरिदम का चयन किया जा सकता है जिससे यह पुनरावर्तन से बच सके क्योंकि हम परीक्षण कर सकते हैं कि संख्या n के लिए निर्मित स्ट्रिंग "पहले से ही" उस संख्या के लिए निर्मित है जो n से कम है। यदि यह पहले से ही निर्मित है तो इसके स्थान पर इनपुट n+1 के लिए आउटपुट का उपयोग करें (रिकर्सिवली) किंतु पुनः परीक्षण करें कि क्या यह "नया" है।
- रिकर्सिवली एन्युमरेबल लैंग्वेज एक फॉर्मल लैंग्वेज है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) उपस्थित है जो इनपुट के रूप में लैंग्वेज में किसी भी स्ट्रिंग के साथ प्रस्तुत होने पर रुक जाएगी तथा स्वीकार कर लेगी, किंतु लैंग्वेज में एक स्ट्रिंग के साथ नहीं प्रस्तुत होने पर या तो रुक सकती है और अस्वीकार कर सकती है या सदैव के लिए लूप कर सकती है। इसकी तुलना रिकर्सिव लैंग्वेज से करें जिनके लिए आवश्यक है कि ट्यूरिंग मशीन सभी स्थितियों में रुक जाए।
सभी रेगुलर लैंग्वेज, कॉन्टेक्स्ट-फ्री, कॉन्टेक्स्ट-सेंसिटिव और रिकर्सिव लैंग्वेज रिकर्सिवली एन्युमरेबल हैं।
पोस्ट के प्रमेय से पता चलता है कि RE अपने कम्प्लीमेंट co-RE, के साथ अंकगणितीय हायरार्की के प्रथम स्तर के अनुरूप है।
उदाहरण
ट्यूरिंग मशीनों को रोकने का सेट रिकर्सिवली एन्युमरेबल है किंतु रिकर्सिव नहीं है। वास्तव में, कोई ट्यूरिंग मशीन चला सकता है और यदि मशीन रुकती है तो उसे स्वीकार कर सकता है, इसलिए यह रिकर्सिवली एन्युमरेबल है। दूसरी ओर समस्या अनिर्णीत है।
कुछ अन्य रिकर्सिवली एन्युमरेबल लैंग्वेज जो रिकर्सिव नहीं हैं उनमें सम्मिलित हैं:
संवृत्त गुण
रिकर्सिवली एन्युमरेबल लैंग्वेज(आरईएल) निम्नलिखित परिचालनों के अंतर्गत संवृत्त हैं। अर्थात्, यदि L और P दो रिकर्सिवली एन्युमरेबल लैंग्वेज हैं तो निम्नलिखित लैंग्वेज भी रिकर्सिवली एन्युमरेबल हैं:
- L का द क्लीन स्टार
- L और P का संयोजन
- संघ (सेट सिद्धांत)
- प्रतिच्छेदन(सेट सिद्धांत) .
रिकर्सिवली एन्युमरेबल लैंग्वेज सेट अंतर या पूरकता (कम्प्लीमेंटशन)के अंतर्गत संवृत्त नहीं होती हैं। यदि रिकर्सिव है तो सेट अंतर रिकर्सिवली एन्युमरेबल है। यदि रिकर्सिवली एन्युमरेबल है, तो का पूरक (कम्प्लीमेंट) रिकर्सिवली एन्युमरेबल है यदि और केवल यदि भी रिकर्सिव है।
यह भी देखें
- कंप्यूटेबली एन्युमरेबल सेट
- रिकर्शन
संदर्भ
- Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
- Kozen, D.C. (1997), Automata and Computability, Springer.
