Regular component splittable languages (Q1272195)

The authors study the problem of decomposing regular and context-free languages into regular components, where a regular component is a language of the form \(uv^+w\) \((u,w\in X^*\), \(v\in X^+\) for some alphabet \(X\)). A language is called (finitely) regular component splittable if it is a (finite) disjoint union of regular components and a finite language. It is shown that all regular languages of the form \((uv^+w)^+\) and those of the form \(uv^+wx^+y\) are regular component splittable. Moreover, the cases are characterized in which these languages are even finitely regular component splittable. The authors conjecture that, in fact, all regular languages are regular component splittable. As for context-free languages, it is shown that the Dyck language and the balanced language (both over a two-letter alphabet) are regular component splittable. Furthermore, each of the so-called abelian-generated normal disjunctive context-free languages is regular component splittable. Finally, the authors construct an infinite context-free language having no infinite regular subset. Consequently, this language constitutes an example of a context-free language which is not regular component splittable.