1
GATE CSE 2020
+2
-0.67
Consider the following languages.

L1 = {wxyx | w, x, y ∈ (0 + 1)+}
L2 = {xy | x, y ∈ (a + b)*, |x| = |y|, x ≠ y}

Which one of the following is TRUE?
A
L1 is regular and L2 is context-free.
B
L1 is context-free but not regular and L2 is context-free.
C
Neither L1 nor L2 is context-free.
D
L1 is context-free but L2 is not context-free.
2
GATE CSE 2018
+2
-0.6
Consider the following languages:

$$\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|m + p = n + q,$$ where $$\left. {m,n,p,q \ge 0} \right\}$$
$$\,\,\,\,\,\,{\rm II}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|m = n$$ and $$p=q,$$ where $$\left. {m,n,p,q \ge 0} \right\}$$
$$\,\,\,\,{\rm III}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|m = n = p$$ and $$p \ne q,$$ where $$\left. {m,n,p,q \ge 0} \right\}$$
$$\,\,\,\,{\rm IV}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|mn = p + q,$$ where $$\left. {m,n,p,q \ge 0} \right\}$$

Which of the languages above are context-free?

A
$${\rm I}$$ and $${\rm IV}$$ only
B
$${\rm I}$$ and $${\rm II}$$ only
C
$${\rm II}$$ and $${\rm III}$$ only
D
$${\rm II}$$ and $${\rm IV}$$ only
3
GATE CSE 2016 Set 1
+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\}\,\,\,\,$$
4
GATE CSE 2015 Set 3
+2
-0.6
Which of the following languages are context-free? \eqalign{ & {L_1} = \left\{ {{a^m}{b^n}{a^n}{b^m}|m,n \ge 1} \right\} \cr & {L_2} = \left\{ {{a^m}{b^n}{a^m}{b^n}|m,n \ge 1} \right\} \cr & {L_3} = \left\{ {{a^m}{b^n}|m = 2n + 1} \right\} \cr}\$
A
$${L_1}$$ and $${L_2}$$ only
B
$${L_1}$$ and $${L_3}$$ only
C
$${L_2}$$ and $${L_3}$$ only
D
$${L_3}$$ only
GATE CSE Subjects
EXAM MAP
Medical
NEET