Editing Context-sensitive grammar (section)

=== ''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>