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\)?
Answer: A. \(L(G) = \{ a^{2} b^n \mid n \geq 1 \} \cup \{ a^n b^2 \mid n \geq 1 \}\) — 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…
- 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 101 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2