Individual differences |
Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |
An archetypical context-free language is , the language of all non-empty even-length strings, the entire first halves of which are 's, and the entire second halves of which are 's. is generated by the grammar , and is accepted by the pushdown automaton where is defined as follows:
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.
Closure Properties Edit
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"
There is a pumping lemma for context-free languages, that gives a necessary condition for a language to be context-free.
- 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|
|Type-0||Unrestricted||Recursively enumerable||Turing machine|
|n/a||(no common name)||Recursive||Decider|
|Each category of languages or grammars is a proper superset of the category directly beneath it.|
|This page uses Creative Commons Licensed content from Wikipedia (view authors).|