GATE CS 2016 Set 1 Q.26 (CS Q.16): Context-Free Grammars, Pushdown Automata and CFLs

Which of the following languages is generated by the given grammar?

S \to aS \mid bS \mid \varepsilon

$\{a^n b^m \mid n, m \ge 0\}$

$\{w \in \{a, b\}^* \mid w \text{ has equal number of } a\text{'s and } b\text{'s}\}$

$\{a^n \mid n \ge 0\} \cup \{b^n \mid n \ge 0\} \cup \{a^n b^n \mid n \ge 0\}$

$\{a, b\}^*$

Official answer and solution

Official answer: D
From: Official GATE 2016 answer key

Solution

Trace the language produced by the recursive context-free grammar.

Given the grammar rules with start symbol $S$ :

S \to aS \mid bS \mid \varepsilon

At each derivation step, $S$ can prepend either the terminal symbol $a$ or $b$ , or terminate by producing $\varepsilon$ :

$S \implies \varepsilon$
$S \implies aS \implies a\varepsilon = a$
$S \implies bS \implies b\varepsilon = b$
$S \implies aS \implies abS \implies abaS \implies aba$

By induction, any arbitrary finite sequence of $a$ 's and $b$ 's can be generated by applying the corresponding production rules followed by $S \to \varepsilon$ . Therefore, the grammar generates the set of all binary strings over $\{a, b\}$ , which is $\{a, b\}^*$ (or $(a + b)^*)$ .

Final answer

Common trap

Assuming the grammar requires $a$ 's before $b$ 's, confusing $S \to aS \mid bS \mid \varepsilon$ with $S \to aS \mid B, B \to bB \mid \varepsilon$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 26 of 65, printed as CS Q.16
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source