Which of the following languages is generated by the given grammar? S → aS |…
2016
Which of the following languages is generated by the given grammar?
S → aS | bS | ε
- A.
{an bm | n,m ≥ 0}
- B.
{w ∈ {a,b}∗ | w has equal number of a’s and b’s }
- C.
{an | n ≥ 0} ∪ {bn | n ≥ 0} ∪ {an bn | n ≥ 0}
- D.
{a,b}*
Attempted by 135 students.
Show answer & explanation
Correct answer: D
Key idea: Each application of aS or bS produces an a or b and recurses; ε ends the derivation. By choosing a or b for each symbol you want, you can generate any finite string over {a,b}.
Empty string: S → ε
Single symbol: S → aS → aε gives 'a' (similarly for 'b').
Any string: for a given string pick productions matching each symbol. Example for 'aba': S → aS → abS → abaS → abaε.
Therefore the language generated is all strings over {a,b}, i.e., {a,b}*.
A video solution is available for this question — log in and enroll to watch it.