What is "context-free grammar"

n. (context computing theory English) a formal grammar in which every production rule is such that the left-hand side is exactly one non-terminal symbol and the right-hand side is zero or more terminal symbols and/or nonterminal symbols. Abbreviation: CFG.

A context-free grammar (CFG) is a term used in formal language theory to describe a certain type of formal grammar. A context-free grammar is a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the rule

A  →  α

Replaces A with α. There can be multiple replacement rules for any given value. For example,

A  →  α

A  →  β

means that A can be replaced with either α or β.

In context-free grammars, all rules are one to one, one to many, or one to none. These rules can be applied regardless of context. The left-hand side of the production rule is also always a nonterminal symbol. This means that the symbol does not appear in the resulting formal language. So in our case, our language contains the letters α and β but not A.

Rules can also be applied in reverse to check if a string is grammatically correct according to the grammar.

Here is an example context-free grammar which describes all two-letter strings containing the letters α and β.

S  →  AA

A  →  α

A  →  β

If we start with the nonterminal symbol S then we can use the rule S  →  AA to turn S into AA. We can then apply one of the two later rules. For example, if we apply A  →  β to the first A we get βA. If we then apply A  →  α to the second A we get βα. Since both α and β are terminal symbols, and in context-free grammars terminal symbols never appear on the left hand side of a production rule, there are no more rules that can be applied. This same process can be used, applying the second two rules in different orders in order to get all possible strings within our simple context-free grammar.

Languages generated by context-free grammars are known as context-free languages (CFL). Different context-free grammars can generate the same context-free language. It is important to distinguish properties of the language (intrinsic properties) from properties of a particular grammar (extrinsic properties). The language equality question (do two given context-free grammars generate the same language?) is undecidable.

Context-free grammars arise in linguistics where they are used to describe the structure of sentences and words in natural language, and they were in fact invented by the linguist Noam Chomsky for this purpose, but have not really lived up to their original expectation. By contrast, in computer science, as the use of recursively-defined concepts increased, they were used more and more. In an early application, grammars are used to describe the structure of programming languages. In a newer application, they are used in an essential part of the Extensible Markup Language (XML) called the Document Type Definition.

In linguistics, some authors use the term phrase structure grammar to refer to context-free grammars, whereby phrase-structure grammars are distinct from dependency grammars. In computer science, a popular notation for context-free grammars is Backus–Naur Form, or BNF.