1
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-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?

A
$$L$$ is recursively enumerable, but not recursive
B
$$L$$ is recursive, but not context-free
C
$$L$$ is context-free, but not regular
D
$$L$$ is regular
2
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-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?
A
$${L_1} \cap {L_2}$$ is deterministic $$CFL$$
B
$${L_3} \cap {L_1}$$ is recursive
C
$${L_1} \cup {L_2}$$ is context-free
D
$${L_1} \cap {L_2} \cap {L_3}$$ is recursively enumerable
3
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
A
$$\overline {{L_1}} $$ is recursive and $$\overline {{L_2}} $$ is recursively enumerable
B
$$\overline {{L_1}} $$ is recursive and $$\overline {{L_2}} $$ is not recursively enumerable
C
$$\overline {{L_1}} $$ and $$\overline {{L_2}} $$ are recursively enumerable
D
$$\overline {{L_1}} $$ is recursively enumerable and $$\overline {{L_2}} $$ is recursive
4
GATE CSE 2003
MCQ (Single Correct Answer)
+2
-0.6
Define Languages $${L_0}$$ and $${L_1}$$ as follows
$${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \right.$$ halts on $$\left. w \right\}$$
$${L_1} = \left\{ { < M,w,1 > \left| M \right.} \right.$$ does not halts on $$\left. w \right\}$$

Here $$ < M,\,w,\,i > $$ is a triplet, whose first component, $$M$$ is an encoding of a Turing Machine, second component, $$w$$, is a string, and third component, $$t,$$ is a bit.
Let $$L = {L_0} \cup {L_1}.$$ Which of the following is true?

A
$$L$$ is recursively enumerable, but $$\overline L $$ is not
B
$$\overline L $$ is recursively enumerable, but $$L$$ is not
C
Both $$L$$ and $$\overline L $$ are recursive
D
Neither $$L$$ nor $$\overline L $$ is recursive enumerable

GATE CSE Subjects

Browse all chapters by subject

Software Engineering
Web Technologies