Regular component splittable languages

Abstract

Every infinite regular language contains a regular subset of the form u upsilon(+)ut for some words u,upsilon,w, where upsilon is not the empty word. The regular subsets of the above form are called regular components. Some well-known context-free languages, such as the Dyck language and the balanced language (over an alphabet X with \X\ = 2), are decomposed as disjoint unions of disjunctive languages. In this paper, we investigate the decompositions of some of the regular languages and the context-free languages as disjoint unions of regular components. An infinite language is called regular component splittable if it can be expressed as a disjoint union of regular components and a finite set. We show that the Dyck language, the balanced language and some disjunctive context-free splittable languages are regular component splittable. We also present an example to show that there is a disjunctive context-free language which is not regular component splittable.