| dc.creator |
Andrei, Å tefan |
|
| dc.creator |
Chin, Wei Ngan |
|
| dc.date |
2003-12-13T19:34:32Z |
|
| dc.date |
2003-12-13T19:34:32Z |
|
| dc.date |
2004-01 |
|
| dc.date.accessioned |
2013-10-09T02:32:53Z |
|
| dc.date.available |
2013-10-09T02:32:53Z |
|
| dc.date.issued |
2013-10-09 |
|
| dc.identifier |
http://hdl.handle.net/1721.1/3865 |
|
| dc.identifier.uri |
http://koha.mediu.edu.my:8181/xmlui/handle/1721 |
|
| dc.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. |
|
| dc.description |
Singapore-MIT Alliance (SMA) |
|
| dc.format |
101341 bytes |
|
| dc.format |
application/pdf |
|
| dc.language |
en_US |
|
| dc.relation |
Computer Science (CS); |
|
| dc.subject |
reduction of a context-free grammar |
|
| dc.subject |
one-letter context-free language |
|
| dc.subject |
regular expression |
|
| dc.title |
A New Constructive Method for the One-Letter Context-Free Grammars |
|
| dc.type |
Article |
|