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.^[1]

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.^[2]

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 .^[3]

Kuroda (1964) introduced Kuroda normal form, into which all noncontracting grammars can be converted.^[4]

Example

S	→	abc
S	→	aSBc
cB	→	Bc
bB	→	bb

This grammar, with the start symbol S, generates the language { aⁿbⁿcⁿ : n ≥ 1 },^[5] 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,^[4][6] 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:^{[note 1]}

X1

X2

...

Xm-1

Xm

→

Z1

X2

...

Xm-1

Xm

Z1

X2

...

Xm-1

Xm

→

Z1

Z2

...

Xm-1

Xm

:

Z1

Z2

...

Xm-1

Xm

→

Z1

Z2

...

Zm-1

Xm

Z1

Z2

...

Zm-1

Xm

→

Z1

Z2

...

Zm-1

Zm

Ym+1

...

Yn

Z1

Z2

...

Zm-1

Zm

Ym+1

...

Yn

→

Y1

Z2

...

Zm-1

Zm

Ym+1

...

Yn

Y1

Z2

...

Zm-1

Zm

Ym+1

...

Yn

→

Y1

Y2

...

Zm-1

Zm

Ym+1

...

Yn

:

Y1

Y2

...

Zm-1

Zm

Ym+1

...

Yn

→

Y1

Y2

...

Ym-1

Zm

Ym+1

...

Yn

Y1

Y2

...

Ym-1

Zm

Ym+1

...

Yn

→

Y1

Y2

...

Ym-1

Ym

Ym+1

...

Yn

where each Z_i ∈ N’ is a new nonterminal not occurring elsewhere.^[7][8]

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:

	[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	→	Z1	B			modified from above in step 3
Z1	B	→	Z1	Z2			modified from above in step 3
Z1	Z2	→	B	Z2			modified from above in step 3
B	Z2	→	B	[c]			modified from above in step 3
[b]	B	→	[b]	[b]			from step 2, further modified below
[b]	B	→	Z3	B			modified from above in step 3
Z3	B	→	Z3	Z4			modified from above in step 3
Z3	Z4	→	[b]	Z4			modified from above in step 3
[b]	Z4	→	[b]	[b]			modified from above in step 3

See also

• Context-sensitive grammar
• Growing context-sensitive grammar
• Kuroda normal form

Notes

1. For convenience, the non-context part of left and right hand side is shown in boldface.