Kuroda normal form
From Wikipedia, the free encyclopedia
In formal language theory, a 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 is monotonic, 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.
[edit] See also
[edit] References
- S.-Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964.
