formal language theory In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet". The alphabet of a formal language consists of symbol ...

, a noncontracting grammar is in Kuroda normal form if all production rules are of the form: :''AB'' → ''CD'' or :''A'' → ''BC'' or :''A'' → ''B'' or :''A'' → ''a'' where A, B, C and D are nonterminal symbols and ''a'' is a

terminal symbol In formal languages, terminal and nonterminal symbols are parts of the ''vocabulary'' under a formal grammar. ''Vocabulary'' is a finite, nonempty set of symbols. ''Terminal symbols'' are symbols that cannot be replaced by other symbols of the v ...

. Some sources omit the ''A'' → ''B'' pattern. It is named after

Sige-Yuki Kuroda , also known as S.-Y. Kuroda, was Professor Emeritus and Research Professor of Linguistics at the University of California, San Diego. Although a pioneer in the application of Chomskyan generative syntax to the Japanese language, he is known fo ...

, who originally called it a linear bounded grammar, a terminology that was also used by a few other authors thereafter. Every grammar in Kuroda normal form is noncontracting, and therefore, generates a

context-sensitive language In formal language theory, a context-sensitive language is a language that can be defined by a context-sensitive grammar (and equivalently by a noncontracting grammar). Context-sensitive is known as type-1 in the Chomsky hierarchy of formal langu ...

. Conversely, every noncontracting grammar that does not generate the

empty string In formal language theory, the empty string, or empty word, is the unique String (computer science), string of length zero. Formal theory Formally, a string is a finite, ordered sequence of character (symbol), characters such as letters, digits ...

can be converted to Kuroda normal form. A straightforward technique attributed to György Révész transforms a grammar in Kuroda normal form to a

context-sensitive grammar A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any Production (computer science), production rules may be surrounded by a context of terminal symbol, terminal and nonterminal symbols. Cont ...

: ''AB'' → ''CD'' is replaced by four context-sensitive rules ''AB'' → ''AZ'', ''AZ'' → ''WZ'', ''WZ'' → ''WD'' and ''WD'' → ''CD''. This proves that every noncontracting grammar generates a context-sensitive language. There is a similar normal form for

unrestricted grammar In automata theory, the class of unrestricted grammars (also called semi-Thue, type-0 or phrase structure grammars) is the most general class of grammars in the Chomsky hierarchy. No restrictions are made on the productions of an unrestricted gramm ...

s as well, which at least some authors call "Kuroda normal form" too: :''AB'' → ''CD'' or :''A'' → ''BC'' or :''A'' → ''a'' or :''A'' → ''ε'' where ε is the empty string. Every unrestricted grammar is weakly equivalent to one using only productions of this form. If the rule AB → CD is eliminated from the above, one obtains context-free grammars in Chomsky Normal Form. The Penttonen normal form (for unrestricted grammars) is a special case where first rule above is ''AB'' → ''AD''. Similarly, for context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form (following Penttonen's own terminology) is: :''AB'' → ''AD'' or :''A'' → ''BC'' or :''A'' → ''a'' For every context-sensitive grammar, there exists a weakly equivalent one-sided normal form.

See also

References

Further reading