Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ipl.2010.09.010
DC FieldValue
dc.titleRegular patterns, regular languages and context-free languages
dc.contributor.authorJain, S.
dc.contributor.authorOng, Y.S.
dc.contributor.authorStephan, F.
dc.date.accessioned2013-07-23T09:23:48Z
dc.date.available2013-07-23T09:23:48Z
dc.date.issued2010
dc.identifier.citationJain, 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
dc.identifier.issn00200190
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/43057
dc.description.abstractIn 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.ipl.2010.09.010
dc.sourceScopus
dc.subjectContext free languages
dc.subjectPattern languages
dc.subjectRegular languages
dc.subjectTheory of computation
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.contributor.departmentMATHEMATICS
dc.description.doi10.1016/j.ipl.2010.09.010
dc.description.sourcetitleInformation Processing Letters
dc.description.volume110
dc.description.issue24
dc.description.page1114-1119
dc.description.codenIFPLA
dc.identifier.isiut000286289800008
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


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