Context-free language

From Wikipedia, the free encyclopedia

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

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 1 Examples 2 Closure Properties 2.1 Nonclosure under intersection 3 Decidability properties 4 Properties of context-free languages 5 References

[edit] Examples

An archetypical context-free language is , 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 , and is accepted by the pushdown automaton M = ({q₀,q₁,q_f},{a,b},{a,z},δ,q₀,{q_f}) where δ is defined as follows:

δ(q₀,a,z) = (q₀,a)
δ(q₀,a,a) = (q₀,a)
δ(q₀,b,a) = (q₁,x)
δ(q₁,b,a) = (q₁,x)
δ(q₁,b,z) = (q_f,z)

δ(state₁,read,pop) = (state₂,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 . Also, most arithmetic expressions are generated by context-free grammars.

[edit] 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 of L and P
• the union of L and P
• the intersection (with a regular language) of L and D

Context-free languages are not closed under complement, intersection, or difference.

[edit] 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 and , which are both context-free. Their intersection is , which can be shown to be non-context-free by the pumping lemma for context-free languages.

[edit] 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  ?
• is L(A) = Σ ^*  ?
• is  ?

The following problems are decidable for context-free languages:

• is  ?
• is L(A) finite?
• Membership: given any word w, does  ? (membership problem is even polynomially decidable - see CYK algorithm)

[edit] 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.

[edit] 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 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		Star-free	Counter-Free
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.