Noncontracting grammar
# 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^nb^nc^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_1X_2...X_{m-1}X_m→Z_1X_2...X_{m-1}X_m$ $Z_1X_2...X_{m-1}X_m→Z_1Z_2...X_{m-1}X_m$  : $Z_1Z_2...X_{m-1}X_m→Z_1Z_2...Z_{m-1}X_m$ $Z_1Z_2...Z_{m-1}X_m→Z_1Z_2...Z_{m-1}Z_mY_{m+1}...Y_n$ $Z_1Z_2...Z_{m-1}Z_mY_{m+1}...Y_n$   →   $Y_1Z_2...Z_{m-1}Z_mY_{m+1}...Y_n$ $Y_1Z_2...Z_{m-1}Z_mY_{m+1}...Y_n→Y_1Y_2...Z_{m-1}Z_mY_{m+1}...Y_n$  : $Y_1Y_2...Z_{m-1}Z_mY_{m+1}...Y_n→Y_1Y_2...Y_{m-1}Z_mY_{m+1}...Y_n$ $Y_1Y_2...Y_{m-1}Z_mY_{m+1}...Y_n→Y_1Y_2...Y_{m-1}Y_mY_{m+1}...Y_n$
       where each $Z_i$ ∈ N’ is a new nonterminal not occurring elsewhere.

For example, the above noncontracting grammar for { $a^nb^nc^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 |
