1
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$$
2
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\}$$
3
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
4
GATE CSE 2004
+2
-0.6
Let $$M = \left( {K,\,\sum {,\,F,\,\Delta ,\,s,\,F} } \right)$$ be a pushdown automation. Where $$K = \left\{ {s,\,f} \right\},\,F = \left\{ f \right\},\,\sum { = \left\{ {a,b} \right\},\,F = \left\{ a \right\}}$$ and $$\Delta = \left\{ {\left( {\left( {s,\,a,\, \in } \right)} \right.,\,\left. {\left( {s,\,a} \right)} \right),\,\left( {\left( {s,\,b,\, \in } \right),\,\left. {\left( {s,\,a} \right)} \right),\,} \right.} \right.$$ $$\left( {\left( {s,\,a,\, \in } \right),\,\left( {f,\, \in } \right),\,\left( {\left( {f,\,a,\,a} \right),\,\left. {\left( {f,\, \in } \right)} \right),\,\left( {\left( {f,\,b,\,a} \right),\,\left. {\left. {\left( {f,\, \in } \right)} \right)} \right\}} \right.} \right.} \right..$$

Which one of the following strings is not a number of $$L(M)?$$

A
$$aaa$$
B
$$aabab$$
C
$$baaba$$
D
$$bab$$
GATE CSE Subjects
EXAM MAP
Medical
NEET