GATE CSE 2014 Set 2 | Recursively Enumerable Language and Turing Machine Question 13 | 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

If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which of the following statements is true?

$$L$$ is necessarily finite

$$L$$ is regular but not necessarily finite

$$L$$ is context free but not necessarily regular

$$L$$ is recursive but not necessarily context free

PREVIOUS NEXT