Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Kuroda normal form
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
In [[formal language theory]], a [[noncontracting grammar]] is in '''Kuroda normal form''' if all production rules are of the form:<ref name="ItoKobayashi2010"/> :''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]].<ref name="ItoKobayashi2010"/> Some sources omit the ''A'' → ''B'' pattern.<ref name="MS190"/> 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.<ref>{{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}}</ref> Every grammar in Kuroda normal form is [[noncontracting grammar|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.<ref name="MS190">{{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}}</ref> 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.<ref name="ItoKobayashi2010">{{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}}</ref> There is a similar normal form for [[unrestricted grammar]]s as well, which at least some authors call "Kuroda normal form" too:<ref name="Meduna2000-722"/> :''AB'' → ''CD'' or :''A'' → ''BC'' or :''A'' → ''a'' or :''A'' → ''ε'' where ε is the empty string. Every unrestricted grammar is [[weak equivalence (formal languages)|weakly equivalent]] to one using only productions of this form.<ref name="MS190"/> If the rule AB → CD is eliminated from the above, one obtains context-free grammars in [[Chomsky Normal Form]].<ref name="Meduna2000-728">{{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}}</ref> The '''Penttonen normal form''' (for unrestricted grammars) is a special case where first rule above is ''AB'' → ''AD''.<ref name="Meduna2000-722">{{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}}</ref> Similarly, for context-sensitive grammars, the Penttonen normal form, also called the '''one-sided normal form''' (following Penttonen's own terminology) is:<ref name="ItoKobayashi2010"/><ref name="MS190"/> :''AB'' → ''AD'' or :''A'' → ''BC'' or :''A'' → ''a'' For every context-sensitive grammar, there exists a weakly equivalent one-sided normal form.<ref name="MS190"/> ==See also== *[[Backus–Naur form]] *[[Chomsky normal form]] *[[Greibach normal form]] ==References== {{reflist}} ==Further reading== * {{cite journal | author=Sige-Yuki Kuroda | title=Classes of languages and linear-bounded automata | journal=Information and Control | volume=7 | number=2 | pages=207–223 | date=June 1964 |doi = 10.1016/S0019-9958(64)90120-2 | doi-access=free }} * G. Révész, "Comment on the paper 'Error detection in formal languages,'" Journal of Computer and System Sciences, vol. 8, no. 2, pp. 238–242, Apr. 1974. {{doi|10.1016/S0022-0000(74)80057-7}} (Révész' trick) * {{Cite journal | last1 = Penttonen | first1 = Martti | date = Aug 1974 | title = One-sided and two-sided context in formal grammars | journal = Information and Control | volume = 25 | issue = 4 | pages = 371–392 | doi = 10.1016/S0019-9958(74)91049-3 | doi-access = free }} {{Formal languages and grammars|state=collapsed}} [[Category:Formal languages]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:Doi
(
edit
)
Template:Formal languages and grammars
(
edit
)
Template:Reflist
(
edit
)