# Noncontracting grammar

In formal language theory, a grammar is noncontracting (or monotonic) if for all of its production rules, α → β (where α and β are strings of nonterminal and terminal symbols), it holds that |α| ≤ |β|, that is β has at least as many symbols as α. A grammar is essentially noncontracting if there may be one exception, namely, a rule S → ε where S is the start symbol and ε the empty string, and furthermore, S never occurs in the right-hand side of any rule.
A context-sensitive grammar is a noncontracting grammar in which all rules are of the form αAβ → αγβ, where A is a nonterminal, and γ is a nonempty string of nonterminal and/or terminal symbols.
However, some authors use the term context-sensitive grammar to refer to noncontracting grammars in general.
A noncontracting grammar in which |α| < |β| for all rules is called a growing context-sensitive grammar.

## History

Chomsky (1959) introduced the Chomsky hierarchy, in which context-sensitive grammars occur as "type 1" grammars; general noncontracting grammars do not occur.
Chomsky (1963) calls a noncontracting grammar a "type 1 grammar", and a context-sensitive grammar a "type 2 grammar", and by presenting a conversion from the former into the latter, proves the two weakly equivalent .
Kuroda (1964) introduced Kuroda normal form, into which all noncontracting grammars can be converted.

## Example

| S | → | abc |
| S | → | aSBc |
| cB | → | Bc |
| bB | → | bb |
This grammar, with the start symbol S, generates the language { a$^n$b$^n$c$^n$ : n ≥ 1 }, which is not context-free due to the pumping lemma.
A context-sensitive grammar for the same language is shown below.

## Expressive power

Every context-sensitive grammar is a noncontracting grammar.
There are easy procedures for
* bringing any noncontracting grammar into Kuroda normal form, and
* converting any noncontracting grammar in Kuroda normal form into a context-sensitive grammar.
Hence, these three types of grammar are equal in expressive power, all describing exactly the context-sensitive languages that do not include the empty string; the essentially noncontracting grammars describe exactly the set of context-sensitive languages.

### A direct conversion

A direct conversion into context-sensitive grammars, avoiding Kuroda normal form:
For an arbitrary noncontracting grammar (N, Σ, P, S), construct the context-sensitive grammar (N’, Σ, P’, S) as follows:
* For every terminal symbol a ∈ Σ, introduce a new nonterminal symbol [a] ∈ N’, and a new rule ([a] → a) ∈ P’.
* In the rules of P, replace every terminal symbol a by its corresponding nonterminal symbol [a]. As a result, all these rules are of the form X$_1$...X$_m$ → Y$_1$...Y$_n$ for nonterminals X$_i$, Y$_j$ and m≤n.
* Replace each rule X$_1$...X$_m$ → Y$_1$...Y$_n$ with m>1 by 2m rules:
       X$_1$X$_2$...X$_{m-1}$X$_m$→Z$_1$X$_2$...X$_{m-1}$X$_m$ Z$_1$X$_2$...X$_{m-1}$X$_m$→Z$_1$Z$_2$...X$_{m-1}$X$_m$  : Z$_1$Z$_2$...X$_{m-1}$X$_m$→Z$_1$Z$_2$...Z$_{m-1}$X$_m$ Z$_1$Z$_2$...Z$_{m-1}$X$_m$→Z$_1$Z$_2$...Z$_{m-1}$Z$_m$Y$_{m+1}$...Y$_n$ Z$_1$Z$_2$...Z$_{m-1}$Z$_m$Y$_{m+1}$...Y$_n$   →   Y$_1$Z$_2$...Z$_{m-1}$Z$_m$Y$_{m+1}$...Y$_n$ Y$_1$Z$_2$...Z$_{m-1}$Z$_m$Y$_{m+1}$...Y$_n$→Y$_1$Y$_2$...Z$_{m-1}$Z$_m$Y$_{m+1}$...Y$_n$  : Y$_1$Y$_2$...Z$_{m-1}$Z$_m$Y$_{m+1}$...Y$_n$→Y$_1$Y$_2$...Y$_{m-1}$Z$_m$Y$_{m+1}$...Y$_n$ Y$_1$Y$_2$...Y$_{m-1}$Z$_m$Y$_{m+1}$...Y$_n$→Y$_1$Y$_2$...Y$_{m-1}$Y$_m$Y$_{m+1}$...Y$_n$
       where each Z$_i$ ∈ N’ is a new nonterminal not occurring elsewhere.
For example, the above noncontracting grammar for { a$^n$b$^n$c$^n$ | n ≥ 1 } leads to the following context-sensitive grammar (with start symbol S) for the same language:
| | [a] | → | a | | | | from step 1 |
| | [b] | → | b | | | | from step 1 |
| | [c] | → | c | | | | from step 1 |
| | S | → | [a] | [b] | [c] | | from step 2, unchanged |
| | S | → | [a] | S | B | [c] | from step 2, unchanged |
| [c] | B | → | B | [c] | | | from step 2, further modified below |
| [c] | B | → | Z$_1$ | B | | | modified from above in step 3 |
| Z$_1$ | B | → | Z$_1$ | Z$_2$ | | | modified from above in step 3 |
| Z$_1$ | Z$_2$ | → | B | Z$_2$ | | | modified from above in step 3 |
| B | Z$_2$ | → | B | [c] | | | modified from above in step 3 |
| [b] | B | → | [b] | [b] | | | from step 2, further modified below |
| [b] | B | → | Z$_3$ | B | | | modified from above in step 3 |
| Z$_3$ | B | → | Z$_3$ | Z$_4$ | | | modified from above in step 3 |
| Z$_3$ | Z$_4$ | → | [b] | Z$_4$ | | | modified from above in step 3 |
| [b] | Z$_4$ | → | [b] | [b] | | | modified from above in step 3 |