Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2007
Expert
Consider the CFG with {S,A,B} as the non-terminal alphabet, {a,b} as the terminal alphabet, S as the start symbol, and production rules: S→aB, S→bA, B→b, B→bS, B→aBB, A→a, A→aS, A→bAA. Which of the following strings is generated by the grammar?
- Aaaaabb
- Baabbbb
- aabbab
- Dabbbba
Explanation
S⇒aB (need B to derive 'abbab'). B⇒aBB (need the two B's to jointly derive 'bbab'): take B₁⇒b (derives 'b') and B₂⇒bS⇒b(aB)⇒ba(b)='bab' — together 'b'+'bab'='bbab' ✓. So B⇒a(b)(bab)='abbab', and S⇒a(abbab)='aabbab', matching option (C) exactly. (The other options have unequal a/b counts, inconsistent with this grammar's balanced structure.)
Source: GATE CS 2007 (2007)
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.