Kuroda normal form
In formal language theory, a grammar is in Kuroda normal form if all production rules are of the form:
where A, B, C and D are nonterminal symbols and a is a terminal symbol. Some sources omit the A → B pattern.
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.
Every grammar in Kuroda normal form is noncontracting, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form.
A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD. This technique also proves that every noncontracting grammar is context-sensitive.
There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too:
where ε is the empty string. Every unrestricted grammar is equivalent to one using only productions of this form.
If the rule AB → CD is eliminated from the above, then one obtains context-free languages. The Penttonen normal form is a special case where A = C in the first rule above. For context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form is just:
As the name suggests, for every context-sensitive grammar, there exists a equivalent one-sided/Penttonen normal form.
