GATE CSE 2016 Set 1 | Question: 16

Question

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

$$S \rightarrow aS \mid bS \mid \varepsilon$$

• A. $\{ a^nb^m \mid n,m \geq 0\}$
• B. $\{ w \in \{ a,b\}^* \mid w\text{ has equal number of a's and b's}\}$
• C. $\{a^n \mid n \geq 0 \} \cup \{b^n \mid n \geq 0\} \cup \{a^n b^n \mid n \geq 0\}$
• D. $\{ a,b\}^*$

Comments

option A : string ba not generate

---

KUCH BHI?

NHI MATLAB KUCH BHI?

---

yes kuch bhi but i think u can generate by own language  :-P

@ijnuhb

---

This is right linear grammar so no need to use substitution method we can easily convert it to dfa.

Answer 1

Option D is correct (a+b)*