Ad blocker interference detected!
Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers
Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.
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).|