Bissoy.com
Doctors Medicines MCQs Q&A

Which of the following statement(s) is/are TRUE? (i) The family of context-free languages are the proper subset of the family of regular languages. (ii) The family of recursive languages is a proper subset of the family of recursively enumerable languages.

Which of the following statement(s) is/are TRUE? (i) The family of context-free languages are the proper subset of the family of regular languages. (ii) The family of recursive languages is a proper subset of the family of recursively enumerable languages. Correct Answer Only (ii)

The correct answer is option 4.

Concept:

Option 1: The family of context-free languages is the proper subset of the family of regular languages.

False, The set of all context-free languages is identical to the set of languages accepted by pushdown automata, and the set of regular languages is a subset of context-free languages

Option 2: The family of recursive languages is a proper subset of the family of recursively enumerable languages.

True, There exists a recursively enumerable language that is not recursive; that is, the family of recursive languages is a proper subset of the family of recursively enumerable languages.

Hence the correct answer is Only (ii).

[ alt="F1 Harshita 14-2-22 Savita D1" src="//storage.googleapis.com/tb-img/production/22/02/F1_Harshita%20_14-2-22_Savita_D1.png" style="width: 475px; height: 407px;">

Related Questions

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. L̅1 (complement of L1) is recursive II. L̅2 (complement of L2) is recursive III. L̅1 is context-free IV. L̅1 ∪ L2 is recursively enumerable
Which of the following statement(s) is/are FALSE? (i) There exists a recursively enumerable language whose complement is not recursively enumerable. (ii) If a language L is recursive, then its complement is NOT recursive.
Assume statements S1 and S2 defined as: S1: L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turing machines is countable. Which of the following is true?
Choose the correct option: Statement: If L1 and L2 are recursively enumerable languages over S, then the following is/are recursively enumerable.
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y̅ reduces to W, and Z reduces to X̅ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0,1} S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet {0,1} S4. Set of all non-regular languages over the alphabet {0,1} Which of the above sets are uncountable?
Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?
Which of the following statements about Regular Expression is/are incorrect? A. The union of two regular expressions is also a regular expression B. The concatenation of two regular expressions is also a regular expression C. The iteration of a regular expression is also a regular expression
Given the following statements: (i) Recursive enumerable sets are closed under complementation. (ii) Recursive sets are closed under complements. Which is/are the correct statements?