1
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+2
-0.6
Consider the following context-free grammars:
$$\eqalign{ & {G_1}:\,\,\,\,\,S \to aS|B,\,\,B \to b|bB \cr & {G_2}:\,\,\,\,\,S \to aA|bB,\,\,A \to aA|B|\varepsilon ,\,\,B \to bB|\varepsilon \cr} $$

Which one of the following pairs of languages is generated by $${G_1}$$ and $${G_2}$$, respectively?

A
$$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.$$ or $$\,\,\,\,$$$$n > \left. 0 \right\}$$ and $$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.$$ and $$\,\,\,\,n > \left. 0 \right\}\,\,\,\,$$
B
$$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.$$ and $$\,\,\,n > \left. 0 \right\}\,\,\,\,$$ and $$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.$$ or $$\,\,\,\,n \ge \left. 0 \right\}$$
C
$$\left\{ {{a^m}{b^n}|m \ge 0\,\,\,\,} \right.$$ or $$\,\,\,\,n > \left. 0 \right\}\,\,\,\,$$ and $$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.\,$$ and $$\,\,\,\,n > \left. 0 \right\}\,\,\,\,$$
D
$$\left\{ {{a^m}{b^n}|m \ge 0\,\,\,\,} \right.$$ and $$\,\,\,n > \left. 0 \right\}\,\,\,\,$$ and $$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.\,$$ or $$\,\,\,\,n > \left. 0 \right\}\,\,\,\,$$
2
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+2
-0.6
Let $$X$$ be a recursive language and $$Y$$ be a recursively enumerable but not recursive language. Let $$W$$ and $$Z$$ be two languages such that $$\overline Y $$ reduces to $$W,$$ and $$Z$$ reduces to $$\overline X $$ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
A
$$W$$ can be recursively enumerable and $$Z$$ is recursive.
B
$$W$$ can be recursive and $$Z$$ is recursively enumerable.
C
$$W$$ is not recursively enumerable and $$Z$$ is recursive.
D
$$W$$ is not recursively enumerable and $$Z$$ is not recursive.
3
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+1
-0.3
Out of the following four sentences, select the most suitable sentence with respect to grammar and usage.
A
I will not leave the place until the minister does not meet me.
B
I will not leave the place until the minister doesn’t meet me.
C
I will not leave the place until the minister meet me.
D
I will not leave the place until the minister meets me.
4
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+1
-0.3
A rewording of something written or spoken is a ______________.
A
paraphrase
B
paradox
C
paradigm
D
paraffin
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12