in formal language theory, a context-free language (cfl) is a language generated by some context-free grammar (cfg). different cf grammars can generate the same cf language. it is important to distinguish properties of the language (intrinsic properties) from properties of a particular grammar (extrinsic properties). 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. indeed, given a cfg, there is a direct way to produce a pushdown automaton for the grammar (and corresponding language), though going the other way (producing a grammar given an automaton) is not as direct. context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar s\to ss ~|~ (s) ~|~ \varepsilon. also, most arithmetic expressions are generated by context-free grammars. ==examples== an archetypal context-free language is l = \{a^nb^n:n\geq1\}, 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 s\to asb ~|~ ab. this language is not regular. it is accepted by the pushdown automaton m=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\}) where \delta is defined as follows:meaning of \delta's arguments and results: \delta(\mathrm{state}_1, \mathrm{read}, \mathrm{pop}) = (\mathrm{state}_2, \mathrm{push}) \delta(q_0, a, z) = (q_0, az) \delta(q_0, a, a) = (q_0, aa) \delta(q_0, b, a) = (q_1, \varepsilon) \delta(q_1, b, a) = (q_1, \varepsilon) 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 \{a^n b^m c^m d^n | n, m > 0\} with \{a^n b^n c^m d^m | n, m > 0\}. this set is context-free, since the union of two context-free languages is always context-free. but there is no way to unambiguously parse strings in the (non-context-free) subset \{a^n b^n c^n d^n | n > 0\} which is the intersection of these two languages. == languages that are not context-free == the set \{a^n b^n c^n d^n | n > 0\} is a context-sensitive language, but there does not exist a context-free grammar generating this language. so 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 or a number of other methods, such as ogden's lemma or parikh's theorem.how to prove that a language is not context-free? == closure properties == con
Formal_languages Languages Linguistics