Consider the following context-free grammar \(G\), where \(S\), \(A\), and \(B\) are the variables (non-terminals), \(a\) and \(b\) are the terminal symbols, \(S\) is the start variable, and the rules of \(G\) are described as:
\(S \to aaB \mid Abb\)
\(A \to a \mid aA\)
\(B \to b \mid bB\)
Which ONE of the languages \(L(G)\) is accepted by \(G\)?
Answer
(A)
Explanation
\(A \to a \mid aA\) generates \(a^{n}\) and \(B \to b \mid bB\) generates \(b^{n}\), for \(n \ge 1\).
So \(S \to aaB\) gives the strings \(a^{2}b^{n}\), and \(S \to Abb\) gives the strings \(a^{n}b^{2}\). Together, \(L(G) = \{a^{2}b^{n} \mid n \ge 1\} \cup \{a^{n}b^{2} \mid n \ge 1\}\).
The other options do not match: for example, \(aabbb \in L(G)\), but it belongs to none of (B), (C) and (D).
Answer: A