 Contextfree language

In formal language theory, a contextfree language is a language generated by some contextfree grammar. The set of all contextfree languages is identical to the set of languages accepted by pushdown automata.
Contents
Examples
An archetypical contextfree language is , the language of all nonempty evenlength 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 , 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.Contextfree languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar . Also, most arithmetic expressions are generated by contextfree grammars.
Closure properties
Contextfree languages are closed under the following operations. That is, if L and P are contextfree languages, the following languages are contextfree as well:
 the union of L and P
 the reversal of L
 the concatenation of L and P
 the Kleene star L ^{*} of L
 the image φ(L) of L under a homomorphism φ
 the image φ ^{− 1}(L) of L under an inverse homomorphism φ ^{− 1}
 the cyclic shift of L (the language )
Contextfree languages are not closed under complement, intersection, or difference. However, if L is a contextfree language and D is a regular language then both their intersection and their difference are contextfree languages.
Nonclosure under intersection and complement
The contextfree languages are not closed under intersection. This can be seen by taking the languages and , which are both contextfree. Their intersection is , which can be shown to be noncontextfree by the pumping lemma for contextfree languages.
Contextfree languages are also not closed under complementation, as for any languages A and B: .
Decidability properties
The following problems are undecidable for arbitrary contextfree grammars A and B:
 Equivalence: is L(A) = L(B)?
 is ? (However, the intersection of a contextfree language and a regular language is contextfree, so if B were a regular language, this problem becomes decidable.)
 is L(A) = Σ ^{*} ?
 is ?
The following problems are decidable for arbitrary contextfree languages:
 is ?
 is L(A) finite?
 Membership: given any word w, does ? (membership problem is even polynomially decidable  see CYK algorithm and Early's Algorithm)
Properties of contextfree languages
 The reverse of a contextfree language is contextfree, but the complement need not be.
 Every regular language is contextfree because it can be described by a contextfree grammar.
 The intersection of a contextfree language and a regular language is always contextfree.
 There exist contextsensitive languages which are not contextfree.
 To prove that a given language is not contextfree, one may employ the pumping lemma for contextfree languages.
References
 Seymour Ginsburg (1966). The Mathematical Theory of ContextFree Languages. New York, NY, USA: McGrawHill, Inc..
 Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 053494728X. Chapter 2: ContextFree Languages, pp. 91–122.
 JeanMichel Autebert, Jean Berstel, Luc Boasson, ContextFree Languages and PushDown Automata, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, SpringerVerlag, 1997, 111174.
Automata theory: formal languages and formal grammars Chomsky hierarchy Type0—Type1———Type2——Type3—Grammars (no common name)Linear contextfree rewriting systems etc.Treeadjoining etc.—Languages ContextfreeMinimal automaton Thread automataEach category of languages is a proper subset of the category directly above it.  Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.Categories: Formal languages
Wikimedia Foundation. 2010.