1
GATE CSE 2005
+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
2
GATE CSE 2005
+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$$
3
GATE CSE 2004
+2
-0.6
Consider the following grammar $$G:$$
\eqalign{ & S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr & A \to bA\,\left| {\,aB} \right. \cr & B \to bB\,\left| {\,aS\,\left| {\,a} \right.} \right. \cr}

Let $${N_a}\left( w \right)$$ and $${N_b}\left( w \right)$$ denote the number of $$a's$$ and $$b's$$ in a string $$w$$ respectively. The language
$$L\left( G \right)\,\,\, \subseteq \left\{ {a,b} \right\} +$$ generated by $$G$$ is

A
$$\left\{ {w\,\left| {Na\left( w \right) > 3Nb\left( w \right)} \right.} \right\}$$
B
$$\left\{ {w\,\left| {Nb\left( w \right) > 3Na\left( w \right)} \right.} \right\}$$
C
$$\left\{ {w\,\left| {Na\left( w \right) = 3k,k \in \left\{ {0,1,2,...} \right\}} \right.} \right\}$$
D
$$\left\{ {w\,\left| {Nb\left( w \right) = 3k,k \in \left\{ {0,1,2,...} \right\}} \right.} \right\}$$
4
GATE CSE 2004
+2
-0.6
The language $$\left\{ {{a^m}{b^n}{c^{m + n}}\left| {m,n \ge } \right.} \right\}$$ is
A
Regular
B
Context-free but not regular
C
Context sensitive but not context free
D
Type-$$0$$ but not context sensitive
GATE CSE Subjects
EXAM MAP
Medical
NEET
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
CBSE
Class 12