Context-free language

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 . Also, most arithmetic expressions are generated by context-free grammars.

Examples

An archetypal 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:

A-Z

A-Z or A to Z may refer to:

Other uses

See also

Free

Media

Arts and philosophy

Computing

Mathematics

Context-free grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form

where is a single nonterminal symbol, and is a string of terminals and/or nonterminals ( can be empty). A formal grammar is considered "context free" when its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a context-sensitive grammar.

Such a grammar has long lists of words, and also rules on what types of words can be added in what order. Higher rules combine several lower rules to make a sentence. Such sentences will be grammatically correct, but may not have any meaning. Each rule has its own symbol, which can be replaced with symbols representing lower rules, which can be replaced with words.

This can also be done in reverse to check if a sentence is grammatically correct.