Recursively Enumerable Language MCQ Quiz in हिन्दी - Objective Question with Answer for Recursively Enumerable Language - मुफ्त [PDF] डाउनलोड करें
Last updated on Apr 7, 2025
Latest Recursively Enumerable Language MCQ Objective Questions
Recursively Enumerable Language Question 1:
निम्नलिखित में से कौन सा कथन असत्य है?
Answer (Detailed Solution Below)
Recursively Enumerable Language Question 1 Detailed Solution
- DFA की शक्ति NFA के बराबर है इसलिए प्रत्येक NFA को तुल्य DFA में परिवर्तित किया जा सकता है और साथ ही प्रत्येक DFA को तुल्य NFA में परिवर्तित किया जा सकता है।
- DTM की शक्ति NTM के बराबर है इसलिए प्रत्येक NTM को तुल्य DTM में बदला जा सकता है और साथ ही प्रत्येक DTM को तुल्य NTM में बदला जा सकता है।
- नियमित भाषा प्रसंग-मुक्त भाषा का एक उपसमुच्चय है, इसलिए प्रत्येक नियमित भाषा एक प्रसंग-मुक्त भाषा है
- पुनरावर्ती भाषा, पुनरावर्ती गणनीय भाषा का उपसमुच्चय है, इसलिए आवर्ती गणनीय समुच्चय का उपसमुच्चय पुनरावर्ती हो भी सकता है और नहीं भी।
चॉम्स्की अनुक्रम:
अतः विकल्प 2 सही उत्तर है।
Recursively Enumerable Language Question 2:
सभी पुनरावर्ती गणना योग्य भाषाओं का सेट क्या है?
Answer (Detailed Solution Below)
Recursively Enumerable Language Question 2 Detailed Solution
C गलत है क्योंकि सभी पुनरावर्ती गणना योग्य भाषाओं (अर्ध-निर्णायक) का सेट सभी पुनरावर्ती भाषाओं (निर्णायक) के सेट का एक STRICT सुपर सेट है।
D गलत है क्योंकि सभी पुनरावर्ती गणना योग्य भाषाओं (सभी ट्यूरिंग मशीनों का सेट) का सेट एक अनंत लेकिन गणनीय सेट है।
Top Recursively Enumerable Language MCQ Objective Questions
सभी पुनरावर्ती गणना योग्य भाषाओं का सेट क्या है?
Answer (Detailed Solution Below)
Recursively Enumerable Language Question 3 Detailed Solution
Download Solution PDFC गलत है क्योंकि सभी पुनरावर्ती गणना योग्य भाषाओं (अर्ध-निर्णायक) का सेट सभी पुनरावर्ती भाषाओं (निर्णायक) के सेट का एक STRICT सुपर सेट है।
D गलत है क्योंकि सभी पुनरावर्ती गणना योग्य भाषाओं (सभी ट्यूरिंग मशीनों का सेट) का सेट एक अनंत लेकिन गणनीय सेट है।
निम्नलिखित में से कौन सा कथन असत्य है?
Answer (Detailed Solution Below)
Recursively Enumerable Language Question 4 Detailed Solution
Download Solution PDF- DFA की शक्ति NFA के बराबर है इसलिए प्रत्येक NFA को तुल्य DFA में परिवर्तित किया जा सकता है और साथ ही प्रत्येक DFA को तुल्य NFA में परिवर्तित किया जा सकता है।
- DTM की शक्ति NTM के बराबर है इसलिए प्रत्येक NTM को तुल्य DTM में बदला जा सकता है और साथ ही प्रत्येक DTM को तुल्य NTM में बदला जा सकता है।
- नियमित भाषा प्रसंग-मुक्त भाषा का एक उपसमुच्चय है, इसलिए प्रत्येक नियमित भाषा एक प्रसंग-मुक्त भाषा है
- पुनरावर्ती भाषा, पुनरावर्ती गणनीय भाषा का उपसमुच्चय है, इसलिए आवर्ती गणनीय समुच्चय का उपसमुच्चय पुनरावर्ती हो भी सकता है और नहीं भी।
चॉम्स्की अनुक्रम:
अतः विकल्प 2 सही उत्तर है।
Recursively Enumerable Language Question 5:
सभी पुनरावर्ती गणना योग्य भाषाओं का सेट क्या है?
Answer (Detailed Solution Below)
Recursively Enumerable Language Question 5 Detailed Solution
C गलत है क्योंकि सभी पुनरावर्ती गणना योग्य भाषाओं (अर्ध-निर्णायक) का सेट सभी पुनरावर्ती भाषाओं (निर्णायक) के सेट का एक STRICT सुपर सेट है।
D गलत है क्योंकि सभी पुनरावर्ती गणना योग्य भाषाओं (सभी ट्यूरिंग मशीनों का सेट) का सेट एक अनंत लेकिन गणनीय सेट है।
Recursively Enumerable Language Question 6:
निम्नलिखित में से कौन सा कथन असत्य है?
Answer (Detailed Solution Below)
Recursively Enumerable Language Question 6 Detailed Solution
- DFA की शक्ति NFA के बराबर है इसलिए प्रत्येक NFA को तुल्य DFA में परिवर्तित किया जा सकता है और साथ ही प्रत्येक DFA को तुल्य NFA में परिवर्तित किया जा सकता है।
- DTM की शक्ति NTM के बराबर है इसलिए प्रत्येक NTM को तुल्य DTM में बदला जा सकता है और साथ ही प्रत्येक DTM को तुल्य NTM में बदला जा सकता है।
- नियमित भाषा प्रसंग-मुक्त भाषा का एक उपसमुच्चय है, इसलिए प्रत्येक नियमित भाषा एक प्रसंग-मुक्त भाषा है
- पुनरावर्ती भाषा, पुनरावर्ती गणनीय भाषा का उपसमुच्चय है, इसलिए आवर्ती गणनीय समुच्चय का उपसमुच्चय पुनरावर्ती हो भी सकता है और नहीं भी।
चॉम्स्की अनुक्रम:
अतः विकल्प 2 सही उत्तर है।
Recursively Enumerable Language Question 7:
निम्नलिखित में से कौन-सा कथन सही नहीं है?
Answer (Detailed Solution Below)
Recursively Enumerable Language Question 7 Detailed Solution
सही उत्तर विकल्प 4 है।
Key Points
- विकल्प 1 - सत्य: पुनरावर्ती (निर्णायक) भाषाएँ पूरक के अंतर्गत बंद होती हैं। यदि कोई भाषा पुनरावर्ती है, तो उसका पूरक भी पुनरावर्ती है।
- विकल्प 2 - सत्य: प्रत्येक पुनरावर्ती भाषा पुनरावर्ती रूप से गणनीय (RE) भी होती है, और इसका पूरक भी RE है क्योंकि यह पुनरावर्ती है (मजबूत स्थिति)।
- विकल्प 3 - सत्य: यदि कोई भाषा और उसका पूरक दोनों पुनरावर्ती रूप से गणनीय हैं, तो भाषा पुनरावर्ती है। यह संगणनीय सिद्धांत में एक प्रसिद्ध परिणाम है।
- विकल्प 4 - असत्य: यदि कोई भाषा पुनरावर्ती रूप से गणनीय है, तो उसका पूरक जरूरी नहीं कि पुनरावर्ती रूप से गणनीय हो।
- उदाहरण: हॉल्टिंग समस्या पुनरावर्ती रूप से गणनीय है लेकिन इसका पूरक नहीं है।
- यह एक मानक प्रति-उदाहरण है जो दर्शाता है कि RE भाषाएँ पूरक के अंतर्गत बंद नहीं होती हैं।
Additional Information
- पुनरावर्ती भाषाएँ: ट्यूरिंग मशीनें हमेशा रुकती हैं और सदस्यता का निर्णय करती हैं।
- रिकर्सिवली एन्यूमरेबल (RE): ट्यूरिंग मशीनें कुछ इनपुट पर नहीं रुक सकती हैं; वे केवल भाषा के सदस्यों को स्वीकार करती हैं।
- समावेशन गुण:
- पुनरावर्ती भाषाएँ संघ, प्रतिच्छेदन और पूरक के अंतर्गत बंद होती हैं।
- RE भाषाएँ संघ और प्रतिच्छेदन के अंतर्गत बंद होती हैं, लेकिन पूरक के अंतर्गत नहीं।
इसलिए, सही उत्तर है: विकल्प 4) यदि कोई भाषा पुनरावर्ती रूप से गणनीय है, तो उसका पूरक भी पुनरावर्ती रूप से गणनीय है — जो सत्य नहीं है।