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 a S b | T$
$T \rightarrow b T | 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 non-terminal $T$ generates strings of the form $b^k$ for $k \ge 1$ (i.e., one or more 'b's).
The non-terminal $S$ generates strings of the form $a^m T b^m$ for $m \ge 0$.
Substituting the strings generated by $T$, we get $a^m b^k b^m = a^m b^{m+k}$.
Let $n = m + k$. Since $k \ge 1$, it follows that $n > m$, or $m < n$.
Also, $m$ can be $0$ (if the first derivation uses $S \rightarrow T$). Therefore, the language is $\\{a^m b^n : 0 \le m < n\\}$.