GATE CSE 2026 Set 2 | Recursively Enumerable Language and Turing Machine Question 1 | Theory of Computation

GATE CSE 2026 Set 2

MCQ (Single Correct Answer)

-0

Which one of the following statements is equivalent to the following assertion?

Turing machine $M$ decides the language $L \subseteq\{0,1\}$.

Turing machine $M$ halts on all input strings in $\{0,1\}^*$

Turing machine $M$ accepts all input strings in $L$

Turing machine $M$ rejects all input strings in $\{0,1\}^*-L$

Turing machine $M$ accepts all input strings in $L$ and rejects all input strings in $\{0,1\}^*-L$

GATE CSE 2022

MCQ (More than One Correct Answer)

-0

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 2020

MCQ (Single Correct Answer)

-0.33

Consider the language
L = { $${a^n}|n \ge 0$$ } $$ \cup $$ { $${a^n}{b^n}|n \ge 0$$ }
and the following statements.

I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?

I only

II only

I and III only

III only

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