यह निर्धारित करने के लिए कि कोई भाषा रिकर्सिव या रिकर्सिव रूप से गणना योग्य है या नहीं?

Question

मुझे यह निर्धारित करना है कि कोई भाषा (उदाहरण के लिए एल = {ए^एनबी^एमसी^एस 0 < = एन < = एम < = एस}) नियमित, संदर्भ मुक्त, पुनरावर्ती, पुनरावर्ती संख्यात्मक या उनमें से कोई भी नहीं है ।

मुझे पता है कि यह निर्धारित करने के लिए कि कोई भाषा नियमित है या नहीं (एक डीएफए या नियमित अभिव्यक्ति जो काम करती है) या संदर्भ मुक्त (पीडीए या संदर्भ-मुक्त व्याकरण जो काम करता है) ढूंढें; मुझे पता है कि एक पुनरावर्ती भाषा में एक ट्यूरिंग मशीन होती है जो हमेशा रोकती है और एक पुनरावर्ती संख्यात्मक भाषा में एक ट्यूरिंग मशीन होती है जो रोक नहीं सकती है।

तो सवाल यह है कि क्या यह निर्धारित करने के लिए एक तेज मानदंड है कि भाषा रिकर्सिव या रिकर्सिव रूप से गणना योग्य है या न ही? उदाहरण के लिए, मुझे यह समझने के लिए पीडीए बनाने की ज़रूरत नहीं है कि एक भाषा संदर्भ-मुक्त है, मैं इसे इस तथ्य से नहीं देख सकता कि इसे एक ढेर की आवश्यकता है; क्या समस्या के लिए एक समान तेज़ दृष्टिकोण है (उम्मीद है कि ट्यूरिंग मशीन बनाने के लिए परेशानी बचाती है)?

Answer 1

यह जांचने के लिए कोई संरचनात्मक तरीका नहीं है कि कोई भाषा रिकर्सिव रूप से गणना करने योग्य बनाम है या नहीं। वास्तव में वास्तव में एक अच्छा सबूत है जो कहता है कि रिकर्सिव भाषाओं को पहचानने में सक्षम किसी भी automaton के लिए, आर में कम से कम एक आरई भाषा नहीं है जो automaton भी स्वीकार करता है; यह विकर्णता तर्क का एक रूप है जिसका उपयोग आप अनावश्यक समस्याओं के अस्तित्व को दिखाने के लिए करते हैं।

मुख्य भाषा जिसमें आप एक भाषा साबित करते हैं, आरई में है, लेकिन आर यह साबित करना है कि भाषा आरई (शायद इसके लिए एक टीएम परिभाषित करके) में है, फिर आरई में ज्ञात समस्या को कम करने के लिए, लेकिन आर मुसीबत। उदाहरण के लिए, यदि आप दिखा सकते हैं कि रोकथाम की समस्या का कोई भी उदाहरण इसे आपकी समस्या के उदाहरण में परिवर्तित करके हल किया जा सकता है, तो आप जानते हैं कि इसमें एक पुनरावर्ती समाधान नहीं हो सकता है, और यदि आप इसे टीएम के साथ पालन करते हैं भाषा आप जानते हैं कि भाषा आरई में है। साथ में, आपके पास आरई में एक भाषा है लेकिन आर

Answer 2

संदर्भ के लिए मुफ्त भाषा एक त्वरित विधि केवल तुलनाओं की संख्या देखती है।
उदाहरण में n<=m और m<=s देखें। तो इसमें दो तुलना शामिल हैं। तो आप इसे आसानी से बता सकते हैं कि यह संदर्भ मुक्त नहीं है। यदि एक एकल तुलना शामिल है तो इसे संदर्भ मुक्त भाषा के रूप में कॉल करें।

नियमित भाषाओं के साथ ही मामला है। दो चर के बीच कोई संबंध नहीं होना चाहिए, मेरा मतलब है कि किसी भी प्रकार की तुलना नहीं होनी चाहिए। उदाहरण के लिए भाषाओं पर विचार करें- 0^m+n 1^n 0^m। ध्यान से देखें कि केवल एक ही तुलना की गई है जो m+n = n+m (प्रतीकों को धक्का और पॉपिंग) है, इसलिए यह संदर्भ मुक्त है।
अब 0^n+m 1^n+m 0^m देखें पहले 2 और अगले दो के बीच की तुलना स्पष्ट रूप से देखें।

मुझे इसे समझने में कुछ समय लगा। लेकिन निर्णय लेने के लिए कुछ लोग इसे लेंगे। मेरा विश्वास करो यह वास्तव में काम करता है। नियमित भाषा के लिए अंतिम उदाहरण यहां दिया गया है। a^n b^2m नियमित रूप से है (वहाँ n और मीटर के बीच कोई तुलना नहीं कर रहे हैं देखें) और {a^n b^m |n=2m} संदर्भ मुक्त है के रूप में यह केवल एक तुलना (नियमित नहीं)

आशा इस मदद करता है