Consider the following context-free grammar \(G\), where \(π, π΄,\) and \(B\)β¦
2025
Consider the following context-free grammar \(G\), where \(π, π΄,\)Β 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:
\(π β πππ΅ | π΄ππ \\ \\π΄ β π | ππ΄ \\ \\π΅ β π | πB \\\)
Which ONE of the languagesΒ \(πΏ(πΊ)\) is accepted by \(G\)?
- A.
\(L(G) = \{ a^{2} b^n \mid n \geq 1 \} \cup \{ a^n b^2 \mid n \geq 1 \}\) - B.
\(L(G) = \{ a^n b^{2n} \mid n \geq 1 \} \cup \{ a^{2n} b^n \mid n \geq 1 \}\) - C.
\(L(G) = \{ a^n b^n \mid n \geq 1 \}\) - D.
\(L(G) = \{ a^{2n} b^{2n} \mid n \geq 1 \}\)
Attempted by 90 students.
Show answer & explanation
Correct answer: A
What A Generates:
A β a | aA (left-recursive) produces a^k for k β₯ 1 (one or more a's).
E.g., A β a, A β aa, A β aaa, etc.
What B Generates:
B β b | bB (right-recursive) produces b^m for m β₯ 1 (one or more b's).
E.g., B β b, B β bb, B β bbb, etc.
From S β aaB:
S β aaB β aa b^m (m β₯ 1).
So, strings of the form a^2 b^m where m β₯ 1.
From S β Abb:
S β Abb β A bb β a^k bb (k β₯ 1).
So, strings of the form a^k b^2 where k β₯ 1.
Overall L(G):
L(G) = {a^2 b^m | m β₯ 1} βͺ {a^k b^2 | k β₯ 1}.
This matches option A: {a^{2n} | n β₯ 1} βͺ {a^n b^2 | n β₯ 1}
A video solution is available for this question β log in and enroll to watch it.