A context-free language is a formal language that is accepted by some pushdown automaton. Context-free languages can be generated by context-free grammars.

Examples

An archetypical context-free language is , the language of all even-lengths strings, the entire first halves of which are a's, and the entire second halves of which are b's. L is generated by the grammar , and is accepted by the pushdown automaton M = ({q₀,q₁,q_f},{a},{a,b,z},δ,q₀,{q_f}) where δ is defined as follows:

Context-free languages have many applications in programming languages; for example, the language of all properly matched parenthesis is generated by the grammar . Also, most arithmetic expressions are generated by context-free grammars.

Closure properties

The family of context-free languages is closed under concatenation and union but not intersection or difference. It is, however, closed under difference with a regular language.

See also

There is a pumping lemma for context-free languages, that gives a necessary condition for a language to be context-free.