Context-free grammars and languages
Theory of Computation · Engineering
Study notes
Grammar for a^n b^n: S -> aSb | epsilon. Derive 'aabb': S => aSb => aaSbb => aabb. The stack-like nesting (each a matched with a later b) is exactly what finite automata cannot do. But 'aab' has no derivation: the grammar rejects it, as desired.