Editing Context-sensitive grammar (section)

== Examples ==
=== ''a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>'' ===
The following context-sensitive grammar, with start symbol ''S'', generates the canonical non-[[context-free language]] { ''a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>'' | ''n'' ≥ 1 } :{{cn|date=January 2022}}

{|
|- 
| 1. &nbsp; &nbsp; &nbsp; || || ''S'' &nbsp; &nbsp; || → &nbsp; &nbsp; || ''a'' || ''B'' || ''C'' 
|-
| 2. || || ''S'' || → || ''a'' || ''S'' || ''B'' || ''C''
|-
| 3. || ''C'' || ''B'' || → || ''C'' || ''Z''
|-
| 4. || ''C'' || ''Z'' || → || ''W'' || ''Z''
|-
| 5. || ''W'' || ''Z'' || → || ''W'' || ''C''
|-
| 6. || ''W'' || ''C'' || → || ''B'' || ''C''
|-
| 7. || ''a'' || ''B'' || → || ''a'' || ''b'' 
|-
| 8. || ''b'' || ''B'' || → || ''b'' || ''b''
|
|-
| 9. || ''b'' || ''C'' || → || ''b'' || ''c''
|-
|10. || ''c'' || ''C'' || → || ''c'' || ''c''
|}
<!---
# ''S'' → ''aSBC''
# ''S'' → ''aBC''
# ''CB'' → ''HB''
# ''HB'' → ''HC''
# ''HC'' → ''BC''
# ''aB'' → ''ab''
# ''bB'' → ''bb''
# ''bC'' → ''bc''
# ''cC'' → ''cc''
--->

