Editing Context-sensitive grammar (section)

=== Formal grammar ===
Let us notate a [[formal grammar]] as <math>G = (N, \Sigma, P, S)</math>, with <math>N</math> a set of nonterminal symbols, <math>\Sigma</math> a set of terminal symbols, <math>P</math> a set of production rules, and <math>S \in N</math> the start symbol.

A string <math>u \in (N \cup \Sigma)^*</math> ''directly yields'', or ''directly derives to'', a string <math>v \in (N \cup \Sigma)^*</math>, denoted as <math>u \Rightarrow v</math>, if ''v'' can be obtained from ''u'' by an application of some production rule in ''P'', that is, if <math>u = \gamma L \delta</math> and <math>v = \gamma R \delta</math>, where <math>(L \to R) \in P</math> is a production rule, and <math>\gamma, \delta \in (N \cup \Sigma)^*</math> is the unaffected left and right part of the string, respectively.
More generally, ''u'' is said to ''yield'', or ''derive to'', ''v'', denoted as <math>u \Rightarrow^* v</math>, if ''v'' can be obtained from ''u'' by repeated application of production rules, that is, if <math>u = u_0 \Rightarrow ... \Rightarrow u_n = v</math> for some ''n'' ≥ 0 and some strings <math>u_1, ..., u_{n-1} \in (N \cup \Sigma)^*</math>. In other words, the relation <math>\Rightarrow^*</math> is the [[reflexive transitive closure]] of the relation <math>\Rightarrow</math>.

The '''language''' of the grammar ''G'' is the set of all terminal-symbol strings derivable from its start symbol, formally: <math>L(G) = \{ w \in \Sigma^* \mid S \Rightarrow^* w \}</math>.
Derivations that do not end in a string composed of terminal symbols only are possible, but do not contribute to ''L''(''G'').