Context-free language
From Freepedia
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-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, 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 intersection and 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.
| Automata theory: formal languages and formal grammars | |||
|---|---|---|---|
| Chomsky hierarchy | Grammars | Languages | Minimal automaton |
| Type-0 | (unrestricted) | Recursively enumerable | Turing machine |
| (unrestricted) | 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 superset of the category directly beneath it. | |||
