CONTEXT-FREE LANGUAGE

A 'context-free language' is a formal language that can be defined by a context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.

Contents

Examples

Closure Properties

Nonclosure under intersection

Decidability properties

Properties of context-free languages

References

Examples

An archetypical context-free language is $L\; =\; \{a^nb^n:ngeq1\}$, 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\; o\; aSb\; ~|~\; ab$, and is accepted by the pushdown automaton $M=(\{q\_0,q\_1,q\_f\},\; \{a,b\},\; \{a,z\},\; delta,\; q\_0,\; \{q\_f\})$ where $delta$ is defined as follows:

$delta(q\_0,\; a,\; z)\; =\; (q\_0,\; a)$

$delta(q\_0,\; a,\; a)\; =\; (q\_0,\; a)$

$delta(q\_0,\; b,\; a)\; =\; (q\_1,\; x)$

$delta(q\_1,\; b,\; a)\; =\; (q\_1,\; x)$

$delta(q\_1,\; b,\; z)\; =\; (q\_f,\; z)$

where z is inital stack symbol and x means pop action.

Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar $S\; o\; SS\; ~|~\; (S)\; ~|~\; 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 $L\; circ\; P$ of ''L'' and ''P''

★ the union $L\; cup\; P$ of ''L'' and ''P''

★ the intersection (with a regular language) $L\; cap\; D$ of ''L'' and ''D''
Context-free languages are not closed under complement, intersection, or difference.

Nonclosure under intersection

The context-free languages are not closed under intersection. Proving this is given as an exercise in Sipser 97. It can be seen by taking the languages $A\; =\; \{a^m\; b^n\; c^n\; mid\; m,\; n\; geq\; 0\; \}$ and $B\; =\; \{a^n\; b^n\; c^m\; mid\; m,n\; geq\; 0\}$, which are both context-free. Their intersection is $A\; cap\; B\; =\; \{\; a^n\; b^n\; c^n\; mid\; n\; geq\; 0\}$, which can be shown to be non-context-free by the pumping lemma for context-free languages.

Decidability properties

The following problems for context-free languages are undecidable:

★ Equivalence: given two context-free grammars A and B, is $L(A)=L(B)$?

★ is $L(A)\; cap\; L(B)\; =\; emptyset$ ?

★ is $L(A)=Sigma^$
★ ?

★ is $L(A)\; subseteq\; L(B)$ ?
The following problems are decidable for context-free languages:

★ is $L(A)=emptyset$ ?

★ is L(A) finite?

★ Membership: given any word w, does $w\; in\; L(A)$ ? (membership problem is even polynomially decidable - see CYK algorithm)

Properties of context-free languages

★ The reverse of a context-free language is context-free, but the complement need not be.

★ Every regular language is context-free because it can be described by a regular grammar.

★ The intersection of a context-free language and a regular language is always context-free.

★ There exist context-sensitive languages which are not context-free.

★ To prove that a given language is not context-free, one may employ the pumping lemma for context-free languages.

References

★ Introduction to the Theory of Computation, Michael Sipser, , , PWS Publishing, 1997, ISBN 0-534-94728-X Chapter 2: Context-Free Languages, pp.91–122.