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 1

MCQ (Single Correct Answer)

-0.3

For any two languages L₁ and L₂ such that L₁ is context-free and L₂ is recursively enumerable but not recursive, which of the following is/are necessarily true?

I. $${\overline L _1}$$ (complement of L₁) is recursive
II. $${\overline L _2}$$ (complement of L₂) is recursive
III. $${\overline L _1}$$ is context-free
IV. $${\overline L _1} \cup {L_2}$$ is recursively enumerable

I only

III only

III and IV only

I and IV only