Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2025
Medium
Consider the following context-free grammar G, where S, A, 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: S → aaB | Abb A → a | aA B → b | bB Which ONE of the languages L(G) is accepted by G?
- L(G) = {a²bⁿ | n≥1} ∪ {aⁿb² | n≥1}
- BL(G) = {aⁿb^(2n) | n≥1} ∪ {a^(2n)bⁿ | n≥1}
- CL(G) = {aⁿbⁿ | n≥1}
- DL(G) = {a^(2n)b^(2n) | n≥1}
Explanation
S→aaB generates "aa"+b^n (n≥1, since B generates b^n) = a²bⁿ. S→Abb generates a^m (m≥1, since A generates a^m) + "bb" = a^mb². Union: {a²bⁿ} ∪ {aⁿb²}.
Source: GATE CS 2025 (Session 1 / CS1) (2025)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.