Home › GATE CSE › computerscience › Theory 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$)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?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$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?