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

SCOPUSTM   
Citations

8
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

6
checked on Nov 18, 2017

Page view(s)

66
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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