Context-free grammars add recursion. They describe nested, balanced structures — arithmetic expressions, matched parentheses, programming language syntax.
Definition · Context-free grammar
A CFG is a 4-tuple (V, Σ, R, S): variables V, terminals Σ, rules R of the form A → w, and a start variable S.
A grammar for the non-regular language { 0ⁿ1ⁿ }:
S → 0 S 1 | εEach application of the recursive rule adds one 0 on the left and one 1 on the right, guaranteeing they stay balanced — something no finite automaton can do.