In formal language theory, a contextfree language is a language generated by some contextfree grammar. The set of all contextfree languages is identical to the set of languages accepted by pushdown automata.
Contents
Examples
An archetypical contextfree language is , the language of all nonempty evenlength 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 = ({q_{0},q_{1},q_{f}},{a,b},{a,z},δ,q_{0},{q_{f}}) where δ is defined as follows:
δ(q_{0},a,z) = (q_{0},a)
δ(q_{0},a,a) = (q_{0},a)
δ(q_{0},b,a) = (q_{1},x)
δ(q_{1},b,a) = (q_{1},x)
δ(q_{1},λ,z) = (q_{f},z)
δ(state_{1},read,pop) = (state_{2},push)
where z is initial stack symbol and x means pop action.
Contextfree 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 contextfree grammars.
Closure properties
Contextfree languages are closed under the following operations. That is, if L and P are contextfree languages, the following languages are contextfree as well:
Full article ▸
