Recursive Languages

Consider the two lists List I and List II given below: List I (i) Context free languages (ii) Recursive languages (iii) Regular languages List II (a) Closed under union (b) Not clo...

Consider the two lists List-I and List-II given below: List - I List - II (i) Context free languages (a) Closed under union (ii) Recursive languages (b) Not closed under complement...

Which of the following statements is/are CORRECT?

Which of the following statements is/are TRUE?

The set of all recursively enumerable languages is

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 $$\overline Y $$ reduces to $$W,$...

Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$ Recursively enumerable. Which of the following is/are TRUE...

For any two languages L 1 and L 2 such that L 1 is context-free and L 2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. $${\overline...

Consider the following statements. $$\,\,\,$$ $${\rm I}.\,\,\,\,\,\,\,\,\,$$ The complement of every Turing decidable language is Turing decidable $$\,$$ $${\rm II}.\,\,\,\,\,\,\,\...

Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?

Consider the following languages $${L_1} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0} \right.} \right\}$$ $${L_2} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0,p \ne r} \right.}...

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 $$\overline L $$ also context-fr...

Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows $$L = \left\{ {\matrix{ {{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P = NP} \cr {\,\,\,\,\,\,\,\phi \,\,...

Which of the following is true?

Which of the following statements is / are true / false? Union of two recursive languages is recursive