Context-free language

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\to 0S1\mid ϵ$ generates $\{0^n{1}^n:n\ge 0\}$. 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.

A **context-free language (CFL)** is a type of formal language that can be generated by a context-free grammar (CFG). In formal language theory, context-free languages are significant because they can describe a wide range of syntactic structures used in programming languages and natural languages. ### Key Concepts: 1. **Context-Free Grammar (CFG)**: - A CFG consists of a set of production rules that define how symbols in the language can be replaced or transformed.