Context-free language

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help Wikipedia by improving the introduction according to the guidelines laid out at Wikipedia:Guide to layout. You can discuss the issue on the talk page.

A context-free language is a formal language that is a member of the set of languages defined by context-free grammars. The set of context-free languages is identical to the set of languages accepted by pushdown automata.

1 Examples
2 Closure Properties
3 See also
4 References

[edit] Examples

An archetypical context-free language is <math>L = \{a^nb^n:n\geq1\}</math>, the language of all non-empty even-length strings, the entire first halves of which are <math>a</math>'s, and the entire second halves of which are <math>b</math>'s. <math>L</math> is generated by the grammar <math>S\to aSb ~|~ ab</math>, and is accepted by the pushdown automaton <math>M=(\{q_0,q_1,q_f\}, \{a\}, \{a,b,z\}, \delta, q_0, \{q_f\})</math> where <math>\delta</math> is defined as follows:

<math>\delta(q_0, a, z) = (q_0, a)</math>
<math>\delta(q_0, b, ax) = (q_1, x)</math>
<math>\delta(q_1, b, ax) = (q_1, x)</math>
<math>\delta(q_1, b, bz) = (q_f, z)</math>

Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar <math>S\to SS ~|~ (S) ~|~ \lambda</math>. 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 <math>L^*</math> of L
the homomorphism φ(L) of L
the concatenation <math>L \circ P</math> of L and P
the union <math>L \cup P</math> of L and P
the intersection (with a Regular Language) <math>L \cap D</math> of L and D

Context-Free Languages are not closed under complement, intersection, or difference.

[edit] See also

There is a pumping lemma for context-free languages that gives a necessary condition for a language to be context-free.

[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
Type-2	Context-free	Context-free	Pushdown
Type-3	Regular	Regular	Finite
Each category of languages or grammars is a proper subset of the category directly above it.