Context-Free Language

A context-free language is a formal language that can be generated by a context-free grammar and recognized by a pushdown automaton. These two characterizations — grammatical and mechanical — are equivalent, and their equivalence is one of the foundational theorems of formal language theory. Context-free languages capture exactly those patterns that exhibit nested, hierarchical structure without arbitrary cross-dependencies: balanced parentheses, XML tags, arithmetic expressions, and the syntax of nearly every programming language. The class is not closed under intersection or complementation, a fact that has direct consequences for the design of parser generators and static analysis tools. Understanding where context-free languages end and context-sensitive languages begin — a boundary tested by the pumping lemma and Ogden's lemma — is essential for anyone who builds languages or analyzes their limits.