A New Constructive Method for the One-Letter Context-Free Grammars
Constructive methods for obtaining the regular grammar counterparts for some sub-classes of the context free grammars (cfg) 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 met...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | en_US |
| Published: |
2003
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/3865 |
| _version_ | 1826199799730274304 |
|---|---|
| author | Andrei, Å tefan Chin, Wei Ngan |
| author_facet | Andrei, Å tefan Chin, Wei Ngan |
| author_sort | Andrei, Å tefan |
| collection | MIT |
| description | Constructive methods for obtaining the regular grammar counterparts for some sub-classes of the context free grammars (cfg) 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 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 single-star occurrence. Through an alphabet factorization theorem, we show how to go beyond the one-letter cfg in a straight-forward way. |
| first_indexed | 2024-09-23T11:26:18Z |
| format | Article |
| id | mit-1721.1/3865 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:26:18Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | mit-1721.1/38652019-04-12T08:07:31Z A New Constructive Method for the One-Letter Context-Free Grammars Andrei, Å tefan Chin, Wei Ngan reduction of a context-free grammar one-letter context-free language regular expression Constructive methods for obtaining the regular grammar counterparts for some sub-classes of the context free grammars (cfg) 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 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 single-star occurrence. Through an alphabet factorization theorem, we show how to go beyond the one-letter cfg in a straight-forward way. Singapore-MIT Alliance (SMA) 2003-12-13T19:34:32Z 2003-12-13T19:34:32Z 2004-01 Article http://hdl.handle.net/1721.1/3865 en_US Computer Science (CS); 101341 bytes application/pdf application/pdf |
| spellingShingle | reduction of a context-free grammar one-letter context-free language regular expression Andrei, Å tefan Chin, Wei Ngan A New Constructive Method for the One-Letter Context-Free Grammars |
| title | A New Constructive Method for the One-Letter Context-Free Grammars |
| title_full | A New Constructive Method for the One-Letter Context-Free Grammars |
| title_fullStr | A New Constructive Method for the One-Letter Context-Free Grammars |
| title_full_unstemmed | A New Constructive Method for the One-Letter Context-Free Grammars |
| title_short | A New Constructive Method for the One-Letter Context-Free Grammars |
| title_sort | new constructive method for the one letter context free grammars |
| topic | reduction of a context-free grammar one-letter context-free language regular expression |
| url | http://hdl.handle.net/1721.1/3865 |
| work_keys_str_mv | AT andreiatefan anewconstructivemethodfortheonelettercontextfreegrammars AT chinweingan anewconstructivemethodfortheonelettercontextfreegrammars AT andreiatefan newconstructivemethodfortheonelettercontextfreegrammars AT chinweingan newconstructivemethodfortheonelettercontextfreegrammars |