Context-free language
|
|
A context-free language is a formal language that is accepted by some pushdown automaton. Context-free languages can be generated by context-free grammars.
Examples
An archetypical context-free language is <math>L = \{a^nb^n:n\geq1\}<math>, the language of all even-lengths 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 parenthesis is generated by the grammar <math>S\to SS ~|~ (S) ~|~ \lambda<math>. Also, most arithmetic expressions are generated by context-free grammars.
Closure properties
The family of context-free languages is closed under concatenation and union but not intersection or difference. It is, however, closed under difference with a regular language.
See also
There is a pumping lemma for context-free languages, that gives a necessary condition for a language to be context-free.
Template:Formal languages and grammarsde:Kontextfreie Sprache