[Solved] Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Q.	Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
A.	L1' is recursive and L2' is recursively enumerable
B.	L1' is recursive and L2' is not recursively enumerable
C.	L1' and L2' are recursively enumerable
D.	L1' is recursively enumerable and L2' is recursive
Answer» B. L1' is recursive and L2' is not recursively enumerable

1.3k

Do you find this helpful?

View all MCQs in

Theory of Computation and Compiler Design

Discussion

No comments yet

Related MCQs

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 L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?
Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L’ (complement of L) also context-free? 3) If L is a regular language, then is L’ also regular? 4) If L is a recursive language, then, is L’ also recursive?
If L and L' are recursively enumerable, then L is
For S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 + 1) | d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true?
For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are
Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
In multi-programmed systems, it is advantageous if some programs such as editors and compilers can be shared by several users. Which of the following must be true of multi-programmed systems in order that a single copy of a program can be shared by several users? I. The program is a macro II. The program is recursive III.The program is reentrant
Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?