1
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known that $${P_1}$$ is decidable and $${P_2}$$ is un-decidable. Which of the following is TRUE?
A
$${P_3}$$ is decidable if $${P_1}$$ is reducible to $${P_3}$$
B
$${P_3}$$ is in-decidable if $${P_3}$$ is reducible to $${P_2}$$
C
$${P_3}$$ is un-decidable if $${P_2}$$ is reducible to $${P_3}$$
D
$${P_3}$$ is decidable if $${P_3}$$ is reducible to $${P_2}'s$$ complement
2
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
3
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
Consider the language :
$${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$
$${L_2}\, = \left\{ {w\, \ne {w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$ where $$ \ne $$ is a special symbol
$${L_3}\, = \left\{ {w\,w\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$

Which one of the following is TRUE?

A
$${L_1}$$ $$=$$ is a deterministic $$CFL$$
B
$${L_2}$$ $$=$$ is a deterministic $$CFL$$
C
$${L_3}$$ is a $$CFL,$$ but not a deterministic $$CFL$$
D
$${L_3}$$ IS A DETERMINISTIC $$CFL$$
4
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
Consider the language :
$${L_1} = \left\{ {{a^n}{b^n}{c^m}\left| {n,m > 0} \right.} \right\}$$ and $${L_2} = \left\{ {{a^n}{b^m}{c^m}\left| {n,m > 0} \right.} \right\}$$

Which of the following statement is FALSE?

A
$${L_1}\, \cap \,{L_2}$$ is a context-free language
B
$${L_1}\, \cap \,{L_2}$$ is a context-free language
C
$${L_1}$$ and $${L_2}$$ are context-free language
D
$${L_1}\, \cap \,{L_2}$$ is a context sensitive language
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12