In computer science, a formal grammar is in Kuroda normal form iff all production rules are of the form:
- AB → CD or
- A → BC or
- A → B or
- A → α
where A, B, C and D are nonterminal symbols and α is a terminal symbol.
Every grammar in Kuroda normal form generates a context-sensitive language, and conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form.
References
- S.-Y. Kuroda, Classes of languages and linear-bounded automata, Information and Control 7(2): 207–223, June 1964.
See also