notesonly.in

One notebook for every subject — open it anywhere.

Log in

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.

← Back to topics for Engineering