Rules 1 and 2 allow for blowing-up ''S'' to ''a''<sup>''n''</sup>''BC''(''BC'')<sup>''n''−1</sup>; rules 3 to 6 allow for successively exchanging each ''CB'' to ''BC'' ([[Revesz' trick|four rules]] are needed for that since a rule ''CB'' → ''BC'' wouldn't fit into the scheme α''A''β → αγβ); rules 7–10 allow replacing a non-terminal ''B'' or ''C'' with its corresponding terminal ''b'' or ''c'', respectively, provided it is in the right place.
A generation chain for ''{{not a typo|aaabbbccc}}'' is:
: ''S''
: →<sub>2</sub> {{not a typo|'''aSBC'''}}
: →<sub>2</sub> {{not a typo|''a'''aSBC'''BC''}}
: →<sub>1</sub> {{not a typo|''aa'''aBC'''BCBC''}}
: →<sub>3</sub> {{not a typo|''aaaB'''CZ'''CBC''}}
: →<sub>4</sub> {{not a typo|''aaaB'''WZ'''CBC''}}
: →<sub>5</sub> {{not a typo|''aaaB'''WC'''CBC''}}
: →<sub>6</sub> {{not a typo|''aaaB'''BC'''CBC''}}
: →<sub>3</sub> {{not a typo|''aaaBBC'''CZ'''C''}}
: →<sub>4</sub> {{not a typo|''aaaBBC'''WZ'''C''}}
: →<sub>5</sub> {{not a typo|''aaaBBC'''WC'''C''}}
: →<sub>6</sub> {{not a typo|''aaaBBC'''BC'''C''}}
: →<sub>3</sub> {{not a typo|''aaaBB'''CZ'''CC''}}
: →<sub>4</sub> {{not a typo|''aaaBB'''WZ'''CC''}}
: →<sub>5</sub> {{not a typo|''aaaBB'''WC'''CC''}}
: →<sub>6</sub> {{not a typo|''aaaBB'''BC'''CC''}}
: →<sub>7</sub> {{not a typo|''aa'''ab'''BBCCC''}}
: →<sub>8</sub> {{not a typo|''aaa'''bb'''BCCC''}}
: →<sub>8</sub> {{not a typo|''aaab'''bb'''CCC''}}
: →<sub>9</sub> {{not a typo|''aaabb'''bc'''CC''}}
: →<sub>10</sub> {{not a typo|''aaabbb'''cc'''C''}}
: →<sub>10</sub> {{not a typo|''aaabbbc'''cc'''''}}
:

=== ''a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>d<sup>n</sup>'', etc. ===
More complicated grammars can be used to parse { ''a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>d<sup>n</sup>'' | ''n'' ≥ 1 }, and other languages with even more letters. Here we show a simpler approach using non-contracting grammars:{{cn|date=January 2022}}
Start with a kernel of regular productions generating the sentential forms
<math>(ABCD)^{n}abcd</math> and then include the non contracting productions
<math>p_{Da} : Da\rightarrow aD</math>,
<math>p_{Db} : Db\rightarrow bD</math>,
<math>p_{Dc} : Dc\rightarrow cD</math>,
<math>p_{Dd} : Dd\rightarrow dd</math>,
<math>p_{Ca} : Ca\rightarrow aC</math>,
<math>p_{Cb} : Cb\rightarrow bC</math>,
<math>p_{Cc} : Cc\rightarrow cc</math>,
<math>p_{Ba} : Ba\rightarrow aB</math>,
<math>p_{Bb} : Bb\rightarrow bb</math>,
<math>p_{Aa} : Aa\rightarrow aa</math>.

=== ''a<sup>m</sup>b<sup>n</sup>c<sup>m</sup>d<sup>n</sup>'' ===
A non contracting grammar (for which there is an equivalent CSG) for the language <math>L_{Cross} = \{ a^mb^nc^{m}d^{n} \mid m \ge 1, n \ge 1 \}</math> is defined by
:<math>p_0 : S \rightarrow RT</math>,
:<math>p_1 : R\rightarrow aRC | aC</math>,
:<math>p_3 : T\rightarrow BTd | Bd</math>,
:<math>p_5 : CB\rightarrow BC</math>,
:<math>p_6 : aB\rightarrow ab</math>, 
:<math>p_7 : bB\rightarrow bb</math>, 
:<math>p_8 : Cd\rightarrow cd</math>, and
:<math>p_9 : Cc\rightarrow cc</math>.

With these definitions, a derivation for <math>a^3b^2c^3d^2</math> is:
<math>S
\Rightarrow_{p_0} RT
\Rightarrow_{p^{2}_{1}p_{2}} a^3C^3T
\Rightarrow_{p_{3}p_{4}    } a^3C^3B^2d^2
\Rightarrow_{p^{6}_{5}     } a^3B^2C^3d^2
\Rightarrow_{p_{6}p_{7}    } a^3b^2C^3d^2
\Rightarrow_{p_{8}p^{2}_{9}} a^3b^2c^3d^2
</math>.{{citation needed|date=November 2018}}

=== ''a''<sup>2<sup>''i''</sup></sup> ===
A noncontracting grammar for the language { ''a''<sup>2<sup>''i''</sup></sup> | ''i'' ≥ 1 } is constructed in Example 9.5 (p.&nbsp;224) of (Hopcroft, Ullman, 1979):<ref>They obtained the grammar by systematic transformation of an [[unrestricted grammar]], given in Exm. 9.4, viz.:
# <math>S\rightarrow ACaB</math>,
# <math>Ca\rightarrow aaC</math>,
# <math>CB\rightarrow DB</math>,
# <math>CB\rightarrow E</math>,
# <math>aD\rightarrow Da</math>,
# <math>AD\rightarrow AC</math>,
# <math>aE\rightarrow Ea</math>,
# <math>AE\rightarrow \varepsilon</math>.
In the context-sensitive grammar, a string enclosed in square brackets, like <math>[ACaB]</math>, is considered a single symbol (similar to e.g. <code><name-part></code> in [[Backus–Naur form#Example|Backus–Naur form]]). The symbol names are chosen to resemble the unrestricted grammar. Likewise, rule groups in the context-sensitive grammar are numbered by the unrestricted-grammar rule they originated from.</ref>

# <math>S\rightarrow [ACaB]</math>
# <math>\begin{cases}
\ [Ca]a\rightarrow aa[Ca] \\ 
\ [Ca][aB]\rightarrow aa[CaB] \\ 
\ [ACa]a\rightarrow [Aa]a[Ca] \\ 
\ [ACa][aB]\rightarrow [Aa]a[CaB] \\ 
\ [ACaB]\rightarrow [Aa][aCB] \\ 
\ [CaB]\rightarrow a[aCB]
\end{cases}</math>
# <math>[aCB]\rightarrow [aDB]</math>
# <math>[aCB]\rightarrow [aE]</math>
# <math>\begin{cases}
\ a[Da]\rightarrow [Da]a \\
\ [aDB]\rightarrow [DaB] \\ 
\ [Aa][Da]\rightarrow [ADa]a \\ 
\ a[DaB]\rightarrow [Da][aB] \\
\ [Aa][DaB]\rightarrow [ADa][aB]
\end{cases}</math>
# <math>[ADa]\rightarrow [ACa]</math>
# <math>\begin{cases}
\ a[Ea]\rightarrow [Ea]a \\
\ [aE]\rightarrow [Ea] \\
\ [Aa][Ea]\rightarrow [AEa]a
\end{cases}</math>
# <math>[AEa]\rightarrow a</math>