In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
Contents
- Context free grammar
- Automata
- Examples
- Dyck language
- Context free parsing
- Closure
- Nonclosure under intersection complement and difference
- Decidability
- Languages that are not context free
- References
Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by context-free grammars.
Context-free grammar
Different CF grammars can generate the same CF language. Intrinsic properties of the language can be distinguished from extrinsic properties of a particular grammar.
Automata
The set of all context-free languages is identical to the set of languages accepted by pushdown automata, which makes these languages amenable to parsing. Further, for a given a CFG, there is a direct way to produce a pushdown automaton for the grammar (and thereby the corresponding language), though going the other way (producing a grammar given an automaton) is not as direct.
Examples
A model context-free language is
Unambiguous CFLs are a proper subset of all CFLs: there are inherently ambiguous CFLs. An example of an inherently ambiguous CFL is the union of
Dyck language
The language of all properly matched parentheses is generated by the grammar
Context-free parsing
The context-free nature of the language makes it simple to parse with a pushdown automaton.
Determining an instance of the membership problem; i.e. given a string
Practical uses of context-free languages require also to produce a derivation tree that exhibits the structure that the grammar associates with the given string. The process of producing this tree is called parsing. Known parsers have a time complexity that is cubic in the size of the string that is parsed.
Formally, the set of all context-free languages is identical to the set of languages accepted by pushdown automata (PDA). Parser algorithms for context-free languages include the CYK algorithm and Earley's Algorithm.
A special subclass of context-free languages are the deterministic context-free languages which are defined as the set of languages accepted by a deterministic pushdown automaton and can be parsed by a LR(k) parser.
See also parsing expression grammar as an alternative approach to grammar and parser.
Closure
Context-free languages are closed under the following operations. That is, if L and P are context-free languages, the following languages are context-free as well:
Context-free languages are not closed under complement, intersection, or difference. This was proved by Scheinberg in 1960. However, if L is a context-free language and D is a regular language then both their intersection
Nonclosure under intersection, complement, and difference
The context-free languages are not closed under intersection. This can be seen by taking the languages
Context-free languages are also not closed under complementation, as for any languages A and B:
Context-free language are also not closed under difference: LC = Σ* L.
Decidability
The following problems are undecidable for arbitrarily given context-free grammars A and B:
The following problems are decidable for arbitrary context-free languages:
According to Hopcroft, Motwani, Ullman (2003), many of the fundamental closure and (un)decidability properties of context-free languages were shown in the 1961 paper of Bar-Hillel, Perles, and Shamir
Languages that are not context-free
The set