Topic: Theory of Computation
Consider the context-free grammar G below. Here S is the starting non-terminal symbol, while a and b are terminal symbols.
$S \rightarrow aaSb | T$
$T \rightarrow Tb | a$
Which of the following statements is true about the language L(G) generated by G?
- A. aabbaabb belongs to L(G) but aabb does not
- B. aaaaabbb belongs to L(G) but aaaabb does not
- C. aaaabb belongs to L(G) but aabbaabb does not
- D. aaabb belongs to L(G) but aaaaabbb does not
Answer: B. aaaaabbb belongs to L(G) but aaaabb does not
Explanation: The production $T \rightarrow Tb | a$ generates $ab^{k}$ (an 'a' followed by $k \ge 0$ 'b's). The production $S \rightarrow aaSb | T$ generates $a^{2m} T b^{m}$ ($m \ge 0$). Substituting T, we get $a^{2m} a b^{k} b^{m} = a^{2m+1} b^{k+m}$. Thus, L(G) consists of strings with an ODD number of 'a's followed by some number of 'b's. The string 'aaaaabbb' has 5 'a's (odd) and belongs to L(G), whereas 'aaaabb' has 4 'a's (even) and does not belong.