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\}, \delta, q_0, \{q_f\})

where

\delta

is defined as follows:

\delta(q_0, a, z) = (q_0, a)

\delta(q_0, b, ax) = (q_1, x)

\delta(q_1, b, ax) = (q_1, x)

\delta(q_1, b, bz) = (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