Context-free language
From Wikipedia, the free encyclopedia
| The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style. |
A context-free language is a formal language that can be defined by a context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.
Contents |
[edit] Examples
An archetypical context-free language is <math>L = \{a^nb^n:n\geq1\}</math>, the language of all non-empty 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,b\}, \{a,z\}, \delta, q_0, \{q_f\})</math> where <math>\delta</math> is defined as follows:
<math>\delta(q_0, a, z) = (q_0, a)</math>
<math>\delta(q_0, a, a) = (q_0, a)</math>
<math>\delta(q_0, b, a) = (q_1, x)</math>
<math>\delta(q_1, b, a) = (q_1, x)</math>
<math>\delta(q_1, b, z) = (q_f, z)</math>
where z is inital stack symbol and x means pop action.
Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar <math>S\to SS ~|~ (S) ~|~ \lambda</math>. Also, most arithmetic expressions are generated by context-free grammars.
[edit] 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 <math>L^*</math> of L
- the image φ(L) of L under a homomorphism φ
- the concatenation <math>L \circ P</math> of L and P
- the union <math>L \cup P</math> of L and P
- the intersection (with a regular language) <math>L \cap D</math> of L and D
Context-free languages are not closed under complement, intersection, or difference.
[edit] Nonclosure under intersection
The context-free languages are not closed under intersection. Proving this is given as an exercise in Sipser 97. It can be seen by taking the languages <math>A = \{a^m b^n c^n \mid m, n \geq 0 \}</math> and <math>B = \{a^n b^n c^m \mid m,n \geq 0\}</math>, which are both context-free. Their intersection is <math>A \cap B = \{ a^n b^n c^n \mid n \geq 0\}</math>, which can be shown to be non-context-free by the pumping lemma for context-free languages.
[edit] Decidability properties
The following problems for context-free languages are undecidable:
- Equivalence: given two context-free grammars A and B, is <math>L(A)=L(B)</math>?
- is <math>L(A) \cap L(B) = \emptyset </math> ?
- is <math>L(A)=\Sigma^*</math> ?
- is <math>L(A) \subseteq L(B)</math> ?
The following problems are decidable for context-free languages:
- is <math>L(A)=\emptyset</math> ?
- is <math>L(A)</math> finite?
- Membership: given any word w, does <math>w \in L(A)</math> ? (membership problem is even polynomially decidable - see CYK algorithm)
[edit] Properties of context-free languages
- The reverse of a context-free language is context-free, but the complement need not be.
- Every regular language is context-free because it can be described by a regular grammar.
- The intersection of a context-free language and a regular language is always context-free.
- There exist context-sensitive languages which are not context-free.
- To prove that a given language is not context-free, one may employ the pumping lemma for context-free languages.
[edit] References
- 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 |
| n/a | Indexed | Indexed | Nested stack |
| n/a | Tree-adjoining | Mildly context-sensitive | Embedded pushdown |
| Type-2 | Context-free | Context-free | Nondeterministic pushdown |
| n/a | Deterministic context-free | Deterministic context-free | Deterministic pushdown |
| Type-3 | Regular | Regular | Finite |
| Each category of languages or grammars is a proper subset of the category directly above it. | |||
cs:Bezkontextový jazyk de:Kontextfreie Sprache es:Lenguaje libre de contexto hr:Kontekstno neovisni jezik it:Linguaggio libero dal contesto he:שפה חופשית הקשר ja:文脈自由言語 pl:Język bezkontekstowy ro:Limbaje independente de context fi:Yhteydetön kieli
