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
 |
This computer-related article is a stub. You can help Wikipedia by expanding it. |
