Editing Chomsky hierarchy (section)

===Context-sensitive (Type-1) grammars===
{{main|Context-sensitive grammar}}

Type-1 grammars generate [[context-sensitive language]]s. These grammars have rules of the form <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math> with <math>A</math> a nonterminal and <math>\alpha</math>, <math>\beta</math> and <math>\gamma</math> strings of terminals and/or nonterminals. The strings <math>\alpha</math> and <math>\beta</math> may be empty, but <math>\gamma</math> must be nonempty.  The rule <math>S \rightarrow \epsilon</math> is allowed if <math>S</math> does not appear on the right side of any rule.  The languages described by these grammars are exactly all languages that can be recognized by a [[linear bounded automaton]] (a nondeterministic Turing machine whose tape is bounded by a constant times the length of the input.)

For example, the context-sensitive language  <math>L = \{a^nb^nc^n \mid n > 0\}</math> is generated by the Type-1 grammar <math>G = (\{S,A,B,C,W,Z\}, \{a, b, c\}, P, S)</math> with the productions <math>P</math> being the following.

:{{math|''S'' → ''aBC''}}
:{{math|''S'' → ''aSBC''}}
:{{math|''CB'' → ''CZ''}}
:{{math|''CZ'' → ''WZ''}}
:{{math|''WZ'' → ''WC''}}
:{{math|''WC'' → ''BC''}}
:{{math|''aB'' → ''ab''}}
:{{math|''bB'' → ''bb''}} 	
:{{math|''bC'' → ''bc''}}
:{{math|''cC'' → ''cc''}}

The language is context-sensitive but not context-free (by the [[pumping lemma for context-free languages]]).
A proof that this grammar generates <math>L = \{a^nb^nc^n \mid n > 0\}</math> is sketched in the article on [[Context-sensitive grammar#anbncn|Context-sensitive grammars]].