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$)._
Keep practising Theory of Computation
Browse all Theory of Computation questions for GATE CSE, or explore more Computer Science topics.
Related questions
Which class of grammars generates ALL recursively enumerable languages?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isContext-free languages are RECOGNISED by which type of machine?A CFG is AMBIGUOUS ifWhich of these is an example of an IRREGULAR (non-regular) language?