1
GATE CSE 2005
+2
-0.6
Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $${D_f}$$ and $${D_p}$$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?
A
$${D_f} \subset {N_f}$$ and $${D_P} \subset {N_p}$$
B
$${D_f} \subset {N_f}$$ and $${D_P} = {N_p}$$
C
$${D_f} = {N_f}$$ and $${D_P} = {N_p}$$
D
$${D_f} = {N_f}$$ and $${D_P} \subset {N_p}$$
2
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
3
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$$
4
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\}$$
GATE CSE Subjects
EXAM MAP
Medical
NEET