= Context-free language
{wiki}
A <context-free language> is a <formal language> generated by a <context-free grammar>, in which each production has exactly one nonterminal on its left side. Equivalently, it is recognized by a <nondeterministic pushdown automaton>.
For example, the grammar $S\to0S1\mid\epsilon$ generates $\{0^n1^n:n\ge0\}$. A derivation adds one matching pair at a time, while the empty production stops the process. The language is not regular: matching the two unbounded counts requires more memory than a finite-state recognizer provides. Context-free languages describe many nested structures, including balanced delimiters and recursive expression syntax.
Back to article page