Context-free language

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 <math>L = \{a^nb^n:n\geq1\}<math>, the language of all even-lengths strings, the entire first halves of which are <math>a<math>'s, and the entire second halves of which are <math>b<math>'s. <math>L<math> is generated by the grammar <math>S\to aSb ~|~ ab<math>, and is accepted by the pushdown automaton <math>M=(\{q_0,q_1,q_f\}, \{a\}, \{a,b,z\}, \delta, q_0, \{q_f\})<math> where <math>\delta<math> 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 <math>S\to SS ~|~ (S) ~|~ \lambda<math>. 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.