GATE 2016 CS – Question 26

Theory of Computation · Context-Free Grammars and Pushdown Automata · 1 mark · Multiple choice

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

$S \rightarrow aS \mid bS \mid \epsilon$

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\{a, b\}^*$

Explanation

At each step the grammar can add either an $a$ or a $b$ in front, in any order, and then stop with $\epsilon$. So it generates every string over $\{a, b\}$, which is $\{a, b\}^*$.