Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.ipl.2010.09.010
Title: | Regular patterns, regular languages and context-free languages | Authors: | Jain, S. Ong, Y.S. Stephan, F. |
Keywords: | Context free languages Pattern languages Regular languages Theory of computation |
Issue Date: | 2010 | Citation: | Jain, S., Ong, Y.S., Stephan, F. (2010). Regular patterns, regular languages and context-free languages. Information Processing Letters 110 (24) : 1114-1119. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ipl.2010.09.010 | Abstract: | In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4. © 2010 Elsevier B.V. All rights reserved. | Source Title: | Information Processing Letters | URI: | http://scholarbank.nus.edu.sg/handle/10635/43057 | ISSN: | 00200190 | DOI: | 10.1016/j.ipl.2010.09.010 |
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.