Bissoy.com
Doctors Medicines MCQs Q&A

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

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 Correct Answer I and IV only

Properties:

Context free language is not closed under complementation.

Recursively enumerable language is not closed under complementation.

Recursively enumerable language is closed under union.

Recursive languages are closed under complementation.

Explanation:

L1: Context-free

L2: recursively enumerable but not recursive

Statement I:

L̅1 (complement of L1) is recursive → TRUE

Since context free language (L1) is not closed under complementation. Therefore, L̅1 is not context free language.

Complement of context free grammar is context sensitive language and every context sensitive language is recursive language.

Statement II:

L̅2 (complement of L2) is recursive → FALSE

Since recursively enumerable language (L2) is not closed under complementation. Therefore, L̅2 is not recursively enumerable language. If a language is not recursively enumerable then it cannot be recursive for sure. Since recursive language is subset of recursively enumerable language.

Statement III:

L̅1 is context-free → FALSE

Since context free language (L1) is not closed under complementation. Therefore, L̅1 is not context free language.

Statement IV: → TRUE

Since context free language (L1) is not closed under complementation. Therefore, L̅1 is not context free language.

Complement of context free grammar is context sensitive language and every context sensitive language is recursively enumerable language.

Also, recursively enumerable language is closed under union. Therefore, L̅1 ∪ L2 is recursively enumerable.

Related Questions

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.
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.
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?
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?
Choose the correct option: Statement: If L1 and L2 are recursively enumerable languages over S, then the following is/are recursively enumerable.
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?
Study the accompanying Venn diagram that represents groups of persons speaking five different languages as follows. Oblong circle = Marathi ; Rectangle = Kannada, Circle = English, Triangle = Gujarati, Equilateral quadrangle = Hindi Using above information select the false statement/s from following list. (a) Area c represent persons speaking 5 languages but area d represents persons speaking 4 languages only. (b) Areas b and d represent persons speaking same number of languages. (c) Areas f, b and e represent persons speaking same languages. (d) Areas g and h represent persons who speak two languages only. 
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?
A,B,C,D,E,G and I are seven friends who study in three different standards namely 5th, 6th and 7th such that not less than two friends study in the same standard. Each friend also has a different favorite subject namely History, Civics, English, Bangla, Science , Maths , and Economics but not necessarily in the same order. A likes Maths and studies in the 5th standard with only one other friend who likes Bangla. I studies with tow other friends . Both the friends who study with I like languages (Here languages include only Science , English and Bangla ) . D studies in the 6th standard with only one person and does not like Civics . E studies with only one friend . The one who likes history does not study in 5th or 6th standard . E does not like languages. C does not like English , Science or Civics. Which combination represents E's favorite subject and the standard in which he studies?
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?