Noncontracting grammar explained

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 ruleS → ε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,^[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 → for nonterminals X_i, Y_j and m≤n.
3. Replace each rule → with m>1 by 2m rules:^[7]

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.^{[8] [9]}

For example, the above noncontracting grammar for 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

References

• Book . R. V. . On the structure of context-sensitive grammars . 10.1007/BF00976059 . International Journal of Computer & Information Sciences . 2 . 2 . 129–139 . 1973 . 2060/19710024701 . 31699138 . free .
• Book: Mateescu . Alexandru . Salomaa. Arto . Grzegorz. Rozenberg. Arto. Salomaa . Handbook of Formal Languages. Volume I: Word, language, grammar . Springer-Verlag . 1997 . 175–252 . Chapter 4: Aspects of Classical Language Theory . 3-540-61486-9.

Notes and References

1. Book: Willem J. M. Levelt. An Introduction to the Theory of Formal Languages and Automata. 2008. John Benjamins Publishing. 978-90-272-3250-2. 125–126.
2. Chomsky, N. 1959a. On certain formal properties of grammars. Information and Control 2: 137–67. (141–42 for the definitions)
3. Book: Noam Chomsky . Formal properties of grammar . 323–418 . Handbook of Mathematical Psychology . R.D. Luce and R.R. Bush and E. Galanter . New York . Wiley . II . 1963 . Here: pp. 360–363 and 367
4. Sige-Yuki Kuroda . Classes of languages and linear-bounded automata . Information and Control . 7 . 2 . 207–223 . June 1964 . 10.1016/s0019-9958(64)90120-2. free .
5. , Example 2.1, p. 188
6. , Theorem 2.2, p. 190
7. For convenience, the non-context part of left and right hand side is shown in boldface.
8. , Theorem 2.1, p. 187
9. Book: John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 1979. Addison-Wesley. 0-201-02988-X. registration. Exercise 9.9, p.230. In the 2003 edition, the chapter on noncontracting / context-sensitive languages has been omitted.