# Context free language

*34,189*pages on

this wiki

Assessment |
Biopsychology |
Comparative |
Cognitive |
Developmental |
Language |
Individual differences |
Personality |
Philosophy |
Social |

Methods |
Statistics |
Clinical |
Educational |
Industrial |
Professional items |
World psychology |

**Language:**
Linguistics ·
Semiotics ·
Speech

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.

## Contents

[show]## ExamplesEdit

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"

Context-Free Languages are not closed under complement, intersection, or difference.

## See alsoEdit

There is a pumping lemma for context-free languages, that gives a necessary condition for a language to be context-free.

## References Edit

- 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 | |||
---|---|---|---|

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 superset of the category directly beneath it. |

de:Kontextfreie Sprachehe:שפה חופשית הקשרro:Limbaje independente de context fi:Yhteydetön kieli

This page uses Creative Commons Licensed content from Wikipedia (view authors). |