Context-free language
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 |
Examples
An archetypical context-free language is , 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 , and is accepted by the pushdown automaton M = ({q0,q1,qf},{a,b},{a,z},δ,q0,{qf}) where δ is defined as follows:
δ(q0,a,z) = (q0,a)
δ(q0,a,a) = (q0,a)
δ(q0,b,a) = (q1,x)
δ(q1,b,a) = (q1,x)
δ(q1,b,z) = (qf,z)
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 . 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 image φ(L) of L under a homomorphism φ
- the concatenation of L and P
- the union of L and P
- the intersection (with a regular language) of L and D
Context-free languages are not closed under complement, intersection, or difference.
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 and , which are both context-free. Their intersection is , which can be shown to be non-context-free by the pumping lemma for context-free languages.
Decidability properties
The following problems for context-free languages are undecidable:
- Equivalence: given two context-free grammars A and B, is L(A) = L(B)?
- is ?
- is L(A) = Σ * ?
- is ?
The following problems are decidable for context-free languages:
- is ?
- is L(A) finite?
- Membership: given any word w, does ? (membership problem is even polynomially decidable - see CYK algorithm)
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.
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. |