Consider the production rules of grammar G: \(\begin{array}{l} \mathrm{S}…
2022
Consider the production rules of grammar G:
\(\begin{array}{l} \mathrm{S} \rightarrow \mathrm{AbB} \\ \mathrm{A} \rightarrow \mathrm{aAb} \mid \lambda \\ \mathrm{B} \rightarrow \mathrm{bB} \mid \lambda \end{array}\)
Which of the following language 𝐿 is generated by grammer 𝐺 ?
- A.
\(\text L=\left\{a^{n} b^{m}: n \geq 0, m>n\right\}\) - B.
\(\text L=\left\{a^{n} b^{m}: n \geq 0, m \geq 0\right\}\) - C.
\(L=\left\{a^{n} b^{m}: n \geq m\right\}\) - D.
\(L=\left\{a^{n} b^{m}: n \geq m, m>0\right\}\)
Attempted by 45 students.
Show answer & explanation
Correct answer: A
Answer: The grammar generates the language { a^n b^m : n ≥ 0, m > n }.
Reason: Analyze each nonterminal.
A generates a^k b^k for k ≥ 0, because A -> aAb adds one a at the front and one b at the end each time, and A -> λ stops the process.
B generates b^m for m ≥ 0 by repeated application of B -> bB and B -> λ.
S -> A b B therefore yields a^k b^k b b^m = a^k b^{k+1+m'}, where k ≥ 0 and m' ≥ 0. If we set n = k and m = k+1+m', then m > n always holds.
Examples:
k = 0, B -> λ: S -> b, giving a^0 b^1 (n = 0, m = 1).
k = 1, B -> λ: A -> ab, S -> ab b = abb, giving a^1 b^2 (n = 1, m = 2).
Thus the correct description of the generated language is { a^n b^m : n ≥ 0, m > n }.
A video solution is available for this question — log in and enroll to watch it.