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. A formal language is a set of words, ie finite strings of letters, or symbols. In Formal semantics, Computer science and Linguistics, a formal grammar (also called formation rules) is a precise description of a Formal ↔ In Computer science, terminal and nonterminal symbols are those symbols that are used to construct production rules in a Formal grammar. In Computer science, terminal and nonterminal symbols are those symbols that are used to construct production rules in a Formal grammar.
Every grammar in Kuroda normal form is monotonic, and therefore, generates a context-sensitive language. In Theoretical computer science, a context-sensitive language is a Formal language that can be defined by a Context-sensitive grammar. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form. In Computer science and Formal language theory, the empty string is the unique string of length Zero.
See also
References
- S. In Computer science, Backus–Naur Form ( BNF) is a Metasyntax used to express Context-free grammars that is a formal way to describe Formal In Computer science, a Formal grammar is said to be in Chomsky normal form if all of its production rules are of the form A\rightarrow\ In Computer science, to say that a Context-free grammar is in Greibach normal form (GNF means that all production rules are of the form A \to \alpha -Y. Kuroda, "Classes of languages and linear-bounded automata", Information and Control, 7(2): 207–223, June 1964.
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic