Back to Search Start Over

[Untitled]

Authors :
Shyr-Shen Yu
Huei-Jan Shyr
Source :
Acta Mathematica Hungarica. 78:251-265
Publication Year :
1998
Publisher :
Springer Science and Business Media LLC, 1998.

Abstract

Every infinite regular language contains a regular subset of the formuv+w for some words u, v, w, where v is not the empty word. The regularsubsets of the above form are called regular components. Some well-knowncontext-free languages, such as the Dyck language and the balanced language(over an alphabet X with |X| = 2), are decomposed as disjointunions of disjunctive languages. In this paper, we investigate thedecompositions of some of the regular languages and the context-freelanguages as disjoint unions of regular components. An infinite language iscalled regular component splittable if it can be expressed as a disjointunion of regular components and a finite set. We show that the Dycklanguage, the balanced language and some disjunctive context-free splittablelanguages are regular component splittable. We also present an example toshow that there is a disjunctive context-free language which is not regularcomponent splittable.

Details

ISSN :
02365294
Volume :
78
Database :
OpenAIRE
Journal :
Acta Mathematica Hungarica
Accession number :
edsair.doi...........4297af361d41fe60c379d552dae8b4a7
Full Text :
https://doi.org/10.1023/a:1006586923902