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 aSb | T$
$T \rightarrow bT | b$
The language generated by G is:
- A. $\{a^{m}b^{n}:0 \le m < n\}$
- B. $\{a^{m}b^{n}:0 < m < n\}$
- C. $\{a^{m}b^{n}:0 < n \le m\}$
- D. $\{a^{n}b^{n}:0 \le n\}$
Answer: A. $\{a^{m}b^{n}:0 \le m < n\}$
Explanation: The production $T \rightarrow bT | b$ generates the language $b^{k}$ for $k \ge 1$. The production $S \rightarrow aSb | T$ generates strings of the form $a^{m} T b^{m}$ for $m \ge 0$. By substituting T, we get $a^{m} b^{k} b^{m} = a^{m} b^{m+k}$. Since $k \ge 1$, the total number of 'b's ($n = m+k$) is strictly greater than the total number of 'a's ($m$). Therefore, the language is $\{a^{m}b^{n}: 0 \le m < n\}$.