Please use this identifier to cite or link to this item:
|Title:||A new algorithm for regularizing one-letter context-free grammars||Authors:||Andrei, S.
|Keywords:||One-letter context-free language
Reduction of a context-free grammar
|Issue Date:||2003||Citation:||Andrei, S., Cavadini, S.V., Chin, W.-N. (2003). A new algorithm for regularizing one-letter context-free grammars. Theoretical Computer Science 306 (1-3) : 113-122. ScholarBank@NUS Repository. https://doi.org/10.1016/S0304-3975(03)00215-9||Abstract:||Constructive methods for obtaining regular grammar counterparts for some sub-classes of context-free grammars (CFGs) have been investigated by many researchers. An important class of grammars for which this is always possible is the one-letter CFG. We show in this paper a new constructive method for transforming an arbitrary one-letter CFG to an equivalent regular expression of star-height 0 or 1. Our new result is considerably simpler than a previous construction by Leiss, and we also propose a new normal form for a regular expression with only a single-star occurrence. Through an alphabet factorization theorem, we show how to go beyond the one-letter CFG in a straight-forward way. © 2003 Elsevier B.V. All rights reserved.||Source Title:||Theoretical Computer Science||URI:||http://scholarbank.nus.edu.sg/handle/10635/43149||ISSN:||03043975||DOI:||10.1016/S0304-3975(03)00215-9|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.