Science Fair Project Encyclopedia
Kuroda normal form
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
12-03-2008 10:22:39
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details