Noncontracting grammar

Example

This grammar, with the start symbol S, generates the language { aⁿbⁿcⁿ : 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:

1. For every terminal symbol a ∈ Σ, introduce a new nonterminal symbol [a] ∈ N’, and a new rule ([a] → a) ∈ P’.
2. 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₁...X_m → Y₁...Y_n for nonterminals X_i, Y_j and m≤n.
3. Replace each rule X₁...X_m → Y₁...Y_n with m>1 by 2m rules:

where each Z_i ∈ N’ is a new nonterminal not occurring elsewhere.

For example, the above noncontracting grammar for { aⁿbⁿcⁿ | n ≥ 1 } leads to the following context-sensitive grammar (with start symbol S) for the same language: