GATE CSE 2022 | Recursively Enumerable Language and Turing Machine Question 1 | Theory of Computation

GATE CSE 2022

MCQ (More than One Correct Answer)

-0.33

Which of the following statements is/are TRUE?

Every subset of a recursively enumerable language is recursive.

If a language L and its complement $$\overline L $$ are both recursively enumerable, then L must be recursive.

Complement of a context-free language must be recursive.

If L₁ and L₂ are regular, then L₁ $$\cap$$ L₂ must be deterministic context-free.

GATE CSE 2022

MCQ (More than One Correct Answer)

-0.33

Which of the following is/are undecidable?

Given two Turing machines M₁ and M₂, decide if L(M₁) = L(M₂).

Given a Turing machine M, decide if L(M) is regular.

Given a Turing machine M, decide if M accepts all strings.

Given a Turing machine M, decide if M takes more than 1073 steps on every string.

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.3

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?

$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ $$\overline {{L_3}} \cup {L_4}$$ is recursively enumerable
$$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ $$\overline {{L_2}} \cup {L_3}$$ is recursive
$$\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ $$L_1^ * \cap {L_2}$$ is context-free
$$\,\,\,{\rm I}V.\,\,\,\,\,\,\,$$ $${L_1} \cup \overline {{L_2}} $$ is context-free

$${\rm I}$$ only

$${\rm I}$$ and $${\rm III}$$ only

$${\rm I}$$ and $${\rm IV}$$ only

$${\rm I},$$ $${\rm II}$$ and $${\rm III}$$ only

GATE CSE 2015 Set 2

MCQ (Single Correct Answer)

-0.3

Consider the following statements.

$$\,\,\,$$ $${\rm I}.\,\,\,\,\,\,\,\,\,$$ The complement of every Turing decidable language is Turing decidable
$$\,$$ $${\rm II}.\,\,\,\,\,\,\,\,\,$$ There exists some language which is in $$NP$$ but is not Turing decidable
$${\rm III}.\,\,\,\,\,\,\,\,\,$$ If $$L$$ is a language in $$NP,$$ $$L$$ is Turing decidable

Which of the above statements is/are true?

Only $${\rm I}$$$${\rm I}$$

Only $${\rm III}$$

Only $${\rm I}$$ and $${\rm II}$$

Only $${\rm I}$$ and $${\rm III}$$