Context-free language
Encyclopedia : C : CO : CON : 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 [L = \], 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 [S\to aSb ~|~ ab], and is accepted by the pushdown automaton [M=(\, \, \, \delta, q_0, \)] where [\delta] is defined as follows:
[\delta(q_0, b, ax) = (q_1, x)]
[\delta(q_1, b, ax) = (q_1, x)]
[\delta(q_1, b, bz) = (q_f, z)]
Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar [S\to SS ~|~ (S) ~|~ \lambda]. Also, most arithmetic expressions are generated by context-free grammars.
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 homomorphism φ(L) of L
- the concatenation LP of L and P
- the union L∪P of L and P
- the intersection (with a Regular Language) L∩D of L and D
Context-Free Languages are not closed under complement, intersection, or difference.
See also
There is a pumping lemma for context-free languages that gives a necessary condition for a language to be context-free.References
- 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. | |||
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.