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. 
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.
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
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.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.