रिकर्सिव लैंग्वेज

This article is about गणित और सैद्धांतिक कंप्यूटर विज्ञान में अध्ययन की जाने वाली औपचारिक भाषाओं की एक कक्षा. For कंप्यूटर भाषाएँ जो किसी फ़ंक्शन को खुद को पुनरावर्ती रूप से कॉल करने की अनुमति देती हैं, see रिकर्सन (कंप्यूटर विज्ञान).

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

निर्णायकता की अवधारणा को संगणना के अन्य मॉडलों तक बढ़ाया जा सकता है। उदाहरण के लिए, कोई गैर-नियतात्मक ट्यूरिंग मशीन पर निर्णायक भाषाओं की बात कर सकता है। इसलिए, जब भी कोई अस्पष्टता संभव हो, पुनरावर्ती भाषा के लिए प्रयुक्त पर्यायवाची ट्यूरिंग-निर्णायक भाषा है, न कि केवल निर्णायक।

सभी पुनरावर्ती भाषाओं के वर्ग को अक्सर R (जटिलता) कहा जाता है, हालाँकि इस नाम का उपयोग वर्ग RP (जटिलता) के लिए भी किया जाता है।

इस प्रकार की भाषा को चॉम्स्की पदानुक्रम में परिभाषित नहीं किया गया था (चोमस्की 1959). सभी पुनरावर्ती भाषाएँ भी पुनरावर्ती रूप से गणना योग्य भाषा हैं। सभी नियमित भाषा, संदर्भ-मुक्त भाषा|संदर्भ-मुक्त और संदर्भ-संवेदनशील भाषा|संदर्भ-संवेदनशील भाषाएं पुनरावर्ती हैं।

परिभाषाएँ

पुनरावर्ती भाषा की अवधारणा के लिए दो समतुल्य प्रमुख परिभाषाएँ हैं:

1. एक पुनरावर्ती औपचारिक भाषा औपचारिक भाषा के वर्णमाला पर सभी संभावित शब्दों के सेट (गणित) में एक पुनरावर्ती सेट सबसेट है।
2. एक पुनरावर्ती भाषा एक औपचारिक भाषा है जिसके लिए एक ट्यूरिंग मशीन मौजूद है, जो किसी भी परिमित इनपुट शाब्दिक स्ट्रिंग के साथ प्रस्तुत की जाती है, यदि स्ट्रिंग भाषा में है, तो रुक जाती है और स्वीकार कर लेती है, और अन्यथा रुक जाती है और अस्वीकार कर देती है। ट्यूरिंग मशीन हमेशा रुकती है: इसे एक ऐसी मशीन के रूप में जाना जाता है जो हमेशा रुकती है और कहा जाता है कि यह पुनरावर्ती भाषा तय करती है।

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

उदाहरण

जैसा कि ऊपर उल्लेख किया गया है, प्रत्येक संदर्भ-संवेदनशील भाषा पुनरावर्ती है। इस प्रकार, पुनरावर्ती भाषा का एक सरल उदाहरण समुच्चय L={abc, aabbcc, aaabbbccc, ...}; अधिक औपचारिक रूप से, सेट

$L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}$ संदर्भ-संवेदनशील है और इसलिए पुनरावर्ती है।

निर्णायक भाषाओं के उदाहरण जो संदर्भ-संवेदनशील नहीं हैं, उनका वर्णन करना अधिक कठिन है। इस तरह के एक उदाहरण के लिए, गणितीय तर्क के साथ कुछ परिचित होना आवश्यक है: प्रेस्बर्गर अंकगणित जोड़ के साथ (लेकिन गुणा के बिना) प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत है। जबकि प्रेस्बर्गर अंकगणित में फर्स्ट-ऑर्डर_लॉजिक#फॉर्मूला|सुव्यवस्थित सूत्रों का सेट संदर्भ-मुक्त है, प्रेस्बर्गर अंकगणित में सही कथनों के सेट को स्वीकार करने वाली प्रत्येक नियतात्मक ट्यूरिंग मशीन में कम से कम सबसे खराब स्थिति वाला रनटाइम होता है $2^{2^{cn}}$, कुछ निरंतर सी> 0 के लिए (फिशर & राबिन 1974). यहाँ, n दिए गए सूत्र की लंबाई को दर्शाता है। चूंकि प्रत्येक संदर्भ-संवेदनशील भाषा को एक रैखिक बाउंडेड ऑटोमेटन द्वारा स्वीकार किया जा सकता है, और इस तरह के एक ऑटोमेटन को नियतात्मक ट्यूरिंग मशीन द्वारा सिम्युलेटेड किया जा सकता है, जिसमें सबसे खराब समय चलने वाला समय होता है। $c^{n}$ कुछ निरंतर सी के लिए, प्रेस्बर्गर अंकगणित में मान्य सूत्रों का सेट संदर्भ-संवेदनशील नहीं है। सकारात्मक पक्ष पर, यह ज्ञात है कि एक नियतात्मक ट्यूरिंग मशीन है जो n में सबसे अधिक त्रिगुणात्मक घातीय समय पर चल रही है जो प्रेस्बर्गर अंकगणित में सही सूत्रों का सेट तय करती है (ओपन 1978). इस प्रकार, यह एक ऐसी भाषा का उदाहरण है जो निर्णायक है लेकिन संदर्भ-संवेदनशील नहीं है।

क्लोजर गुण

पुनरावर्ती भाषाएं निम्नलिखित संक्रियाओं के अंतर्गत क्लोजर (गणित) हैं। अर्थात्, यदि L और P दो पुनरावर्ती भाषाएँ हैं, तो निम्नलिखित भाषाएँ भी पुनरावर्ती हैं:

• क्लेन स्टार $L^{*}$
• इमेज φ(L) एक होमोमोर्फिज्म के तहत #औपचारिक भाषा सिद्धांत|ई-फ्री होमोमोर्फिज्म φ
• संधि $L\circ P$
• संगठन $L\cup P$
• चौराहा $L\cap P$
• का पूरक $L$
• निर्धारित अंतर $L-P$

अंतिम संपत्ति इस तथ्य से अनुसरण करती है कि सेट अंतर को प्रतिच्छेदन और पूरक के रूप में व्यक्त किया जा सकता है।

यह भी देखें

• पुनरावर्ती गणना योग्य भाषा
• संगणनीय सेट
• पुनरावर्तन

संदर्भ

• Michael Sipser (1997). "Decidability". Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 978-0-534-94728-6.
• Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.
• Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41.
• Oppen, Derek C. (1978). "A 2^22pn Upper Bound on the Complexity of Presburger Arithmetic". J. Comput. Syst. Sci. 16 (3): 323–332. doi:10.1016/0022-0000(78)90021-1.