Categories: Formal languages | Automata theory

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 $L = \{a^nb^n:n\geq1\}$ , 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 $S\to aSb ~|~ ab$ , and is accepted by the pushdown automaton $M = ({q 0, q 1, q f},{a},{a, b, z},δ, q 0,{q f})$ where $δ$ is defined as follows:

$δ(q 0, a, z) = (q 0, a)$
$δ(q 0, b, a x) = (q 1, x)$
$δ(q 1, b, a x) = (q 1, x)$
$δ(q 1, b, b z) = (q f, z)$

Context-free languages have many applications in programming languages; for example, the language of all properly matched parenthesis is generated by the grammar $S\to SS ~|~ (S) ~|~ \lambda$ . 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.

Context-free language

Examples

Closure properties

See also