• » When is the International Literacy Day observed every year? » 8th September
• » आयुष मंत्रालय ने व्यक्तिगत (अंतरराष्ट्रीय) श्रेणी में किसे 'प्रधानमंत्री योग पुरस्कार 2019' दिए जाने की घोषणा जून, 2019 में की- » अन्‍तोनिएता रोजी, इटली
• » वह अरब राष्ट्र जो की 'फाइनेंशियल एक्शन टास्क फोर्स' (FATF) की पूर्ण सदस्यता प्राप्त करने वाला पहला अरब देश जून, 2019 में बना- » सऊदी अरब
• » भारत ने किस देश को 3-1 से पराजित कर 'वुमेन एफआईएच सीरीज फाइनल हॉकी टूर्नामेंट' का खिताब 23 जून, 2019 को जीता? » जापान
• » भाजपा सांसद ओम बिरला राजस्थान के किस संसदीय क्षेत्र से सांसद चुने गए हैं; जिन्हें 17वीं लोकसभा का अध्यक्ष 19 जून, 2019 को चुना गया? » कोटा-बूंदी
If you find this context important and usefull. We request to all visitors to sheare this with your friends on social networking channels.

## THEORY OF COMPUTATION 6

THEORY OF COMPUTATION 6

# Q101. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs that generate infinte languages} And L1={<G,G’,1>|G,G’ are the encodings of cfgs that either one or both do not generate infinite sets}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ102. Let L0={<G,G’,0>|G,G’ are the encodings of csgs that generate the same set} And L1={<G,G’,1>|G,G’ are the encodings of csgs that either one or both do generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ103. Let L0={<G,G’,0>|G,G’ are the encodings of unrestricted grammars that generate the same set} And L1={<G,G’,1>|G,G’ are the encodings of unrestricted grammars that either one or both do generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ104. Let L0={<G,G’,0>|G,G’ are the encodings of linear bounded automata that generate the same set} And L1={<G,G’,1>|G,G’ are the encodings of linear bounded automata that either one or both do generate the same set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ105. Let L0={<G,G’,0>|G,G’ are the encodings of unrestricted grammars such that they generate L and LR respectively with L=LR} And L1={<G,G’,1>|G,G’ are the encodings of unrestricted grammars that generate languages L and LR with L not the same as LR respectively}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ106. Let L0={<G,G’,0>|G,G’ are the encodings of C programs that produce the same output for all inputs} And L1={<G,G’,1>|G,G’ are the encodings of C programs that do not produce the same output for all inputs}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ107. Let L0={<G,G’,0>|G,G’ are the encodings of C programs that produce some output for all inputs} And L1={<G,G’,1>|G,G’ are the encodings of C programs that do not produce some output for all inputs}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ108. Let L0={<G,G’,0>|G,G’ are the encodings of C programs that loop on some input} And L1={<G,G’,1>|G,G’ are the encodings of C programs that do not loop on some input}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ109. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs where the intersection of the langugaes generated is a cfl} And L1={<G,G’,1>|G,G’ are the encodings of cfgs where the intersection of the languages generated is not a cfl}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ110. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs that generate regular sets} And L1={<G,G’,1>|G,G’ are the encodings of cfs that both or either does not generate a regular set}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ111. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs such that L(G’) is contained in L(G)} And L1={<G,G’,1>|G,G’ are the encodings of cfgs sucht that L(G’) is not contained in L(G)}. Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ112. Let L0={<G,G’,0>|G,G’ are the encodings of cfgs which generate languages whose complement is also a cfl} And L1={<G,G’,1>|G,G’ are the encodings of C programs that generate languages whose complement is not both a cfl}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ113. Let L0={<G,G’,0>|G,G’ are the encodings of ambiguous cfgs} And L1={<G,G’,1>|G,G’ are the encodings of unambiguous cfgs}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ114. Let L0={<G,G’,0>|G,G’ are the encodings of inherently ambiguous cflss} And L1={<G,G’,1>|G,G’ are the encodings of cfls that are not inherently ambiguous}.Let L=L0UL1. Let L’ be the complement of L. Choose the correct statement a)L is recursively enumerable but not recursive and L’ is recursive b) L is recursive and L’ is recursively enumerable c) L is not recursively enumerable and L’ is recursive d) Neither L nor L’ is recursively enumerableQ115. Choose the false statement a) PCP over a one symbol alphabet is decidable b) It is undecidable if a csl is a cfl c) It is undecidable if a turing machine accepts at least 10 inputs d) It is undecidable if two regular grammars generate the same setQ116. Define languages L0 and L1 as follows: L0={<M,M1,0>|M is equivalent to M1} L1={<M,M1,1>| M is not equivalent to M1} Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a nondeterministic linear bounded automaton, and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerableQ117. Define languages L0 and L1 as follows: L0={<M,M1,0>|M is equivalent to M1} L1={<M,M1,1>| M is not equivalent to M1} Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing machine , second component M1 is the encoding of a 100 tape nondeterministic turing machine that halts on all inputs, and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d) Neither L nor L’ is recursively enumerableQ118. Define languages L0 and L1 as follows: L0={<M,w,0>|M in the course of its computation visits state w} L1={<M,w,1>| M does not halt visit state w} Here <M,w,I> is a triplet, whose first component, M is an encoding of a nondeterministic 789 pushdown tape machine , second component w, is a state and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d)Neither L nor L’ is recursively enumerableQ119. Define languages L0 and L1 as follows: L0={<M,w,0>|M prints symbol w} L1={<M,w,1>| M never prints symbol w} Here <M,w,I> is a triplet, whose first component, M is an encoding of a nondeterministic 789 pushdown tape machine , second component w, is a symbol and third component I is a bit. Let L=L0 U L1. Which of the following is true? (a) L is recursively enumerable but L’ is not (b) L’ is recursively enumerable but L is not (c) Both L and L’ are recursive (d)Neither L nor L’ is recursively enumerable

## Tags

#

06 Jun, 2020, 14:20:51 PM