Editing Context-sensitive grammar (section)

=== Context-sensitive grammar ===
A formal grammar is '''context-sensitive''' if each rule in ''P'' is either of the form <math>S \to \varepsilon</math> where <math>\varepsilon</math> is the [[empty string]], or of the form
: α''A''β → αγβ
with ''A'' ∈ ''N'',<ref group="note">i.e., ''A'' a single [[nonterminal]]</ref> <math>\alpha, \beta\in (N \cup \Sigma \setminus\{S\})^*</math>,<ref group="note">i.e., α and β strings of nonterminals (except for the start symbol) and [[Terminal symbol|terminals]]</ref> and <math>\gamma\in (N \cup \Sigma \setminus\{S\})^+</math>.<ref group="note">i.e., γ is a nonempty string of nonterminals (except for the start symbol) and terminals</ref>

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.
By contrast, in a [[context-free grammar]], no context is present: the left hand side of every production rule is just a nonterminal.

The string γ is not allowed to be empty.  Without this restriction, the resulting grammars become equal in power to [[unrestricted grammar]]s.<ref name="Vide1999" />