Just like every context-free grammar can be ``normalized'' or ``standardized'' in one of the so-called normal forms, so can a context-sensitive grammar, and in fact arbitrary grammar, be normalized. The particular normalization discussed in this entry is what is known as the Kuroda normal form.

A formal grammar $G=(\Sigma,N,P,\sigma)$ is in Kuroda normal form if its productions have one of the following forms:

1. $A\to a$ ,
2. $A\to BC$ ,
3. $AB\to CD$ .

Note: Sometimes the form $A\to B$ , where $B\in N$ is added to the list above. However, we may remove a production of this form by replacing all occurrences of $B$ by $A$ in every production of $G$ .

The usefulness of the Kuroda normal forms is captured in the following result:

Note that the third production form $AB\to CD$ may be replaced by the following productions

1. $AB\to AX$
   
2. $AX\to YX$
   
3. $YX\to YD$
   
4. $YD\to CD$
   

1. $A\to a$ ,
2. $A\to BC$ ,
3. $AB\to AC$ ,
4. $AB\to CB$ .

As a corollary, every $\lambda$ -free context-sensitive language (not containing the empty word $\lambda$ ) can be generated by a grammar in one-sided normal form.

What if we throw in production of the form $A\to \lambda$ in the above list? Then certainly every context-sensitive language has a grammar in this ``extended'' normal form. In fact, we have

Bibliography

1

G. E. Révész, Introduction to Formal Languages, Dover Publications (1991).

2

A. Mateescu, A. Salomaa, Chapter 4 - Aspects of Classical Language Theory, Handbook of Formal Languages: Volume 1. Word, Language, Grammar, Springer, (1997).