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\; =\; \backslash \{a^nb^n:n\backslash geq1\backslash \}$, the language of all non-empty even-length 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\backslash to\; aSb\; ~|~\; ab$, and is accepted by the pushdown automaton $M=(\backslash \{q\_0,q\_1,q\_f\backslash \},\; \backslash \{a\backslash \},\; \backslash \{a,b,z\backslash \},\; \backslash delta,\; q\_0,\; \backslash \{q\_f\backslash \})$ where $\backslash delta$ is defined as follows:

$\backslash delta(q\_0,\; a,\; z)\; =\; (q\_0,\; a)$
$\backslash delta(q\_0,\; b,\; ax)\; =\; (q\_1,\; x)$
$\backslash delta(q\_1,\; b,\; ax)\; =\; (q\_1,\; x)$
$\backslash 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 parentheses is generated by the grammar $S\backslash to\; SS\; ~|~\; (S)\; ~|~\; \backslash lambda$. Also, most arithmetic expressions are generated by context-free grammars.

Closure Properties

---

Context-Free Languages are closed under the following operations. That is, if L and P are Context-Free Languages and D is a Regular Language, the following languages are Context-Free as well:

• the Kleene star L^* of L
• the homomorphism φ(L) of L
• the concatenation LP of L and P
• the union L∪P of L and P
• the intersection (with a Regular Language) L∩D of L and D

Context-Free Languages are not closed under complement, intersection, or difference.

See also

---

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

References

---

• Chapter 2: Context-Free Languages, pp.91–122.

formal languages

Bezkontextový jazyk | Kontextfreie Sprache | Linguaggio context-free | שפה חופשית הקשר | Język bezkontekstowy | Limbaje independente de context | Yhteydetön kieli