GATE CSE 2014 Set 2 | Recursively Enumerable Language and Turing Machine Question 15 | Theory of Computation

GATE CSE 2014 Set 2

MCQ (Single Correct Answer)

-0.3

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?

If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursive then $$A$$ is recursive.

If $$A\,\,{ \le _m}\,\,B$$ and $$A$$ is undecidable then $$B$$ is un-decidable.

If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursively enumerable then $$A$$ is recursively enumerable.

If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is not recursively enumerable then $$A$$ is not recursively enumerable.

GATE CSE 2013

MCQ (Single Correct Answer)

-0.3

Which of the following statements is/are FALSE?
$$1.$$ For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine
$$2.$$ Turing recognizable languages are closed under union and complementation
$$3.$$ Turing decidable languages are closed under intersection and complementation
$$4.$$ Turing recognizable languages are closed under union and intersection

$$1$$ and $$4$$ only

$$1$$ and $$3$$ only

$$2$$ only

$$3$$ only

GATE CSE 2008

MCQ (Single Correct Answer)

-0.3

Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?

It is not accepted by a Turing machine

It is regular but not context-free

It is context-free but not regular

It is neither regular nor context-free, but accepted by a Turing machine

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

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 \,\,\,\,Otherwise} \cr } } \right.$$

Which of the following statement is true?

$$L$$ is recursive

$$L$$ is recursively enumerable but not recursive

$$L$$ is not recursively enumerable

Whether $$L$$ is recursive or not will be known after we find out if $$P=NP.$$

PREVIOUS NEXT