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

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

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