Context-free language

A context-free language is defined as the set of strings generated by a context-free grammar (CFG) — a tuple (V, Σ, R, S) where V is a finite set of nonterminal symbols, Σ a finite alphabet of terminals, R a finite set of production rules of the form A → α with A ∈ V and α ∈ (V ∪ Σ)*, and S ∈ V the start symbol. Equivalently, it is the language accepted by a nondeterministic pushdown automaton (PDA) by final state or empty stack.¹ The class of context-free languages is closed under union, concatenation, Kleene star, and reversal, but not under intersection or complement. The pumping lemma for context-free languages provides a necessary (but not sufficient) condition for a language to be context-free, often used to prove that certain languages are not context-free, such as {aⁿbⁿcⁿ | n ≥ 0}.²

Context-free languages are precisely those that can be recognized by pushdown automata, which use a single stack to store unbounded information.¹ They are closed under substitution, homomorphism, and inverse homomorphism, but not under intersection with regular languages (though the intersection of a context-free language with a regular language is context-free). A famous result is that the emptiness, finiteness, and membership problems are decidable for context-free languages, but the equivalence problem is undecidable. The class includes the well-known language of balanced parentheses, {aⁿbⁿ | n ≥ 0}, and arithmetic expressions. However, it excludes languages requiring two independent counting mechanisms, such as {aⁿbⁿcⁿ} or {ww | w ∈ {a,b}*}.

Context-free grammars are the backbone of most programming language definitions and compiler front ends, where they specify the syntax of languages like C, Java, and Python. In natural language processing, context-free grammar (often augmented with features) models the syntactic structure of sentences, though the full complexity of human language may exceed context-freeness.³ Markup languages such as SGML, XML, and HTML are defined by context-free grammars, enabling machine parsing and validation. The theory also underpins the design of recursive descent parsers and the LL(k) and LR(k) families of parsing algorithms.

While the classic Dyck language of balanced parentheses is context-free, the language of strings with an equal number of a's and b's is also context-free, but the language of strings with twice as many a's as b's is not.² A surprising result is that the determinism of context-free languages (those recognized by deterministic pushdown automata) is a proper subclass — e.g., the language of palindromes over {a,b} is context-free but not deterministic.¹ The intersection of two context-free languages can be context-sensitive but not context-free, illustrating the limits of the class. Another niche fact: the language {aⁿbⁿcⁿ} is context-sensitive, but the language {aⁿbⁿcⁿdⁿ} is not context-sensitive in the usual hierarchy, though it is in the indexed grammar class. The Chomsky–Schützenberger theorem characterizes context-free languages as the homomorphic images of the Dyck language, a deep structural result.

Context-free grammar

A formal grammar whose production rules are of the form A → α, where A is a single nonterminal and α is a string of terminals and nonterminals.

Pushdown automaton

A finite automaton augmented with a stack that can push and pop symbols, used to recognize context-free languages.

Pumping lemma

A lemma that provides a necessary condition for a language to be context-free, often used to prove non-context-freeness.

Chomsky hierarchy

A containment hierarchy of classes of formal grammars and languages, ranging from Type 0 (unrestricted) to Type 3 (regular).

Dyck language

The language of well-formed parentheses strings, a canonical example of a context-free language.