Please use this identifier to cite or link to this item:
https://doi.org/10.1016/S0304-3975(03)00215-9
| Title: | A new algorithm for regularizing one-letter context-free grammars | Authors: | Andrei, S. Cavadini, S.V. Chin, W.-N. |
Keywords: | One-letter context-free language Reduction of a context-free grammar Regular expression |
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.