Formal definition

In formal language theory, a grammar

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

 is noncontracting (or monotonic) if all of its production rules are of the form

α → β where |α| ≤ |β|, where |α| denotes the length of α.

That is, none of the rules decreases the size of the string that is being rewritten.

It is essentially noncontracting if there may be one exception, namely, a rule

S → ε

where S is the start symbol and ε the empty string.

Example

S → abc

S → aSBc

cB → Bc

bB → bb

This grammar generates the language ,
which is not context-free

Context-free language

In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...

.

There is also a (much more complex) noncontracting grammar for the language
.

Equivalent types of grammars; expressive power

There is an easy procedure for bringing any noncontracting grammar into Kuroda normal form

Kuroda normal form

In formal language theory, a grammar is in Kuroda normal form if, and only if, all production rules are of the form:Every grammar in Kuroda normal form is monotonic, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the...

.

Procedures are known for transforming any noncontracting grammar into a context-sensitive grammar

Context-sensitive grammar

A context-sensitive grammar is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols...

 and vice versa.

Therefore, noncontracting grammars, grammars in Kuroda normal form, and context-sensitive grammars have the same expressive power.

To be precise, the noncontracting grammars describe exactly the context-sensitive language

Context-sensitive language

In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...

s that do not include the empty string, while the essentially noncontracting grammars describe exactly the set of context-sensitive language

Context-sensitive language

In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...

s.