*** Welcome to piglix ***

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 , the language of all non-empty even-length strings, the entire first halves of which are 's, and the entire second halves of which are 's. is generated by the grammar . This language is not regular. It is accepted by the pushdown automaton where is defined as follows:


...
Wikipedia

...