Context-free language

In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).

Context-free languages have many applications in programming languages, in partiular, most arithmetic expressions are generated by context-free grammars.

Different CF grammars can generate the same CF language. Intrinsic properties of the language can be distinguished from extrinsic properties of a particular grammar.

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.

A model context-free language is $L=\{a^{n}b^{n}:n\geq 1\}$ $L=\{a^{n}b^{n}:n\geq 1\}$ , the language of all non-empty even-length strings, the entire first halves of which are $a$ $a$ 's, and the entire second halves of which are $b$ $b$ 's. $L$ $L$ is generated by the grammar $S\to aSb~|~ab$ $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}\})$ $M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})$ where $\delta$ $\delta$ is defined as follows:

...
Wikipedia