Context-free language: Information from Answers.com

The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style. (October 2009)

In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.

1 Examples
2 Closure properties
- 2.1 Nonclosure under intersection
3 Decidability properties
4 Properties of context-free languages
5 References

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,λ, z) = (q f, z)$

$δ(state 1,read,pop) = (state 2,push)$
where $z$ is initial 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. This 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 are undecidable for arbitrary context-free grammars A and B:

Equivalence: 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 arbitrary 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

Seymour Ginsburg (1966). The Mathematical Theory of Context-Free Languages. New York, NY, USA: McGraw-Hill, Inc..
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 etc.	(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
n/a	n/a	Star-free	Aperiodic finite

Each category of languages or grammars is a proper subset of the category directly above it;
and any automaton in each category has an equivalent automaton in 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

	Discuss the usefulness of Context Free Grammer CFG Construct context free grammer for all the conditional and looping statements in C language? Read answer...
	What cultures have high context languages? Read answer...
	Why is a programming language not described in terms of context-sensitive grammar? Read answer...

	Want context free grammar for c language compiler?
	How do you write a context free grammar for c language?
	Want context free grammer for c language compiler?

Context-free language

Contents