In formal language theory, a context-free grammar (CFG) is a grammar in which every production rule is of the form
- V → w
where V is a single nonterminal symbol, and w is a string of terminalsand/or nonterminals (possibly empty). The term "context-free" expresses the fact that nonterminals can be rewritten without regard to the context in which they occur. A formal language is context-free if some context-free grammar generates it.
This grammar generates the context-free language { anbn: n ≥ 1 }
A formal grammar G = (N, Σ, P, S), where N is a set of nonterminal symbols, Σ is a set of terminal symbols, P is a set of production rules, and Sis the start symbol, is context-sensitive if all rules in P are of the form
- αAβ → αγβ
where A ∈ N (i.e., A is a single nonterminal), α,β ∈ (N U Σ)* (i.e., α and β are strings of nonterminals and terminals) and γ ∈ (N U Σ)+(i.e., γ is a nonempty string of nonterminals and terminals).
The name context-sensitive is explained by the α and β that form the context of A and determine whether A can be replaced with γ or not. This is different from a context-free grammar where the context of a nonterminal is not taken into consideration. (Indeed, every production of a context free grammar is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty)).
This grammar generates the canonical non-context-free language { anbncn : n ≥ 1 }