Computer Science · Theory of Computation

निम्नलिखित में से कौन-सा/से कथन सत्य है/हैं? S1: प्रत्येक बाएँ-पुनरावर्ती (left-recursive) व्याकरण को दाएँ-पुनरावर्ती (right-recursive) व्याकरण में और इसके विपरीत बदला जा सकता है। S2: चॉम्स्की नॉर्मल फॉर्म (Chomsky normal form) में संदर्भ-मुक्त व्याकरण द्वारा उत्पन्न स्ट्रिंग्स के व्युत्पत्ति वृक्ष (derivation trees) हमेशा लगभग पूर्ण बाइनरी वृक्ष होते हैं। S3: पुनरावर्ती रूप से गणनीय सेट (recursively enumerable set) का प्रत्येक उपसमुच्चय पुनरावर्ती (recursive) होता है।