In formal language theory, a noncontracting grammar is in Kuroda normal form if all production rules are of the form:[1]
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.[1] Some sources omit the A → B pattern.[2]
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.[3]
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.[2]
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.[1]
There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too:[4]
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.[2]
If the rule AB → CD is eliminated from the above, one obtains context-free grammars in Chomsky Normal Form.[5] The Penttonen normal form (for unrestricted grammars) is a special case where first rule above is AB → AD.[4] Similarly, for context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form (following Penttonen's own terminology) is:[1][2]
AB → AD or
A → BC or
A → a
For every context-sensitive grammar, there exists a weakly equivalent one-sided normal form.[2]
^ abcdMasami Ito; Yūji Kobayashi; Kunitaka Shoji (2010). Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20-22 September 2008. World Scientific. p. 182. ISBN 978-981-4317-60-3.
^ abcdeMateescu, Alexandru; Salomaa, Arto (1997). "Chapter 4: Aspects of Classical Language Theory". In Rozenberg, Grzegorz; Salomaa, Arto (eds.). Handbook of Formal Languages. Volume I: Word, language, grammar. Springer-Verlag. p. 190. ISBN 978-3-540-61486-9.
^Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2.
^ abAlexander Meduna (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 722. ISBN 978-1-85233-074-3.
^Alexander Meduna (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 728. ISBN 978-1-85233-074-3.
and 24 Related for: Kuroda normal form information
language theory, a noncontracting grammar is in Kurodanormalform if all production rules are of the form: AB → CD or A → BC or A → B or A → a where A,...
halt at depth n. Backus–Naur form Chomsky normalformKurodanormalform Greibach, Sheila (January 1965). "A New Normal-Form Theorem for Context-Free Phrase...
Backus–Naur form CYK algorithm Greibach normalformKurodanormalform Pumping lemma for context-free languages — its proof relies on the Chomsky normalform that...
art he reported Kuroda to the Committee of Unpatriotic Activities. This results in Kuroda being punished and his paintings burned. Kuroda therefore develops...
diameter. They form the upper part of Layer 2 of normal oceanic crust. Pillow lavas are commonly of basaltic composition, although pillows formed of komatiite...
p. 41. Kuroda 1981, pp. 4–5; Teeuwen 2002, p. 237. Kuroda 1981, p. 6; Teeuwen 2002, p. 237; Hardacre 2017, p. 42. Kuroda 1981, p. 7. Kuroda 1981, pp...
Blasters. Kumiko Yamaguchi is the granddaughter of a yakuza boss, Kuroda of the Kuroda Ikka. Her parents died when she was at the age of seven, and her...
noses. When Inugami enters their class, the younger Kuroda twin threw the knife at the board as a form of hostile intent. When this was ineffective, he tries...
Academic Publishers. pp. 139–155. Kouchi, A.; Yamamoto, T.; Kozasa, T.; Kuroda, T.; Greenberg, J. M. (1994). "Conditions for condensation and preservation...
Pictures and directed by Tomoya Tanaka, with scripts written by Yōsuke Kuroda, character designs by Hisashi Toshima, and music composed by Masaru Yokoyama...
which a natural nuclear reactor could exist were predicted in 1956 by Paul Kuroda. The remnants of an extinct or fossil nuclear fission reactor, where self-sustaining...
April 2019. Kuroda, Kenji; Suzuragi, Karin; Keller-Nelson, Alexander (2018). Ao oni. J-Novel Club. ISBN 978-1-7183-0144-3. OCLC 1037273475. Kuroda, Kenji,...
nicotinic acid (a form of vitamin B3). Trigonelline is a methyl betaine of nicotinic acid. Merck Index, 11th Edition, 9606. Kuroda, Rei; Kazumura, Kimiko;...
handled by Kiyoshi Tateishi, and music composed by Ken Itō [ja] and Kenichi Kuroda. It aired from July 5 to September 20, 2022, on AT-X, Tokyo MX, BS11, and...
on 2009-02-25. Retrieved 2009-07-06. P.K. Kuroda, Accounts of Chemical Research, 1979, 12(2), 73-78 [1] Kuroda, P. K., and Myers, W. A. "Plutonium-244 Dating...
his modern portrayals as a bumbling oaf due to his final loss and death. Kuroda "Charlie" Kanbei (黒田チャーリー官兵衛) Voiced by: Kazuhiko Inoue Once one of the...
They were originally normal humans until their body chemistry was slightly altered to utilize Chouriki (超力, Chōriki), a form of energy used by an ancient...
received a generally positive reception from fans and critics alike. Junko Kuroda said the manga is "definitely an adventure fantasy that can be enjoyed smoothly"...
series was produced by Bones and directed by Kenji Nagasaki, with Yōsuke Kuroda handling series composition, Yoshihiko Umakoshi providing character designs...
Global Information