Kuroda normal form

In formal language theory, a 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 context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form.[2]

A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB CD is replaced by four context-sensitive rules AB AZ, AZ WZ, WZ WD and WD CD. This technique also proves that every noncontracting grammar is context-sensitive.[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, then one obtains context-free languages.[5] The Penttonen normal form (for unrestricted grammars) is a special case where A = C in the first rule above.[4] For context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form (following Penttonen's own terminology) is just:[1][2]

AB AD or
A BC or
A a

As the name suggests, for every context-sensitive grammar, there exists a [weakly] equivalent one-sided/Penttonen normal form.[2]

See also

References

  1. 1 2 3 4 Masami 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.
  2. 1 2 3 4 5 Mateescu, Alexandru; Salomaa, Arto (1997). "Chapter 4: Aspects of Classical Language Theory". In Rozenberg, Grzegorz; Salomaa, Arto. Handbook of Formal Languages. Volume I: Word, language, grammar. Springer-Verlag. p. 190. ISBN 3-540-61486-9.
  3. Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 126–127. ISBN 90-272-3250-4.
  4. 1 2 Alexander Meduna (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 722. ISBN 978-1-85233-074-3.
  5. Alexander Meduna (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 728. ISBN 978-1-85233-074-3.

Further reading

This article is issued from Wikipedia - version of the Sunday, August 24, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.