Practice free →
HomeGATE CSEcomputerscienceTheory of Computation › Consider the CFG with rule $S \to aSb \mid \vare…

Consider the CFG with rule $S \to aSb \mid \varepsilon$. The language generated is

A$\{a^n b^n \mid n \geq 0\}$
B$\{a, b\}^*$
C$\{a^n b^m \mid n, m \geq 0\}$
D$\{ab\}$
Answer & Solution
Correct answer: A. $\{a^n b^n \mid n \geq 0\}$
1. Starting from $S$, repeatedly apply $S \to aSb$ to grow the string by one $a$ on each side and one $b$ on each side... wait. 2. Apply $S \to aSb$ once: derives $aSb$. Twice: $a(aSb)b = aaSbb$. Thrice: $aaaSbbb$. 3. Finally apply $S \to \varepsilon$: replaces the remaining S with empty string. 4. So derivations: $S \Rightarrow \varepsilon$ (n=0), $aSb \Rightarrow ab$ (n=1), $aaSbb \Rightarrow aabb$ (n=2), etc. 5. Language: $\{a^n b^n \mid n \geq 0\}$. 6. CRUCIAL: this language is NOT regular but IS context-free. Demonstrates the power gap between CFGs and DFAs. 7. Other options don't match the derivation pattern. _Source: Jeff Erickson, "Models of Computation", §5.2 (CFG examples — $a^n b^n$)._
Solve this in the app — GATE CSE practice & 24k+ MCQs →
Related questions