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.

Examples

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

δ(q 0, a, z) = (q 0, a)

δ(q 0, a, a) = (q 0, a)

δ(q 0, b, a) = (q 1, x)

δ(q 1, b, a) = (q 1, x)

δ(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\to 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 image φ(L) of L under a homomorphism φ
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) = Σ *$ ?
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

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

Automata theory: formal languages and formal grammars
Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
n/a	Indexed	Indexed	Nested stack
n/a	Tree-adjoining	Mildly context-sensitive	Embedded pushdown
Type-2	Context-free	Context-free	Nondeterministic pushdown
n/a	Deterministic context-free	Deterministic context-free	Deterministic pushdown
Type-3	Regular	Regular	Finite
Each category of languages or grammars is a proper subset of the category directly above it.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	What year is this in chinese calender?
	Who was the female drummer and backup singer who sang with Robbie Nevil on the C'est la Vie track?
	Which universities in the US give need-based financial aid to international students?
	How do you delete a Label in Gmail if the 'Delete Label xx' does not work?
	What sports are in the Olympics?