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

PREVIOUS NEXT

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}$$

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

PREVIOUS NEXT