Back to Search
Start Over
[Untitled]
- 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