1
GATE CSE 2006
+2
-0.6
Consider the following statements about the context-free grammar
$$G = \left\{ {S \to SS,\,S \to ab,\,S \to ba,\,S \to \varepsilon } \right\}$$
$$1.$$ $$G$$ is ambiguous
$$2.$$ $$G$$ produces all strings with equal number of $$a's$$ and $$b's$$
$$3.$$ $$G$$ can be accepted by a deterministic $$PDA$$.

Which combination below expresses all the true statements about $$G?$$

A
$$1$$ only
B
$$1$$ and $$3$$ only
C
$$2$$ and $$3$$ only
D
$$1, 2$$ and $$3$$
2
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}$$
3
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
4
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$$
GATE CSE Subjects
EXAM MAP
Medical
NEET