1
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
2
GATE CSE 2002
MCQ (Single Correct Answer)
+2
-0.6
Which of the following is true?
A
The complement of a recursively language is recursive.
B
The complement of a recursively enumerable language is recursively enumerable.
C
The complement of a recursively language is either recursive or recursively enumerable.
D
The complement of a context-free language is context-free.
3
GATE CSE 2002
MCQ (Single Correct Answer)
+2
-0.6
The $$C$$ language is:
A
A context free language
B
A context sensitive language
C
A regular language
D
Parsable fully only by a Turing machine
4
GATE CSE 1997
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following is not decidable?
A
Given a Turing machine $$M,$$ a stings s and an integer $$k,$$ $$M$$ accepts $$s$$ within $$k$$ steps
B
Equivalence of two given Turing machines
C
Language accepted by a given finite state machine is not empty
D
Language generated by a context free grammar is non empty
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP