1
GATE CSE 2005
MCQ (Single Correct Answer)
+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
MCQ (Single Correct Answer)
+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$$
3
GATE CSE 2004
MCQ (Single Correct Answer)
+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
MCQ (Single Correct Answer)
+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
Software Engineering
Web Technologies
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12