Kuroda normal form

In formal language theory, a noncontracting grammar is in Kuroda normal form if all production rules are of the form:^[1]

AB → CD or

A → BC or

A → B or

A → a

where A, B, C and D are nonterminal symbols and a is a terminal symbol.^[1] Some sources omit the A → B pattern.^[2]

It is named after Sige-Yuki Kuroda, who originally called it a linear bounded grammar, a terminology that was also used by a few other authors thereafter.^[3]

Every grammar in Kuroda normal form is noncontracting, and therefore, generates a context-sensitive language. Conversely, every noncontracting grammar that does not generate the empty string can be converted to Kuroda normal form.^[2]

A straightforward technique attributed to György Révész transforms a grammar in Kuroda normal form to a context-sensitive grammar: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD. This proves that every noncontracting grammar generates a context-sensitive language.^[1]

There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too:^[4]

AB → CD or

A → BC or

A → a or

A → ε

where ε is the empty string. Every unrestricted grammar is weakly equivalent to one using only productions of this form.^[2]

If the rule AB → CD is eliminated from the above, one obtains context-free grammars in Chomsky Normal Form.^[5] The Penttonen normal form (for unrestricted grammars) is a special case where first rule above is AB → AD.^[4] Similarly, for context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form (following Penttonen's own terminology) is:^[1][2]

AB → AD or

A → BC or

A → a

For every context-sensitive grammar, there exists a weakly equivalent one-sided normal form.^[2]

See also

• Backus–Naur form
• Chomsky normal form
• Greibach normal form