1
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\}$$
2
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
3
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$$
4
GATE CSE 2000
+2
-0.6
Consider the following decision problems:
$${P_1}$$ Does a given finite state machine accept a given string
$${P_2}$$ Does a given context free grammar generate an infinite number of stings.

Which of the following statements is true?

A
Both $${P_1}$$ and $${P_2}$$ are decidable
B
Neither $${P_1}$$ and $${P_2}$$ are decidable
C
Only $${P_1}$$ is decidable
D
Only $${P_2}$$ is decidable
GATE CSE Subjects
EXAM MAP
Medical
NEET