[Solved] 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?

Q.	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?
A.	L2 – L1 is recursively enumerable.
B.	L1 – L3 is recursively enumberable
C.	L2 intersection L1 is recursively enumberable
D.	L2 union L1 is recursively enumberable
Answer» B. L1 – L3 is recursively enumberable

639

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, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is 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
Which of the following statements are TRUE? I. There exist parsing algorithms for some programming languages whose complexities are less than O(n3). II. A programming language which allows recursion can be implemented with static storage allocation. III. No L-attributed definition can be evaluated in the framework of bottom-up parsing. IV. Code improving transformations can be performed at both source language and intermediate code level.
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
Consider the following two statements: S1: { 0^2n |n >= l} is a regu1ar language S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language Which of the following statements is correct?
Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-free