Noncontracting grammar

Formal definition

In formal language theory, a grammar 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 $\{ a^n b^n c^n : n \ge 1 \}$, which is not context-free.

There is also a (much more complex) noncontracting grammar for the language $\{ a^n b^n c^n d^n : n \ge 1 \}$.

Equivalent types of grammars; expressive power

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

Procedures are known for transforming any noncontracting grammar into a context-sensitive grammar 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 languages that do not include the empty string, while the essentially noncontracting grammars describe exactly the set of context-sensitive languages.

See also

• Context-sensitive grammar
• Kuroda normal form