Kuroda normal form

From Wikipedia, the free encyclopedia

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.

[edit] References

• S.-Y. Kuroda, Classes of languages and linear-bounded automata, Information and Control 7(2): 207–223, June 1964.

[edit] See also

• Backus-Naur_form
• Chomsky normal form
• Greibach normal form