GATE CSE 2014 Set 1 | Recursively Enumerable Language and Turing Machine Question 15 | Theory of Computation

PREVIOUS NEXT

GATE CSE 2014 Set 1

MCQ (Single Correct Answer)

-0.6

Let $$L$$ be a language and $$\overline L $$ be its complement. Which one of the following is NOT a viable possibility?

Neither $$L$$ nor $$\overline L $$ is recursively enumerable (r.e).

One of $$L$$ and $$\overline L $$ is r.e. but not recursive; the other is not r.e.

Both $$L$$ and $$\overline L $$ are r.e. but not recursive.

Both $$L$$ and $$\overline L $$ are recursive.

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

If $$L$$ and $$\overline L $$ are recursively enumerable then $$L$$ is

Regular

Context-free

Context-sensitive

Recursive.

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enumerable, but not recursive, language. Which one of the following statement is false?

$${L_1} \cap {L_2}$$ is deterministic $$CFL$$

$${L_3} \cap {L_1}$$ is recursive

$${L_1} \cup {L_2}$$ is context-free

$${L_1} \cap {L_2} \cap {L_3}$$ is recursively enumerable

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

For $$s \in {\left( {0 + 1} \right)^ * },$$ let $$d(s)$$ denote the decimal value of $$s(e. g.d(101)=5)$$
Let $$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {\,d\left( s \right)\,} \right.} \right.$$ mod $$5=2$$ and $$d(s)$$ mod $$\left. {7 \ne 4} \right\}$$

Which of the following statement is true?

$$L$$ is recursively enumerable, but not recursive

$$L$$ is recursive, but not context-free

$$L$$ is context-free, but not regular

$$L$$ is regular

PREVIOUS NEXT