A new algorithm for regularizing one-letter context-free grammars Export

@article{citeulike:1751152, 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.}, author = {Andrei, Stefan and Cavadini, Salvador V. and Chin, Wei-Ngan}, citeulike-article-id = {1751152}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0304-3975(03)00215-9}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6V1G-48GFSHM-7/2/f0893878aaf736e632c5b590eebe72a2}, day = {5}, doi = {10.1016/S0304-3975(03)00215-9}, journal = {Theoretical Computer Science}, keywords = {grammar}, month = {September}, number = {1-3}, pages = {113--122}, posted-at = {2007-10-10 16:52:33}, priority = {2}, title = {A new algorithm for regularizing one-letter context-free grammars}, url = {http://dx.doi.org/10.1016/S0304-3975(03)00215-9}, volume = {306}, year = {2003} }

TY - JOUR ID - citeulike:1751152 L3 - citeulike-article-id:1751152 N2 - 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. IS - 1-3 JF - Theoretical Computer Science EP - 122 TI - A new algorithm for regularizing one-letter context-free grammars VL - 306 SP - 113 KW - grammar AU - Andrei, Stefan AU - Cavadini, Salvador AU - Chin, Wei-Ngan PY - 2003/09/05/ UR - http://dx.doi.org/10.1016/S0304-3975(03)00215-9 ER -