Kuroda normal form

In formal language theory, 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. Some sources omit the A → B pattern.

It is named after Sige-Yuki Kuroda, who originally called it a linear bounded grammar, a terminology that was also used by a few other authors thereafter.{{cite book|author=Willem J. M. Levelt|title=An Introduction to the Theory of Formal Languages and Automata|url=https://books.google.com/books?id=tFvtwGYNe7kC&pg=PA126|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2|pages=126–127}}

Every grammar in Kuroda normal form is noncontracting, and therefore, generates a context-sensitive language. Conversely, every noncontracting grammar that does not generate the empty string can be converted to Kuroda normal form.{{cite book |last1=Mateescu | first1=Alexandru |last2=Salomaa|first2=Arto |editor1-first=Grzegorz| editor1-last=Rozenberg|editor2-first=Arto| editor2-last=Salomaa |title=Handbook of Formal Languages. Volume I: Word, language, grammar |publisher=Springer-Verlag |year=1997 |chapter=Chapter 4: Aspects of Classical Language Theory |isbn=978-3-540-61486-9|page=190}}

A straightforward technique attributed to György Révész transforms a grammar in Kuroda normal form to a context-sensitive grammar: 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.{{cite book|author1=Masami Ito|author2=Yūji Kobayashi|author3=Kunitaka Shoji|title=Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20-22 September 2008|url=https://books.google.com/books?id=xuaR2bJq0rcC&pg=PA182|year=2010|publisher=World Scientific|isbn=978-981-4317-60-3|page=182}}

There is a similar normal form for unrestricted grammars 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.{{cite book|author=Alexander Meduna|title=Automata and Languages: Theory and Applications|url=https://books.google.com/books?id=s7gEErax71cC&pg=PA728|year=2000|publisher=Springer Science & Business Media|isbn=978-1-85233-074-3|page=728|author-link=Alexander Meduna}} The Penttonen normal form (for unrestricted grammars) is a special case where first rule above is AB → AD.{{cite book|author=Alexander Meduna|title=Automata and Languages: Theory and Applications|url=https://books.google.com/books?id=s7gEErax71cC&pg=PA722|year=2000|publisher=Springer Science & Business Media|isbn=978-1-85233-074-3|page=722|author-link=Alexander Meduna}} 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.