1
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6

Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules:

$$\eqalign{ & S \to bA\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,S \to aB \cr & A \to a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to b \cr & A \to aS\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to bS \cr & S \to bAA\,\,\,\,\,\,\,\,\,\,\,B \to aBB \cr} $$

Which of the following strings is generated by the grammar?

A
aaaabb
B
aabbbb
C
aabbab
D
abbbba
2
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6

Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules:

$$\eqalign{ & S \to bA\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,S \to aB \cr & A \to a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to b \cr & A \to aS\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to bS \cr & S \to bAA\,\,\,\,\,\,\,\,\,\,\,B \to aBB \cr} $$

For the correct answer strings to the previous question, how many derivation trees are there?

A
1
B
2
C
3
D
4
3
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6

Consider the following grammar:

$$\eqalign{ & S \to FR \cr & R \to *S\,|\,\varepsilon \cr & F \to id \cr} $$

In the predictive parser table, M, of the grammar the entries $$M\left[ {S,id} \right]$$ and $$M\left[ {R,\$ } \right]$$ respectively.

A
$$\left\{ {S \to FR} \right\}$$ and $$\left\{ {R \to \varepsilon } \right\}$$
B
$$\left\{ {S \to FR} \right\}$$ and $$\left\{ {\,\,} \right\}$$
C
$$\left\{ {S \to FR} \right\}$$ and $$\left\{ {R \to * S} \right\}$$
D
$$\left\{ {F \to id} \right\}$$ and $$\left\{ {R \to \varepsilon } \right\}$$
4
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6
In the correct grammar of the previous question, what is the length of the derivation (number of steps starring from S) to generate the string $${a^l}{b^m}$$ with $$l \ne m$$?
A
$$\max (l,m) + 2$$
B
$$l + m + 2$$
C
$$l + m + 3$$
D
$$\max (l,m) + 3$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP